C語言版數據結構知識點匯總

1、用計算機解決問題具體問題引言z 一 |12斗回 廠口 22” c般步驟:I _>編程、調試得到答案20A插入新元素的時候只需要改變指針所指向的地址。一般來說，用計算機解決一個具體問題時，大致經過以下幾個步驟：首先要從具體問題抽象 出一個適當的數學模型，然后設計一個解此數學模型的算法，最后編出程序進行測試調整知道的到最終解答。尋求數學模型的實質就是分析問題，從中提取操作的對象，并找出這些操作對象之 間含有的關系，然后用數學的語言加以描述。三種經典的數學模型圖書書目自動檢索系統(tǒng)一一線性關系 博弈問題一一樹城市道路問題一一圖數據結構（data structure簡單的解釋：相互之間存在一種或多

2、種特定關系的數據元素的集合。 數據間的聯(lián)系有邏輯關系、存儲聯(lián)系，通常的數據結構指的是邏輯結構。前面提到的三種經典的數學模型體現(xiàn)了數據結構的基本結構，數據結構通常有如下四種關 系：（1 ）集合結構 （2）線性結構 （3 ）樹形結構 （4 ）圖狀結構 線性表（一）N個數據元素的有限序列 存儲結構：順序存儲結構、鏈式存儲結構(1)(2)(3)(4)(5)(6)(7)(8)12131522343843二維數組與線性表如果某一線性表，它的每一個數據元素分別是一個線性表，這樣的二維表在數據實現(xiàn)上通常使用 二維數組。二維數組的一個形象比喻多個縱隊形成的方塊 m * nalla12a13a14 換Ila21a

