2007-2008學(xué)年第一學(xué)期

《數(shù)據(jù)結(jié)構(gòu)》教案PAGEPAGE14教案2007-2008學(xué)年第一學(xué)期課程名稱：數(shù)據(jù)結(jié)構(gòu)課程編號：411101：信息科學(xué)與工程學(xué)院計本06任課教師：鄭志華信息科學(xué)與工程學(xué)院山東師范大學(xué)課程簡介《數(shù)據(jù)結(jié)構(gòu)》是計算機專業(yè)的一門重要的專業(yè)技術(shù)基礎(chǔ)課程，主要介紹軟件設(shè)計中常用的數(shù)據(jù)結(jié)構(gòu)及其運算，包括：線性表、棧、隊列、串、數(shù)組、廣義表、樹、二叉樹、圖結(jié)構(gòu)等幾種基本的數(shù)據(jù)結(jié)構(gòu)及其存儲結(jié)構(gòu)和所施加的運算與實現(xiàn)等。另外還介紹軟件設(shè)計中常用的幾種查找和排序運算，以及遞歸技術(shù)等，在介紹各項內(nèi)容的同時，還涉及到算法設(shè)計與分析的基本技術(shù)和面向?qū)ο蟪绦蛟O(shè)計的理論與技術(shù)等內(nèi)容。通過本課程的學(xué)習(xí)，學(xué)生應(yīng)能熟練掌握上述結(jié)構(gòu)及其運算的實現(xiàn)和性能特點，掌握各種排序和查找運算以及遞歸技術(shù)，并能對給定的實際問題，建立準(zhǔn)確的問題模型，設(shè)計有效的問題求解方法，選擇合理的數(shù)據(jù)結(jié)構(gòu)及其運算集，設(shè)計有效的算法，從而為提高軟件設(shè)計水平打好基礎(chǔ)。教學(xué)大綱課程編號：4111201英文課程名：DataStructure總學(xué)時：88學(xué)時（其中含實驗教學(xué)16學(xué)時）學(xué)分：4學(xué)分 課程類別：專業(yè)基礎(chǔ)課適用專業(yè)：計算機科學(xué)與技術(shù)、通信工程、信息技術(shù)方向先修課程：高級程序設(shè)計一、課程性質(zhì)與目的、要求《數(shù)據(jù)結(jié)構(gòu)》是計算機科學(xué)與技術(shù)專業(yè)本科生的一門必修的專業(yè)基礎(chǔ)課，是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，也是計算機專業(yè)的核心課程。本課程的主要目標(biāo)是使學(xué)生深入了解數(shù)據(jù)結(jié)構(gòu)的思想和數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法，特別是數(shù)據(jù)結(jié)構(gòu)在實際工作中的應(yīng)用和技術(shù)。本課程以C或C++語言作為算法的描述工具，強化數(shù)據(jù)結(jié)構(gòu)基本知識和程序設(shè)計能力的雙基訓(xùn)練，加深學(xué)生對所學(xué)內(nèi)容的理解，追求理論聯(lián)系實際，實踐教學(xué)與相應(yīng)的教學(xué)內(nèi)容相呼應(yīng)。培養(yǎng)發(fā)展學(xué)生從事發(fā)展算法與程序設(shè)計研究和實踐的能力，為后續(xù)專業(yè)課的學(xué)習(xí)和專業(yè)素質(zhì)的培養(yǎng)奠定堅實的基礎(chǔ)。二、教學(xué)內(nèi)容及學(xué)時分配第一章：緒論2課時1、數(shù)據(jù)結(jié)構(gòu)定義、基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、算法等。2、抽象數(shù)據(jù)類型。描述算法的程序語言3、算法與算法復(fù)雜度分析第二章線性表8課時1、線性表的基本概念及抽象數(shù)據(jù)類型2、線性表的順序表的表示和實現(xiàn)：順序表的定義和特點；順序表的定義、查找、插入和刪除3、線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)：（1）單鏈表：單鏈表的結(jié)構(gòu)定義；單鏈表的查找、插入與刪除；帶表頭結(jié)點的單鏈表及靜態(tài)鏈表；（2）循環(huán)鏈表、雙向鏈表的定義和基本操作4、一元多項式的表示和相加第三章棧和隊列6課時1、棧。棧的定義、抽象數(shù)據(jù)類型及特點，棧的順序存儲表示和實現(xiàn)，棧的鏈接存儲表示和實現(xiàn)。2、棧的應(yīng)用：數(shù)制轉(zhuǎn)換、括號匹配的檢驗及表達(dá)式求值3、棧與遞歸的實現(xiàn)4、隊列：隊列的定義、抽象數(shù)據(jù)類型及特點，循環(huán)隊列——隊列的順序存儲表示和實現(xiàn)；5、隊列的鏈接存儲表示和實現(xiàn)；第四章串4課時1、串類型的定義2、串的表示和實現(xiàn)3、定長順序存儲、堆分配存儲、塊鏈存儲表示，4、串的模式匹配算法：第五章數(shù)組和廣義表6課時1、數(shù)組的定義、數(shù)組的表示和實現(xiàn)2、矩陣的壓縮存儲：特殊矩陣，稀疏矩陣的表示和存儲、矩陣轉(zhuǎn)置與快速轉(zhuǎn)置、矩陣乘法3、廣義表：廣義表的概念；廣義表的表示及操作；廣義表存儲結(jié)構(gòu)的實現(xiàn)；廣義表的遞歸算法第六章樹和二叉樹12課時1、樹和二叉樹：樹的定義；樹的術(shù)語；二叉樹的定義；二叉樹的性質(zhì)；二叉樹的順序表示；二叉鏈表表示2、二叉樹遍歷及應(yīng)用：中序遍歷；前序遍歷；后序遍歷；3、線索二叉樹：線索；線索化二叉樹4、樹與森林：樹的存儲結(jié)構(gòu)；森林與二叉樹的轉(zhuǎn)換；樹和森林的遍歷5、哈夫曼樹及其應(yīng)用：最優(yōu)二叉樹（哈夫曼樹）、構(gòu)造哈夫曼樹、哈夫曼編碼的方法及帶權(quán)路徑長度的計算；第八章圖12課時1、圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型2、圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表3、圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；關(guān)節(jié)點與重連通分量4、最小生成樹：kruskul算法；prim算法5、最短路徑問題：dijkstra算法和Floyd算法6、活動網(wǎng)絡(luò)：AOV網(wǎng)絡(luò)與拓?fù)渑判?；AOE網(wǎng)絡(luò)與關(guān)鍵路徑第九章查找8課時1、靜態(tài)查找表：順序表的查找，有序表的查找，靜態(tài)表的搜索；索引順序表2、動態(tài)查找表：二叉排序樹和AVL樹（AVL樹定義；平衡化旋轉(zhuǎn)；AVL樹的插入和刪除；AVL樹高度）；B樹和B+樹；鍵樹的查找3、哈希表：哈希表，哈希函數(shù)，哈希函數(shù)的構(gòu)造方法；處理沖突的方法；哈希表的查找及其分析第十章內(nèi)部排序10課時1、插入排序：直接插入排序；折半插入排序；2-路排序；希爾排序2、交換排序：冒泡排序；快速排序3、選擇排序：簡單選擇排序；樹型選擇排序；堆排序4、歸并排序5、基數(shù)排序6、各種內(nèi)部排序方法的比較第十一章外部排序2課時1、外部信息存儲2、外排序方法：外排序的基本過程；k路平衡歸并；置換-選擇排序；3、最佳歸并樹第十二章文件2課時1、文件的基本概念2、順序文件、索引文件及組織三、教學(xué)方法以教師講授為主，結(jié)合學(xué)生的大量練習(xí)與實踐四、成績考核方式考試以閉卷形式進(jìn)行，筆試包含實驗考核內(nèi)容。五、教材與參考書教材：《數(shù)據(jù)結(jié)構(gòu)》(C語言版)，嚴(yán)蔚敏等，清華大學(xué)出版社，2006.5參考資料：[1]《數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計》(C語言第二版)，(美)RobertL.Kuse等著，敖富江譯，清華大學(xué)出版社，2006.[2]《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》(C語言版)，李春葆等，清華大學(xué)出版社，2006[3]《數(shù)據(jù)結(jié)構(gòu)習(xí)題集》(C語言版)，嚴(yán)蔚敏等，清華大學(xué)出版社，2006授課時間9.2~8第1、2次課授課章節(jié)第一章緒論任課教師及職稱鄭志華教學(xué)方法與手段多媒體課時安排4《數(shù)據(jù)結(jié)構(gòu)》（C語言版）嚴(yán)蔚敏著，清華大學(xué)出版社教學(xué)目的與要求：ch11.1了解課程的研究內(nèi)容，課程的地位，什么是數(shù)據(jù)，理解數(shù)據(jù)結(jié)構(gòu)和算法等基本概念1.2理解基本術(shù)語：介紹數(shù)據(jù)、記錄、字段、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算、算法及其內(nèi)在關(guān)系等。1.3理解算法及其描述：介紹算法的定義和描述語言。1.4算法分析：評價算法的幾項指標(biāo)，算法的時間復(fù)雜度及其基本求解方法和常用的時間復(fù)雜度。教學(xué)重點，難點：1.數(shù)據(jù)、數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)、算法和算法復(fù)雜度2.線性表的定義教學(xué)內(nèi)容：第一章緒論隨著計算機的發(fā)展及應(yīng)用領(lǐng)域的迅速擴展，計算機已不再僅僅適用于科學(xué)計算，而更多的是用于控制、管理、數(shù)據(jù)處理等多方面的非數(shù)值計算。因此，計算機加工的對象不再是單純的數(shù)值，而更多的是字符、圖像、聲音、表格等。這些數(shù)據(jù)不能隨意堆放，而是要分析數(shù)據(jù)的特性及數(shù)據(jù)之間的關(guān)系后，對數(shù)據(jù)進(jìn)行有效的存儲和處理。什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值應(yīng)用問題中數(shù)據(jù)之間的邏輯關(guān)系和對數(shù)據(jù)的操作，同時還研究如何將具有邏輯關(guān)系的數(shù)據(jù)按一定的存儲方式存放在計算機內(nèi)。分析數(shù)據(jù)之間的邏輯關(guān)系和確定數(shù)據(jù)在計算機內(nèi)的存儲結(jié)構(gòu)是程序設(shè)計前兩個必須完成的任務(wù)。處理非數(shù)值計算問題和數(shù)值計算問題的解決方案不同。例1求一組整數(shù)中的最大值求一組(n個)整數(shù)中的最大值137932502026這是一個線性結(jié)構(gòu)例2學(xué)生的數(shù)據(jù)庫管理學(xué)生檔案表就是一個數(shù)據(jù)結(jié)構(gòu)。計算機檔案管理的主要功能包括：查找、瀏覽、插入、修改、刪除、統(tǒng)計等。如果把表中的一行看成一個記錄并稱為一個結(jié)點，則在此表中，結(jié)點和結(jié)點之間的關(guān)系是一種最簡單的線性關(guān)系。例3：人機對弈

