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

1、1、數(shù)據(jù)(Data) ：是客觀(guān)事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。 數(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ì)客觀(guān)事物某一方面特性的數(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ù)元素的集合。元素之間的相互聯(lián)系(關(guān)系)稱(chēng)為邏輯

2、結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類(lèi)型，如圖1-3所示。 集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外，沒(méi)有其它關(guān)系。 線(xià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)依賴(lài)于所采用的存儲(chǔ)結(jié)構(gòu)。 在C語(yǔ)言中，用一維數(shù)組表示順序存儲(chǔ)結(jié)構(gòu)；用結(jié)構(gòu)體類(lèi)型表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、C語(yǔ)言中用帶指針的結(jié)構(gòu)體類(lèi)型來(lái)

3、描述typedef struct Lnode ElemType data; /*數(shù)據(jù)域，保存結(jié)點(diǎn)的值 */struct Lnode *next; /*指針域*/LNode; /*結(jié)點(diǎn)的類(lèi)型 */4、循環(huán)隊(duì)列為空：front=rear 。 循環(huán)隊(duì)列滿(mǎn)：(rear+1)%MAX_QUEUE_SIZE =front。5、性質(zhì)1：在非空二叉樹(shù)中，第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)。性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k1) 。性質(zhì)3：對(duì)任何一棵二叉樹(shù)，若其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)(Full Binary T

4、ree)。完全二叉樹(shù)的特點(diǎn)：若完全二叉樹(shù)的深度為k ，則所有的葉子結(jié)點(diǎn)都出現(xiàn)在第k層或k-1層。對(duì)于任一結(jié)點(diǎn)，如果其右子樹(shù)的最大層次為l，則其左子樹(shù)的最大層次為l或l+1。性質(zhì)4：n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為：2n +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（1in)的結(jié)點(diǎn)： 若i=1：則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親結(jié)點(diǎn)；否則，若i1，則其雙親結(jié)點(diǎn)編號(hào)是 i/2 。 如果2in：則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左孩子；否則，其左孩子結(jié)點(diǎn)編號(hào)是2i。 如果2i+1n：則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子結(jié)點(diǎn)編號(hào)是2i+1。

5、6、線(xiàn)索二叉樹(shù)：設(shè)一棵二叉樹(shù)有n個(gè)結(jié)點(diǎn)，則有n-1條邊(指針連線(xiàn)) ， 而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ù)，稱(chēng)這棵樹(shù)為Huffman樹(shù)(或稱(chēng)最優(yōu)樹(shù)) 。8、完全無(wú)向圖：對(duì)于無(wú)向圖，若圖中頂點(diǎn)數(shù)為n ，用e表示邊的數(shù)目，則e 0，n(n-1)/2 。具有n(n-1)/2條邊的無(wú)向圖稱(chēng)為完全無(wú)向圖。完全有向圖：對(duì)于有向圖，若圖中頂點(diǎn)數(shù)為n ，用e表示

6、弧的數(shù)目，則e0，n(n-1) 。具有n(n-1)條邊的有向圖稱(chēng)為完全有向圖。生成樹(shù)、生成森林：一個(gè)連通圖(無(wú)向圖)的生成樹(shù)是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)和只有足以構(gòu)成一棵樹(shù)的n-1條邊，稱(chēng)為圖的生成樹(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) 有n-1條邊的圖不一定是生成樹(shù)。9、最小生成樹(shù)(Minimum Spanning Tree) ：帶權(quán)連通圖中代價(jià)最小的生成樹(shù)稱(chēng)為最小生成樹(shù)。 最小生成樹(shù)在實(shí)際中具有重要用途，如設(shè)計(jì)通信網(wǎng)。設(shè)圖的頂點(diǎn)表示

