數據結構——C語言描數據結構——C語言描 主 C91的綜述；第2章至第7章分別介紹了線性表、棧、隊列、串、多維數組廣義表、樹和圖等幾種基本的數據結構；第8章和第9章分別介紹了查找圖書在版編目（CIP）數據結構：C語言描述/王國鈞主編.—北京：科學出（面向21世紀高等院校計算機系列規劃教材ISBN7-03-016077-Ⅰ.數… Ⅱ.王… Ⅲ.數據結構-高等學校-教材Ⅳ.TP311.12中國版本圖書館CIP數據核字（2005）第088632號責任編輯：呂建 趙衛江／責任校對：劉彥責任印制：呂春珉／封面設計：飛天創出版北京東黃城根北街16雙青印刷廠印科學出版社發行各地新華書店經*2005年8月第一 開本：787×10922006年8月第二次印 印張：16印數：3501－5 字數：376定價：22.00（如有印裝質量問題，我社負責調換<環偉銷售部電輯部電 本書共91章為概論2章至第4章分別介紹了線性表、棧、隊列和串幾種基本的數據結構，它們都屬于線性結構5章至第7章分別介紹了多維數組義表、樹和圖等非線性結構；第8章和第9章分別介紹了查找和排序，它們都是數據處和詳盡的注釋，自始至終使用C語言來描述算法和數據結構，各章的程序都在TurboC或VisualC++6.0中調試通過，以方便讀者在計算機上進行實踐，有助于理解算法的實另外，本書也可供從事計算機應用的工程技術人員參考，讀者只需掌握C語言編程為了方便教學，本書配有教學課件，可在科學出版社網站wcecm）載。由于編者水平有限，因此書中錯誤難免，殷切希望廣大讀者批評指正若需與編者交換意見，或索要部分習題參考解答，請發函至下列E-mail信箱 20055 第1 數據和數據元 數據對象和數據類 數據結 學習數據結構的重要 數據結構的應用舉 什么是算 算法的描述和設 算法分 第2 線性表的定 線性表的基本操 順序 順序表的基本操 一個完整的例子 單鏈表的基本概 單鏈表的基本操 一個完整的例子 循環鏈 雙向鏈 雙向循環鏈 靜態鏈 約瑟夫問 多項式加 電文加 數據結構——C 第3 棧的定義與基本操 順序棧的存儲結構和操作的實 鏈棧的存儲結構和操作的實 數制轉 括號匹配問 子程序的調 利用一個棧逆置一個帶頭結點的單鏈 隊列的定義與基本操 鏈隊列的存儲結構和操作的實 順序隊列的存儲結構和操作的實 打印楊輝三角 迷宮問題：尋找一條從迷宮入口到出口的最短路 *第4章 串的定 串的基本操 串的定長順序存 串的堆存儲結 串的塊鏈存儲結 基本的模式匹配算 模式匹配的改進算法——KMP算 第5 多維數組的定 數組的存儲結 目錄v目錄v特殊矩 稀疏矩 第6 樹的定 樹的一些基本慨 樹的基本操 二叉樹的定義和基本操 二叉樹的性 二叉樹的存儲結 二叉樹的遍 線索二叉 基于遍歷的應用與線索二叉樹的應 樹的存儲結 樹、森林和二叉樹之間的轉 樹和森林的遍 與哈夫曼樹相關的基本概 哈夫曼樹的應 哈夫曼編碼算法的實 第7 圖的定 圖的相關術 鄰接矩陣表示 鄰接表表示 深度優先搜索 數據結構——C廣度優先搜索 非連通圖的遍 生成樹的概 構造最小生成樹的普里姆（Prim）算 構造最小生成樹的克魯斯卡爾(Kruskal)算 從某個源點到其余各頂點的最短路 每一對頂點之間的最短路 第8 查找表和查 查找表的數據結構表 平均查找長度 順序查 二分查 分塊查 二叉排序 B- B-樹上的基本運 散列表的概 散列函數的構造方 處理沖突的方 散列表上的運 第9 關鍵字與排 排序的穩定 排序方法的分 排序算法性能評 不同存儲方式的排序過 目錄目錄直接插入排 希爾排 冒泡排 快速排 直接選擇排 堆排 多關鍵字的排 鏈式基數排 第1 本章要 什么是數據結 為什么要學習數據結 算法和算法分本章學習目 了解數據結構的基本概念，理解常用術 掌握數據元素間的4類結構關 掌握算法的定義及特性，掌握算法設計的要 初步掌握分析算法的時間復雜度和空間復雜度的方 數據結構——C語言描數據和數據元數據（da）是信息的載體，是對客觀事物的符號表示，它能夠被計算機識別、存數據的范疇。數據元素（dataelement）是數據的基本單位，通常在計算機程序中作為一個整體進數據對象和數據類數據對象（dataobjec）是性質相同的數據元素的集合，它是數據的一個子集。例如，整數數據對象是集合N={01，±2，±3，…；大寫字母字符數據對象是集合C=N1應該是上述集NN1={012±xntxint是依賴于所使用的計算機和語言的最大整數。數據類型（datatype）是計算機程序中的數據對象以及定義在這個數據對象集合上的一組操作的總稱。例如，C語言中的整數類型是區間-maxint，maxint]上的整數，在提供的，如C語言中的整型、實型、字符型等；結構數據類型是利用計算機語言提供的一種描述數據元素之間邏輯關系的機制由用戶自己定義而成的C語言中的數組類數據結數據結構（datastructure）是指數據對象以及該數據對象集合中的數據元素之間的數據元素的組織形式一般包含下列內容列4類（見圖1.1）。①集合：其中的數據元素之間除了“屬于同一個集合”的關系以外，別無其他②線性結構：其中的數據元素之間存在一對一的關系第1 圖 4類基本邏輯結構關③樹型結構：其中的數據元素之間存在一對多的關系④圖狀結構（或稱網狀結構）：其中的數據元素之間存在多對多的關系由于數據的邏輯結構是從邏輯關系上描述數據，它獨立于計算機，與數據的存儲C語言描述的算法來實現。例 學生成績表（見表1.1）是一個數據結構學生成績學姓高等普通平均陳小馬麗林春王澄######張吉表1.1（或記錄），由學號、姓名、（或字段（又稱直接前驅（又稱直接后繼 數據結構——C語言描“馬麗麗”所在結點的直接前驅結點是“陳小潔”結點，其后繼結點是“林春英”結點，上述結點之間的關系構成了這張學生成績表的邏輯結構。其次，表1.1的存儲結構是指用計算機語言如何表示各結點之間的這種關系，也就第三，在表1.1中，經常要查看一些學在不會產生混淆的前提下，可以將數據的邏輯結構簡稱為數據結構。本書的第2到第4章介紹的都是線性結構，第5章到第7章介紹的都是非線性結構數據的存儲結構可采用以下4種基本的存儲方法得到順序存儲方該方法主要應用于線性的數據結構，而非線性的數據結構可以通過某種線性化的法來實現順序存儲鏈接存儲方索引存儲方稱為索引項。索引項的一般形式是：（關鍵字，地址），所謂關鍵字（ky）是指能夠組結點的起始存儲位置。散列存儲方該方法的基本思想是根據結點的關鍵字直接計算出該結點的存儲地址上述4種基本的存儲方法，既可以單獨使用，也可以組合起來對數據結構進行存儲第1 需需要指出的是，不管怎樣定義數據結構，都應該將數據的邏輯結構、數據的存儲學習數據結構的重要數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之要想更有效地使用計算機，就必須學習數據結構的有關知識。約占用了90%以上的計算機時間。由于非數值計算問題所涉及的數據結構更為復雜，數Nrh數據結構的應用舉例 電話號碼的查詢問題66數據結構——C序，另外構造一張姓氏索引表，存儲結構如圖.2更為有效。在第8章中將進一步討論查找策略。圖 電話號碼查詢問題的索引存例 n個城市之間鋪設光纜的問題假設需要在nnn1n數學模型是如圖1.（圖n中選取n1n“求圖的最小生成樹”的問題，見圖1.3（b），將在第7圖 圖及其最小生成樹示第1 什么是算算法（algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列，其每一條指令表示一個或多個操作。此外，一個算法還具有下列5個特性有窮性。一個算法必須在執行有窮步之后結束，即算法必須在有限時間內完成確定性。算法中每一步必須有確切的含義，不會產生二義性。并且，在任何條件下，算法只有唯一的一條執行路徑，即對于相同的輸入只能得出相同的輸出。可行性。一個算法是可行的，即算法中的每一步都可以通過已經實現的基本運算執行有限次得以實現。輸入。一個算法有零個或多個輸入，它們是算法開始時對算法給出的初始量輸出。一個算法有一個或多個輸出，它們是與輸入有特定關系的量算法的描述和設算法是一個十分古老的研究課題，然而計算機的出現為這個課題注入了青春和活助，許多過去靠人工無法計算的復雜問題都有了解決的希望。一個算法可以采用自然語言、數學語言或者約定的符號語言（如偽碼、框圖等）88數據結構——C描述。為了方便讀者的閱讀和實踐，本書中的算法和數據結構均使用C語言來描述。C語言遵照NICroC或Vsual++6.0中調試通過。對書中采用的一些預定義常量，簡要說明如下#defineTRUE1#defineFALSE#defineOK#defineERROR其他有關C語言的知識，請參考專門介紹C語言的書籍在例1.2中，我們介紹了電話號碼的查詢問題的兩種算法，那么如何來評價這些算正確性——算法應當滿足具體問題的需求健壯性——當輸入數據非法時，算法也能適當地做出反應或進行處理，而不會產生莫明其妙的輸出結果或出錯信息，并中止程序的執行。可讀性——算法主要是為了方便人們的閱讀和交流，其次才是機器執行執行算法所耗費的時間執行算法所耗費的存儲空間，其中主要考慮輔助存儲空間算法分的就是程序所用算法在運行時所要花費的時間代價和程序中使用的數據結構所占有的空間代價。通常就稱為時間復雜度（時間代價）和空間復雜度（空間代價）。算法的時間復雜度分當需要解決的問題的規模（以某種單位計算）由1增至n時，解決問題的算法所耗費的時間也以某種單位由f(1)增至f(n)，這時就稱該算法的時間代價為f(n)。型的操作（或算法類型“原該語句重復執行的次數。1.4有下列三個程序段（2）for(i=1;i<=n;i++){x=x+1;（3）for(j=1;j<=n;for(k=1;k<=n;k++){x=x+1;第1 它們含基本操作“x加1”的語句的頻度分別為1、n和n2例1.5對n個記錄進行升序排序的問題，采用最簡單的選擇排序方法每次處理時，先從n個未排序的記錄中選出一個最小記錄，則第一次要經過n-1次比較，才能選出最小記錄；第二次再從剩下的n-1個記錄中經過n-2次比較，選出次小記錄……如此反復，直到只剩兩個記錄時，經過1次比較就可以確定它們的大小。整個(n-1)+(n-2)+…+1=n×(n-在同一個算法處理兩個規模相同的問題，所花費的時間和空間代價也不一定相同。（即對同樣規模的問題所花費的人們通常采用大O表示法來描述算法分析的結果。如果存在正的常數M和n0，當問題的規模n≥n0后，算法的時間量度T(n)≤Mf(n)那么就稱該算法的時間復雜度為O(f(n))。這種說法意味著：當n充分大時，該算法的時間復雜度不大于f(n)的一個常對于例1.4的程序段（1）來說，其時間復雜度為O(1)，程序段（2）的時間復雜度為O(n)，程序段（3）的時間復雜度為O(n2)；而對于例1.5的選擇排序方法來說，其時間復雜度為O(n2)。算法另外還可能呈現的時間復雜度有：O(log2n)和O(2n)等。通常c<log2n<n<nlog2n<n2<n3<10其中，c是與n無關的任意常數。上述函數排序與數學中對無窮大的分級完全一致，因為考慮的也是n值變化過程中的趨勢，參見圖1.4。圖 常見函數曲線變化速度的比較數據結構——C1.6要交換變量xy中的內容，其程序段為temp=x;x=y;由于以上3條語句的頻度均為1，說明該程序段的執行時間是一個與問題規模n無關的常數，因此，算法的時間復雜度為O(1)。1.7程序段如下for((i=1;i<=n;i++)for(j=1;j<=n;j++)for(k=1;k<=n;k++)在此程序段中，因為含基本操作“x加1”的語句“x++;”的頻度是n3，所以該序段的時間復雜度為O(n3)算法的空間復雜度分與算法的時間復雜度類似，可以定義算法的空間復雜度如下：如果存在正的常數M和n0，當問題的規模n≥n0后，算法的空間量度S(n)M·f(n)那么就稱該算法的空間復雜度為O(f(n))。數據的表示形式有關（見第8章1.8求例1.5中選擇排序方法的空間復雜度一個中間變量（temp）的存儲空間，這是與問題規模n無關的常數，因此，選擇排序方法的空間復雜度為O(1)。夠區分算法與程序的異同，了解怎樣的算法才是一個“好”的算法，并學會利用時間本章小結的內容：數據的邏輯結構，數據的存儲結構，數據的運算。討論了數據邏輯結構的4第1 基本結構關系，以及數據存儲的4種基本方法。讀者學習這些內容后，希望能對數據結算法和數據結構密切相關，不可分割。本章介紹了算法的定義和5個特性，討論了本書使用C語言來描述算法和數據結構，以方便讀者在計算機上進行實踐活動 一、填空數據的邏輯結構是數據元素之間的邏輯關系，通常有下列4類 數據的存儲結構是數據在計算機存儲器里的表示，主要有4種基本存儲方法 二、選擇一個算法必須在執行有窮步之后結束，這是算法的 ）正確 B.有窮C.確定 D.可行也就是說對于每步需要執行的動作必須嚴格、清楚地給出規定，這是算法的（ ）。正確 B.有窮C.確定 D.可行序列”，其中的每一步都是我們力所能及的一個動作，這是算法的（ ）。正確 B.有窮C.確定 D.可行三、簡答算法與程序有何異同什么是數據結構？試舉一個簡單的例子說明什么是數據的邏輯結構？什么是數據的存儲結構什么是算法？算法有哪些特性四、算法分析將下列復雜度由小到大重新排序：2n、n!、n2、10000、log2n、nlog2n用大O表示法描述下列復雜度 （2）6（3）3n4+n （4）nlog2n+n數據結構——C設n為正整數，請用大O表示法描述下列程序段的時間復雜度（1）i=1;k=0; （2）i=0;k=0; {k=k+10*i; （3）i=1;j=0; {if(i>j) else}（5）for((i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) {if(x>100){x-=10;y--;}x+=c;(c為常數) elsex++;}第2 線性本章要令線性表的基本概念令線性表的順序存儲令線性表的鏈式存令線性表兩種不同存儲結構的比令線性表的應本章學習目 掌握單鏈表上的基本運 掌握循環鏈表、雙向鏈表和靜態鏈表的概 學會利用線性表來解決問 數據結構——C線性結構是指結構中的數據元素之間存在一對一的關系。線性結構的基本特征是①有而且只有一個“第一元素”②有而且只有一個“最后元素”③除第一元素之外，其他元素都有唯一的直接前驅④除最后元素之外，其他元素都有唯一的直接后繼線性表是一種常用的簡單的數據結構，它屬于線性結構的范疇例2.1 26個大寫英文字母表（A,B,C,…,Z）就是一個線性表，表中的每一個字母例2.2 第1章例1.1中的學生成績表（表1.1），也是一個線性表，其中每個學生綜上所述，線性表可以描述如下線性表的定(a1,a2,…,ai-1,ai,ai+1,…,其中，數據元素的個數n稱為線性表的長度。當n＝0時稱為空表始結點（第一元素）a1，它沒有直接前驅，只有一個直接后繼a2；有而且只有一個終端結點（最后元素）an，它沒有直接后繼，只有一個直接前驅an-1；而除了a1和an外，其他的每一個結點ai（2≤i≤n-1）都有而且只有一個直接前驅ai-1和一個直接后繼ai+1。例2.3例2.1中介紹的26個大寫英文字母表（A,B,C,…,Z）的表長是26，在該表中，起始結點A沒有直接前驅，A的唯一直接后繼是B；終端結點Z沒有直接后繼，Z的唯一直接前驅是Y；而對于B,C,D,…,Y中的任意一個字母，都有一個唯一的直接前線性表的基本操設線性表L=(a1,a2,…,an)，則可以定義以下基本操作：1）InitList(L)：初始化操作，置L為空線性表。ClearList(L)：清除線性表的內容，將L置為空表ListLength(L)：求表長Ins(L，i，Item)：插入數據。把Item插入到表L的第i個位置，表長加1；如果i<1或i>ListLength(L)+1，則插入不成功。Del(L，i)：刪除數據。如果1≤i≤ListLength(L)，則刪除第i個數據，線性表的長度減1，返回TRUE；否則，刪除不成功，返回FALSE第2 線性 GetNode(L，i)：獲取表L中第i(1≤i≤ListLength)個結點的值。7）Loc(L，Item)：定位(按值查找)。如果表L中存在一個值為Item的結點，則返該結點的位置；若表L中存在多個值為Item的結點，則返回第一次找到的結點位置；若表L中不存在值為Item的結點，則返回0。8）GetNext(L，Item，p)：獲取后繼結點。首先找到Item所在的位置，然后把的后繼結點的值賦給p；若成功，則返回TRUE；否則，返回FALSE。9）GetPrior(L，Item，p)：獲取前驅結點。首先找到Item所在的位置，然后把Item順序C組來描述順序表的。例2.4一個順序存儲結構的線性表（順序表）的示例typedef{charname[20];charno[10];floatscore;STUDENT則s就是一個以STUDENT類型為數據元素的線性表假設線性表L的每個元素需占用m個存儲單元，并以所占的第一個單元的存儲地址作為數據元素的存儲位置，則線性表中第i+1個數據元素的存儲位置LOC(ai+1)和第i個數據元素的存儲位置LOC(ai)之間滿足如下關系： 線性表L的第i個元素的存儲位置和第一個元素的存儲位置的關系為LOC(ai)=LOC(a1)+(i-1) 其中LOC(a1)是線性表的第一個數據元素a1的存儲位置，通常稱為線性表的起始位順序表的特點是以元素在計算機內部存儲的物理位置相鄰來表示線性表中數據元2.2地址，就能計算出該數據元素的直接前驅和直接后繼的地址，計算公式見式（2.1）。 數據結構——C例2.5 在例2.4的線性表s中，如果設第一個數據元素的地址為b，則可以得出如圖2.1所示的存儲結構圖。注意：s中每一個數據元素所占的存儲單元為20+10+4=34圖 線性表s的順序存儲結構順序表的基本操現在利用C語言來描述一個順序表，由于表的長度通常是可變的，因此需要定義一typedefintdatatype; /*定義數據元素的類型，這里假設為int*/#definemaxsize1024 /*線性表的最大長度，這里假設為1024*/typedefstruct datatypeint /*表長其中，數據域data是存放線性表結點的一個數組，數組下標范圍為0～maxsize-1。length是線性表的長度。順序表的初始算法 構造一個空的順序表voidInitList(sequenlist*L/*構造一個空的順序表，只需要把表長度置為0{/*L是sequenlist類型的指針變量L /*0}存取第i個數據元素，只需要知道線性表的基地址就可以了。需要注意的是，在C語言第第2 線性 其中，m是數據元素所占的單元數目。清除線性表的內長置為0。算法 清除一個已經存在的線性表的內容voidClearList(sequenlist{L-}本算法時間復雜度為O(1)定位(按值查找則返回。算法 定位（按值查找）intLoc(sequenlistL，datatype{intj=L.length;/*取出線性表的長度*/ /*空表*/returnFALSE;{if(L.data[i]==Item)/*找到Item*/returni; /*返回找到的位置*/}printf(″找不到該return0;/*沒有找到0}本算法中，可能找到Item，這時平均比較次數為O(n/2)，其中，n是線性表的長度；也可能找不到Item，這時算法的比較次數為O(n)。因此，本算法的時間復雜度為O(n)插入數要在線性表中第i個位置插入一個數據元素Item，需要考慮以下因素i是否在1和L.length之間，如果是，則先將原來的第i個位置及以后的數據元素向后移動一個位置，然后把Item插入到第i個位置，再將線性表長度加1，返回TRUE；如果i不在1和L.length之間，則說明插入位置不合適，返回FALSE，如圖2.2所示。 數據結構——C插入…ai……插入…ai……圖 在順序表中插入結點的示意算法 插入數據intIns(sequenlist*L，inti，datatype{/*在順序表*L的第i個位置插入新結點*/intj;if(i<1||i>L-returnFALSE； /*位置不合適*/L->data[j]=L->data[j-1];/*結點后移L->data[i- /*1*/returnTRUE;}數為(n/2)，其中，n是線性表的長度。因此，本算法的時間復雜度為O(n)。注意:本算法最直觀的思考方法是從前向后移動數據，也就是用語句for(j=i;j<=L-L->data[j+1]=L-這個算法是不正確的，因為前面的值會把后面的值覆蓋刪除數刪除數據和插入數據很相似，都要求判斷i的值是否合適，如果位置合適，則把后面的數據向前移動，刪除成功，表的長度減1，返回TRUE，否則，返回FALSE。如所示圖 在順序表中刪除結點的示意第第2 線性算法 刪除數據intDel(sequenlist*L，int{/*刪除順序表*L中的第i個結點*/intj;if(i<1||i>L->length)/*位置不合適returnFALSE；L->data[j]=L->data[j+1];/*結點前移 /*表長減1*/returnTRUE；}一個完整的例子例6 編制C程序，利用順序存儲方式來實現下列功能：根據鍵盤輸入數據建立一個線性表并輸出該線性表然后根據屏幕菜單的選擇可以進行數據的插入或刪除并在插入或刪除數據后再輸出線性表最后在屏幕菜單中選擇Q或q的運行。程序如下：#include"stdio.h" #include"malloc.h"#definemaxsize1024typedefchardatatype;typedefstruct datatypedata[maxsize];intlast;/*在第i個元素前插入元素x（注意：元素從0始計數）*/intinsert(sequenlist*L,datatypex,inti) intif(L->last==maxsize- /*如果原線性表已滿{printf("overflow");return0;}elseif(i<0)||(i>L /*如果輸入的i值超出范圍{printf("error,pleaseinputtheright'i'");return0;}{for(j=L->last;j>=i;j--)/*從第i個元素起,