計(jì)算機(jī)軟件技術(shù)基礎(chǔ)主講：劉海明Email：Office:三號樓210第2頁關(guān)于本課程選修課、雙語課（2學(xué)分）英文教材、中英文課件（PPT），中文講述基礎(chǔ)理論課以理論介紹為主，輔以適當(dāng)?shù)膶?shí)例講解和實(shí)用技術(shù)介紹；目的：學(xué)習(xí)軟件技術(shù)的基本概念、基本原理，作為將來深入學(xué)習(xí)、研究和應(yīng)用的基礎(chǔ)。學(xué)完這門課，我就會編程、能夠開發(fā)軟件了嗎？第3頁課程內(nèi)容和學(xué)時(shí)安排課程內(nèi)容學(xué)時(shí)數(shù)主要學(xué)習(xí)內(nèi)容1.概述3軟件技術(shù)簡介2.數(shù)據(jù)結(jié)構(gòu)與算法151、數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和定義在存儲結(jié)構(gòu)上的運(yùn)算；2、查找和排序算法3.操作系統(tǒng)原理9操作系統(tǒng)概念及其主要功能的實(shí)現(xiàn)原理4.數(shù)據(jù)庫系統(tǒng)9關(guān)系型數(shù)據(jù)庫、SQL語言應(yīng)用以及數(shù)據(jù)庫應(yīng)用程序的開發(fā)合計(jì)36詳細(xì)課時(shí)安排見另一文檔第4頁教材英文教材：數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)——C++語言描述（影印版），RobertK.Cruse等編，高等教育出版社操作系統(tǒng)概念（第六版影印版），AbrahamSilberschatz編，高等教育出版社數(shù)據(jù)庫系統(tǒng)概念（第四版影印版），AbrahamSilberschatz編，高等教育出版社中文參考教材：計(jì)算機(jī)軟件技術(shù)導(dǎo)論，龐麗萍等編，高等教育出版社（舊版書名為“計(jì)算機(jī)軟件技術(shù)基礎(chǔ)”，華中理工大學(xué)出版社）其它“計(jì)算機(jī)軟件技術(shù)基礎(chǔ)”類教材（見下頁）第5頁其它中文參考教材計(jì)算機(jī)軟件技術(shù)基礎(chǔ)（第二版），麥中凡等編，高等教育出版社計(jì)算機(jī)軟件技術(shù)基礎(chǔ)，陳建鐸編，高等教育出版社計(jì)算機(jī)軟件技術(shù)基礎(chǔ)，徐士良編，清華大學(xué)出版社計(jì)算機(jī)軟件技術(shù)及應(yīng)用基礎(chǔ)，馮萍編，清華大學(xué)出版社……第6頁教學(xué)內(nèi)容和教材關(guān)系三個重要章節(jié)對應(yīng)三本英文教材內(nèi)容范疇；教材內(nèi)容節(jié)選自三本英文教材（詳細(xì)內(nèi)容見另一專門文檔），并結(jié)合中文教材進(jìn)行增補(bǔ)和刪減，相關(guān)知識點(diǎn)難易程度作適當(dāng)調(diào)整；實(shí)際教學(xué)內(nèi)容以PPT課件內(nèi)容為準(zhǔn)。請復(fù)印節(jié)選的英文教材進(jìn)行閱讀和學(xué)習(xí)。第7頁相關(guān)知識基礎(chǔ)計(jì)算機(jī)基礎(chǔ)編程語言基礎(chǔ)（C++）專業(yè)英語基礎(chǔ)（計(jì)算機(jī)專業(yè)詞匯）第8頁關(guān)于教學(xué)方式教學(xué)方式：課堂講授、隨機(jī)提問、課堂測驗(yàn)、課后作業(yè)上機(jī)練習(xí)課件：Powerpoint講義；可到學(xué)校教務(wù)處網(wǎng)頁的“教學(xué)在線”網(wǎng)站下載課件、作業(yè)及其它有關(guān)文檔；Tips：課堂學(xué)習(xí)、消化是關(guān)鍵，課堂測驗(yàn)、課后作業(yè)是檢驗(yàn)、反饋和保證。第9頁“教學(xué)在線”的使用“華工主頁”－>“教務(wù)處”－>“教學(xué)在線”（鏈接在教務(wù)處主頁左邊欄底部）進(jìn)入；頁面左上角登錄欄中（如右圖），用學(xué)號作為帳號和密碼登錄（首次登錄后最好修改個人密碼）；在同一位置出現(xiàn)歡迎窗口時(shí)點(diǎn)擊“進(jìn)入”按鈕進(jìn)入“教學(xué)在線”平臺（如右下圖）。在網(wǎng)頁左上方選擇“軟件技術(shù)基礎(chǔ)”課程可進(jìn)入本課程教學(xué)資源網(wǎng)頁，所有課件、作業(yè)及相關(guān)文檔均放在“教學(xué)材料”目錄下。第10頁關(guān)于課程考核總評成績＝平時(shí)成績（20％）＋考試成績（80％）平時(shí)成績：考勤、課堂測驗(yàn)、課后作業(yè)課堂測驗(yàn)：課堂完成、即時(shí)提交，即時(shí)講解。作業(yè)（2~3次）：紙版，課后獨(dú)立完成，按時(shí)提交，批改后再安排課時(shí)講解。注意：測驗(yàn)內(nèi)容、答案及作業(yè)答案均不下發(fā)！考試成績＝卷面成績×80％考試方式：閉卷考試作業(yè)和測驗(yàn)題型及知識點(diǎn)50％為英語題型（其中至少一半要用英文作答）缺勤一半以上或缺交作業(yè)半數(shù)以上者取消考試資格！計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第1章軟件技術(shù)概述第12頁第1章軟件技術(shù)概述1.計(jì)算機(jī)系統(tǒng)2.軟件技術(shù)概述2.1程序設(shè)計(jì)語言2.2數(shù)據(jù)結(jié)構(gòu)與算法2.3操作系統(tǒng)2.4數(shù)據(jù)庫技術(shù)2.5軟件工程2.6軟件開發(fā)方法第13頁學(xué)習(xí)內(nèi)容和學(xué)習(xí)目標(biāo)了解軟件技術(shù)所涵蓋的主要分支及其研究內(nèi)容；學(xué)習(xí)和掌握軟件、程序、軟件工程、軟件生命周期等基本概念。第14頁1.計(jì)算機(jī)系統(tǒng)什么是計(jì)算機(jī)？

計(jì)算機(jī)是接收、處理和提供數(shù)據(jù)的裝置，它由硬件和軟件兩大部分組成。計(jì)算機(jī)就是我們平時(shí)常用的PC機(jī)嗎？

PC機(jī)只是計(jì)算機(jī)的一種，計(jì)算機(jī)家族中還有很多其他的成員。第15頁養(yǎng)在深閨的巨型計(jì)算機(jī)超過100萬個處理器每個處理器每秒可運(yùn)算10億次，運(yùn)算能力相當(dāng)于擊敗國際象棋世界級棋手的超級電腦“深藍(lán)”的1000倍；占地達(dá)兩個籃球場之大，重達(dá)106噸。IBM的BlueGene/L巨型計(jì)算機(jī)國產(chǎn)銀河、曙光第16頁無處不在的嵌入式家族第17頁第18頁（1）計(jì)算機(jī)硬件及其發(fā)展什么是硬件？ 硬件是組成計(jì)算機(jī)系統(tǒng)的所有電子的、機(jī)械的、磁性的、光學(xué)的裝置和部件。配置一臺個人計(jì)算機(jī)需要購買哪些東西？CPU、內(nèi)存、硬盤、主板、鍵鼠、顯示器…馮·諾依曼：1945年，“存儲程序式計(jì)算機(jī)”5大部件構(gòu)成：

