②森林中第一棵樹的根結(jié)點(diǎn)就是轉(zhuǎn)換后二叉樹的根結(jié)點(diǎn)，依次將后一棵樹作為前一棵樹根結(jié)點(diǎn)的右子樹。

　　二叉樹轉(zhuǎn)換為森林的步驟是:

　　①森林第一棵樹的根就是二叉樹的根;

　　②二叉樹的左子樹轉(zhuǎn)換為森林的第一棵樹，二叉樹的右子樹對(duì)應(yīng)于森林中其余的樹;③二叉樹右子樹的根結(jié)點(diǎn)作為余下樹中第一棵樹的根結(jié)點(diǎn)……，以此類推。

　　五、圖

　　圖的概念

　　圖是一種較線性表和樹形結(jié)構(gòu)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中每個(gè)數(shù)據(jù)元素只有一個(gè)(直接)前驅(qū)和后繼，即各數(shù)據(jù)元素之間僅有線性關(guān)系。在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有明顯的層次關(guān)系，每一層中的數(shù)據(jù)元素只和上一層中的一個(gè)元素(即雙親結(jié)點(diǎn))相關(guān)。而在圖中，任意兩個(gè)數(shù)據(jù)元素之間均有可能相關(guān)。

　　圖(graph)是圖型結(jié)構(gòu)的簡(jiǎn)稱。它是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。圖在各個(gè)領(lǐng)域都有著廣泛的應(yīng)用。圖的二元組定義為:

　　G=(V，E)

　　其中，V是非空的頂點(diǎn)集合，即

　　V={v i |1≤i≤n，n≥1，v i ∈elemtype，n為頂點(diǎn)數(shù)｝

　　E是V上二元關(guān)系的集合，一般只討論僅含一個(gè)二元關(guān)系的情況，且直接用E表示這個(gè)關(guān)系。這樣，E就是V上頂點(diǎn)的序偶或無序?qū)?每個(gè)無序?qū)?x，y)是兩個(gè)對(duì)稱序偶和的簡(jiǎn)寫形式)的集合。對(duì)于V上的每個(gè)頂點(diǎn)，在E中都允許有任意多個(gè)前驅(qū)和任意多個(gè)后繼，即對(duì)每個(gè)頂點(diǎn)的前驅(qū)和后繼個(gè)數(shù)均不加限制。回顧一下線性表和樹的二元組定義，都是在其二元關(guān)系上規(guī)定了限制條件，線性表的限制條件是只允許每個(gè)結(jié)點(diǎn)有一個(gè)前驅(qū)和一個(gè)后繼，樹的限制條件是只允許每個(gè)結(jié)點(diǎn)有一個(gè)前驅(qū)。因此，圖比線性表和樹更具有廣泛性，它包含線性表和樹在內(nèi)，線性表和樹可以認(rèn)為是圖的簡(jiǎn)單情況。

　　快速排序的基本思想是把表中某元素作為基準(zhǔn)，將表劃分為大于該值和小于該值的兩部分，然后用遞歸的方法處理這兩個(gè)子表，直到完成整個(gè)表的排序。快速排序的比較次數(shù)為(n-1)+(n-2)+…+1=n(n-1)/2，移動(dòng)次數(shù)最多也是n(n-1)/2。如果每次的基準(zhǔn)元素剛好是表的中值，使表分為大小相等的兩個(gè)子表，則比較次數(shù)為nlog 2 n;如果表已排好序，則移動(dòng)次數(shù)為0。

　　6.常用排序方法的性能比較如下表所示:

　　常用排序方法的性能比較

　　排序方法 平均時(shí)間 最壞情況的時(shí)間 輔助存儲(chǔ)

　　冒泡法、直接選擇法、直接插入法 O(n2 ) O(n2 ) O(1)

　　快速排序 O(nlog2 n) O(n2 ) O(log2 n)

　　堆排序 O(nlog2n) O(nlog2 n) O(1)

　　歸并排序 O(nlog2 n) O(nlog2 n) O(n)

　　注:在上表中，我們將n(n-1)/2也記為O(n2 )。如果在待排序的表中含有多個(gè)碼值相同的記錄，經(jīng)過排序后，這些記錄的相對(duì)次序不變，則稱這種排序方法是穩(wěn)定的，否則是不穩(wěn)定的。根據(jù)上述說法，可以看出直接插入法、歸并法是穩(wěn)定的;而直接選擇法、冒泡法、快速排序法、堆排序法是不穩(wěn)定的。

