軟件技術(shù)基礎(chǔ)課件版

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

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

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

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

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

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

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

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

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

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

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

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

001111100000100100111111B或3E093FH匯編語(yǔ)言

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

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

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

初步需求分析

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

建造原型

用戶評(píng)估原型（新需求）

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

開(kāi)始

結(jié)束

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

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

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

學(xué)號(hào)課程編號(hào)成績(jī)時(shí)間

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

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

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

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

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

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

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

implementation）

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

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

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

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

C語(yǔ)言中的數(shù)據(jù)類(lèi)型charintfloatdoublevoid

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

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

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

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

{

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

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

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

ADT

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

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

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

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

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

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

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

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

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

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

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

算法≠程序！

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

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

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

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

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

與

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

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

//以二維數(shù)組存儲(chǔ)矩陣元素，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頁(yè)例二選擇排序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個(gè)最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j]

)j=k;第118頁(yè)例三冒泡排序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頁(yè)程序指令本身所占空間常量和變量所占空間數(shù)據(jù)操作所需的工作單元實(shí)現(xiàn)數(shù)據(jù)計(jì)算時(shí)所需的輔助空間算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為:

表示隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)空間的增長(zhǎng)率與函數(shù)g(n)的增長(zhǎng)率相同。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í)和理解線性表的順序存儲(chǔ)結(jié)構(gòu)（順序表）的C++類(lèi)定義和類(lèi)模板定義方法；掌握順序表的基本操作的實(shí)現(xiàn)原理和方法；3、學(xué)習(xí)和理解線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表）的C++類(lèi)定義和類(lèi)模板定義方法；掌握單鏈表、雙向鏈表和循環(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)訪問(wèn)數(shù)據(jù)元素(每個(gè)元素只訪問(wèn)一次)線性表(LinearList)線性表的定義和特點(diǎn)

定義

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

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

ai

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

線性表的特點(diǎn)除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)。除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接后繼。相鄰數(shù)據(jù)元素之間存在序偶關(guān)系?！靶蚺肌卑瑑蓪雍x：順序、配對(duì)a1a2a3a4a5a6抽象數(shù)據(jù)類(lèi)型線性表的定義如下：ADTList{

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

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

n

為線性表的表長(zhǎng);

稱

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)銷(xiāo)毀操作

引用型操作

加工型操作

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

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

MaxSize

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

SeqList[MaxSize];

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

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

intlast; //順序表最后一個(gè)元素下標(biāo)public://SeqList類(lèi)的函數(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ù)上頁(yè)）順序表(SeqList)類(lèi)的定義(C++類(lèi)模板實(shí)現(xiàn))template<classType>

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

Type*data;//順序表存儲(chǔ)數(shù)組(指針?lè)绞蕉x) intMaxSize; //最大允許長(zhǎng)度(元素個(gè)數(shù)) intlast; //最后一個(gè)元素的下標(biāo)public://SeqList類(lèi)的函數(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ù)上頁(yè)）類(lèi)模板和模板類(lèi)類(lèi)模板是對(duì)結(jié)構(gòu)相同但數(shù)據(jù)類(lèi)型不同的類(lèi)的抽象描述；利用類(lèi)模板創(chuàng)建的實(shí)例被稱為模板類(lèi)，是具體的類(lèi)。利用已定義的類(lèi)模板可以創(chuàng)建實(shí)例，如：SeqList<int>A;上述語(yǔ)句將創(chuàng)建一個(gè)線性表實(shí)例A（模板類(lèi)），它具有類(lèi)模板SeqList所有的特性，同時(shí)其數(shù)據(jù)成員“data數(shù)組”的數(shù)據(jù)類(lèi)型為整型。使用類(lèi)模板可以減少重復(fù)定義，提高重用性。順序表部分公共操作的實(shí)現(xiàn)

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

template<classType>

SeqList<Type>::SeqList(intListSize){

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

MaxSize=ListSize;last=-1;

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

data=newType[MaxSize];

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

MaxSize=0;}

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

012345data查找

16i253457164809

i253457164809

i253457164809

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

01234data查找50i2534571648

i2534571648

i2534571648

i2534571648

i查找失敗，返回－1查找過(guò)程示例（查找值為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ū)域，而不是整個(gè)數(shù)組。表項(xiàng)（數(shù)據(jù)元素）的插入操作253457164809630123456data50插入

x253457501648096301234567data50i＝3在進(jìn)行數(shù)據(jù)插入操作時(shí)，需要注意：插入位置i的有效取值范圍：此處為0～last+1線性表為滿表(last=Maxsize-1)時(shí)，不允許插入操作lastLast——在表中第i個(gè)元素前插入一個(gè)新元素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í)，不允許刪除操作——?jiǎng)h除表中的第i個(gè)元素

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í)間確定；元素最大個(gè)數(shù)需預(yù)先設(shè)定，若估計(jì)不當(dāng)會(huì)造成空間浪費(fèi)或空間溢出；插入或刪除操作需要耗費(fèi)較多時(shí)間移動(dòng)數(shù)據(jù)元素，其時(shí)間復(fù)雜度為O(n)

，n為線性表長(zhǎng)度。順序表的應(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)酱鎯?chǔ)結(jié)構(gòu)鏈表特點(diǎn)：用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素，用指針?lè)从硵?shù)據(jù)元素之間的線性關(guān)系，以“結(jié)點(diǎn)的序列”來(lái)表示線性表。即：元素(數(shù)據(jù)元素值的映象)

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