清華大學(xué)嚴(yán)蔚敏新版數(shù)據(jù)結(jié)構(gòu)考研要點(diǎn)(精華新版)

1、1數(shù)據(jù)(Data):是客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并 被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的基本單位，在程序中通常作為一個(gè)整體來(lái)進(jìn)行考慮和 處理。一個(gè)數(shù)據(jù)元素可由若干個(gè) 數(shù)據(jù)項(xiàng)(Data Item)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù) 據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對(duì)象(Data Object):是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如字符集合 C= A , ' B'。，' C,數(shù)據(jù)結(jié)構(gòu)(Data Structure):是指相互之間具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集

2、合。 元素 之間的相互聯(lián)系(關(guān)系)稱為邏輯結(jié)構(gòu)。 數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型，如圖1-3所示。 集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外，沒(méi)有其它關(guān)系。 線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。 樹(shù)型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。2、順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的；鏈?zhǔn)浇Y(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒(méi)有要求。數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯 結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu)。在C語(yǔ)言中，用一維數(shù)組表示順序存儲(chǔ)結(jié)構(gòu)；用結(jié)構(gòu)體類型表示鏈?zhǔn)酱?/p>

3、儲(chǔ)結(jié)構(gòu)。3、C語(yǔ)言中用帶指針的結(jié)構(gòu)體類型來(lái)描述typedef struct Lnode ElemType data; /*數(shù)據(jù)域，保存結(jié)點(diǎn)的值*/struct Lnode *next;/* 指針域 */LNode;/*結(jié)點(diǎn)的類型 */4、 循環(huán)隊(duì)列為空：front=rear 。循環(huán)隊(duì)列滿：(rear+1)%MAX_QUEUE_SIZE =front5、 性質(zhì)1在非空二叉樹(shù)中，第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i= 1)。性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k仝1)。性質(zhì)3:對(duì)任何一棵二叉樹(shù)，若其葉子結(jié)點(diǎn)數(shù)為n°,度為2的結(jié)點(diǎn)數(shù)為 匹，則n°=n2+1。一棵深度為 k且

4、有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)(Full Binary Tree)完全二叉樹(shù)的特點(diǎn)：若完全二叉樹(shù)的深度為 k ,則所有的葉子結(jié)點(diǎn)都出現(xiàn)在第k層或k-1層。對(duì)于任一結(jié)點(diǎn)，如果其右子樹(shù)的最大層次為I，則其左子樹(shù)的最大層次為I或l+1。性質(zhì)5:若對(duì)一棵有 n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（深度為 哋2n+1）的結(jié)點(diǎn)按層（從第_1層到 第趙2n +1層）序自左至右進(jìn)行編號(hào)，則對(duì)于編號(hào)為i （1 w iw n）的結(jié) 占：八、 若i=1:則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親結(jié)點(diǎn)；否則，若i>1，則其雙親結(jié)點(diǎn)編號(hào)是|li/2 。如果2i>n：則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左孩子；否則，其左孩子結(jié)點(diǎn)編號(hào)是2i。 如果2

5、i+1>n:則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子結(jié)點(diǎn)編號(hào)是2i+1。圖6-21森林轉(zhuǎn)換成二艾樹(shù)的過(guò)程圖22二叉樹(shù)還原成森林的過(guò)程6、 線索二叉樹(shù)： 設(shè)一棵二叉樹(shù)有 n個(gè)結(jié)點(diǎn)，則有n-1條邊（指針連線），而n個(gè)結(jié)點(diǎn)共有2n個(gè)指針域（Lchild和Rchild），顯然有n+1個(gè)空閑指針域未用。則可以利 用這些空閑的指針域來(lái)存放結(jié)點(diǎn)的直接前驅(qū)和直接后繼信息。7、 Huffman樹(shù)：具有n個(gè)葉子結(jié)點(diǎn)（每個(gè)結(jié)點(diǎn)的權(quán)值為 wi）的二叉樹(shù)不止一棵，但在所有的這些二叉樹(shù)中，必定存在一棵 WPL值最小的樹(shù)，稱這棵樹(shù)為Huffman樹(shù)（或 稱最優(yōu)樹(shù)）。第妙一第一出圖&詰nulfinsinM的構(gòu)造過(guò)程第A

6、歩,用e表示邊的數(shù)目,則 e 二0, n(n-1)/2。&完全無(wú)向圖：對(duì)于無(wú)向圖，若圖中頂點(diǎn)數(shù)為n 具有n(n-1)/2條邊的無(wú)向圖稱為完全無(wú)向圖。完全有向圖：對(duì)于有向圖，若圖中頂點(diǎn)數(shù)為 n，用e表示弧的數(shù)目，則 e 0，n(n-1)具有n(n-1)條邊的有向圖稱為完全有向圖。生成樹(shù)、生成森林：一個(gè)連通圖(無(wú)向圖)的生成樹(shù)是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)和只有足以構(gòu)成一棵樹(shù)的n-1條邊，稱為圖的生成樹(shù)關(guān)于無(wú)向圖的生成樹(shù)的幾個(gè)結(jié)論:1) 一棵有n個(gè)頂點(diǎn)的生成樹(shù)有且僅有n-1條邊；2) 如果一個(gè)圖有n個(gè)頂點(diǎn)和小于n-1條邊，則是非連通圖；3) 如果多于n-1條邊，則一定有環(huán)；4)