運(yùn)算器＋控制器＋存儲器＋輸入設(shè)備＋輸出設(shè)備CPUIO設(shè)備第19頁計(jì)算機(jī)硬件的發(fā)展發(fā)展歷史邏輯元件：電子管→晶體管→集成電路發(fā)展規(guī)律及特點(diǎn)速度慢→速度快體積大容量小→體積小容量大外設(shè)少、簡單→外設(shè)繁多、復(fù)雜外設(shè)速度發(fā)展慢于CPU速度的發(fā)展摩爾定律（假設(shè)價(jià)格保持不變，處理器芯片上的晶體管數(shù)每18個月翻一番）第20頁世界上第一臺電子計(jì)算機(jī)ENIAC誕生于1946年18800個晶體管70000個電阻器18000個電容器5百萬個焊接點(diǎn)重量30噸耗電174千瓦/h5000次加法/s第21頁P(yáng)entiumIV（2000）42,000,000個晶體管時(shí)鐘頻率1.5GHz運(yùn)算速度為1700MIPS（MIPS代表‘百萬指令集每秒’）第22頁雙核處理器（2005）IntelPentium雙核處理器AMDAthlon64X2雙核處理器第23頁三核、四核、六核處理器AMD三核處理器Intel四核處理器AMD六核處理器Intel六核處理器第24頁（2）計(jì)算機(jī)軟件軟件＝程序？開發(fā)軟件＝寫程序？認(rèn)識的誤區(qū)！程序只是軟件的一個組成部分；寫程序只是軟件開發(fā)的過程中的一個步驟。軟件是程序、數(shù)據(jù)以及有關(guān)文檔資料的集合。軟件是（可運(yùn)行的）思想和內(nèi)容的數(shù)字化思想：算法、規(guī)律、方法→程序內(nèi)容：圖形、圖像、數(shù)據(jù)、聲音、文字等→數(shù)據(jù)第25頁軟件的兩方面含義個體含義，表示計(jì)算機(jī)系統(tǒng)中具體的程序、數(shù)據(jù)和有關(guān)文檔，例如操作系統(tǒng)軟件“WindowsXP”，是從個體含義上講的；整體含義，它相對于硬件而言，是對計(jì)算機(jī)系統(tǒng)中所有程序、數(shù)據(jù)及相關(guān)文檔的概括。第26頁軟件的靜態(tài)和動態(tài)屬性軟件有兩種屬性：靜態(tài)屬性：它由程序、數(shù)據(jù)及相關(guān)文檔組成，可以存儲，也可供人們閱讀和交流；動態(tài)屬性：它是可運(yùn)行的，蘊(yùn)涵著一定的操作內(nèi)容和步驟，由計(jì)算機(jī)執(zhí)行而產(chǎn)生特定的結(jié)果或動態(tài)效應(yīng)。第27頁軟件的特征從軟件的屬性來看，它是一種特殊的事物，具有自身的特性，可概括如下：（1）智能性（6）依附性（2）無形性（7）非損性（3）抽象性（8）復(fù)制性（4）系統(tǒng)性（9）演化性（5）泛域性第28頁軟件的分類所有的硬件都是相似的，軟件則各有各的不同。但是軟件的開發(fā)過程存在很多規(guī)律和共性，找到并利用這些規(guī)律來幫助和指導(dǎo)軟件的開發(fā)，這正是各類軟件技術(shù)所研究的內(nèi)容。操作系統(tǒng)、語言編譯器、數(shù)據(jù)庫管理系統(tǒng)文字處理軟件、財(cái)務(wù)軟件、用戶自己開發(fā)的軟件等硬件系統(tǒng)軟件應(yīng)用軟件用戶第29頁常見軟件介紹1.操作系統(tǒng)操作系統(tǒng)是對硬件的首次擴(kuò)充，它管理著計(jì)算機(jī)系統(tǒng)的軟、硬件資源，其它軟件都是在操作系統(tǒng)的基礎(chǔ)上運(yùn)行的。2.數(shù)據(jù)庫管理系統(tǒng)信息管理是計(jì)算機(jī)的一個重要應(yīng)用領(lǐng)域，而信息管理的核心就是數(shù)據(jù)庫管理系統(tǒng)。3.群件系統(tǒng)群件拓寬了電子郵件的內(nèi)涵，涵蓋很多通信協(xié)調(diào)功能，如制定會議的計(jì)劃、共享項(xiàng)目進(jìn)度表等。第30頁4.辦公軟件組件文字處理軟件、電子表格處理軟件、演示制作軟件、個人數(shù)據(jù)庫、個人信息管理軟件等。5.多媒體處理軟件多媒體處理軟件主要包括圖形、圖像處理、動畫制作、音頻視頻處理、桌面排版等。6.程序開發(fā)工具環(huán)境集成的環(huán)境中，包含了語言編輯器（有的還包括界面和外觀的編輯）、調(diào)試工具、編譯工具、運(yùn)行工具、圖標(biāo)圖像制作工具等。第31頁7.Internet工具軟件主要有Web服務(wù)器軟件，Web瀏覽器，文件傳送工具、遠(yuǎn)程訪問工具、郵件軟件、新聞閱讀工具、信息檢索、多媒體、Web頁創(chuàng)作工具等。8.系統(tǒng)工具軟件幫助操作系統(tǒng)更有效地完成系統(tǒng)的管理和維護(hù)。包括殺病毒軟件、文件壓縮、快速復(fù)制工具、磁盤維護(hù)與診斷工具、實(shí)用工具軟件等。9.其它一些常見軟件學(xué)習(xí)、游戲軟件、電子字典、各種小工具軟件第32頁（3）硬件與軟件的關(guān)系軟硬件獨(dú)立原理和互動原理獨(dú)立原理：軟件理論上能實(shí)現(xiàn)的功能本質(zhì)上與硬件是獨(dú)立的（不管硬件是何種形式）互動原理：軟件實(shí)際能實(shí)現(xiàn)的功能受制于硬件，硬件發(fā)展一個臺階，軟件就能前進(jìn)一大步軟硬件等效定律簡單的硬件+復(fù)雜的軟件簡單的軟件+復(fù)雜的硬件最終都可以完成同一個任務(wù)，不同的只是開發(fā)時(shí)間和成本！第33頁硬件是計(jì)算機(jī)系統(tǒng)的物質(zhì)基礎(chǔ)；軟件是提高計(jì)算機(jī)系統(tǒng)效率和方便用戶使用計(jì)算機(jī)的程序擴(kuò)展；它們二者相互依賴、相互促進(jìn)、共同發(fā)展。好的軟件能充分發(fā)揮硬件的性能，提升計(jì)算機(jī)的價(jià)值。各類軟件技術(shù)的最終目的就是設(shè)計(jì)出好的軟件，以便最大限度地合理利用和發(fā)揮硬件的能力，使計(jì)算機(jī)系統(tǒng)更好地為用戶服務(wù)。“沒有軟件的硬件是僵尸，沒有硬件的軟件是幽靈”第34頁2.軟件技術(shù)概述軟件技術(shù)發(fā)展歷程（1）程序設(shè)計(jì)時(shí)代（1946年~1955年）以硬件為中心，編程處于從屬地位（2）軟件行業(yè)化時(shí)代（1955年~1970年）程序需求增加；軟件概念的提出；軟件行業(yè)誕生（3）軟件工程時(shí)代（1970年至現(xiàn)在）軟件危機(jī)；軟件工程領(lǐng)域的出現(xiàn)第一代軟件技術(shù)：模塊化、自頂而下結(jié)構(gòu)化設(shè)計(jì)第二代軟件技術(shù)：軟件測試方法、技術(shù)、原理、理論第三代軟件技術(shù)：軟件需求定義技術(shù)軟件開發(fā)集成環(huán)境——第四代軟件技術(shù)？第35頁軟件技術(shù)的研究領(lǐng)域