7、城市，邊表示兩個(gè)城市之間的通信線(xiàn)路，邊的權(quán)值表示建造通信線(xiàn)路的費(fèi)用。n個(gè)城市之間最多可以建n(n-1)/2條線(xiàn)路，如何選擇其中的n-1條，使總的建造費(fèi)用最低?10、工程完成最短時(shí)間：從起點(diǎn)到終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度(路徑上各活動(dòng)持續(xù)時(shí)間之和) 。長(zhǎng)度最長(zhǎng)的路徑稱(chēng)為關(guān)鍵路徑，關(guān)鍵路徑上的活動(dòng)稱(chēng)為關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)是影響整個(gè)工程的關(guān)鍵。 11、查找方法比較順序查找折半查找分塊查找ASL最大最小兩者之間表結(jié)構(gòu)有序表、無(wú)序表有序表分塊有序表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性鏈表順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性鏈表12、在隨機(jī)情況下，二叉排序樹(shù)的平均查找長(zhǎng)度ASL和(n)(樹(shù)的深度)是等數(shù)量級(jí)的。二叉排序樹(shù)(Binary

8、Sort Tree或Binary Search Tree) 的定義為：二叉排序樹(shù)或者是空樹(shù)，或者是滿(mǎn)足下列性質(zhì)的二叉樹(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ù)，或者是滿(mǎn)足下列性質(zhì)的二叉樹(shù)。：左子樹(shù)和右子樹(shù)深度之差的絕對(duì)值不大于1；：左子樹(shù)和右子樹(shù)也都是平衡二叉樹(shù)。 平衡因子(Balance Factor) ：二叉樹(shù)上結(jié)點(diǎn)的左子樹(shù)的深度減去其右子樹(shù)深度稱(chēng)

9、為該結(jié)點(diǎn)的平衡因子。平衡二叉排序樹(shù)上進(jìn)行查找的平均查找長(zhǎng)度和2n是一個(gè)數(shù)量級(jí)的，平均時(shí)間復(fù)雜度為O(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階B_樹(shù)，或者是空樹(shù)，或者是滿(mǎn)足以下性質(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é)

10、點(diǎn)應(yīng)包含如下信息： (n，A0，K1，A1，K2，A2， ，Kn，An)其中Ki(1in)是關(guān)鍵字，且KiKi+1 (1in-1)；Ai(i=0，1， ，n)為指向孩子結(jié)點(diǎn)的指針，且Ai-1所指向的子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字都小于Ki ，Ai所指向的子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字都大于Ki ；n是結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，且m/2-1nm-1，n+1為子樹(shù)的棵數(shù)。根據(jù)m階B_樹(shù)的定義，第一層上至少有1個(gè)結(jié)點(diǎn)，第二層上至少有2個(gè)結(jié)點(diǎn)；除根結(jié)點(diǎn)外，所有非終端結(jié)點(diǎn)至少有m/2棵子樹(shù)，第h層上至少有m/2h-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)鍵字

11、數(shù)目n滿(mǎn)足：因此有： h1+ s(n+1)/2)=1+m/2(n+1)/2) 即在含有n個(gè)關(guān)鍵字的B_樹(shù)上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到待查找記錄關(guān)鍵字的結(jié)點(diǎn)的路徑上所涉及的結(jié)點(diǎn)數(shù)不超過(guò)1+ 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é)

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

13、)=key MOD 7，沖突處理采用線(xiàn)性探測(cè)法。解：H(15)=15 MOD 7=1 H(14)=14 MOD 7=0 H(28)=28 MOD 7=0 沖突 H1(28)=1 又沖突H2(28)=2 H(26)=26 MOD 7=5 H(56)=56 MOD 7=0 沖突 H1(56)=1 又沖突H2(56)=2 又沖突 H3(56)=3 H(23)=23 MOD 7=2 沖突 H1(23)=3 又沖突H3(23)=4各種散列函數(shù)所構(gòu)造的散列表的ASL如下： 17、排序的穩(wěn)定性 若記錄序列中有兩個(gè)或兩個(gè)以上關(guān)鍵字相等的記錄： Ki =Kj(ij，i, j=1, 2, n)，且在排序前Ri先于

14、Rj(ij)，排序后的記錄序列仍然是Ri先于Rj，稱(chēng)排序方法是穩(wěn)定的，否則是不穩(wěn)定的。排序的分類(lèi) 待排序的記錄數(shù)量不同，排序過(guò)程中涉及的存儲(chǔ)器的不同，有不同的排序分類(lèi)。 待排序的記錄數(shù)不太多：所有的記錄都能存放在內(nèi)存中進(jìn)行排序，稱(chēng)為內(nèi)部排序； 待排序的記錄數(shù)太多：所有的記錄不可能存放在內(nèi)存中， 排序過(guò)程中必須在內(nèi)、外存之間進(jìn)行數(shù)據(jù)交換，這樣的排序稱(chēng)為外部排序。18、插入排序采用的是以 “玩橋牌者”的方法為基礎(chǔ)的。即在考察記錄Ri之前，設(shè)以前的所有記錄R1, R2 ,., Ri-1已排好序，然后將Ri插入到已排好序的諸記錄的適當(dāng)位置。=最基本的插入排序是直接插入排序(Straight Inser

15、tion 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)的各種排列的概率相同，則取以上兩種情況的平均值，作為排序的關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)，約為n2/4，則復(fù)雜度為O(n2) 。算法實(shí)現(xiàn)void straight_insert_sort(Sqlist *L) int i, j ;for (i=2; ilength; i+) L-R