7、 有n-1條邊的圖不- -定是 生成樹(shù)。9、最小生成樹(shù)(Minimum Spanning Tree):帶權(quán)連通圖中代價(jià)最小的生成樹(shù)稱為最小生成樹(shù)。 最小生成樹(shù)在實(shí)際中具有重要用途，如設(shè)計(jì)通信網(wǎng)。設(shè)圖的頂點(diǎn)表示城市，邊表示兩個(gè)城市之間的通信線路，邊的權(quán)值表示建造通信線路的費(fèi)用。n個(gè)城市之間最多可以建n (n-1)/2條線路，如何選擇其中的n-1條，使總的建造費(fèi)用最低?S7-ZI載”il吩諄法從心出發(fā)構(gòu)造最小生成栩的過(guò)程4rW>37-22枝制訃心譏算法構(gòu)造垠小生成樹(shù)的過(guò)程w 有向圖 (|»輸出Vi后 輸出"后(<0輸岀口后關(guān)鍵。S7-24 -木丄0蹈圖阿帶權(quán)有向圖及

8、其鄰接麟(e)輸出巧后圖7J3有向圖的拓?fù)渑判蜻^(guò)程10、工程完成最短時(shí)間：從起點(diǎn)到終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度(路徑上各活動(dòng)持續(xù)時(shí)間之和)。長(zhǎng)度最長(zhǎng)的路徑稱為關(guān)鍵路徑，關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)是影響整個(gè)工程的11、查找方法比較順序查找折半查找ASL最大最小表結(jié)構(gòu)有序表、無(wú)序表有序表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性鏈表順序存儲(chǔ)結(jié)構(gòu)分塊查找兩者之間分塊有序表 順序存儲(chǔ)結(jié)構(gòu)線性鏈表12、在隨機(jī)情況下，二叉排序樹(shù)的平均查找長(zhǎng)度ASL和log (n)(樹(shù)的深度)是等數(shù)量級(jí)的。二叉排序樹(shù)(Binary Sort Tree或Binary Search Tree)的定義為：二叉排序樹(shù)或者是空樹(shù)，或者是滿足下列性質(zhì)

9、的二叉樹(shù)。(1) :若左子樹(shù)不為空，則左子樹(shù)上所有結(jié)點(diǎn)的值(關(guān)鍵字)都小于根結(jié)點(diǎn)的值；(2) :若右子樹(shù)不為空，則右子樹(shù)上所有結(jié)點(diǎn)的值(關(guān)鍵字)都大于根結(jié)點(diǎn)的值；(3) :左、右子樹(shù)都分別是二叉排序樹(shù)。結(jié)論：若按中序遍歷一棵二叉排序樹(shù)，所得到的結(jié)點(diǎn)序列是一個(gè)遞增序列。13、平衡二叉樹(shù)或者是空樹(shù)，或者是滿足下列性質(zhì)的二叉樹(shù)。：左子樹(shù)和右子樹(shù)深度之差的 絕對(duì)值不大于1;：左子樹(shù)和右子樹(shù)也都是平衡二叉樹(shù)。平衡因子 但alance Factor)：二叉樹(shù)上結(jié)點(diǎn)的左子樹(shù)的深度減去其右子樹(shù)深度稱為該結(jié) 點(diǎn)的平衡因子。平衡二叉排序樹(shù)上進(jìn)行查找的平均查找長(zhǎng)度和噸2n是一個(gè)數(shù)量級(jí)的，平均時(shí)間復(fù)雜度為O(log

10、2n)。四種平衡化旋轉(zhuǎn)，其正確性容易由遍歷所得中序序列不變”來(lái)證明。并且，無(wú)論是哪種情況，平衡化旋轉(zhuǎn)處理完成后，形成的新子樹(shù)仍然是平衡二叉排序樹(shù)，且其深度和插入前以a為根結(jié)點(diǎn)的平衡二叉排序樹(shù)的深度相同。所以，在平衡二叉排序樹(shù)上因插入結(jié)點(diǎn)而失衡， 僅需對(duì)失衡子樹(shù)做平衡化旋轉(zhuǎn)處理。14、一棵m階BJ樹(shù)，或者是空樹(shù)，或者是滿足以下性質(zhì)的m叉樹(shù)： 根結(jié)點(diǎn)或者是葉子，或者至少有兩棵子樹(shù)，至多有m棵子樹(shù)； 除根結(jié)點(diǎn)外，所有非終端結(jié)點(diǎn)至少有m/2棵子樹(shù)，至多有 m棵子樹(shù)； 所有葉子結(jié)點(diǎn)都在樹(shù)的同一層上；每個(gè)結(jié)點(diǎn)應(yīng)包含如下信息：(n, Ao, K1 , A1 , K2, A2,，Kn, An)其中氏(1 w

11、i 是關(guān)鍵字，且 K<K+i (1 w i琲)n Ai(i=0, 1,，n)為指向孩子結(jié)點(diǎn)的指針，且Ai-1所指向的子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字都小于K , Ai所指向的子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字都大于Ki ; n是結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，且 |lm/2 -1w n<m1, n+1為子樹(shù)的棵數(shù)。根據(jù)m階B_對(duì)的定義，第一層上至少有1個(gè)結(jié)點(diǎn)，第二層上至少有2個(gè)結(jié)點(diǎn)；除根結(jié)點(diǎn)外, 所有非終端結(jié)點(diǎn)至少有 m/2棵子樹(shù)，第h層上至少有m/2 h-2個(gè)結(jié)點(diǎn)。在這些結(jié)點(diǎn)中： 根結(jié)點(diǎn)至少包含1個(gè)關(guān)鍵字，其它結(jié)點(diǎn)至少包含 m/2 -1個(gè)關(guān)鍵字，設(shè)s= m/2，則總的關(guān)鍵字?jǐn)?shù)目n滿足:因此有：hW 1+ log