軟件本質(zhì)上是一種思想：利用計(jì)算機(jī)來解決某個問題的思想！軟件的實(shí)現(xiàn)就是將這個思想數(shù)字化的過程！在這個過程中要用到各種各樣的軟件技術(shù)，有的是抽象的指導(dǎo)理論，有的是具體的實(shí)現(xiàn)工具。程序設(shè)計(jì)語言編譯技術(shù)軟件及實(shí)現(xiàn)技術(shù)操作系統(tǒng)及實(shí)用程序計(jì)算機(jī)數(shù)據(jù)庫技術(shù)軟件技術(shù)軟件工具軟件工程軟件開發(fā)方法與技術(shù)程序設(shè)計(jì)方法

數(shù)據(jù)結(jié)構(gòu)和算法第36頁2.1程序與程序設(shè)計(jì)語言

程序:是使計(jì)算機(jī)完成某種任務(wù)的一組有序命令（指令語句）的集合。

程序設(shè)計(jì)語言發(fā)展的三個階段：

機(jī)器語言→匯編語言→高級語言寫程序就像寫文章，要解決兩個問題：1.明確自己要表達(dá)的是什么2.用一種語言把它表達(dá)出來程序設(shè)計(jì)語言是編寫計(jì)算機(jī)程序所用的語言。第37頁程序設(shè)計(jì)語言機(jī)器語言

是機(jī)器指令的集合，其代碼由0、1組成的二進(jìn)制串表示，不需翻譯可直接為機(jī)器所接受。匯編語言

為符號化的機(jī)器語言。它用助記符和標(biāo)識符代替機(jī)器指令的操作碼和地址碼。高級語言

是一種與具體的計(jì)算機(jī)指令系統(tǒng)無關(guān)、獨(dú)立于計(jì)算機(jī)類型、且表達(dá)方式接近于自然語言或數(shù)學(xué)語言、容易被人們掌握和書寫的語言。如C，Pascal，java等。第38頁舉例任務(wù)：x＋1→x機(jī)器語言

001111100000100100111111B或3E093FH匯編語言

MOVAX,XINCAXMOVX,AXC語言x=x+1 或x++ 或++x第39頁高級語言的優(yōu)點(diǎn)比機(jī)器語言或匯編語言更易于學(xué)習(xí)；程序更易于編寫和調(diào)試（程序更為短小；記號本身更自然，因此更多注意力可放在程序邏輯而非語法細(xì)節(jié)上）；程序可讀性更強(qiáng)；較好的平臺無關(guān)性；上述原因使得解決問題的時(shí)間和成本減少。第40頁語言翻譯翻譯程序是把甲種語言程序翻譯為等價(jià)的乙種語言程序的程序。其中，甲種語言稱為源語言。乙種語言稱為目標(biāo)語言。匯編程序若源語言是匯編語言，目標(biāo)語言是機(jī)器語言，則該翻譯程序被稱為匯編程序。編譯程序若源語言是高級語言，目標(biāo)語言是匯編語言或機(jī)器語言，則該翻譯程序被稱為編譯程序。解釋程序是翻譯程序的另一種形式，它對源程序的語句邊解釋邊執(zhí)行，不產(chǎn)生目標(biāo)程序。第41頁2.2數(shù)據(jù)結(jié)構(gòu)與算法程序中往往要處理大量的數(shù)據(jù)，這些數(shù)據(jù)采用什么樣的方式來組織、存放才能最大限度地方便應(yīng)用處理，提高程序效率呢？數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的組織形式，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及在該數(shù)據(jù)結(jié)構(gòu)上所施加的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計(jì)的基礎(chǔ)。第42頁算法算法是對解題方法的精確描述。描述的方式可以是各種各樣的。如自然語言、流程圖、偽代碼、程序設(shè)計(jì)語言等。算法必須具有有窮性、確定性、能行性、輸入和輸出。一個問題可以有多種解題方法，那么就有多個對應(yīng)的算法。算法的優(yōu)劣由算法的時(shí)間復(fù)雜度和空間復(fù)雜度來衡量。第43頁2.3操作系統(tǒng)裸機(jī)：沒有安裝任何軟件的計(jì)算機(jī)。操作系統(tǒng)是直接運(yùn)行于裸機(jī)之上的系統(tǒng)軟件，它負(fù)責(zé)對計(jì)算機(jī)系統(tǒng)的各種軟硬件資源進(jìn)行管理和分配，為用戶提供友好的計(jì)算機(jī)使用界面和平臺。在裸機(jī)上配置操作系統(tǒng)之后就構(gòu)成了操作系統(tǒng)虛擬機(jī)。所有其它的軟件或程序都在擴(kuò)充后的機(jī)器上運(yùn)行。第44頁應(yīng)用程序用戶程序操作系統(tǒng)虛擬機(jī)操作系統(tǒng)裸機(jī)第45頁2.4數(shù)據(jù)庫技術(shù)數(shù)據(jù)庫是一種強(qiáng)大的數(shù)據(jù)處理技術(shù)。它把應(yīng)用中所有的數(shù)據(jù)有結(jié)構(gòu)地集中在一起，并提供對這些數(shù)據(jù)的存儲管理、多用戶共享、操作、安全保護(hù)、完整性控制等強(qiáng)大功能。一個國家的信息化程度是衡量該國國力的重要標(biāo)準(zhǔn)，而信息化是以數(shù)據(jù)庫技術(shù)為基礎(chǔ)的。現(xiàn)代的銀行、金融、證券、保險(xiǎn)等各行業(yè)的高效運(yùn)營都依賴于數(shù)據(jù)庫技術(shù)。第46頁2.5