16、0=L-Ri; 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 插入到已排好序的記錄子表R1i-1中時(shí)，由于R1, R2 , Ri-1已排好序，則查找插入位置可以用“折半查找”實(shí)現(xiàn)，則直接插入排序就變成為折半插入排序。從時(shí)間上比較，折半插入排序僅僅減少了關(guān)鍵字的比較次數(shù)，卻沒(méi)有減少記錄的移動(dòng)次數(shù)，故時(shí)間復(fù)雜度仍然為O(n2) 。排序示例：設(shè)有一組關(guān)鍵字30, 13, 70, 85, 39, 42,

17、6, 20，采用折半插入排序方法排序的過(guò)程 算法實(shí)現(xiàn) void Binary_insert_sort(Sqlist *L) int i, j, low, high, mid ;for (i=2; ilength; i+) L-R0=L-Ri; /* 設(shè)置哨兵 */ low=1 ; high=i-1 ; while (lowR0.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-路插入

18、排序排序示例：設(shè)有初始關(guān)鍵字集合49, 38, 65, 13, 97, 27, 76 ，采用2-路插入排序的過(guò)程例：設(shè)有關(guān)鍵字集合49, 38, 65, 97, 76, 13, 27, 49 ，采用表插入排序的過(guò)程=希爾排序(Shell Sort，又稱(chēng)縮小增量法)是一種分組插入排序方法。排序示例 設(shè)有10個(gè)待排序的記錄，關(guān)鍵字分別為9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是5, 3, 1，希爾排序的過(guò)程：算法實(shí)現(xiàn) 先給出一趟希爾排序的算法，類(lèi)似直接插入排序。void shell_pass(Sqlist *L, int d) /* 對(duì)順序表L進(jìn)行一趟希爾排序,

19、增量為d */ int j, k ;for (j=d+1; jlength; j+) L-R0=L-Rj ; /* 設(shè)置監(jiān)視哨兵 */k=j-d ;while (k0<(L-R0.key, L-Rk.key) ) L-Rk+d=L-Rk ; k=k-d ; L-Rk+j=L-R0 ;void shell_sort(Sqlist *L, int dk, int t) /* 按增量序列dk0 t-1,對(duì)順序表L進(jìn)行希爾排序 */ int m ;for (m=0; m=t; m+)shll_pass(L, dkm) ;=冒泡排序排序示例 ： 設(shè)有9個(gè)待排序的記錄，關(guān)鍵字分別為23, 38, 22

20、, 45, 23, 67, 31, 15, 41，冒泡排序的過(guò)程：void Bubble_Sort(Sqlist *L) int j ,k , flag ;for (j=0; jlength; j+) /* 共有n-1趟排序 */ flag=TRUE ; for (k=1; klength-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-R0 ; if (flag=TRUE) break ;算法分析:時(shí)間復(fù)雜度:最好情況(正序)：比較次數(shù)：n-1；

21、移動(dòng)次數(shù)：0；最壞情況(逆序)：故時(shí)間復(fù)雜度：T(n)=O(n)空間復(fù)雜度：S(n)=O(1)=快速排序的平均時(shí)間復(fù)雜度是：T(n)=O(n2n) 從所需要的附加空間來(lái)看，快速排序算法是遞歸調(diào)用，系統(tǒng)內(nèi)用堆棧保存遞歸參數(shù)，當(dāng)每次劃分比較均勻時(shí)，棧的最大深度為2n+1 。 快速排序的空間復(fù)雜度是：S(n)=O(2n) 從排序的穩(wěn)定性來(lái)看，快速排序是不穩(wěn)定的。一趟排序示例 設(shè)有6個(gè)待排序的記錄，關(guān)鍵字分別為29, 38, 22, 45, 23, 67，一趟快速排序的過(guò)程算法實(shí)現(xiàn) 一趟快速排序算法的實(shí)現(xiàn)int quick_one_pass(Sqlist *L , int low, int high)

22、L-R0=L-Ri ; /* R0作為臨時(shí)單元和哨兵 */do while (LQ(L-R0.key, L-Rj.key)&(ji) j- ;if (ji) L-Ri=L-Rj ; i+; while (LQ(L-Ri.key, L-R0.key)&(ji) i+ ;if (ji) 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 (lowhigh) k=quick_one_pass(L,

23、 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 (lowhigh) k=quick_one_pass(L,low,high); stack+top=high ; stack+top=k+1 ; /* 第二個(gè)子序列的上,下界分別入棧 */ high

24、=k-1 ; if (top!=0) low=stacktop- ; high=stacktop- ; while (top!=0&lowhigh) ;=簡(jiǎn)單選擇排序(Simple Selection Sort ，又稱(chēng)為直接選擇排序)排序示例 例：設(shè)有關(guān)鍵字序列為：7, 4, -2, 19, 13, 6，直接選擇排序的過(guò)程算法實(shí)現(xiàn)void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1; mlength; m+) k=m ; for (n=m+1; nlength; n+) if ( LT(L-Rn.key, L-Rk.key) )

25、 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)控制每一趟的排序。進(jìn)行第i趟排序時(shí)，關(guān)鍵字的比較次數(shù)為n-i，則： 時(shí)間復(fù)雜度是：T(n)=O(n2) 空間復(fù)雜度是：S(n)=O(1) 從排序的穩(wěn)定性來(lái)看，直接選擇排序是不穩(wěn)定的。=堆的定義 是n個(gè)元素的序列H=k1, k2 , kn ，滿(mǎn)足： 堆的性質(zhì) 堆是一棵采用順序存儲(chǔ)結(jié)構(gòu)的完全二叉樹(shù)， k1是根結(jié)點(diǎn)； 堆的根結(jié)點(diǎn)是關(guān)鍵字序列中的最小(或最大)值，分別稱(chēng)為小(或大)根堆； 從

26、根結(jié)點(diǎn)到每一葉子結(jié)點(diǎn)路徑上的元素組成的序列都是按元素值(或關(guān)鍵字值)非遞減(或非遞增)的；(4)堆中的任一子樹(shù)也是堆。 利用堆頂記錄的關(guān)鍵字值最小(或最大)的性質(zhì)，從當(dāng)前待排序的記錄中依次選取關(guān)鍵字最小(或最大)的記錄，就可以實(shí)現(xiàn)對(duì)數(shù)據(jù)記錄的排序，這種排序方法稱(chēng)為堆排序。堆排序思想 對(duì)一組待排序的記錄，按堆的定義建立堆； 將堆頂記錄和最后一個(gè)記錄交換位置，則前n-1個(gè)記錄是無(wú)序的，而最后一個(gè)記錄是有序的； 堆頂記錄被交換后，前n-1個(gè)記錄不再是堆，需將前n-1個(gè)待排序記錄重新組織成為一個(gè)堆，然后將堆頂記錄和倒數(shù)第二個(gè)記錄交換位置，即將整個(gè)序列中次小關(guān)鍵字值的記錄調(diào)整(排除)出無(wú)序區(qū)； 重復(fù)上述

27、步驟，直到全部記錄排好序?yàn)橹埂?結(jié)論：排序過(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) int j ;for (j=H-length/2; j0; j-)Heap_adjust(H, j , H-length) ; /* 初始建堆 */for (j=H-length/2; j=1; j-) H-R0=H-R1 ; H-R1=H-Rj ;H-Rj=H-R0

28、 ; /* 堆頂與最后一個(gè)交換 */Heap_adjust(H, 1, j-1) ; 堆排序的比較次數(shù)的數(shù)量級(jí)為： T(n)=O(n2n)；而附加空間就是交換時(shí)所用的臨時(shí)空間，故空間復(fù)雜度為： S(n)=O(1)=歸并(Merging) ：是指將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列。若采用線(xiàn)性表(無(wú)論是那種存儲(chǔ)結(jié)構(gòu))易于實(shí)現(xiàn)，其時(shí)間復(fù)雜度為O(m+n) 。歸并排序的算法 開(kāi)始?xì)w并時(shí)，每個(gè)記錄是長(zhǎng)度為1的有序子序列，對(duì)這些有序子序列逐趟歸并，每一趟歸并后有序子序列的長(zhǎng)度均擴(kuò)大一倍；當(dāng)有序子序列的長(zhǎng)度與整個(gè)記錄序列長(zhǎng)度相等時(shí)，整個(gè)記錄序列就成為有序序列。算法是： void Merge_sor

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

30、數(shù)排序，它們的基本策略分別是：1 插入排序：依次將無(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)行合并

31、，直到合并為一個(gè)有序序列為止。5 基數(shù)排序：按待排序記錄的關(guān)鍵字的組成成分(“位”)從低到高(或從高到低)進(jìn)行。每次是按記錄關(guān)鍵字某一“位”的值將所有記錄分配到相應(yīng)的桶中，再按桶的編號(hào)依次將記錄進(jìn)行收集，最后得到一個(gè)有序序列。 各種內(nèi)部排序方法的性能比較如下表。文件的基本概念 數(shù)據(jù)項(xiàng)(Item或field) ：數(shù)據(jù)文件中最小的基本單位，反映實(shí)體某一方面的特征屬性的數(shù)據(jù)表示。 記錄(Record) ：一個(gè)實(shí)體的所有數(shù)據(jù)項(xiàng)的集合。 用來(lái)標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)集合(一個(gè)或多個(gè))稱(chēng)為關(guān)鍵字項(xiàng)(Key) ，關(guān)鍵字項(xiàng)的值稱(chēng)為關(guān)鍵字；能唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字稱(chēng)為主關(guān)鍵字(Primary Key)，其它的關(guān)鍵