　　七、檢索

　　1.順序檢索

　　檢索又稱為查找。順序檢索是將待查找的關(guān)鍵碼值與線性表中個(gè)結(jié)點(diǎn)的關(guān)鍵碼值逐一比較，直到找到所需的記錄，檢索成功;或者在表中找不到所需記錄而檢索失敗。順序檢索不要求線性表事先排序。設(shè)線性表有n個(gè)元素，則最多檢索次數(shù)為n，最少檢索次數(shù)為1。

　　2.二分法檢索

　　二分法檢索要求線性表結(jié)點(diǎn)按關(guān)鍵排序且以順序方式存儲(chǔ)。在查找時(shí)，首先與表的中間位置上結(jié)點(diǎn)的關(guān)鍵值比較，若相等則檢索成功;否則根據(jù)比較結(jié)果確定下一步在表的前半部或后半部中繼續(xù)進(jìn)行。二分法檢索的效率較主動(dòng)，設(shè)線性表有n個(gè)元素，則最多的檢索次數(shù)為大于log 2 n的最小整數(shù)，最少的檢索次數(shù)為1。

　　3.分塊檢索

　　分塊檢索把線性表分成若干塊，塊內(nèi)結(jié)點(diǎn)不必有序，但塊與塊之間必須有序，即每一塊中各結(jié)點(diǎn)的關(guān)鍵值必須大于(或小于，與此類推)前一塊最大關(guān)鍵值。為加快查找，還要建立一個(gè)索引表，表中給出每一塊的最大關(guān)鍵值和指向塊內(nèi)第一個(gè)結(jié)點(diǎn)位置的指針。分塊檢索分兩步進(jìn)行，先查索引表，確定要找的記錄在哪一塊;然后再在相應(yīng)的塊中檢索。分塊檢索適合于線性表很大，數(shù)據(jù)又是動(dòng)態(tài)變化的情況。在查索引表時(shí)，可采用順序法或二分法;在塊內(nèi)查找所求記錄時(shí)，采用順序法。由于分塊而縮小了查找范圍，從而加快檢索速。

　　4.散列表檢索

　　根據(jù)關(guān)鍵值，就可以迅速找到該記錄所對(duì)應(yīng)的存儲(chǔ)位置，這就是建立在散列函數(shù)基礎(chǔ)上的散列檢索。設(shè)記錄的關(guān)鍵值為k，則該記錄的存儲(chǔ)位置可用散列函數(shù)H來計(jì)算H=H(k)。常用來產(chǎn)生的散列函數(shù)的方法是除余法，即取H(k)=k mod p設(shè)散列表長(zhǎng)度為n，取p為小于n的最大素?cái)?shù)。一般說來，關(guān)鍵碼值的集合比散列表存儲(chǔ)位的數(shù)目大得多，這正是體現(xiàn)散列表的優(yōu)勢(shì)所在，但同時(shí)帶來了沖突問題，即不同的關(guān)鍵值經(jīng)散列函數(shù)計(jì)算，可能得到相同的存儲(chǔ)位置。一個(gè)好的散列函數(shù)應(yīng)該使沖突的可能性盡量小。最常用的解決沖突的方法是線性探測(cè)法，就是在發(fā)生沖突時(shí)，從H(k)以后的位置逐一探測(cè)，直至找到一個(gè)空位置，將新記錄插入;在檢索時(shí)，如果H(k)中不是所需關(guān)鍵值的記錄，也是從H(k)往下逐一搜索，直到找到所需關(guān)鍵值或查找失敗為止。應(yīng)注意查找次序是:H(k)，H(k)+1，H(k)+2，…n-1，0，1，2，…，H(k)-1即在n-1以后，又從0開始，因?yàn)樵谖恢蒙鲜茄h(huán)的。雙重散列技術(shù)是對(duì)線性探測(cè)法的改進(jìn)。它使用兩個(gè)散列函數(shù)H1和H2。對(duì)關(guān)鍵值k，計(jì)算H1(k)，求得0到n-1之間的一個(gè)散列地址;若在這個(gè)地址上沖突，下一個(gè)被探測(cè)的地址為(H1(k)+H2(k))mod n，關(guān)于選擇H2的方法在此不做討論。