軟件工程產(chǎn)生背景（上個世紀(jì)70年代）硬件的發(fā)展使得計(jì)算機(jī)的應(yīng)用領(lǐng)域迅速擴(kuò)大，導(dǎo)致軟件的規(guī)模和復(fù)雜度急劇增長。早期手工作坊式的軟件開發(fā)方式因無法適應(yīng)這種變化而形成了“軟件危機(jī)”。主要表現(xiàn)在：開發(fā)成本和進(jìn)度估計(jì)不準(zhǔn)確，生產(chǎn)效率低。軟件產(chǎn)品的質(zhì)量不可靠。軟件常常是不可維護(hù)的。缺乏適當(dāng)?shù)奈臋n資料。用戶對軟件系統(tǒng)不滿意的現(xiàn)象經(jīng)常發(fā)生。第47頁軟件工程概念什么是“軟件工程”？1983年IEEE給出的定義為：“軟件工程是開發(fā)、運(yùn)行、維護(hù)和修復(fù)軟件的系統(tǒng)方法”。軟件工程是指導(dǎo)計(jì)算機(jī)軟件開發(fā)和維護(hù)的工程學(xué)科，采用工程的概念、原理、技術(shù)和方法來開發(fā)與維護(hù)軟件。軟件工程是一門交叉學(xué)科，用管理學(xué)的原理、方法來進(jìn)行軟件生產(chǎn)管理；用工程學(xué)的觀點(diǎn)來進(jìn)行費(fèi)用估算、制定進(jìn)度和實(shí)施方案；用數(shù)學(xué)方法來建立軟件可靠性模型以及分析各種算法。第48頁軟件工程的基本目標(biāo)在給定成本、進(jìn)度的前提下，開發(fā)出具有可修改性、有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適用性、可移植性、可追蹤性、可互操作性和滿足用戶需求的軟件產(chǎn)品。第49頁軟件生命周期貫穿“軟件工程”這一學(xué)科的基本線索是軟件生命周期學(xué)說，它告訴軟件開發(fā)者和維護(hù)者“什么時(shí)候做什么以及怎么做”。軟件生命周期就象人的壽命一樣，從出生算到死亡，從產(chǎn)生開發(fā)需求一直到軟件報(bào)廢為止。包括：軟件計(jì)劃、需求分析、軟件開發(fā)和軟件維護(hù)四個時(shí)期。第50頁軟件生命周期階段軟件計(jì)劃（系統(tǒng)定義）用戶想解決什么問題？（軟件定義）這個問題能否解決？（可行性分析）需求分析（系統(tǒng)分析）目標(biāo)系統(tǒng)應(yīng)該做成什么樣子？軟件開發(fā)（系統(tǒng)實(shí)現(xiàn)）怎樣實(shí)現(xiàn)目標(biāo)系統(tǒng)？（軟件設(shè)計(jì)）系統(tǒng)的具體實(shí)現(xiàn)（軟件編程）實(shí)現(xiàn)的系統(tǒng)與是否符合目標(biāo)？（軟件測試）軟件維護(hù)（系統(tǒng)維護(hù)）如何保持系統(tǒng)正常運(yùn)行？如何升級或修復(fù)錯誤？第51頁軟件開發(fā)模型軟件開發(fā)模型是軟件開發(fā)的全部過程、活動和任務(wù)的結(jié)構(gòu)框架。瀑布模型原型模型螺旋模型第52頁軟件開發(fā)模型1．瀑布模型（1）各階段間具有順序性和依賴性。即后一階段工作必須在前一階段工作完成后才能進(jìn)行，前一階段的輸出文檔是后一階段的輸入文檔。（2）質(zhì)量保證機(jī)制的依賴性。即每一步都必須循序漸進(jìn)，及早消除故障隱患，保證本階段的工作的質(zhì)量，從而達(dá)到保證整體軟件質(zhì)量的目的。（3）推遲實(shí)現(xiàn)原則。前一階段工作做的越細(xì)、越扎實(shí)，后一階段工作進(jìn)行的就越順利，強(qiáng)調(diào)“寧慢求好”。因此，各階段工作總是容易一拖再拖，致使整個工期推遲實(shí)現(xiàn)。顯然瀑布模型不能滿足呈爆炸狀增長的社會應(yīng)用需求。

第53頁軟件開發(fā)模型之一：瀑布模型軟件計(jì)劃需求分析軟件設(shè)計(jì)軟件編碼軟件測試軟件維護(hù)變化的需求第54頁2．原型模型也稱樣品模式，即開始提出一個樣品雛形，通過不斷改進(jìn)，完善樣品，使得最后得到用戶所需要的產(chǎn)品。由于在項(xiàng)目開發(fā)初始階段人們對軟件的需求認(rèn)識常常弄不清楚，原型模型提出分兩次開發(fā)軟件能較好地使用戶滿意:第一次只是試驗(yàn)開發(fā)，其目標(biāo)在于探索可行性，弄清軟件需求。通常把第一次得到的試驗(yàn)性產(chǎn)品稱為原型。第二次則在原型基礎(chǔ)上獲得較滿意的軟件產(chǎn)品。顯然，原型模型在克服瀑布模型缺點(diǎn)，減少由于軟件需求不明確而給開發(fā)工作帶來的風(fēng)險(xiǎn)，有著顯著的效果。第55頁軟件開發(fā)模型之二：原型模型

初步需求分析

快速設(shè)計(jì)

建造原型

用戶評估原型（新需求）

開發(fā)產(chǎn)品

開始

結(jié)束

第56頁原型模型的優(yōu)點(diǎn)：（1）開發(fā)人員和用戶在原型上達(dá)成一致，共同承擔(dān)因修改原型而造成的風(fēng)險(xiǎn)，用戶成了名副其實(shí)的開發(fā)組成員。可以減少設(shè)計(jì)中的錯誤和開發(fā)中的風(fēng)險(xiǎn)，從而提高了系統(tǒng)的準(zhǔn)確性、正確性以及用戶的滿意程度。（2）縮短了開發(fā)周期，加快了工程進(jìn)度，降低了成本。原形模型的缺點(diǎn)：原型樣品只是一個臨時(shí)的系統(tǒng)，它沒有考慮整體的質(zhì)量和日后的可維護(hù)性等問題。第57頁3．螺旋模型螺旋模型將瀑布模型與原型模型結(jié)合起來，并且加入風(fēng)險(xiǎn)分析，構(gòu)成具有特色的模式，可以彌補(bǔ)前兩種模型的不足。螺旋模型將工程分為4個主要活動：制定計(jì)劃，風(fēng)險(xiǎn)分析，實(shí)現(xiàn)工程和用戶評價(jià)。4個活動螺旋式地重復(fù)執(zhí)行，直到最終得到用戶認(rèn)可的產(chǎn)品。螺旋模型的缺點(diǎn)：（1）它很難讓用戶確信這種研發(fā)方法是可控制的；（2）它要求有風(fēng)險(xiǎn)評價(jià)的專門技術(shù)，如果主要風(fēng)險(xiǎn)不能發(fā)現(xiàn)，則問題一定會發(fā)生；第58頁生命周期計(jì)劃需求計(jì)劃風(fēng)險(xiǎn)分析原型1原型2原型3可操作的原型建模模擬評價(jià)操作概念軟件需求需求確認(rèn)開發(fā)計(jì)劃組裝測試計(jì)劃風(fēng)險(xiǎn)分析風(fēng)險(xiǎn)分析風(fēng)險(xiǎn)分析軟件產(chǎn)品設(shè)計(jì)設(shè)計(jì)驗(yàn)證與確認(rèn)詳細(xì)設(shè)計(jì)編碼單元測試組裝測試驗(yàn)收測試實(shí)現(xiàn)成本順時(shí)針為進(jìn)展方向計(jì)劃：明確目標(biāo)、約束條件選擇方案風(fēng)險(xiǎn)分析構(gòu)造原型工程實(shí)現(xiàn)用戶評價(jià)；階段評審驗(yàn)收測試計(jì)劃需求精化計(jì)劃需求評價(jià)評審決策實(shí)現(xiàn)計(jì)劃軟件開發(fā)模型之三：螺旋模型第59頁2.6軟件開發(fā)方法結(jié)構(gòu)化方法自頂向下，逐步細(xì)化模塊化結(jié)構(gòu)化程序設(shè)計(jì)面向?qū)ο蠓椒ǖ?0頁自頂向下，逐步細(xì)化由于人類思維能力的限制，如果一次面臨的因素太多，就無法作出精確的思維。例如：舉辦一個生日party布置場地準(zhǔn)備食物準(zhǔn)備節(jié)目邀請客人自頂向下，逐步細(xì)化就是將復(fù)雜的問題分解成若干個子問題，直到所有子問題都簡單到能用程序設(shè)計(jì)語言來表達(dá)的方法。第61頁示例：選擇排序算法設(shè)計(jì)（1）頂層設(shè)計(jì)第62頁（2）第2層設(shè)計(jì)第63頁（3）第3層設(shè)計(jì)第64頁（4）選擇排序法的N-S框圖第65頁模塊化程序設(shè)計(jì)把一個程序按功能分解成若干彼此具有一定獨(dú)立性同時(shí)也具有一定聯(lián)系的組成部分，這些組成部分稱為模塊。每個程序由一個或多個模塊組成。方法：按功能劃分；自頂而下逐步求精，直到獲得單一的功能模塊。優(yōu)點(diǎn)：降低復(fù)雜度：若P=P1+P2，則C(P)>C(P1)+C(P2)軟件結(jié)構(gòu)清晰容易測試和調(diào)試提高軟件的可修改性方便開發(fā)任務(wù)的分配第66頁模塊化設(shè)計(jì)示例報(bào)表加工任務(wù)的模塊化設(shè)計(jì)第67頁結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)使用程序的三種基本控制結(jié)構(gòu)（順序、選擇和循環(huán)