將一個棋局看成一個結(jié)點，這就是一個樹型結(jié)構(gòu)。ABCDE例4多叉路口交通燈的管理問題。在多叉路口設(shè)計幾種顏色的信號燈才能使車輛間不相撞，且達(dá)到車輛最大流。設(shè)如圖的五叉路口，其中，ABCDE這是一個圖型結(jié)構(gòu)的問題。假設(shè)一條通路為一個頂點,通路之間互相矛盾的關(guān)系以兩個頂點之間的連線表示。設(shè)置紅綠燈問題等價與對圖的頂點的染色問題。綜上所述：描述這類非數(shù)值計算問題通常用表、樹、圖等結(jié)構(gòu)。簡單地說：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學(xué)科。1.2基本概念和術(shù)語數(shù)據(jù)(data)指所有能輸入到計算機中并被計算機程序處理的符號的總稱。計算機輸入和處理的數(shù)據(jù)除數(shù)值外，還有字符串、表格、圖像甚至聲音等，它們都是數(shù)字編碼范疇。數(shù)據(jù)元素(dataelement)數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進(jìn)行考慮和處理。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成，也可以只由一個數(shù)據(jù)項組成。數(shù)據(jù)元素又被稱為元素、結(jié)點(node)或記錄(record)。數(shù)據(jù)項(dataitem)指數(shù)據(jù)的不可分割的、含有獨立意義的最小單位，數(shù)據(jù)項有時也稱字段(field)或域。上面的學(xué)生檔案表格是要存放到計算機中進(jìn)行處理的數(shù)據(jù)，表中每一行記錄了一個學(xué)生的檔案信息，在數(shù)據(jù)操作中作為一個整體考慮，對應(yīng)為一個數(shù)據(jù)元素，又稱為一個記錄。這個記錄中包含有學(xué)號、姓名等若干個數(shù)據(jù)項。操作的基本單位是記錄，如學(xué)生的插入或刪除一定是作用于一個學(xué)生的全部信息即一個記錄，而不可能是作用于其中的某個數(shù)據(jù)項。設(shè)想刪除操作只刪除某個學(xué)生的姓名或?qū)W號，將引起數(shù)據(jù)的不完整等嚴(yán)重后果。每個數(shù)據(jù)項(如學(xué)生的姓名或?qū)W號)均有獨立的含義，但在檔案管理這個實際問題中并無完整的意義，而組合在一個記錄中構(gòu)成學(xué)生的檔案，就具有了完整的實際意義。數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項實際上反映了數(shù)據(jù)組織的三個層次：數(shù)據(jù)可由若干個數(shù)據(jù)元素構(gòu)成，而數(shù)據(jù)元素又可以由一個或若干個數(shù)據(jù)項組成。數(shù)據(jù)邏輯結(jié)構(gòu)(datalogicalstructure)數(shù)據(jù)結(jié)構(gòu)主要是研究數(shù)據(jù)元素之間的關(guān)聯(lián)方式。數(shù)據(jù)元素之間存在的一種或多種特定的關(guān)系被稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。通常有四類基本結(jié)構(gòu)。見圖。數(shù)據(jù)物理結(jié)構(gòu)(dataphysicalstructure)數(shù)據(jù)在計算機中的存放方式稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機存儲器中的實現(xiàn)。數(shù)據(jù)元素在計算機中主要有兩種不同的存儲方法：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲的特點是在內(nèi)存中開辟一組連續(xù)的空間(高級語言中的數(shù)組)來存放數(shù)據(jù)，數(shù)據(jù)元素之間的邏輯關(guān)系通過元素在內(nèi)存中存放的相對位置來確定，又稱向量存儲。鏈?zhǔn)酱鎯Φ奶攸c是通過指針反映數(shù)據(jù)元素之間的邏輯關(guān)系，又稱動態(tài)存儲。數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的兩個密切相關(guān)的方面，同一邏輯結(jié)構(gòu)可以對應(yīng)不同的存儲結(jié)構(gòu)。算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于指定的存儲結(jié)構(gòu)。例如，10以內(nèi)的奇數(shù)1，3，5，7，9用順序存儲結(jié)構(gòu)的方式依次存放在以300為起地址的內(nèi)存向量中，并且兩個字長存放一個奇數(shù)，如圖1.5(a)所示。在順序存儲結(jié)構(gòu)中，如要讀取第三個奇數(shù)，它的地址可以通過起地址和要讀取奇數(shù)的位置序號計算得到。若本例中的奇數(shù)改用鏈?zhǔn)酱鎯Y(jié)構(gòu)存放，那么，第一個奇數(shù)存放在地址為300的內(nèi)存單元中，第二個奇數(shù)存放的地址和第一個奇數(shù)存放的地址無關(guān)，但第二個奇數(shù)所在的地址存放在第一個奇數(shù)相關(guān)的指針中，后面奇數(shù)的存放也按如此的規(guī)律。設(shè)兩個字長存放一個奇數(shù)，一個字長存放一個指針，如圖1.5(b)所示。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，如要讀取第三個奇數(shù)，只能從第一個奇數(shù)所在的地址開始，通過第一個奇數(shù)關(guān)聯(lián)的指針得到第二個奇數(shù)存放的地址105，再找到第三個奇數(shù)存放的地址400，才能讀出。從以上的例子和分析看，數(shù)據(jù)結(jié)構(gòu)主要就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)、相應(yīng)的存儲結(jié)構(gòu)以及完成數(shù)據(jù)操作的算法設(shè)計。數(shù)據(jù)類型(datatype)和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念，在用高級程序設(shè)計語言編寫的程序中，每個變量、常量或表達(dá)式都對應(yīng)一個確定的數(shù)據(jù)類型。數(shù)據(jù)類型可分為兩類：一類是非結(jié)構(gòu)的原子類型，如C語言中的基本類型(整型、實型、字符型等)、指針類型和空類型；另一類是結(jié)構(gòu)類型，它的成分可以由多個結(jié)構(gòu)類型組成，并可以分解。結(jié)構(gòu)類型的成分中可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。例如數(shù)組的值由若干分量組成，每個分量可以是整數(shù)，也可以是數(shù)組等結(jié)構(gòu)類型。本書在討論各種數(shù)據(jù)結(jié)構(gòu)時，針對其邏輯結(jié)構(gòu)和具體的存儲結(jié)構(gòu)給出對應(yīng)的數(shù)據(jù)類型，進(jìn)一步在確定的數(shù)據(jù)類型上實現(xiàn)各種操作。算法(algorithm)指解決特定問題的一種方法或一種描述。1968年，美國唐·歐·克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計算機程序設(shè)計技巧》第一卷《基本算法》是第一部較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及算法的著作。20世紀(jì)70年代初，大型程序出現(xiàn)，軟件業(yè)飛速發(fā)展，結(jié)構(gòu)化程序設(shè)計成為程序設(shè)計方法學(xué)的主要內(nèi)容，人們越來越重視數(shù)據(jù)結(jié)構(gòu)，認(rèn)為程序設(shè)計的實質(zhì)是確定數(shù)據(jù)的結(jié)構(gòu)，加上設(shè)計一個好的算法，也就是人們所說的“程序=數(shù)據(jù)結(jié)構(gòu)+算法”。1.3算法描述程序設(shè)計人員需要對程序處理的問題準(zhǔn)確理解，只有準(zhǔn)確理解問題后才能研究出解決問題的方法。算法是指解決問題的一種方法或過程描述。如果將問題看做函數(shù)，那么算法能把輸入轉(zhuǎn)化為輸出。解決一個問題可以有多種算法，但一個給定的算法只能解決一個特定的問題。例如對一組數(shù)據(jù)排序，可給出5種甚至更多種的排序算法。可以用多種算法求解問題的優(yōu)點在于：根據(jù)問題的具體限定條件，可以選用合適的算法求解。例如，有的排序算法適合于元素個數(shù)少的序列，有的算法適合于元素個數(shù)多的序列，有的算法則適合于定長數(shù)值型數(shù)據(jù)的排序。計算機程序就是用某種程序設(shè)計語言去具體地實現(xiàn)一個算法，或稱為代真。本書中主要介紹各種算法，并給出一部分算法對應(yīng)的C語言程序。當(dāng)然使用其他的程序設(shè)計語言也可以實現(xiàn)算法的代真。綜上所述，問題、算法、程序是三個互相關(guān)聯(lián)的不同概念。1.3.1算法的重要特性正確性它必須解決具體的問題，完成所期望的功能，給出正確的輸出。確定性算法執(zhí)行的每一步和下一步必須確定，不能有二義性。有限性一個算法必須由有限步組成。無限步組成的算法無法用計算機程序來實現(xiàn)。因此算法必須可以終止，不能進(jìn)入死循環(huán)。輸入一個算法有零個或多個輸入。輸出一個算法有一個或多個輸出。1.3.2數(shù)據(jù)結(jié)構(gòu)上的基本操作基本操作主要有以下幾種：查找尋找滿足特定條件的數(shù)據(jù)元素所在的位置。讀取讀出指定位置上數(shù)據(jù)元素的內(nèi)容。插入在指定位置上添加新的數(shù)據(jù)元素。刪除刪去指定位置上對應(yīng)的數(shù)據(jù)元素。更新修改某個數(shù)據(jù)元素的值。根據(jù)操作的結(jié)果可將操作分為兩種基本類型：加工型操作其操作改變了原邏輯結(jié)構(gòu)的“值”，如數(shù)據(jù)元素的個數(shù)；某數(shù)據(jù)元素的內(nèi)容等(一般不考慮改變邏輯結(jié)構(gòu)的類型)。上面基本操作中的后三種操作均為加工型操作。引用型操作其操作不改變原邏輯結(jié)構(gòu)的“值”，只是查找或讀取。1.3.3算法的描述方法算法的描述方法有很多，根據(jù)描述算法語言的不同，可將算法分為以下四種：框圖算法描述這種描述方法在算法研究的早期曾流行過。它的優(yōu)點是直觀、易懂，但用來描述比較復(fù)雜的算法就顯得不夠方便，也不夠清晰簡潔。非形式算法描述用中文語言，同時還使用一些程序設(shè)計語言中的語句來描述算法，這稱為非形式算法描述。類C語言算法描述類C語言算法又稱為偽語言算法。這種算法不能直接在計算機上運行，但專業(yè)設(shè)計人員經(jīng)常使用類C語言來描述算法，它容易編寫、閱讀和統(tǒng)一格式。C語言編寫的程序或函數(shù)這是可在計算機上運行并獲得結(jié)果的算法，使給定問題能在有限時間內(nèi)被求解，通常這種算法也稱程序。下面以求兩個整數(shù)m,n(m≥n)的最大公因子為例來看看不同的算法描述的方法。該問題的框圖描述：非形式算法描述：a.［求余數(shù)］以n除m，并令r為余數(shù)(0≤r<n)；b.［余數(shù)是零否］若r=0則結(jié)束算法，n就是最大公因子；c.［替換并返回a］若r≠0則m←n,n←r返回a。C語言函數(shù)描述：intmax_common_factor(intm,intn){intr;r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}我們主要介紹算法的思路和實現(xiàn)過程，且盡可能地將算法對應(yīng)的C語言函數(shù)或程序提供給讀者閱讀或上機運行，以便更好地理解算法。1.4算法分析1.4.1算法設(shè)計的要求設(shè)計一個“好”的算法應(yīng)考慮以下幾個方面：易讀性算法應(yīng)易于閱讀和理解，以便于調(diào)試、修改和擴充。健壯性正確的輸入能得到正確的輸出這是算法必須具有的特性之一。但當(dāng)遇到非法輸入時，算法應(yīng)能做出反應(yīng)或處理(如提示信息等)，而不會產(chǎn)生不需要的或不正確的結(jié)果。高效率即達(dá)到所需的時空性能。一個算法的時空性能是指該算法的時間性能(時間效率)和空間性能(空間效率)。解決同一問題如果有多個算法，執(zhí)行時間短的算法時間效率高，而存儲量和輔助空間量少的算法空間效率高。這兩者都和問題的規(guī)模有關(guān)。1.4.2算法時間效率的度量分析本節(jié)重點介紹算法的時間效率分析的基礎(chǔ)知識。算法運行的時間分析和程序運行的時間分析有區(qū)別。同一算法由不同的編程員所編出來的程序有優(yōu)劣之分，程序運行的時間也就有所不同；程序在不同的機器上運行的速度又和機器本身的速度有關(guān)。我們感興趣的是對解決問題的算法作時間上的度量分析，或?qū)鉀Q同一問題的兩種或兩種以上的算法運行的時間加以比較。我們稱這種度量分析為算法的時間復(fù)雜度分析。它可以估算出當(dāng)問題的規(guī)模變大時，算法運行時間增長的速度。這種分析實際上是一種數(shù)學(xué)化了的估算方法。估算算法運行時間的基本考慮是：確定問題的“規(guī)模”和確定算法執(zhí)行“基本操作”的次數(shù)。一個算法的“規(guī)?！焙汀盎静僮鳌币暰唧w算法而定?！耙?guī)?！币话闶侵篙斎肓康臄?shù)目，比如在排序問題中，問題的規(guī)?？梢允潜慌判虻脑財?shù)目?！盎静僮鳌币话闶侵冈谀硞€數(shù)據(jù)類型上的“標(biāo)準(zhǔn)操作”，比如兩個整數(shù)相加、比較兩個整數(shù)的大小等都可以視為是基本操作。例1.4查找一維n元整數(shù)數(shù)組中最大元素的算法。該算法從數(shù)組中下標(biāo)為0的元素開始，遍歷數(shù)組中的所有元素，在遍歷過程中，將當(dāng)前最大元素保存在變量currlarge中。下面是對應(yīng)的算法：intlargest(int*array,intn){intcurrlarge,i;currlarge=array［0］;for(i=1;i<n;i++)if(array［i］>currlarge)currlarge=array［i］;returncurrlarge;}其中，數(shù)組array中存放有n個整數(shù)，則問題的規(guī)模為n?；静僮魇恰氨容^”，即將數(shù)組中的一個整數(shù)和現(xiàn)有的最大整數(shù)作比較。影響算法運行時間的最主要的因素就是輸入規(guī)模n，我們經(jīng)常把運行算法所需要的時間T寫成輸入規(guī)模n的函數(shù)，記作T(n)。我們把largest函數(shù)中比較一個元素所需要的時間記作c1，“比較”這一基本操作是對數(shù)組中每一個元素都要做的工作。算法主要考慮這一基本操作所花的時間，忽略當(dāng)找到一個新的最大元素時要做的工作的時間，也不考慮函數(shù)初始化時所需要的時間，這樣就能得到運行該算法的一個合理的近似時間。因此，運行l(wèi)argest函數(shù)的總時間可近似地認(rèn)為是c1n。largest函數(shù)運行的時間代價可以用下面的等式來表示：T(n)=c1n。這個等式表明了順序檢索數(shù)組中最大元素的算法的時間是隨著n的增長而線性增長。例1.5將一個整數(shù)數(shù)組的第一個元素值賦給另一個變量。完成這一功能所需要的時間是固定的。無論這個數(shù)組有多大，復(fù)制一個元素值的時間總是確定的，記作c2。因此該算法運行時間代價的等式就是T(n)=c2。輸入規(guī)模即n的大小對運行時間不產(chǎn)生影響。這個等式稱為常數(shù)運行時間。例1.6再看下面一個算法段：sum=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++;顯然，隨著n的增大，其運行時間也會增大。本例的基本操作是sum的累加，假設(shè)這個基本操作所需要的時間為c3，忽略了初始化sum的時間和循環(huán)變量i和j累加的時間，基本操作總次數(shù)為n2，因此，該算法運行時間代價可用下面的等式來表示：T(n)=c3·n2。增長率的概念是非常重要的。它可以幫助我們比較算法的運行效率。圖1.6給出了五個常見的運行時間函數(shù)的曲線，每一條曲線反映出某種算法的時間代價，顯示了不同算法的增長率。標(biāo)記為100n的函數(shù)為一直線，增長率稱為線性增長率。這說明，當(dāng)n增大時，算法的運行時間線性增大。如果算法的運行時間函數(shù)中含有如n2這樣的高