32、字稱(chēng)為次關(guān)鍵字(Secondary Key) 。 利用外存對(duì)數(shù)據(jù)文件進(jìn)行排序稱(chēng)為外部排序。算法部分：素?cái)?shù)的判斷算法。Void prime( int n)/* n是一個(gè)正整數(shù) */ int i=2 ; while ( (n% i)!=0 & i*1.0sqrt(n) )printf(“&d 是一個(gè)素?cái)?shù)n” , n) ;elseprintf(“&d 不是一個(gè)素?cái)?shù)n” , n) ;-冒泡排序法。Void bubble_sort(int a，int n) change=false;for (i=n-1; change=TURE; i1 & change; -i)for (j=0; jaj+1) aj

33、aj+1 ; change=TURE ; 最好情況：0次 最壞情況：1+2+3+n-1=n(n-1)/2 平均時(shí)間復(fù)雜度為： O(n2) -算法說(shuō)明 ：算法中pa ，pb分別是待考察的兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn)，pc是合并過(guò)程中合并的鏈表的最后一個(gè)結(jié)點(diǎn)。LNode *Merge_LinkList(LNode *La， LNode *Lb) /* 合并以L(fǎng)a, 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

34、 (pa-datadata) pc-next=pa ; pc=pa ; pa=pa-next ; /* 將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn) */if (pa-datapb-data) pc-next=pb ; pc=pb ; pb=pb-next ; /* 將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn) */ if (pa-data=pb-data) pc-next=pa ; pc=pa ; pa=pa-next ; ptr=pb ; pb=pb-next ; free(ptr) ; /* 將pa所指的結(jié)點(diǎn)合并，pb所指結(jié)點(diǎn)刪除 */ if (pa!=NULL) pc-next=pa ;els