。第68頁結(jié)構(gòu)化程序設(shè)計(jì)的特點(diǎn)只有一個入口和一個出口；不存在從結(jié)構(gòu)內(nèi)跳到結(jié)構(gòu)外，也不存在從結(jié)構(gòu)外跳到結(jié)構(gòu)內(nèi)的情況；程序進(jìn)入結(jié)構(gòu)后，肯定能到達(dá)出口，不會出現(xiàn)“死循環(huán)”。有限制地使用Goto語句進(jìn)行跳轉(zhuǎn)。第69頁面向?qū)ο蠹夹g(shù)OO（面向?qū)ο螅┘夹g(shù)：將客觀世界的實(shí)體看作不同類型的對象，對象的屬性和方法對應(yīng)實(shí)體的自然屬性和行為特性。面向?qū)ο蠹夹g(shù)主要包括面向?qū)ο蟮姆治觯∣OA）、面向?qū)ο蟮脑O(shè)計(jì)（OOD）、面向?qū)ο蟮膶?shí)現(xiàn)（OOI）三個方面。基本概念：對象、類、方法、消息、繼承、封裝等面向?qū)ο蠹夹g(shù)特點(diǎn)：可重用性、可維護(hù)性、表示方法的一致性面向?qū)ο蟮木幊陶Z言：C++，Java等第70頁應(yīng)用軟件的開發(fā)作為應(yīng)用軟件開發(fā)者，一些必須的準(zhǔn)備是：熟悉應(yīng)用開發(fā)平臺上的常用工具至少掌握一種程序設(shè)計(jì)語言注重分析、注意寫文檔軟件開發(fā)應(yīng)注意：采用科學(xué)的、現(xiàn)代化的組織管理模式；選用先進(jìn)的設(shè)計(jì)思想與方法。軟件開發(fā)經(jīng)驗(yàn)之談通過理論學(xué)習(xí)去理解和掌握基本概念和方法通過實(shí)踐去加深認(rèn)識，積累開發(fā)經(jīng)驗(yàn)和提高軟件開發(fā)能力。第2章數(shù)據(jù)結(jié)構(gòu)與算法一、數(shù)據(jù)結(jié)構(gòu)討論與研究的范疇二、算法第1節(jié)概述第72頁學(xué)習(xí)內(nèi)容與要求學(xué)習(xí)和了解數(shù)據(jù)結(jié)構(gòu)所研究的內(nèi)容；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的定義和基本分類；學(xué)習(xí)和掌握與數(shù)據(jù)結(jié)構(gòu)有關(guān)的名詞術(shù)語（如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)類型、抽象數(shù)據(jù)類型ADT等等）；學(xué)習(xí)和了解算法的概念、特點(diǎn)以及算法的評價(jià)標(biāo)準(zhǔn)。第73頁DataStructures+Algorithms=Programs——NicklausWirth程序:數(shù)據(jù)結(jié)構(gòu):

算法:利用計(jì)算機(jī)語言編制的一組具有確定功能的指令集合。處理問題的策略。問題或?qū)ο蟮臄?shù)學(xué)模型(如何描述數(shù)據(jù)的外部表現(xiàn)形式和內(nèi)部存儲結(jié)構(gòu))。第74頁一、數(shù)據(jù)結(jié)構(gòu)研究和討論的范疇第75頁“學(xué)生”數(shù)據(jù)123456789第76頁“課程”數(shù)據(jù)第77頁“選課”數(shù)據(jù)學(xué)號課程編號成績時(shí)間981640240028206.6.10981640240169006.6.15981650240028506.6.10981650240167606.6.15981650240248906.6.139816598164024016024002024024學(xué)生課程第78頁學(xué)生(學(xué)號,姓名,性別,籍貫)課程(課程號,課程名,學(xué)分)選課(學(xué)號,課程號,成績)“選課”數(shù)據(jù)包含如下信息:

學(xué)號課程編號成績時(shí)間

學(xué)生選課系統(tǒng)中“學(xué)生”和“課程”這兩個實(shí)體構(gòu)成了網(wǎng)狀（圖狀）關(guān)系（即“選課”關(guān)系）。第79頁UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/(root)binlibuseretcmathdsswlintaoxieStack.cppQueue.cppTree.cpp第80頁數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容

綜合上述例子可見，描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。簡單地說，作為一門學(xué)科，數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題當(dāng)中計(jì)算機(jī)的操作對象（數(shù)據(jù)）以及它們之間的關(guān)系（邏輯結(jié)構(gòu)和物理結(jié)構(gòu)）和操作（算法實(shí)現(xiàn)）。第81頁若干名詞術(shù)語數(shù)據(jù)（data）數(shù)據(jù)元素（dataelement）數(shù)據(jù)項(xiàng)（dataitem）數(shù)據(jù)對象（dataobject）數(shù)據(jù)結(jié)構(gòu)（datastructure）數(shù)據(jù)類型（datatype）抽象數(shù)據(jù)類型（ADT）第82頁數(shù)據(jù)（data）數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中、被計(jì)算機(jī)程序識別和處理的符號的集合。數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)第83頁數(shù)據(jù)元素(dataelement)和

數(shù)據(jù)項(xiàng)（dataitem）數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、記錄。有時(shí)一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)（dataitem）組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識單位。第84頁數(shù)據(jù)對象(dataobject)具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合，數(shù)據(jù)的子集。例：整數(shù)數(shù)據(jù)對象N={0,1,2,…}學(xué)生數(shù)據(jù)對象有窮集和無窮集第85頁什么是數(shù)據(jù)結(jié)構(gòu)定義:

由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。

與“數(shù)據(jù)對象”這一概念的區(qū)別？作為術(shù)語名詞和作為學(xué)科名詞的區(qū)別？第86頁數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲內(nèi)的表示，即數(shù)據(jù)的存儲表示（物理結(jié)構(gòu)、物理表示）。數(shù)據(jù)的運(yùn)算，即對數(shù)據(jù)元素施加的操作。作為學(xué)科，數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的組織形式，包括以下內(nèi)容：第87頁數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從數(shù)據(jù)的邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)，與數(shù)據(jù)元素本身的具體形式、內(nèi)容無關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型。第88頁數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類：線性結(jié)構(gòu)：一對一關(guān)系樹形結(jié)構(gòu)：一對多關(guān)系圖狀結(jié)構(gòu)：多對多關(guān)系集合結(jié)構(gòu)：簡單隸屬關(guān)系第89頁數(shù)據(jù)邏輯結(jié)構(gòu)的描述方式Data_Structure={D,R}

