C語(yǔ)言版數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)匯總

1、用計(jì)算機(jī)解決問(wèn)題具體問(wèn)題引言z 一 |12斗回 廠口 22” c般步驟:I _>編程、調(diào)試得到答案20A插入新元素的時(shí)候只需要改變指針?biāo)赶虻牡刂?。一般?lái)說(shuō)，用計(jì)算機(jī)解決一個(gè)具體問(wèn)題時(shí)，大致經(jīng)過(guò)以下幾個(gè)步驟：首先要從具體問(wèn)題抽象 出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，最后編出程序進(jìn)行測(cè)試調(diào)整知道的到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)就是分析問(wèn)題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之 間含有的關(guān)系，然后用數(shù)學(xué)的語(yǔ)言加以描述。三種經(jīng)典的數(shù)學(xué)模型圖書(shū)書(shū)目自動(dòng)檢索系統(tǒng)一一線性關(guān)系 博弈問(wèn)題一一樹(shù)城市道路問(wèn)題一一圖數(shù)據(jù)結(jié)構(gòu)（data structure簡(jiǎn)單的解釋?zhuān)合嗷ブg存在一種或多

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

3、22a23a24a2na31a32a33a34a3n數(shù)組地址計(jì)算問(wèn)題題目描述：已知 N*（N+1） / 2個(gè)數(shù)據(jù)，按行的順序存入數(shù)組 b1,b2,中。其中第一個(gè)下標(biāo)表示 行，第二個(gè)下標(biāo)表示列。若 aij （i>=j ,j=1,2，”n）存于bk中，問(wèn)：k,i,j之間的關(guān)系如何表示？給 定k值，寫(xiě)出能決定相應(yīng)i,j的算法。20當(dāng)需要在順序存儲(chǔ)的線性表中插入一個(gè)數(shù)據(jù)元素時(shí)，需要順序移動(dòng)后續(xù)的元素以“騰”出某 個(gè)合適的位置放置新元素。刪除元素呢？線性表（二） 鏈?zhǔn)酱鎯?chǔ)答案 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,'對(duì)應(yīng)的 i,j 為： ,i,' ,' ,j)棧特殊的線性表操作特點(diǎn)：后進(jìn)先出(Last In First Out)棧頂一一表尾棧底表頭空棧棧(考題分析)（1998）棧S初始狀態(tài)為空，現(xiàn)有 5個(gè)元素組成的序列1，2，3，4，5，對(duì)該序列在棧 S上一次進(jìn)行如下操作（從序列中的 1開(kāi)始，出棧后不再進(jìn)棧）：進(jìn)棧、進(jìn)棧、進(jìn)棧、出棧、進(jìn)棧、出棧、進(jìn)棧。問(wèn)出棧的元素序列是 D（A） 5,4,321（B） 2,1 （C） 2,3 （D） 3,4隊(duì)列先進(jìn)先出允許插入的一端稱為隊(duì)尾（rear），允許刪除的一端稱為隊(duì)頭（f

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

6、0010 0010100110 10000 000無(wú)向圖、帶權(quán)圖的鄰接矩陣排序冒泡排序選擇排序快速排序希爾排序一、插入排序(Insertion Sort)1. 基本思想：每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序;直到待排序數(shù)據(jù)元素全部插入完為止。2. 排序過(guò)程：【示例】：初始關(guān)鍵字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. 基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。2. 排序過(guò)程：【示例】：初始關(guān)鍵字 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最后排序結(jié)果13 2738 49 49 76 76 971015 Z96/、 /|10 15|36|25|30|70253070存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)3630/ /251510邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)小根堆示例三、冒泡排序(BubbleSort)1. 基本思想：兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反 序的數(shù)據(jù)元素為止。2. 排序過(guò)程：設(shè)想

9、被排序的數(shù)組 R : 1.N垂直豎立，將每個(gè)數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不 能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復(fù)進(jìn)行，直至最后任何兩個(gè)氣泡都是輕者在上，重者在下為止?！臼纠浚?9 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. 基本思想：在當(dāng)前無(wú)序區(qū)R1.H中任取一個(gè)數(shù)據(jù)元素作為比較的”基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序區(qū)：R1.-1和RI+1.H,且左邊的無(wú)序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無(wú)序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即 R1.I-1 < X.Key < RI+1.H(1 < I < H)，當(dāng) R1.I-1和 RI+1.H均非空時(shí)，分別對(duì)它 們進(jìn)行上述的劃分過(guò)程，直至所有無(wú)序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?. 排序過(guò)程：【示例

11、】：初始關(guān)鍵字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 :(一次劃分過(guò)程)初始關(guān)鍵字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最后的排序結(jié)果 13 27 38 49 49 65 76 97各趟排序之后的狀態(tài) 五、堆排序(Heap Sort)1. 基本思想：堆排序是一樹(shù)形選擇排序，在排序過(guò)程中，將R1.N看成是一顆完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu),利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素。2. 堆的定義：N個(gè)元素的序列K1,K2,K3,.,Kn.稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：Ki < K2i Ki < K2i+1(1 < I < N/2)大根堆示例六、幾種排序算法的比較和選擇1. 選取排

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

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

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

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

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

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

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

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

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