35、e pc-next=pb ; /*將剩余的結(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=Init_Stack();while (n0) 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 TransMa

36、trix(TMatrix a , 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=0n” );else q=0;for (col=1; col= ; col+) /* 每循環(huán)一次找到轉(zhuǎn)置后的一個(gè)三元組 */for (p=0 ;pdata) ; /* 訪(fǎng)問(wèn)根結(jié)點(diǎn) */PreorderTraverse(T-Lchild) ;PreorderTraverse(T-Rchild) ; 非遞歸算

37、法 設(shè)T是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹(shù)為空，則返回；否則，令p=T； 訪(fǎng)問(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)，直到?？諡橹埂Ｋ惴▽?shí)現(xiàn)：#define MAX_NODE 50void PreorderTraverse( BTNode *T) BTNode *StackMAX_NODE ,*p=T, *q ;int top=0 ;if (T=NULL) printf(“ Binary Tree is Empty!n”) ;else do visit( p- dat

38、a ) ; q=p-Rchild ; if ( q!=NULL ) stack+top=q ; p=p-Lchild ; if (p=NULL) p=stacktop ; top- ; while (p!=NULL) ;=中序遍歷的遞歸算法void InorderTraverse(BTNode *T) if (T!=NULL) InorderTraverse(T-Lchild) ;visit(T-data) ; /* 訪(fǎng)問(wèn)根結(jié)點(diǎn) */InorderTraverse(T-Rchild) ;非遞歸算法 設(shè)T是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹(shù)為空，則返回；否則，令p=T 若p不為空