其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。一般表現(xiàn)形式如下：D={d1,d2,…,dn}R={r1,r2,…,rm}關(guān)鍵字：數(shù)據(jù)元素中可用于標(biāo)識該數(shù)據(jù)元素的某個分量（數(shù)據(jù)項(xiàng)）。通常用關(guān)鍵字區(qū)別不同的數(shù)據(jù)元素。第90頁D＝{01,02,03,04,05,06,07,08,09,10}R1={<08,05>,<05,02>,<02,01>,<01,03>,<03,09>,<09,04>,<04,06>,<06,10>,<10,07>}R2={<01,02>,<01,05>,<01,08>,<02,03>,<02,04>,<05,06,>,<05,07>,<08,09>,<08,10>}R3={<01,04>,<04,01>,<01,05>,<05,01>,<01,08>,<08,01>,<04,07>,<07,04>,<05,06>,<06,05>,<06,04>,<04,06>,<05,08>,<08,05>,<06,09>,<09,06>,<09,02>,<02,09>,<08,10>,<10,08>,<04,03>,<03,04>}第91頁R1={<08,05>,<05,02>,<02,01>,<01,03>,<03,09>,<09,04>,<04,06>,<06,10>,<10,07>}用連線表示數(shù)據(jù)元素之間的聯(lián)系第92頁R2={<01,02>,<01,05>,<01,08>,<02,03>,<02,04>,<05,06>,<05,07>,<08,09>,<08,10>}第93頁R3={<01,04>,<04,01>,<01,05>,<05,01>,<01,08>,<08,01>,<04,07>,<07,04>,<05,06>,<06,05>,<06,04>,<04,06>,<05,08>,<08,05>,<06,09>,<09,06>,<09,02>,<02,09>,<08,10>,<10,08>,<04,03>,<03,04>}第94頁由上述數(shù)據(jù)結(jié)構(gòu)的描述可得出結(jié)論：相同數(shù)據(jù)元素的集合（即同一數(shù)據(jù)對象），因其關(guān)系的不同而構(gòu)成不同的數(shù)據(jù)邏輯結(jié)構(gòu)。對一實(shí)際應(yīng)用問題，合理選擇數(shù)據(jù)邏輯結(jié)構(gòu)才能夠設(shè)計(jì)出有效的算法。例：根據(jù)下列選課情況安排考試日程，使得在不沖突的情況下用盡可能短的時(shí)間安排所有考試。學(xué)生姓名選修課1選修課2選修課3甲ABC乙DE丙DCF丁EFA戊BF第95頁數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲方式，依賴于計(jì)算機(jī)語言。存儲結(jié)構(gòu)分類

順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)索引結(jié)構(gòu)散列結(jié)構(gòu)第96頁順序存儲（矢量存儲）結(jié)構(gòu)Contiguousimplementation（vector

implementation）

所有元素存放在一片連續(xù)的存儲單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存中其存儲地址仍然相鄰。

鏈?zhǔn)酱鎯Y(jié)構(gòu)Linkedimplementation

所有元素可以存放在不連續(xù)的存儲單元中，元素之間的關(guān)系通過地址確定，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存后其存儲地址不一定是相鄰的。第97頁順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖第98頁數(shù)據(jù)類型數(shù)據(jù)類型

定義：一組性質(zhì)相同的值的集合,以及定義于這個值集合上的一組操作的總稱。

C語言中的數(shù)據(jù)類型charintfloatdoublevoid

字符型整型浮點(diǎn)型雙精度型無值

基本數(shù)據(jù)類型（原子類型）：可以看作是計(jì)算機(jī)中程序設(shè)計(jì)語言已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。構(gòu)造型數(shù)據(jù)類型：由相同或不同成分的類型構(gòu)成，如數(shù)組、結(jié)構(gòu)體、類等。第99頁抽象數(shù)據(jù)類型

(ADTs:AbstractDataTypes)由用戶定義，用以表示實(shí)際應(yīng)用問題的數(shù)據(jù)模型。由基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的服務(wù)（或稱操作）。第100頁抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型從形式上可用（D，R，O）三元組表示。其中：D是數(shù)據(jù)對象，R是D上的關(guān)系集，O是對D的基本操作集。一般采用如下格式描述ADT

抽象數(shù)據(jù)類型名

{

數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}

ADT

抽象數(shù)據(jù)類型名第101頁ADT基本操作的定義格式基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

參數(shù)：賦值參數(shù)只為操作提供輸入值;引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。若初始條件為空,則省略之。操作結(jié)果：說明操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。第102頁例如，抽象數(shù)據(jù)類型“復(fù)數(shù)”的定義：數(shù)據(jù)對象：D＝{<e1,e2>｜e1,e2∈RealSet}數(shù)據(jù)關(guān)系：R1＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分，

e2是復(fù)數(shù)的虛數(shù)部分}ADTComplex{第103頁基本操作：plex(&Z,v1,v2)操作結(jié)果：構(gòu)造一個復(fù)數(shù)Z，其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。plex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。第104頁

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個復(fù)數(shù)z1,z2的和值。}ADTComplex第105頁抽象數(shù)據(jù)類型的實(shí)現(xiàn)

抽象數(shù)據(jù)類型描述的是抽象的數(shù)據(jù)模型及其操作，需要通過固有數(shù)據(jù)類型(高級編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。引入抽象數(shù)據(jù)類型的意義

通常研究一個數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)問題可以從研究其抽象數(shù)據(jù)類型著手，例如通過對抽象數(shù)據(jù)類型的加工來用C++類實(shí)現(xiàn)該數(shù)據(jù)結(jié)構(gòu)：類的數(shù)據(jù)成員對應(yīng)于ADT所描述的數(shù)據(jù)結(jié)構(gòu)，類的方法對應(yīng)于ADT所描述的操作。第106頁二、算法第107頁關(guān)于算法

算法是為了解決某類問題而設(shè)計(jì)的一個有限長的操作序列。算法特性有窮性、確定性、可行性、有輸入、有輸出第108頁有窮性：對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在有限時(shí)間內(nèi)完成。確定性：對于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行；并且在任何條件下，算法都只有一條執(zhí)行路徑。可行性：算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。第109頁有輸入：作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上輸入已被嵌入算法之中。有輸出：它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。第110頁用自然語言描述算法：用我們?nèi)粘Ｉ钪械淖匀徽Z言也可以描述算法。算法描述方法用流程圖描述算法：一個算法可以用流程圖的方式來描述，輸入輸出、判斷、處理分別用不同的框圖表示，用箭頭表示流程的流向。這是一種描述算法的較好方法，目前在一些高級語言程序設(shè)計(jì)中仍然采用。用其它方式描述算法：我們還可以用數(shù)學(xué)語言或約定的符號語言（如偽代碼）來描述算法。用C++描述算法：在本課程中，我們將采用C++來描述算法，所有算法的描述都用C++中的函數(shù)形式。第111頁算法和程序的關(guān)系

算法≠程序！

算法著重體現(xiàn)思路和方法，程序著重體現(xiàn)計(jì)算機(jī)的實(shí)現(xiàn)。程序不一定滿足有窮性（例如死循環(huán)情形）；另外，程序中的指令必須是機(jī)器可執(zhí)行的，算法中的指令無此限制。算法用計(jì)算機(jī)語言來書寫時(shí)才是程序。第112頁算法設(shè)計(jì)原則正確性可讀性健壯性高效率低需求算法評價(jià)標(biāo)準(zhǔn)

時(shí)間特性：時(shí)間復(fù)雜度T(n)

空間特性：空間復(fù)雜度S(n)算法設(shè)計(jì)原則與評價(jià)標(biāo)準(zhǔn)第113頁一個特定算法的運(yùn)行時(shí)間由其“運(yùn)行工作量”決定。其運(yùn)行工作量的大小，通常只依賴于問題的規(guī)模（通常由問題涉及的數(shù)據(jù)量決定，用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。算法的運(yùn)行時(shí)間

假如，隨著問題規(guī)模n

的增長，算法執(zhí)行時(shí)間的增長率和函數(shù)f(n)的增長率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的時(shí)間復(fù)雜度。第114頁程序執(zhí)行時(shí)間的計(jì)算事后統(tǒng)計(jì)法事前分析估算法算法策略問題規(guī)模程序設(shè)計(jì)語言機(jī)器代碼運(yùn)行效率機(jī)器執(zhí)行指令的速度第115頁如何估算算法的時(shí)間復(fù)雜度？算法=控制結(jié)構(gòu)+基本操作(基本數(shù)據(jù)類型的操作)算法的執(zhí)行時(shí)間=∑基本操作的執(zhí)行次數(shù)×基本操作的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間

與

基本操作執(zhí)行次數(shù)之和

成正比。從算法中選取一種對于所研究的問題來說是基本操作的操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。第116頁例一兩個矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲矩陣元素，c為a和b的乘積for(i=1;i<=n;++i)