12、s(n+1)/2)=1 + log m/2 (n+1)/2)即在含有n個(gè)關(guān)鍵字的BJ樹(shù)上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到待查找記錄關(guān)鍵字的結(jié)點(diǎn) 的路徑上所涉及的結(jié)點(diǎn)數(shù)不超過(guò)1+ g m/2 (n+1)/2)。15、m階B+樹(shù)。它與B_樹(shù)的主要不同是葉子結(jié)點(diǎn)中存儲(chǔ)記錄。在 B+樹(shù)中，所有的非葉子 結(jié)點(diǎn)可以看成是索引，而其中的關(guān)鍵字是作為 分界關(guān)鍵字”用來(lái)界定某一關(guān)鍵字的記錄所 在的子樹(shù)。一棵 m階B+樹(shù)與m階B_樹(shù)的主要差異是： 若一個(gè)結(jié)點(diǎn)有n棵子樹(shù)，則必含有 n個(gè)關(guān)鍵字；所有葉子結(jié)點(diǎn)中包含了全部記錄的關(guān)鍵字信息以及這些關(guān)鍵字記錄的指針，而且葉子結(jié)點(diǎn)按關(guān)鍵字的大小從小到大順序鏈接； 所有的非葉子結(jié)點(diǎn)可以看

13、成是索引的部分，結(jié)點(diǎn)中只含有其子樹(shù)的根結(jié)點(diǎn)中的最大(或最小)關(guān)鍵字。16、哈希函數(shù)：在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系叫哈希函數(shù)。哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象?？蓪懗桑篴ddr(aj)=H(k),其中i是表中一個(gè)元素，addr(ai)是ai的地址，ki是aj的關(guān)鍵字。哈希表：應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫哈希表。哈希查找(又叫散列查找)：禾U用哈希函數(shù)進(jìn)行查找的過(guò)程叫哈希查找。例1 :設(shè)散列表長(zhǎng)為7,記錄關(guān)鍵字組為:15, 14, 28, 26, 56, 23,散列函數(shù)：H(key)=key

14、MOD7,沖突處理采用線性探測(cè)法。解：H(15)=15 MOD 7=1H(14)=14 MOD 7=0H(28)=28MOD 7=0沖突 H1(28)=1 又沖突出(28)=2H(26)=26 MOD 7=5H(56)=56MOD 7=0沖突H1(56)=1又沖突H2(56)=2又沖突H3(56)=3H(23)=23MOD 7=2沖突H1 (23)=3又沖突H3(23)=4各種散列函數(shù)所構(gòu)造的散列表的ASL如下:卷中填入的記錄數(shù) 哈希表氏度(1)線性探測(cè)法的平均査找長(zhǎng)度是： 滋駭功a* x(l+ lAx) Sm失妒卡&1+(1_；尸)二次探測(cè)-偽隨機(jī)探測(cè).再哈希法的平均査找長(zhǎng)度 是：S