3、22a23a24a2na31a32a33a34a3n數組地址計算問題題目描述：已知 N*（N+1） / 2個數據，按行的順序存入數組 b1,b2,中。其中第一個下標表示 行，第二個下標表示列。若 aij （i>=j ,j=1,2，”n）存于bk中，問：k,i,j之間的關系如何表示？給 定k值，寫出能決定相應i,j的算法。20當需要在順序存儲的線性表中插入一個數據元素時，需要順序移動后續(xù)的元素以“騰”出某 個合適的位置放置新元素。刪除元素呢？線性表（二） 鏈式存儲答案 K二i*(i-1)/2+j Read(k);For i:=1 to k dofor j:=1 to i doif k=(t

4、runc(l*(l-1)/2)+j) then writeln(k,'對應的 i,j 為： ,i,' ,' ,j)棧特殊的線性表操作特點：后進先出(Last In First Out)棧頂一一表尾棧底表頭空棧棧(考題分析)（1998）棧S初始狀態(tài)為空，現(xiàn)有 5個元素組成的序列1，2，3，4，5，對該序列在棧 S上一次進行如下操作（從序列中的 1開始，出棧后不再進棧）：進棧、進棧、進棧、出棧、進棧、出棧、進棧。問出棧的元素序列是 D（A） 5,4,321（B） 2,1 （C） 2,3 （D） 3,4隊列先進先出允許插入的一端稱為隊尾（rear），允許刪除的一端稱為隊頭（f

5、ront）。出隊列入隊列攜al a2 a3 a4 an循環(huán)隊列頭指針指向隊列中隊頭元素的前一個位置，尾指針指示隊尾元素在隊列中的當前位置。樹根、葉子、子樹結點的度：結點擁有的子樹數二叉樹二叉樹層次(R-F+N) mod N特點：每個結點至多只有二棵子樹，并且二叉樹 的子樹有左右之分。第i層至多有 2i-1個結點（i>=1）深度為K的二叉樹最多有2k-1個結點（K>=1）滿二艮樹完全二文樹先（根）序遍歷ABDFGCEH中（根）序遍歷BFDGACHE后（根）序遍歷FGDBHECA例題分析與后序遍歷:DGEBHIFCA ，畫出此二叉樹。圖有向圖1 2 3 4 512345有向圖、0 11

6、0010 0010100110 10000 000無向圖、帶權圖的鄰接矩陣排序冒泡排序選擇排序快速排序希爾排序一、插入排序(Insertion Sort)1. 基本思想：每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序;直到待排序數據元素全部插入完為止。2. 排序過程：【示例】：初始關鍵字49 38 65 97 76 13 27 49J=2(38) 38 49 65 97 76 13 27 49J=3(65) 38 49 65 97 76 13 27 49J=4(97) 38 49 65 97 76 13 27 49J=5(76) 38 49 65 76 97

7、 13 27 49J=6(13) 13 38 49 65 76 97 27 49J=7(27) 13 27 38 49 65 76 97 49J=8(49) 13 27 38 49 49 65 76 97二、選擇排序1. 基本思想：每一趟從待排序的數據元素中選出最小(或最大)的一個元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。2. 排序過程：【示例】：初始關鍵字 49 38 65 97 76 13 27 49第一趟排序后13 :38 65 97 76 49 27 49第二趟排序后13 27: 65 97 76 49 38 49第三趟排序后13 2738 97 76 49 6

8、5 49第四趟排序后13 2738 49 49 97 65 76第五趟排序后13 2738 49 49 97 97 76第六趟排序后13 2738 49 49 76 76 97第七趟排序后13 2738 49 49 76 76 97最后排序結果13 2738 49 49 76 76 971015 Z96/、 /|10 15|36|25|30|70253070存儲結構邏輯結構3630/ /251510邏輯結構存儲結構小根堆示例三、冒泡排序(BubbleSort)1. 基本思想：兩兩比較待排序數據元素的大小，發(fā)現(xiàn)兩個數據元素的次序相反時即進行交換，直到沒有反 序的數據元素為止。2. 排序過程：設想

9、被排序的數組 R : 1.N垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不 能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最后任何兩個氣泡都是輕者在上，重者在下為止。【示例】：49 13 13 13 13 13 13 1338 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49

10、49 76 97 97 97 97四、快速排序(Quick Sort)1. 基本思想：在當前無序區(qū)R1.H中任取一個數據元素作為比較的”基準"(不妨記為X)，用此基準將當前無序區(qū)劃分為左右兩個較小的無序區(qū)：R1.-1和RI+1.H,且左邊的無序子區(qū)中數據元素均小于等于基準元素，右邊的無序子區(qū)中數據元素均大于等于基準元素，而基準X則位于最終排序的位置上，即 R1.I-1 < X.Key < RI+1.H(1 < I < H)，當 R1.I-1和 RI+1.H均非空時，分別對它 們進行上述的劃分過程，直至所有無序子區(qū)中的數據元素均已排序為止。2. 排序過程：【示例

11、】：初始關鍵字49 38 65 97 76 13 27 49 :第一次交換后27 38 65 97 76 13 49 49 :第二次交換后27 38 49 97 76 13 65 49 :J向左掃描，位置不變，第三次交換后27 38 13 97 76 49 65 49 :I向右掃描，位置不變，第四次交換后27 38 13 49 76 97 65 49:J 向左掃描27 38 13 49 76 97 65 49 :(一次劃分過程)初始關鍵字49 38 65 97 76 13 27 49 :一趟排序之后27 38 13 : 49 : 76 97 65 49 :二趟排序之后13 27 :38 49

12、: 49 65: 76 :97三趟排序之后 13 27 38 49 49: 65 76 97最后的排序結果 13 27 38 49 49 65 76 97各趟排序之后的狀態(tài) 五、堆排序(Heap Sort)1. 基本思想：堆排序是一樹形選擇排序，在排序過程中，將R1.N看成是一顆完全二叉樹的順序存儲結構,利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。2. 堆的定義：N個元素的序列K1,K2,K3,.,Kn.稱為堆，當且僅當該序列滿足特性：Ki < K2i Ki < K2i+1(1 < I < N/2)大根堆示例六、幾種排序算法的比較和選擇1. 選取排

13、序方法需要考慮的因素：(1) 待排序的元素數目n；(2) 元素本身信息量的大?。?3) 關鍵字的結構及其分布情況；(4) 語言工具的條件，輔助空間的大小等。2. 小結：(1) 若n較小(n <= 50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記 錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。(2) 若文件的初始狀態(tài)已按關鍵字基本有序，則選用直接插入或冒泡排序為宜。(3) 若n較大，則應采用時間復雜度為0(nlog2n)的排序方法：快速排序、堆排序或歸并排序?？焖倥判蚴悄壳盎诒容^的內部排序法中被認為是最好的方法。 在基于比較排序方法中，

14、每次比較兩個關鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉移，因此 可以用一棵二叉樹來描述比較判定過程，由此可以證明：當文件的n個關鍵字隨機分布時，任何借助于”比較”的排序算法，至少需要0(nlog2n)的時間。(5) 當記錄本身信息量較大時，為避免耗費大量時間移動記錄，可以用鏈表作為存儲結構。 線性結構：串、棧、隊列串一、串的概念串又稱為字符串，是由0個或多個字符組成的有限序列。長度為 0的串稱為空串，它不包含任何字符。串用和'括起來。二、串的運算1串的定義：一般用一維數組實現(xiàn)串的運算，由此串的定義也用數組的形式來實現(xiàn)：typestri ngtype=packed array1.80 of

15、char;vars:stri ngtype;另外，還有一種更簡便的定義方法，利用turbo pascaI中的string類型：vars:stri ng;但是string類型有一個限制：運用string類型定義的數據長度只能是1 255,也就是說不能超過255個字符。2串的標準函數在turbo pascal中有如下標準函數可實現(xiàn)串的運算：copy(s,x,y):獲取從s的第x個位置開始的y個字符concat(s1,s2,.,sn)：相等于 s1+s2+.+sndelete(s,x,y):將s中從第x個位置開始的y個字符刪去insert(s1,s,x):將si插到s中的第x個位置length(s)

16、:獲取s的長度3. 串的基本運算(1) 賦值(2) 連接求串長(4) 取子串(5) 求子串序號(6) 插入(7) 刪除(8) 置換三、串的匹配算法示例：四、練習題：1. 讀入一英文句子，單詞之間用空格或逗號隔開，統(tǒng)計其中單詞個數，并輸出各個字母出現(xiàn) 的頻率。(句子末尾不一定用"."結束)(word1)2. 一個句子，只含英文字母，單詞間用空格或逗號作為分隔符。統(tǒng)計句子中的單詞數，如果含有其他的字符，則只要求輸出錯誤信息及錯誤類型。(word2)含有大寫字母錯誤類型error 1數字(0-9)錯誤類型error 2其他非法字符錯誤類型error 3如輸入：It is 12!輸

17、出：error 1 2 3輸入：i am ,a stude nt輸出：43. 編碼解碼：從鍵盤輸入一個英文句子，設計一個編碼、解碼程序。(stri ng)編碼過程：先鍵入一個正整數N(1<=N<=26)。這個N決定了轉換關系。 例如當N=1，輸入的句子為ABCXYZ 時，則其轉換碼為 ABCXYZ 不變。當N=2時，其轉換碼為 BCDYZA，其它 的非字母字符不變。為使編碼較于破譯，將轉換碼的信息自左而右兩兩交換，若最后僅剩單個字 符則不換。然后，將一開始表示轉換關系的N根據ascii表序號化成大寫字母放在最前面。女口： abcABCxyzXYZ-/,1. n=3 cdeCDEza

18、bZAB-/,1. 根據N的值轉換 dcCeEDazZbBA/-1,. 兩兩交換 CdcCeEDazZbBA/-1,. 最后編碼解碼過程為編碼的逆過程。棧1棧的特點：棧是一種線性表，對于它所有的插入和刪除都限制在表的同一端進行，這一端叫做棧的“頂”，另一端則叫做棧的“底”，其操作特點是“后進先出”。2.棧的一般定義：type stack=recorddata:array1.m of datatype;t:0.men d;vars:stack;3. 棧的基本運算：(1) 棧的插入push(s,x):往棧st中推入一個值為x的項目；若 t=m 貝U print('overflow'

19、)否則 t:=t+1;datat:=x;棧的彈出pop(s):從棧st中彈出一個項目；若 t=0 則 print('underflow')否則 t:=t-1;(3) 讀棧頂元素top(s,x):把棧頂元素的值讀到變量x中，棧保持不變；若 t=0 則 print('error')否則 x:=datat;判棧是否為空sempty(s):這是一個布爾函數，當棧st中沒有元素(即t=0)時，稱它為空棧, 函數取真值，否則值為假。若 t=0 則 sempty:=true否貝U sempty:=false;4. 棧的應用之一一一計算表達式的值(1) 表達式的三種形式：中綴表

20、達式：運算符放在兩個運算對象中間，如：(2+1)*3 ;后綴表達式：不包含括號，運算符放在兩個運算對象的后面，所有的計算按運算符出現(xiàn)的順序，嚴格從左向右進行(不再考慮運算符的優(yōu)先規(guī)則，如：21+ 3 * ;前綴表達式：同后綴表達式一樣，不包含括號，運算符放在兩個運算對象的前面，如：* + 2 1 3。(2) 表達式的計算：由于后綴表達式中沒有括號，不需判別優(yōu)先級，計算嚴格從左向右進行，故計算一個后綴表 達式要比計算機一個中綴表達式簡單得多。將中綴表達式轉換為后綴表達式的算法思想：當讀到數字直接送至輸出隊列中當讀到運算符t時，a. 將棧中所有優(yōu)先級高于或等于t的運算符彈出，送到輸出隊列中；b.

21、t進棧讀到左括號時總是將它壓入棧中讀到右括號時，將靠近棧頂的第一個左括號上面的運算符全部依次彈出，送至輸出隊列后,再丟棄左括號。運用后綴表達式進行計算的具體做法：建立一個棧 S從左到右讀后綴表達式，讀到數字就將它轉換為數值壓入棧S中，讀到運算符則從棧中依次彈出兩個數分別到Y和X，然后以“ X運算符Y”的形式計算機出結果，再壓加棧S中如果后綴表達式未讀完，就重復上面過程，最后輸出棧頂的數值則為結束5. 棧的應用之二一一遞歸算法的非遞歸實現(xiàn)示例：隊列1. 隊列的特點：隊列也是一種線性表，對于它所有的插入都在隊列的一端進行，所有的刪除都在另一端進行，進行刪除的一端叫隊列的“頭”，進行插入的一端叫隊列的“尾”，其操作特點是“先進先出”。2. 隊列的一般定義：typequeue=recorddata:array1.m of datatype;head,tail:1.men d;varq:queue;3. 隊列的基本操作：(1) 隊列的插入enq(q,x):在隊列q中插入一個值為x的元素，也稱為進隊；qtail:=x;若 tail=m 則 tail:=1否則 tail:=tail+1;若 tail=head 貝U print('