for(j=1;j<=n;++j){c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作時(shí)間復(fù)雜度:

O(n3)第117頁例二選擇排序voidselect_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列

}//select_sort基本操作:數(shù)據(jù)比較操作時(shí)間復(fù)雜度:O(n2)for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}j=i;//選擇第i個最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j]

)j=k;第118頁例三冒泡排序voidbubble_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列for

(i=n-1,change=TRUE;i>1&&

change;--i)}//冒泡排序基本操作:

賦值操作時(shí)間復(fù)雜度:

O(n2){

change=FALSE;

//change為元素進(jìn)行交換標(biāo)志

for(j=0;j<i;++j)

if(a[j]>a[j+1])

{

a[j]←→a[j+1];

change=TRUE;}}//一趟冒泡排序第119頁程序指令本身所占空間常量和變量所占空間數(shù)據(jù)操作所需的工作單元實(shí)現(xiàn)數(shù)據(jù)計(jì)算時(shí)所需的輔助空間算法的存儲空間需求算法的空間復(fù)雜度定義為:

表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲空間的增長率與函數(shù)g(n)的增長率相同。S(n)=O(g(n))第2章數(shù)據(jù)結(jié)構(gòu)與算法Section2

LinearList（線性表）一、基本概念二、順序表三、鏈表學(xué)習(xí)內(nèi)容和目標(biāo)1、學(xué)習(xí)和掌握線性表的定義（邏輯結(jié)構(gòu)）及其特點(diǎn)；2、學(xué)習(xí)和理解線性表的順序存儲結(jié)構(gòu)（順序表）的C++類定義和類模板定義方法；掌握順序表的基本操作的實(shí)現(xiàn)原理和方法；3、學(xué)習(xí)和理解線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈表）的C++類定義和類模板定義方法；掌握單鏈表、雙向鏈表和循環(huán)鏈表的結(jié)構(gòu)特點(diǎn)以及基本操作的實(shí)現(xiàn)原理和方法。Subsection1

BasicConceptDefinitionofList

Alistofelements(數(shù)據(jù)元素)oftypeTisafinitesequence(有限序列)

ofelementsofTtogetherwiththefollowingoperations(操作):1.Construct(構(gòu)造)

thelist,leavingitempty.2.Determine(確定)

whetherthelistisemptyornot.3.Determinewhetherthelistisfullornot.4.Findthesizeofthelist.5.Clearthelisttomakeitempty.6.Insert(插入)

anentry(數(shù)據(jù)元素)ataspecifiedpositionofthelist.7.Remove(刪除)anentryfromaspecifiedpositioninthelist.8.Retrieve(檢索)theentryfromaspecifiedpositioninthelist.9.Replace(替換)theentryataspecifiedpositioninthelist.10.Traverse(遍歷)thelist,performing(執(zhí)行)agivenoperationoneachentry.

遍歷:逐項(xiàng)訪問數(shù)據(jù)元素(每個元素只訪問一次)線性表(LinearList)線性表的定義和特點(diǎn)

定義

n（0）個數(shù)據(jù)元素的有限序列，記作

（a1,a2,…,an）或（a0,a1,…,an-1）

ai

是表中數(shù)據(jù)元素，n是表長度。數(shù)據(jù)類型的任意性和一致性直接前驅(qū)元素和直接后繼元素

線性表的特點(diǎn)除第一個元素外，其他每一個元素有一個且僅有一個直接前驅(qū)。除最后一個元素外，其他每一個元素有一個且僅有一個直接后繼。相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。“序偶”包含兩層含義：順序、配對a1a2a3a4a5a6抽象數(shù)據(jù)類型線性表的定義如下：ADTList{

數(shù)據(jù)對象：D＝{ai|ai

∈ElemSet,i=1,2,...,n,n≥0}{稱

n

為線性表的表長;

稱

n=0

時(shí)的線性表為空表。}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{設(shè)線性表為(a1，a2,...，ai，...，an),

稱i為ai在線性表中的位序。}

基本操作：

結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作

引用型操作

加工型操作

}ADTList初始化操作InitList(&L)操作結(jié)果：構(gòu)造一個空線性表L結(jié)構(gòu)銷毀操作DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。引用型操作:Empty(L) Length(L)Prior(L,x,&pre)Next(L,x,&next)Get(L,i) Locate(L,x)加工型操作：Clear(&L)PutElem(&L,i,x)Insert(&L,i,x)Delete(&L,i,&x)

線性表的基本操作Empty(L)（判斷線性表是否為空）初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則FALSE。Length(L)（求線性表的長度）初始條件：線性表L已存在。操作結(jié)果：返回L中元素個數(shù)。引用型操作Prior(L,x,&pre)（求數(shù)據(jù)元素的前驅(qū)）初始條件：線性表L已存在。操作結(jié)果：若x是L的元素，但不是第一個，則用pre返回它的前驅(qū)，否則操作失敗，pre無定義。Next(L,x,&next)（求數(shù)據(jù)元素的后繼）初始條件：線性表L已存在。操作結(jié)果：若x是L的元素，但不是最后一個，則用next返回它的后繼，否則操作失敗，next無定義。Get(L,i)（獲取線性表中某個數(shù)據(jù)元素）初始條件：線性表L已存在，且1≤i≤Length(L)。操作結(jié)果：返回L中第i個元素的值。Locate(L,x)（確定元素在表中位置）初始條件：線性表L已存在，x為給定值操作結(jié)果：返回L中第1個與x相等的元素的位序。若這樣的元素不存在，則返回值為0。Clear(&L)（線性表置空）初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。PutElem(&L,i,x)（改變數(shù)據(jù)元素的值）初始條件：線性表L已存在，且1≤i≤Length(L)。操作結(jié)果：L中第i個元素賦值為x的值。加工型操作Insert(&L,i,x)（插入數(shù)據(jù)元素）初始條件：線性表L已存在，且1≤i≤Length(L)+1操作結(jié)果：在L的第i個元素之前插入新的元素x，L的長度增1。Delete(&L,i)（刪除數(shù)據(jù)元素）初始條件：線性表L已存在且非空，1≤i≤Length(L)。操作結(jié)果：刪除L的第i個元素，L的長度減1。線性表的存儲結(jié)構(gòu)線性表常用的兩種存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)（順序表）鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈表）注意：任意一種存儲結(jié)構(gòu)，都不僅要存儲數(shù)據(jù)本身，還需要存儲（保留）數(shù)據(jù)與數(shù)據(jù)之間的邏輯關(guān)系，并且在數(shù)據(jù)操作過程中不破壞這種邏輯關(guān)系。邏輯上定義的線性表，在計(jì)算機(jī)中實(shí)現(xiàn)時(shí)需要考慮其物理存儲結(jié)構(gòu)以及相關(guān)操作的實(shí)現(xiàn)。Subsection2SequentialList（順序表）——線性表的順序存儲結(jié)構(gòu)順序表(SequentialList)順序表的定義和特點(diǎn)線性表的順序存儲結(jié)構(gòu)：將線性表中的元素相繼存放在一個連續(xù)的存儲空間中。特點(diǎn)：元素存儲位置體現(xiàn)邏輯關(guān)系如何用程序設(shè)計(jì)語言實(shí)現(xiàn)順序表？一維數(shù)組一維數(shù)組實(shí)現(xiàn)順序表數(shù)組下標(biāo)：0123456789data253457164809

需要預(yù)先定義數(shù)組大小（即線性表的最大長度）；需要跟蹤線性表的長度，以便掌握線性表的相關(guān)信息以及進(jìn)行相應(yīng)的算法操作。或通過記錄尾元素的下標(biāo)來跟蹤線性表長度直接記錄線性表的長度順序表(SeqList)的定義（C語言實(shí)現(xiàn)）#define

MaxSize

表中最大元素個數(shù)Type

SeqList[MaxSize];