39、，p進(jìn)棧， p=p-Lchild ； 否則(即p為空)，退棧到p，訪(fǎng)問(wèn)p所指向的結(jié)點(diǎn)； p=p-Rchild ，轉(zhuǎn)(1)；直到?？諡橹?。算法實(shí)現(xiàn)：#define MAX_NODE 50void InorderTraverse( BTNode *T) BTNode *StackMAX_NODE ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“ Binary Tree is Empty!n”) ; else do while (p!=NULL) stack+top=p ; p=p-Lchild ; if (top=0) bool=0 ; else

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

41、根結(jié)點(diǎn)時(shí)，還是不能訪(fǎng)問(wèn)，還需遍歷其右子樹(shù)。所以，此根結(jié)點(diǎn)還需再次進(jìn)棧，當(dāng)其右子樹(shù)遍歷完后再退棧到到該根結(jié)點(diǎn)時(shí)，才能被訪(fǎng)問(wèn)。 因此，設(shè)立一個(gè)狀態(tài)標(biāo)志變量tag ： 0 ： 結(jié)點(diǎn)暫不能訪(fǎng)問(wèn)1 ： 結(jié)點(diǎn)可以被訪(fǎng)問(wèn) 其次，設(shè)兩個(gè)堆棧S1、S2 ，S1保存結(jié)點(diǎn)，S2保存結(jié)點(diǎn)的狀態(tài)標(biāo)志變量tag 。S1和S2共用一個(gè)棧頂指針。設(shè)T是指向根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹(shù)為空，則返回；否則，令p=T； 第一次經(jīng)過(guò)根結(jié)點(diǎn)p，不訪(fǎng)問(wèn)： p進(jìn)棧S1 ， tag 賦值0，進(jìn)棧S2，p=p-Lchild 。 若p不為空，轉(zhuǎn)(1)，否則，取狀態(tài)標(biāo)志值tag ： 若tag=0：對(duì)棧S1，不訪(fǎng)問(wèn)，不出棧；修改S2棧頂

42、元素值(tag賦值1) ，取S1棧頂元素的右子樹(shù)，即p=S1top-Rchild ，轉(zhuǎn)(1)； 若tag=1：S1退棧，訪(fǎng)問(wèn)該結(jié)點(diǎn)；直到?？諡橹?。算法實(shí)現(xiàn)： #define MAX_NODE 50void PostorderTraverse( BTNode *T) BTNode *S1MAX_NODE ,*p=T ;int S2MAX_NODE , top=0 , bool=1 ;if (T=NULL) printf(“Binary Tree is Empty!n”) ;else do while (p!=NULL) S1+top=p ; S2top=0 ; p=p-Lchild ; if (top=0) bool=0 ; else if (S2top=0) p=S1top-Rchild ; S2top=1 ; else p=S1top ; top- ; visit( p-data ) ; p=NULL ; /* 使循環(huán)繼續(xù)進(jìn)行而不至于死循環(huán) */ while (bool!=0) ;=設(shè)T是指向根結(jié)點(diǎn)的指針變量，層次遍歷非遞歸算法是：若二叉樹(shù)為空，則返回；否則，令p=T，p入隊(duì)； 隊(duì)首元素出隊(duì)到p；訪(fǎng)問(wèn)p所指向的結(jié)點(diǎn)； 將p所指向的結(jié)點(diǎn)的左、右子結(jié)點(diǎn)依次入隊(duì)。直到隊(duì)空為止。#define MAX_NODE 50void LevelorderTraverse( BTNode *