15、nl成功九-尋 X In (1-cc)雲(yún)失妒：3)用鏈地址法解決沖突的平均査找長(zhǎng)度是二Sm成功G十號(hào)呂皿失敗爼<x+e17、排序的穩(wěn)定性若記錄序列中有兩個(gè)或兩個(gè)以上關(guān)鍵字相等的記錄：Ki =Kj(i多j,j=1,2,，且在排序前R先于Rj(i<j)，排序后的記錄序列仍然是Ri先于Rj,稱排序方法是穩(wěn)定的，否則是不穩(wěn)定的。排序的分類待排序的記錄數(shù)量不同，排序過(guò)程中涉及的存儲(chǔ)器的不同，有不同的排序分類。 待排序的記錄數(shù)不太多：所有的記錄都能存放在內(nèi)存中進(jìn)行排序，稱為內(nèi)部排序； 待排序的記錄數(shù)太多：所有的記錄不可能存放在內(nèi)存中，排序過(guò)程中必須在內(nèi)、外存之間進(jìn)行數(shù)據(jù)交換，這樣的排序稱為外部

16、排序。18、 插入排序采用的是以“玩橋牌者”的方法為基礎(chǔ)的。即在考察記錄Ri之前，設(shè)以前的所有記錄Ri,甩，.,R已排好序，然后將 Ri插入到已排好序的諸記錄的適當(dāng)位置。最基本的插入排序是直接插入排序(Straight Insertion Sort)。 最好情況：若待排序記錄按關(guān)鍵字從小到大排列(正序),算法中的內(nèi)循環(huán)無(wú)須執(zhí)行， 則一趟排序時(shí)：關(guān)鍵字比較次數(shù)1次，記錄移動(dòng)次數(shù)2次 最壞情況：若待排序記錄按關(guān)鍵字從大到小排列(逆序)，則一趟排序時(shí)：算法中的內(nèi) 循環(huán)體執(zhí)行i-1，關(guān)鍵字比較次數(shù)i次，記錄移動(dòng)次數(shù)i+1。一般地，認(rèn)為待排序的記錄可能出現(xiàn)的各種排列的概率相同，則取以上兩種情況的平均值，

17、 作為排序的關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)，約為n2/4，則復(fù)雜度為0(n2)。例= 設(shè)有關(guān)鍵字序列為=7, 4,-2, 19, 13, 6,直接插 入排序的過(guò)程如下圖所示=初始記錄的關(guān)鍵字：PJ4-219136第一越排序占r 4i19136第二睦排序；廠 -247|19I13石篥三越排序=-247T196第阿臘排序三1-247廠136第五睦排序：1 2I-467131賀(5110 1貞接插入排序的對(duì)程算法實(shí)現(xiàn)void straight_insert_sort(Sqlist *L) int i, j ;for (i=2; iv=L->length; i+)L->R0=L->Ri

18、; j=i-1;/* 設(shè)置哨兵 */while( LT(L->R0.key, L->Rj.key)L->Rj+1=L->Rj;j-;/*查找插入位置*/L->Rj+1=L->R0;/*插入到相應(yīng)位置*/折半插入排序當(dāng)將待排序的記錄Ri插入到已排好序的記錄子表R1-1 中時(shí)，由于R1, R2，,R已 排好序，則查找插入位置可以用 折半查找”實(shí)現(xiàn)，則直接插入排序就變成為折半插入排序。從時(shí)間上比較，折半插入排序僅僅減少了關(guān)鍵字的比較次數(shù)，卻沒(méi)有減少記錄的移動(dòng) 次數(shù)，故時(shí)間復(fù)雜度仍然為0(n2)。排序示例：設(shè)有一組關(guān)鍵字30, 13, 70, 85, 39, 42,

19、 6, 20 ,采用折半插入排序方法排序的過(guò)程i=11370394220i=1 3_3O>VOJ*爭(zhēng)-» 2&1=7G2uJO3970SS>N4>直=8NO工3304270NOTtTliiicl“Eli1=甘20427020TTTlO'WlU 1<3iiieii1=20230394N70NU o'WVrn i <1NO1 33仃-"70m o算法實(shí)現(xiàn)void Binary_insert_sort(Sqlist *L) int i, j, low, high, mid ;for (i=2; iv=L->length;

20、 i+) L->R0=L->Ri;/*設(shè)置哨兵*/low=1 ; high=i-1 ;while (low<=high) if ( LT(L->R0.key, L->Rmid.key) high=mid-1 ;else low=mid+1 ;/*查找插入位置*/for (j=i-1; j>=high+1; j-)L->Rj+1=L->Rj;L->Rhigh+1=L->R0; /*插入到相應(yīng)位置*/ 2-路插入排序排序示例：設(shè)有初始關(guān)鍵字集合49, 38, 65, 13, 97, 27, 76,采用2-路插入排序的過(guò)程firstfina

21、l/'7x/nalCA丿、J ilnalfinalfirst圖10-3 2-路插入排掙過(guò)程例：設(shè)有關(guān)鍵字集合49, 38, 65, 97, 76, 13, 27, 49，采用表插入排序的過(guò)程O1234S678MAXIN 1*13971LJncxt-fe1=2MAJCDVT7(54號(hào)|LTJ1=3VIAXINT49386=4386513少72764些431o2一二1=5MAXINT38g13'9776494121 5L-i=<>MA.XINT49njs13972776 1I 49 I43i56O21t7MA.XINT4938651397277

22、64夕431O25i=S1V1AMNT3B132776珂4疝| R2予 |3J 4衣棲入誹仔泌程希爾排序（Shell Sort,又稱縮小增量法）是一種分組插入排序方法。排序示例設(shè)有10個(gè)待排序的記錄，關(guān)鍵字分別為9, 13, 8, 2, 5, 13, 7, 1, 15, 11 ,增量序列是5, 3, 1, 希爾排序的過(guò)程：初始關(guān)鍵字序列：?13«25 V 711511713第一越排序過(guò)程:4萃III I第一趙排序后：97125131381S1111| I I 丁 IH|1第二趨排序后：251971181S13第三趙排序后：1Z呂789甘13K110-5希爾排序過(guò)程算法實(shí)現(xiàn)先給出一趟希

23、爾排序的算法，類似直接插入排序。void shell_pass(Sqlist *L, int d)/*對(duì)順序表L進(jìn)行一趟希爾排序，增量為d */ int j, k ;for (j=d+1; jv=L->length; j+) L->RO=L->Rj ;/*設(shè)置監(jiān)視哨兵*/k=j-d ;while (k>0&&LT(L->R0.key, L->Rk.key) L->Rk+d=L->Rk ; k=k-d ; L->Rk+j=L->RO;void shell_sort(Sqlist *L, int dk, int t)/*按

24、增量序列dk0 -111,對(duì)順序表L進(jìn)行希爾排序 */ int m ;for (m=0; mv=t; m+)shll_pass(L, dkm);冒泡排序排序示例：設(shè)有9個(gè)待排序的記錄，關(guān)鍵字分別為23, 38, 22, 45, 23, 67, 31, 15, 41 ,冒泡排序的過(guò)程：初始關(guān)施字序列：2338224S23<>731IS41第一趟排序局2322382345311541G第二廚排序刊2223233S3 11541-45Q第三超排序局2223Z331IS3841-ISG第四趟排序局2223IS313拮414S<>722231S233138-11<S7第六趟

25、剁酎竽啟：221S23Z33138-11-IS671522232331384呂67腐110-<5void Bubble_Sort(Sqlist *L) int j ,k , flag ;for (j=0; jvL->length; j+)/* 共有 n-1 趟排序 */ flag=TRUE ;for (k=1; kv=L->length-j; k+)/*一趟排序*/if (LT(L->Rk+1.key, L->Rk.key ) flag=FALSE ; L->R0=L->Rk;L->Rk=L->Rk+1;L->Rk+1=L->R

26、0;if (flag=TRUE) break ;算法分析：時(shí)間復(fù)雜度：Bl13i=l.最好情況(正序):比較次數(shù)：n-1;移動(dòng)次數(shù)：0;干券劭7欠救=最壞情況(逆序):故時(shí)間復(fù)雜度：T(n)=O(n2)空間復(fù)雜度：S(n)=0(1)快速排序的平均時(shí)間復(fù)雜度是：T(n)=O(n噸2n)從所需要的附加空間來(lái)看，快速排序算法是遞歸調(diào)用，系統(tǒng)內(nèi)用堆棧保存遞歸參數(shù)，當(dāng)每次劃分比較均勻時(shí)，棧的最大深度為噸2n+1 ?？焖倥判虻目臻g復(fù)雜度是：S(n)=0(log 2n)從排序的穩(wěn)定性來(lái)看，快速排序是不穩(wěn)定的。一趟排序示例設(shè)有6個(gè)待排序的記錄，關(guān)鍵字分別為29, 38, 22, 45, 23, 67，一趟快速

27、排序的過(guò)程0初始關(guān)鍵字序列：2929382245236731丿丿j前移2個(gè)位置后，2338224567J31Rlj放Ril的位宣：i后移1個(gè)位置后，“1232245J386731只岡放只加的位置：丿j前移2個(gè)位置后，29232245.1386731Rj放Ri的位置：丿i后前移1個(gè)位置后，23122J2945386731f和j的位置重合：丿丿10-7一趟快速排序過(guò)程算法實(shí)現(xiàn)一趟快速排序算法的實(shí)現(xiàn)int quick_one_pass(Sqlist *L , int low, int high) L->RO=L->Ri ;/*R0作為臨時(shí)單元和哨兵*/do while (LQ(L->

28、;R0.key, L->Rj.key)&&(j>i)j-;if (j>i)L->Ri=L->Rj ; i+;while (LQ(L->Ri.key, L->R0.key)&&(j>i)i+ ;if (j>i)L->Rj=L->Ri ; j-; while(i!=j) ;/* i=j 時(shí)退出掃描 */L->Ri=L->R0;return(i);遞歸算法void quick_Sort(Sqlist *L , int low, int high) int k ;if (lowvhigh) k

29、=quick_one_pass(L, low, high);quick_Sort(L, low, k-1);quick_Sort(L, k+1, high);/*序列分為兩部分后分別對(duì)每個(gè)子序列排序*/非遞歸算法# define MAX_STACK 100void quick_Sort(Sqlist *L , int low, int high) int k , stackMAX_STACK , top=0;do while (lowvhigh) k=quick_one_pass(L,low,high);stack+top=high ; stack+top=k+1 ;/*第二個(gè)子序列的上，下界

30、分別入棧*/high=k-1 ;if (top!=0) low=stacktop- ; high=stacktop- ; while (top!= 0&&lowvhigh);簡(jiǎn)單選擇排序(Simple Selection Sort，又稱為直接選擇排序)排序示例例：設(shè)有關(guān)鍵字序列為：7,4, -2, 19, 13, 6，直接選擇排序的過(guò)程初始id錄的興讎壬74-21913笫超排序=47工¥1 3第二超排序U-247191 3石第三影封冊(cè)予=-24五19137第四趟林序=-24671319-24石71 31 9第兀趟林序二-246713 9® 10-8宜按選拝排

31、序的過(guò)程算法實(shí)現(xiàn)void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1; m<L->length; m+) k=m ;for (n=m+1; n<=L->length; n+)if ( LT(L->Rn.key, L->Rk.key) ) k=n ;if (k!=m)/*記錄交換*/ L->R0=L->Rm; L->Rm=L->Rk;L->Rk=L->R0;算法分析整個(gè)算法是二重循環(huán)：外循環(huán)控制排序的趟數(shù)，對(duì)n個(gè)記錄進(jìn)行排序的趟數(shù)為n-1趟;內(nèi)循環(huán)控制每一趟的

32、排序。進(jìn)行第i趟排序時(shí)，關(guān)鍵字的比較次數(shù)為 n-i ，則：比較次數(shù)=丈右-匚尸從Ji=l立時(shí)間復(fù)雜度是：T(n)=O(n2)空間復(fù)雜度是：S(n)=O(1)從排序的穩(wěn)定性來(lái)看，直接選擇排序是不穩(wěn)定的。堆的定義是n個(gè)元素的序列 H=ki, k2 ,nk，滿足：臉嗆 當(dāng)2辻n時(shí)或 | kk21出2迄11時(shí)丄芒知屮當(dāng)2i+l<n時(shí)當(dāng)2i+l<uS'J其中LnJ堆的性質(zhì) 堆是一棵采用順序存儲(chǔ)結(jié)構(gòu)的完全二叉樹(shù)，ki是根結(jié)點(diǎn)； 堆的根結(jié)點(diǎn)是關(guān)鍵字序列中的最?。ɑ蜃畲螅┲?，分別稱為?。ɑ虼螅└?； 從根結(jié)點(diǎn)到每一葉子結(jié)點(diǎn)路徑上的元素組成的序列都是按元素值（或關(guān)鍵字值）非遞減（或非遞增）的

33、；（4）堆中的任一子樹(shù)也是堆。利用堆頂記錄的關(guān)鍵字值最?。ɑ蜃畲螅┑男再|(zhì)，從當(dāng)前待排序的記錄中依次選取關(guān)鍵字最 小（或最大）的記錄，就可以實(shí)現(xiàn)對(duì)數(shù)據(jù)記錄的排序，這種排序方法稱為堆排序。堆排序思想 對(duì)一組待排序的記錄，按堆的定義建立堆； 將堆頂記錄和最后一個(gè)記錄交換位置，則前n-1個(gè)記錄是無(wú)序的， 而最后一個(gè)記錄是有序的； 堆頂記錄被交換后，前 n-1個(gè)記錄不再是堆，需將前 n-1個(gè)待排序記錄重新組織成為一個(gè)堆，然后將堆頂記錄和倒數(shù)第二個(gè)記錄交換位置，即將整個(gè)序列中次小關(guān)鍵字值的記錄調(diào)整（排除）出無(wú)序區(qū)； 重復(fù)上述步驟，直到全部記錄排好序?yàn)橹?。結(jié)論：排序過(guò)程中，若采用小根堆，排序后得到的是非遞減

34、序列；若采用大根堆，排序后 得到的是非遞增序列。注意二篩選過(guò)程中"根結(jié)點(diǎn)的左*冇子樹(shù)都是華，因 此，篩選足從抿結(jié)點(diǎn)到某個(gè)葉子結(jié)點(diǎn)的一次調(diào)整過(guò)程。堆排序算法實(shí)現(xiàn)堆的根結(jié)點(diǎn)是關(guān)鍵字最小的記錄，輸出根結(jié)點(diǎn)后，是以序列的最后一個(gè)記錄作為 根結(jié)點(diǎn)，而原來(lái)堆的左、右子樹(shù)都是堆，則進(jìn)行一次篩選就可以成為堆。void Heap_Sort（Sqlist *H） intj ；for （j=H->length/ 2; j>0; j-）Heap_adjust（H, j , H->le ngth） ;/*初始建堆*/for （j=H->length/ 2; j>=1; j-）H-

35、>R0=H->R1 ; H->R1=H->Rj;H->Rj=H->RO ;/*堆頂與最后一個(gè)交換*/Heap_adjust(H, 1, j-1);堆排序的比較次數(shù)的數(shù)量級(jí)為：T(n)=O(n log 2n);而附加空間就是交換時(shí)所用的臨時(shí)空間,故空間復(fù)雜度為：S(n)=O(1)歸并(Merging):是指將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列。若采用線性表(無(wú)論是那種存儲(chǔ)結(jié)構(gòu))易于實(shí)現(xiàn)，其時(shí)間復(fù)雜度為O(m+n)。例匸 設(shè)有鳥(niǎo)個(gè)待排序的 記錄，關(guān)鍵字分別為23, 3S, 22, 45, 23, ©7, 31, 15, 41,歸并斟乍序的過(guò)程如

36、圖睦歸并后：23L3S222L1531 J141JI二越歸并后：122n231_38451523 T31671 41I三趙歸并后二152223T23311_3845671fjll四屜歸并后；1522232331381414567圖10-11 歸并搏序過(guò)程歸并排序的算法開(kāi)始?xì)w并時(shí)，每個(gè)記錄是長(zhǎng)度為1的有序子序列，對(duì)這些有序子序列逐趟歸并， 每一趟歸并后有序子序列的長(zhǎng)度均擴(kuò)大一倍；當(dāng)有序子序列的長(zhǎng)度與整個(gè)記錄序列長(zhǎng)度相 等時(shí)，整個(gè)記錄序列就成為有序序列。算法是：void Merge_sort(Sqlist *L, RecType DR) int d=1 ;while(d<L->leng

37、th) Merge_pass(L->R, DR, d, L->length);Merge_pass(DR, L->R, 2*d, L->length);d=4*d ;具有n個(gè)待排序記錄的歸并次數(shù)是g 2n,而一趟歸并的時(shí)間復(fù)雜度為 O(n)，則整個(gè)歸并排 序的時(shí)間復(fù)雜度無(wú)論是最好還是最壞情況均為 O(n g 2n)。在排序過(guò)程中，使用了輔助向量 DR,大小與待排序記錄空間相同，則空間復(fù)雜度為 O(n)。歸并排序是穩(wěn)定的。各種內(nèi)部排序的比較：各種內(nèi)部排序按所采用的基本思想 (策略)可分為：插入排序、交換排序、選擇排序、歸并排 序和基數(shù)排序，它們的基本策略分別是：1插入排序

38、：依次將無(wú)序序列中的一個(gè)記錄，按關(guān)鍵字值的大小插入到已排好序一個(gè)子序列的適當(dāng)位置，直到所有的記錄都插入為止。具體的方法有：直接插入、表插入、2-路插入 和shell排序。2交換排序：對(duì)于待排序記錄序列中的記錄，兩兩比較記錄的關(guān)鍵字，并對(duì)反序的兩個(gè)記 錄進(jìn)行交換，直到整個(gè)序列中沒(méi)有反序的記錄偶對(duì)為止。具體的方法有：冒泡排序、快速 排序。3選擇排序：不斷地從待排序的記錄序列中選取關(guān)鍵字最小的記錄，放在已排好序的序列 的最后，直到所有記錄都被選取為止。具體的方法有：簡(jiǎn)單選擇排序、堆排序。4歸并排序：利用“歸并”技術(shù)不斷地對(duì)待排序記錄序列中的有序子序列進(jìn)行合并，直到 合并為一個(gè)有序序列為止。5基數(shù)排序

39、：按待排序記錄的關(guān)鍵字的組成成分(位”)從低到高(或從高到低)進(jìn)行。每次是按記錄關(guān)鍵字某一 位”的值將所有記錄分配到相應(yīng)的桶中，再按桶的編號(hào)依次將記錄進(jìn)行收集，最后得到一個(gè)有序序列。各種內(nèi)部排序方法的性能比較如下表。7-1主喪內(nèi)部拆序力法的性龍力法平均時(shí)冋晟壞所需時(shí)問(wèn)附加空冋稔定性T7接插入CXJ不稔定的直接進(jìn)拝OCn>OCU十就企的堆排序0(0( n血了nOCU可U総定的M泡排序0( n*OCri3 joci)律定的快速排序0(O(na>OCJoRnl歸并排序0( >0( nljn )CK市 'ROfn+f)文件的基本概念 數(shù)據(jù)項(xiàng)(Item或field)：數(shù)據(jù)文件中

40、最小的基本單位，反映實(shí)體某一方面的特征一屬性的數(shù)據(jù)表示。記錄(Record): 一個(gè)實(shí)體的所有數(shù)據(jù)項(xiàng)的集合。用來(lái)標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)集合(一個(gè)或多個(gè))稱為關(guān)鍵字項(xiàng)(Key)，關(guān)鍵字項(xiàng)的值稱為關(guān)鍵字；能唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字稱為主關(guān)鍵字(Primary Key，其它的關(guān)鍵字稱為次關(guān)鍵字(Secondary Key)。利用外存對(duì)數(shù)據(jù)文件進(jìn)行排序稱為外部排序。算法部分：素?cái)?shù)的判斷算法。Void prime( int n)/* n是一個(gè)正整數(shù) */ int i=2 ;while ( (n% i)!=0 && i*1.0< sqrt(n) )i+ ;if (i*1.0>sq

41、rt(n)printf(“ 是一個(gè)素?cái)?shù) n” , n);elseprintf(“不是一個(gè)素?cái)?shù)n” , n);冒泡排序法。Void bubble_sort(int a， int n) change=false;for (i=n-1; change=TURE; i>1 && change; -i)for (j=0; j<i; +j)if (aj>aj+1) aj<-> aj+1 ; change=TURE ; - 最好情況：0次- 最壞情況：1+2+3+? +n-仁n(n-1)/2- 平均時(shí)間復(fù)雜度為：0(n2)pc是合并過(guò)程中合并的算法說(shuō)明：算法中p

42、a , pb分別是待考察的兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn), 鏈表的最后一個(gè)結(jié)點(diǎn)。LNode *Merge_LinkList(LNode *La, LNode *Lb)/* 合并以La, Lb為頭結(jié)點(diǎn)的兩個(gè)有序單鏈表*/ LNode *Lc, *pa , *pb , *pc, *ptr ;Lc=La ; pc=La ; pa=La->next ; pb=Lb->next ;while (pa!=NULL && pb!=NULL) if (pa->datavpb->data)pa=pa->next ;pa指向下一個(gè)結(jié)點(diǎn)*/pb=pb->next ;pa指向下

43、一個(gè)結(jié)點(diǎn)*/pa=pa->next ; pc->next=pa ; pc=pa ;/* 將pa所指的結(jié)點(diǎn)合并, if (pa->data>pb->data) pc->next=pb ; pc=pb ;/* 將pa所指的結(jié)點(diǎn)合并, if (pa->data=pb->data) pc->next=pa ; pc=pa ;ptr=pb ; pb=pb->next ; free(ptr) ;/* 將pa所指的結(jié)點(diǎn)合并，pb所指結(jié)點(diǎn)刪除*/if (pa!=NULL) pc->next=pa ;else pc->next=pb ;/*

44、將剩余的結(jié)點(diǎn)鏈上 */free(Lb);return(Lc); 采用靜態(tài)順序棧方式實(shí)現(xiàn)void conversion(int n , int d)/*將十進(jìn)制整數(shù) N轉(zhuǎn)換為d(2或8)進(jìn)制數(shù)*/ SqStack S ; int k, *e ;S=lnit_Stack();while (n>0) k=n%d ; push(S , k) ; n=n/d ;/* 求出所有的余數(shù)，進(jìn)棧 */while (S.top!=0)/* 棧不空時(shí)出棧，輸出 */ pop(S, e);printf(“ 1d' , *e);求轉(zhuǎn)置矩陣的算法如下：void TransMatrix(TMatrix a ,

45、 TMatrix b) int p , q , col ; b.rn= ; =a.rn ; b.tn=a.tn ;/*置三元組表b.data的行、列數(shù)和非0元素個(gè)數(shù)*/if (b.tn=0) printf( “ The Matrix A=”)；elseq=0;for (col=1; col<= ; col+)/*每循環(huán)一次找到轉(zhuǎn)置后的一個(gè)三元組*/for (p=0 ;p<a.tn ; p+)/*循環(huán)次數(shù)是非0元素個(gè)數(shù) */if (a.datap.col=col) b.dataq.row=a.datap.col ;b.dataq.col=a.datap.row ;b.dataq.va

46、lue=a.datap.value;q+ ;先序遍歷的遞歸算法void PreorderTraverse(BTNode *T) if (T!=NULL) visit(T->data) ;/*訪問(wèn)根結(jié)點(diǎn)*/PreorderTraverse(T->Lchild); PreorderTraverse(T->Rchild);非遞歸算法設(shè)T是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是: 若二叉樹(shù)為空，則返回；否則，令 p=T；訪問(wèn)p所指向的結(jié)點(diǎn)；q=p->Rchild，若q不為空，則q進(jìn)棧；p=p->Lchild，若p不為空，轉(zhuǎn)(1)，否則轉(zhuǎn)(4)； 退棧到p，轉(zhuǎn)(1)，直到

47、?？諡橹?。算法實(shí)現(xiàn)：#define MAX_NODE 50 void PreorderTraverse( BTNode *T) BTNode *StackMAX_NODE ,*p=T, *q ;int top=0 ;if (T=NULL) printf( “ Binary Tree is Empnt”y!) ; else do visit( p-> data ) ; q=p->Rchild ; if ( q!=NULL ) stack+top=q ; p=p->Lchild ;if (p=NULL) p=stacktop ; top- ; while (p!=NULL) ;中

48、序遍歷的遞歸算法void InorderTraverse(BTNode *T) if (T!=NULL) InorderTraverse(T->Lchild) ; visit(T->data) ; /* 訪問(wèn)根結(jié)點(diǎn) */ InorderTraverse(T->Rchild) ; 非遞歸算法 設(shè) T 是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是： 若二叉樹(shù)為空，則返回；否則，令 p=T 若 p 不為空， p 進(jìn)棧， p=p->Lchild ； 否則(即p為空)，退棧到P,訪問(wèn)p所指向的結(jié)點(diǎn)； p=p->Rchild ，轉(zhuǎn) (1)； 直到?？諡橹?。算法實(shí)現(xiàn)：#defin

49、e MAX_NODE 50void InorderTraverse( BTNode *T) BTNode *StackMAX_NODE ,*p=T ;int top=0 , bool=1 ;if (T=NULL) printf( “ Binary Tree is Emnpt”y!) ;else do while (p!=NULL) stack+top=p ; p=p->Lchild ;if (top=0) bool=0 ; else p=stacktop ; top- ;visit( p->data ) ; p=p->Rchild ; while (bool!=0) ;后序遍

50、歷的遞歸算法void PostorderTraverse(BTNode *T) if (T!=NULL) PostorderTraverse(T->Lchild) ;PostorderTraverse(T->Rchild) ;visit(T->data) ; /* 訪問(wèn)根結(jié)點(diǎn) */非遞歸算法在后序遍歷中，根結(jié)點(diǎn)是最后被訪問(wèn)的。因此，在遍歷過(guò)程中，當(dāng)搜索指針指向某一 根結(jié)點(diǎn)時(shí)，不能立即訪問(wèn)，而要先遍歷其左子樹(shù)，此時(shí)根結(jié)點(diǎn)進(jìn)棧。當(dāng)其左子樹(shù)遍歷完后 再搜索到該根結(jié)點(diǎn)時(shí)，還是不能訪問(wèn)，還需遍歷其右子樹(shù)。所以，此根結(jié)點(diǎn)還需再次進(jìn)棧， 當(dāng)其右子樹(shù)遍歷完后再退棧到到該根結(jié)點(diǎn)時(shí)，才能被訪問(wèn)。

51、因此，設(shè)立一個(gè)狀態(tài)標(biāo)志變量 tag ： 0 ： 結(jié)點(diǎn)暫不能訪問(wèn)1 ： 結(jié)點(diǎn)可以被訪問(wèn)其次，設(shè)兩個(gè)堆棧Si、S2,Si保存結(jié)點(diǎn)，S2保存結(jié)點(diǎn)的狀態(tài)標(biāo)志變量tag。S,和Sz共用一個(gè)棧頂指針。設(shè) T 是指向根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹(shù)為空，則返回；否則，令 p=T；第一次經(jīng)過(guò)根結(jié)點(diǎn)p,不訪問(wèn)：p 進(jìn)棧 Si ， tag 賦值 0，進(jìn)棧 S2， p=p->Lchild 。若p不為空，轉(zhuǎn)(1)，否則，取狀態(tài)標(biāo)志值tag : 若tag=0 :對(duì)棧S1，不訪問(wèn)，不出棧；修改S2棧頂元素值(tag賦值1)，取S1棧頂元素的右子樹(shù)，即 p=S1top->Rchild，轉(zhuǎn)(1); 若 tag=1 ： S1 退棧，訪問(wèn)該結(jié)點(diǎn)；直到?？諡橹?。算法實(shí)現(xiàn)：#define MAX_NODE 50void PostorderTraverse( B