//定義數(shù)組intlast;

//表中最后一個元素的下標(biāo)#define為宏定義;如:＃defineMaxSize10數(shù)據(jù)類型Type可以是原子類型，也可以是已實(shí)現(xiàn)的結(jié)構(gòu)類型，但在定義順序表時(shí)必須已經(jīng)顯式定義該數(shù)據(jù)類型。數(shù)組下標(biāo)有效取值范圍?線性表中元素有效下標(biāo)范圍？順序表長度與Last的關(guān)系？空表和滿表的判斷？0～MaxSize－1表長度=last+10～last順序表(SeqList)類的定義(C++類實(shí)現(xiàn))classSeqList{protected://SeqList類的數(shù)據(jù)成員Type*data; //定義數(shù)組 intMaxSize; //順序表允許長度

intlast; //順序表最后一個元素下標(biāo)public://SeqList類的函數(shù)成員 SeqList(intMaxSize);//構(gòu)造函數(shù) ~SeqList(){delete[]data;}//析構(gòu)函數(shù) intLength()const{returnlast+1;}intLocate(

Typex)const; //定位intInsert(inti,Type

x);//插入intDelete(inti); //刪除

intNext(Typex,Type

&next);//后繼intPrior(Typex,Type

&pre);//前驅(qū)intEmpty(){returnlast==-1;

}//判空intFull(){returnlast==MaxSize-1;

}TypeGet(inti){//提取

returni<0||i>last？NULL:data[i];}}

（續(xù)上頁）順序表(SeqList)類的定義(C++類模板實(shí)現(xiàn))template<classType>

classSeqList{protected://SeqList類的數(shù)據(jù)成員

Type*data;//順序表存儲數(shù)組(指針方式定義) intMaxSize; //最大允許長度(元素個數(shù)) intlast; //最后一個元素的下標(biāo)public://SeqList類的函數(shù)成員 SeqList(intListSize);//構(gòu)造函數(shù) ~SeqList(){delete[]data;}//析構(gòu)函數(shù) intLength()const{returnlast+1;}intLocate(

Typex)const; //定位intInsert(inti,Type

x);//插入intDelete(inti); //刪除

intNext(Typex,Type

&next);//后繼intPrior(Typex,Type

&pre);//前驅(qū)intEmpty(){returnlast==-1;

}//判空intFull(){returnlast==MaxSize-1;

}TypeGet(inti){//提取

returni<0||i>last？NULL:data[i];}}

（續(xù)上頁）類模板和模板類類模板是對結(jié)構(gòu)相同但數(shù)據(jù)類型不同的類的抽象描述；利用類模板創(chuàng)建的實(shí)例被稱為模板類，是具體的類。利用已定義的類模板可以創(chuàng)建實(shí)例，如：SeqList<int>A;上述語句將創(chuàng)建一個線性表實(shí)例A（模板類），它具有類模板SeqList所有的特性，同時(shí)其數(shù)據(jù)成員“data數(shù)組”的數(shù)據(jù)類型為整型。使用類模板可以減少重復(fù)定義，提高重用性。順序表部分公共操作的實(shí)現(xiàn)

——SeqList類模板的若干函數(shù)成員的實(shí)現(xiàn)構(gòu)造函數(shù)：線性表的初始化查找函數(shù)：根據(jù)元素值或序號查找元素插入函數(shù)：在指定位置插入一個新元素刪除函數(shù)：刪除指定數(shù)值（或位置）的元素注意：在數(shù)據(jù)操作過程中不能破壞線性表的邏輯關(guān)系。

template<classType>

SeqList<Type>::SeqList(intListSize){

//創(chuàng)建一個最大長度為ListSize的空線性表if(ListSize>0){

MaxSize=ListSize;last=-1;

//申請分配內(nèi)存空間

data=newType[MaxSize];

//空間申請失敗處理if(data==NULL){

MaxSize=0;}

}}構(gòu)造函數(shù)（初始化）查找過程示例（查找值為16的元素）253457164809

012345data查找

16i253457164809

i253457164809

i253457164809

i查找成功，返回3查找函數(shù)（定位函數(shù)）的實(shí)現(xiàn)2534571648

01234data查找50i2534571648

i2534571648

i2534571648

i2534571648

i查找失敗，返回－1查找過程示例（查找值為50的元素）template<classType> int

SeqList<Type>::Locate(Type

&x)const{//查找函數(shù)：在順序表中從前向后查找元素值//等于給定值x的數(shù)據(jù)元素,返回所在單元下標(biāo)

inti=0;

while(i<=last

&&data[i]!=x)i++;

if(i>last)return

-1; //返回-1表示查找失敗

elsereturni; }查找函數(shù)（定位函數(shù)）注意：只需搜索有效元素區(qū)域，而不是整個數(shù)組。表項(xiàng)（數(shù)據(jù)元素）的插入操作253457164809630123456data50插入

x253457501648096301234567data50i＝3在進(jìn)行數(shù)據(jù)插入操作時(shí)，需要注意：插入位置i的有效取值范圍：此處為0～last+1線性表為滿表(last=Maxsize-1)時(shí)，不允許插入操作lastLast——在表中第i個元素前插入一個新元素x

template<classType>int

SeqList<Type>::Insert(inti,Typex){//判斷刪除位置i是否合理以及表是否已滿if(i<0

||

i>last+1

||

last==MaxSize-1)

return0;//插入操作不成功

else{last++;

for(intj=last;j>i;j--)data[j]=data[j-1]; //元素后移

data[i]=x;return1;//操作成功

}}插入函數(shù)表項(xiàng)的刪除操作253457501648096301234567data16刪除位置i2534575048096363

01234567dataLastLast在進(jìn)行刪除操作時(shí)，需要注意：刪除位置i的有效取值范圍：0～Last線性表為空（Last＝－1）時(shí)，不允許刪除操作——刪除表中的第i個元素

template<classType>int

SeqList<Type>::Delete(inti){

//判斷插入位置i是否合理,表是否為空表

if(i<0||i>last||last<0)return0;

//數(shù)據(jù)元素前移for(intj=i+1;j<=last;j++)data[j-1]=data[j];//元素前移(覆蓋)last--;

return1; //成功刪除

}刪除函數(shù)順序表的特點(diǎn)順序表是隨機(jī)存取結(jié)構(gòu)，數(shù)據(jù)元素尋址時(shí)間確定；元素最大個數(shù)需預(yù)先設(shè)定，若估計(jì)不當(dāng)會造成空間浪費(fèi)或空間溢出；插入或刪除操作需要耗費(fèi)較多時(shí)間移動數(shù)據(jù)元素，其時(shí)間復(fù)雜度為O(n)

，n為線性表長度。順序表的應(yīng)用：集合的“并”運(yùn)算已知兩集合A、B，求兩集合的并集，結(jié)果存放于Avoid

Union(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length

();

intm=B.Length

();

for(inti=0;i<m;i++){ intx=B.Get(i);//在B中取一元素 intk=A.Locate(x);//在A中搜索它 if(k==

-1)//若未找到,插入元素

{A.Insert(n,x);n++;}}}已知兩集合A、B，求兩集合的交集，結(jié)果存放于A

voidIntersection(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();inti=0;

while(i<n){intx=A.Get(i);//在A中取一元素

intk=B.Locate(x);//在B中搜索它

if(k==-1){A.Delete(i);n--;}elsei++;//未找到，在A中刪除它

}}順序表的應(yīng)用：集合的“交”運(yùn)算Subsection3LinkedList（鏈表）——線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈表特點(diǎn)：用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素，用指針反映數(shù)據(jù)元素之間的線性關(guān)系，以“結(jié)點(diǎn)的序列”來表示線性表。即：元素(數(shù)據(jù)元素值的映象)

+指針(指示后繼元素存儲位置)=