《數(shù)據(jù)結(jié)構(gòu)(C語言版)》復(fù)習(xí)重點(diǎn)(總31頁)

上傳人:29 文檔編號:33773537 上傳時間:2021-10-19 格式:DOC 頁數(shù):32 大?。?.02MB
收藏 版權(quán)申訴 舉報(bào) 下載
《數(shù)據(jù)結(jié)構(gòu)(C語言版)》復(fù)習(xí)重點(diǎn)(總31頁)_第1頁
第1頁 / 共32頁
《數(shù)據(jù)結(jié)構(gòu)(C語言版)》復(fù)習(xí)重點(diǎn)(總31頁)_第2頁
第2頁 / 共32頁
《數(shù)據(jù)結(jié)構(gòu)(C語言版)》復(fù)習(xí)重點(diǎn)(總31頁)_第3頁
第3頁 / 共32頁

下載文檔到電腦,查找使用更方便

20 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《《數(shù)據(jù)結(jié)構(gòu)(C語言版)》復(fù)習(xí)重點(diǎn)(總31頁)》由會員分享,可在線閱讀,更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)(C語言版)》復(fù)習(xí)重點(diǎn)(總31頁)(32頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)(C語言版)復(fù)習(xí)重點(diǎn)重點(diǎn)在二、三、六、七、九、十章,考試內(nèi)容兩大類:概念,算法 第1章、緒論1. 數(shù)據(jù):是對客觀事物的符號表示,在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。2. 數(shù)據(jù)元素:是數(shù)據(jù)的基本單位,在計(jì)算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。3. 數(shù)據(jù)結(jié)構(gòu):是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。其4類基本結(jié)構(gòu):集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)4. 邏輯結(jié)構(gòu):是數(shù)據(jù)元素之間的邏輯關(guān)系的描述。5. 物理結(jié)構(gòu)(存儲結(jié)構(gòu)):是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱映像)。其4種存儲結(jié)構(gòu):順序存數(shù)結(jié)構(gòu)、鏈?zhǔn)酱鏀?shù)結(jié)構(gòu)、索引存數(shù)結(jié)構(gòu)、散列存數(shù)結(jié)構(gòu)6

2、. 算法:是對特定問題求解步驟的一種描述,它是指令的有限序列,其中每一條指令表示一個或多個操作。其5個重要特性:有窮性、確定性、可行性、輸入、輸出7. 時間復(fù)雜度:算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間度量記作,T(n)=O(f(n) ;他表示隨問題規(guī)模n的增大,算法執(zhí)行時間的增長率和f(n)的增長率相同,稱做算法的漸進(jìn)時間復(fù)雜度,簡稱時間復(fù)雜度。例如: (a) +x;s=0;(b) for(i=1;i=n;+i)+x;s += x;(c) for(j=1;j=n;+j)for(k=1;knext為第一個結(jié)點(diǎn)地址,L-next=NULL為空表。生成結(jié)點(diǎn):p=(L

3、inkList)malloc(sizeof(LNode)回收結(jié)點(diǎn):free(q)2) 循環(huán)鏈表特點(diǎn):表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn),整個鏈表形成一個環(huán)。循環(huán)鏈表的操作與線性鏈表基本一致,差別僅在于算法中的循環(huán)條件不是P或P-next是否為空,而是它們是否等于頭指針。3) 雙向鏈表特點(diǎn):有2個指針域,其一指向直接后繼,另一指向直接前趨。第3章、棧和隊(duì)列1. 棧:是限定僅在表尾進(jìn)行插入或刪除操作的線性表。表尾端稱為棧頂,表頭端稱為棧底,不含有元素的空表稱為空棧;棧又稱為后進(jìn)先出的線性表。2. 隊(duì)列:是一種先進(jìn)先出的線性表,它只允許在表的一端進(jìn)行插入,而另一端刪除元素。允許插入的一端叫做隊(duì)尾,允

4、許刪除的一端則稱為隊(duì)頭。1) 鏈隊(duì)列:用鏈表示的隊(duì)列。一個隊(duì)列需要兩個分別指示隊(duì)頭和隊(duì)尾的指針(分別成為頭指針和尾指針)才能確定唯一。和單鏈表一樣,也給鏈隊(duì)列添加一個頭結(jié)點(diǎn),并令頭指針指向頭結(jié)點(diǎn)。2) 循環(huán)隊(duì)列:與順序棧類似,除了用一組地址連續(xù)的存儲單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外,尚需附設(shè)兩個指針front和rear分別指示隊(duì)列頭元素及隊(duì)列尾元素的位置。初始化建空隊(duì)列時,令front = rear = 0,每當(dāng)插入新的隊(duì)列尾元素時,“尾指針增1”;每當(dāng)刪除隊(duì)列頭元素時,“頭指針增1”。第4章、串1. 串:是由零個或多個字符組成的有限序列。第5章、數(shù)組和廣義表1. 數(shù)組特點(diǎn):與線性表一樣

5、,所有數(shù)據(jù)元素都必須屬于同一數(shù)據(jù)類型。2. 數(shù)組的順序存儲結(jié)構(gòu):由于數(shù)組一般不作插入或刪除操作,一旦建立了數(shù)組,則結(jié)構(gòu)中的數(shù)據(jù)元素個數(shù)和元素之間的關(guān)系就不會發(fā)生變動,因此采用順序存儲結(jié)構(gòu)表示數(shù)組。存儲位置計(jì)算:假設(shè)每個數(shù)據(jù)元素需占用L個存儲單元,則二維數(shù)組A中任一元素aij的存儲位置可由下式確定以行序?yàn)橹餍虻拇鎯Y(jié)構(gòu):LOC(i,j)=LOC(0,0)+(b2*i+j)*L以列序?yàn)橹餍虻拇鎯Y(jié)構(gòu):LOC(i,j)=LOC(0,0)+(b2*j+i)*L式中LOC(i,j)是aij的存儲位置;LOC(0,0)是a00的存儲位置,即二維數(shù)組A的起始存儲位置,也稱基地址或基址;b2在以行序?yàn)橹餍虻拇?/p>

6、儲結(jié)構(gòu)時為每行存儲元素的個數(shù)(列數(shù)),在以列序?yàn)橹餍虻拇鎯Y(jié)構(gòu)時為每列存儲元素的個數(shù)(行數(shù))。3. 廣義表:是線性表的推廣,也有人稱其為列表(lists,用復(fù)數(shù)形式以示與統(tǒng)稱的表list的區(qū)別)。記作LS=(a1,a2,an) ,其中LS是廣義表(a1,a2,an)的名稱,n是它的長度。在線性表的定義中,ai(1in)只限于是單個元素。而在廣義表的定義中,ai可以是單個元素,也可以是廣義表,分別稱為廣義表LS的原子和子表。例如:第6章、樹和二叉樹1. 二叉樹:是一種樹型的結(jié)構(gòu),它的特點(diǎn)是每個結(jié)點(diǎn)至多只有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點(diǎn)),并且,二叉樹的子樹有左右之分,其次序不能任意顛倒

7、。2. 二叉樹的性質(zhì):1) 性質(zhì)1:在二叉樹的第i層上至多有2的i減1次方個結(jié)點(diǎn)(i1)。2) 性質(zhì)2:深度為k的二叉樹至多有2的k次方減1個結(jié)點(diǎn)(k1)。深度為k的二叉樹至少有k個結(jié)點(diǎn)(k1)。深度為k的完全二叉樹至少有2的k次方減2的k減1次方個結(jié)點(diǎn)(k1)。3) 性質(zhì)3:對任何一棵二叉樹T,如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。4) 性質(zhì)4:具有n個結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。5) 性質(zhì)5:如果對一棵有n個結(jié)點(diǎn)的完全二叉樹(其深度為log2n+1)的結(jié)點(diǎn)按層序編號(從第1層到第log2n+1層,每層從左到右),則對任一結(jié)點(diǎn)i(1in)有:a) 如果i

8、=1,則結(jié)點(diǎn)i是二叉樹的根,無雙親;如果i1,則其雙親PARENT(i)是結(jié)點(diǎn)i/2。b) 如果2in,則結(jié)點(diǎn)i無左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn));否則其左孩子LCHILD(i)是結(jié)點(diǎn)2i。c) 如果2i+1n,則結(jié)點(diǎn)i無右孩子;否則其右孩子RCHILD(i)是結(jié)點(diǎn)2i+1。3. 滿二叉樹:一顆深度為k且有 2的k次方減1個結(jié)點(diǎn)的二叉樹。4. 完全二叉樹:深度為k的,有n個結(jié)點(diǎn)的二叉樹,當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)。5. 遍歷二叉樹:1) 根據(jù)二叉樹寫遍歷結(jié)果:a) 先序遍歷(先根遍歷):DLR- + a * b - c d / e fb) 中序遍歷(中根遍

9、歷):LDRa + b * c - d - e / fc) 后序遍歷(后根遍歷):LRDa b c d - * + e f / -2) 根據(jù)遍歷結(jié)果畫二叉樹:一棵二叉樹的先序、中序和后序序列分別如下,其中有部分未給出,試求出空格處的結(jié)點(diǎn)字符,并畫出該二叉樹。先序:_B_EHI_FG_K中序:D_HEIA_CJG_后序:_H_EBF_KG_A解題思路:a) 由先序或后序確定根結(jié)點(diǎn);如本題后序最后一個為A,根結(jié)點(diǎn)為A,所以先序第一個空就為A。b) 在中序找出根結(jié)點(diǎn),根結(jié)點(diǎn)左側(cè)為左子樹,右側(cè)為右子樹;如本題D_HEI為左子樹,_CJG_為右子樹。c) 由先序確定緊跟在根結(jié)點(diǎn)后的左子樹根;如本題緊跟在

10、A后的是B,B為左子樹根,中序根結(jié)點(diǎn)的左子樹只有一個空,所以為B。d) 繼續(xù)由中序確定左子樹根的左右子樹,左側(cè)為左子樹,右側(cè)為右子樹;如本題B的左子樹為D,右子樹為HEI,所以先序第二個空為D。e) 重復(fù)c)、d)步驟確定整棵左子樹;如本題先序中緊跟在D后的是E,E為B的右子樹,由中序中看出E左子樹為H,右子樹為I,補(bǔ)充后序填空,前兩空分別為D和I。f) 由后序確定右子樹根的左子樹,再由中序確定右子樹根;如本題緊跟在B后的是F,F(xiàn)為右子樹根的左子樹,已知中序_CJG_為右子樹,F(xiàn)只可能第一個空,那第二個空為K,補(bǔ)全先序、中序、后序填空并可畫出二叉樹。6. 森林與二叉樹的轉(zhuǎn)換:1) 樹轉(zhuǎn)換成二叉

11、樹:連兄弟,留長子,刪孩子。a) 連線,連接所有兄弟結(jié)點(diǎn)。b) 刪線,僅保留雙親與長子結(jié)點(diǎn)的連線,刪除與其他孩子結(jié)點(diǎn)之間的連線。c) 整理,原有的長子結(jié)點(diǎn)為左子樹,從兄弟轉(zhuǎn)換為孩子的結(jié)點(diǎn)為右子樹。d) 注意,由于樹根沒有兄弟結(jié)點(diǎn),固樹轉(zhuǎn)換為二叉樹后,二叉樹根結(jié)點(diǎn)的右子樹必為空。2) 森林轉(zhuǎn)換成二叉樹:連樹根及兄弟,留長子,刪孩子。a) 連線,連接每棵樹的根結(jié)點(diǎn)及所有兄弟結(jié)點(diǎn)。b) 刪線,僅保留雙親與長子結(jié)點(diǎn)的連線,刪除與其他孩子結(jié)點(diǎn)之間的連線。c) 整理,第一棵樹根結(jié)點(diǎn)為二叉樹根結(jié)點(diǎn),原有的長子結(jié)點(diǎn)為左子樹,從兄弟轉(zhuǎn)換為孩子的結(jié)點(diǎn)為右子樹。3) 二叉樹轉(zhuǎn)換成樹:連左孩子的右孩子及其右孩子,刪原

12、樹右孩子。a) 連線,若某結(jié)點(diǎn)X存在左孩子XL,則將這個左孩子的右孩子結(jié)點(diǎn)XLR、左孩子的右孩子的右孩子結(jié)點(diǎn)XLRR、左孩子的右孩子的右孩子的右孩子結(jié)點(diǎn)XLRRR都與X結(jié)點(diǎn)連線。b) 刪線,刪除原二叉樹的所有雙親與右孩子結(jié)點(diǎn)的連線。c) 整理,原二叉樹根結(jié)點(diǎn)為樹根結(jié)點(diǎn)。4) 二叉樹轉(zhuǎn)換成森林:連左孩子的右孩子及其右孩子,刪原樹右孩子。a) 連線,若某結(jié)點(diǎn)X存在左孩子XL,則將這個左孩子的右孩子結(jié)點(diǎn)XLR、左孩子的右孩子的右孩子結(jié)點(diǎn)XLRR、左孩子的右孩子的右孩子的右孩子結(jié)點(diǎn)XLRRR都與X結(jié)點(diǎn)連線。b) 刪線,刪除原二叉樹的所有雙親與右孩子結(jié)點(diǎn)的連線。c) 整理,調(diào)整為多棵樹的森林。7. 赫夫

13、曼樹:又稱最優(yōu)樹,是一類帶權(quán)路徑長度最短的樹。a) 兩個最小數(shù)值組成一對,小的在前,大的在后;如上圖中2與4最小,2在前,4在后。b) 將兩個最小數(shù)值的和算作一個數(shù),再與其他數(shù)重復(fù)a)步驟;如上圖中2與4的和為6,5與6最小,5在前,6在后。c) 最后計(jì)算WPL,它等于每個數(shù)值乘以從根結(jié)點(diǎn)到這個數(shù)值的連線個數(shù)的積之和;如上圖中WPL=2*3+4*3+5*2+7*1=35。8. 赫夫曼編碼:a) 在赫夫曼樹上,左分支代表0,右分支代表1。b) 由根結(jié)點(diǎn)到指定結(jié)點(diǎn)的路徑(從上到下把0、1連起來),就是該結(jié)點(diǎn)的赫夫曼編碼;如上圖(d)中a為0,b為10,c為110,d為111。第7章、圖1. 圖:多

14、個結(jié)點(diǎn),結(jié)點(diǎn)之間的關(guān)系可以是任意的,圖中任意兩個數(shù)據(jù)元素之間都有可能相關(guān)。2. 無向完全圖:有n(n-1)/2條邊的無向圖。3. 有向完全圖:有n(n-1)條邊的有向圖。4. 入度:以頂點(diǎn)V為頭的弧的數(shù)目稱為V的入度。5. 出度:以V為尾的弧的數(shù)目稱為V的出度。6. 連通圖:在無向圖中,任意兩個頂點(diǎn)之間都有路徑。7. 連通分量:在無向圖中的極大連通子圖。8. 鄰接矩陣:無向圖的鄰接矩陣關(guān)于主對角線對稱,在整個矩陣中非零元素的個數(shù)等于邊個數(shù)的2倍,第i行和第i列中非零元素的個數(shù)等于該結(jié)點(diǎn)的度。9. 鄰接表:無向圖的鄰接矩陣關(guān)于主對角線對稱,在整個矩陣中非零元素的個數(shù)等于邊個數(shù)的2倍,第i行和第i

15、列中非零元素的個數(shù)等于該結(jié)點(diǎn)的度。10. 深度優(yōu)先遍歷:從圖中某個頂點(diǎn)出發(fā),搜索與之相關(guān)聯(lián)的頂點(diǎn),選擇一個訪問(從左到右,從上到下);再從該頂點(diǎn)出發(fā),搜索與之相關(guān)聯(lián)且未訪問過的頂點(diǎn),選擇一個訪問;重復(fù)上步驟,直到?jīng)]有相關(guān)聯(lián)且未訪問過的頂點(diǎn);后退一個頂點(diǎn)繼續(xù)搜索訪問,直到所有頂點(diǎn)都被訪問過。a) 從V0出發(fā),先找到V0的關(guān)聯(lián)頂點(diǎn)V3。b) 由V3出發(fā),找到V1;由V1出發(fā),沒有關(guān)聯(lián)的頂點(diǎn)。c) 回到V3,從V3出發(fā),找到V2;由V2出發(fā),沒有關(guān)聯(lián)的頂點(diǎn)。d) 回到V3,再回到V0,由V0出發(fā),找到V4。e) 從V4出發(fā),找到V1,因?yàn)閂1已經(jīng)被訪問過了,所以不訪問。所以最后順序是V0, V3,

16、V1, V2, V4。11. 廣度優(yōu)先遍歷:從圖中某個頂點(diǎn)出發(fā),搜索與之相關(guān)聯(lián)的頂點(diǎn),逐個訪問(從左到右,從上到下);再從這些頂點(diǎn)出發(fā),搜索與之相關(guān)聯(lián)且未訪問過的頂點(diǎn),逐個訪問;重復(fù)上步驟,直到所有頂點(diǎn)都被訪問過。a) 從V0出發(fā),先找到V0的關(guān)聯(lián)頂點(diǎn)V3、V4。b) 由V3出發(fā),找到V1、V2;由V4出發(fā),找到V1,因?yàn)閂1已經(jīng)被訪問過了,所以不訪問。c) 由V1出發(fā),沒有關(guān)聯(lián)的頂點(diǎn);由V2出發(fā),沒有關(guān)聯(lián)的頂點(diǎn)。所以最后順序是V0, V3, V4, V1, V2。12. 最小生成樹:1) 普里姆算法:連相鄰權(quán)值最小的。2) 克魯斯卡爾算法:先連權(quán)值最小的,再依次連。13. 拓?fù)渑判颍河赡硞€集

17、合上的一個偏序得到該集合上的一個全序的操作。14. 關(guān)鍵路徑:路徑長度最長的路徑。1) 如圖,先求各事件的最早發(fā)生時間(順序?yàn)閂1V9)V1的最早發(fā)生時間為0,V2的最早發(fā)生時間為6,V3的最早發(fā)生時間為4,V4的最早發(fā)生時間為5。對于V5,需要V2,V3均發(fā)生,V2發(fā)生且完成的時間為6+1=7;V3發(fā)生且完成的時間為4+1=5,因而V5的最早發(fā)生時間為7。同理可求出各頂點(diǎn)的最早發(fā)生時間:V1V2V3V4V5V6V7V8V9e(i)0645771614182) 求各事件的最晚發(fā)生時間(順序?yàn)閂9V1)V9的最晚時間為18,V8的最晚時間為18-a11=14,V7的最晚時間為18-a10=16,

18、V6的最晚時間為14-a9=10,V5的最晚時間為V7的最晚時間減去a7和V8的最晚時間減去a8兩者較小的,則V5的最晚時間為7,同理可得其他頂點(diǎn)的最晚發(fā)生時間:V1V2V3V4V5V6V7V8V9l(i) 0668710161418則li與ei相等的事件即為關(guān)鍵事件即:V1,V2,V5,V7,V8,V9可得關(guān)鍵路徑:V1,V2,V5,V7,V9或V1,V2,V5,V8,V93) 求各活動的最早發(fā)生時間a1a2a3a4a5a6a7a8a9a10a11e(i)00064577716144) 求各活動的最晚發(fā)生時間a1a2a3a4a5a6a7a8a9a10a11l(i)6-6=06-4=28-5=

19、37-1=67-1=610-2=816-9=714-7=714-4=1018-2=1618-4=14則li與ei相等的活動即為關(guān)鍵活動即:a1,a4,a7,a8,a10,a11可得關(guān)鍵路徑:V1,V2,V5,V7,V9或V1,V2,V5,V8,V915. 最短路徑:從某頂點(diǎn)出發(fā),沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中,各邊上權(quán)值之和最小的一條路徑。1) 迪杰斯特拉算法:2) 弗洛伊德算法:方法:兩條線,從左上角開始計(jì)算一直到右下角 如下所示:給出矩陣,其中矩陣A是鄰接矩陣,而矩陣Path記錄u,v兩點(diǎn)之間最短路徑所必須經(jīng)過的點(diǎn)。最后A3即為所求結(jié)果。第9章、查找1. 查找表:是由同一類型的數(shù)據(jù)元素

20、(或記錄)構(gòu)成的集合。2. 關(guān)鍵字:是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項(xiàng)的值,用它可以標(biāo)識(識別)一個數(shù)據(jù)元素(或記錄)。3. 靜態(tài)查找表:查詢某個特定的數(shù)據(jù)元素是否在查找表中,檢索某個特定的數(shù)據(jù)元素的各種屬性。1) 順序查找法:從表中最后一個記錄開始,逐個進(jìn)行記錄的關(guān)鍵字和給定值比較,若某個記錄的關(guān)鍵字和給定值比較相等,則查找成功,找到所查記錄;反之若直至第一個記錄,其關(guān)鍵字和給定值比較都不相等,則表明表中沒有所查記錄,查找不成功。其存儲結(jié)構(gòu)要求:以順序表或線性鏈表表示的靜態(tài)查找表。其平均查找長度:假設(shè)每個記錄的查找概率相等,即Pi=1/n,則在等概率情況下順序查找的平均查找長度為,ASL=(n

21、+1)/2。2) 折半查找法(二分查找法):先確定待查記錄所在的范圍(區(qū)間),然后逐步縮小范圍直到找到或找不到該記錄為止。其存儲結(jié)構(gòu)要求:以有序表表示的靜態(tài)查找表。其平均查找長度:假設(shè)表中每個記錄的查找概率相等(Pi=1/n),則查找成功時折半查找的平均查找長度為,ASL=(n+1)/n*log2(n+1)-1。3) 索引順序表查找法(分塊查找法):先確定待查記錄所在的塊(子表),然后在塊中順序查找。其存儲結(jié)構(gòu)要求:以索引順序表表示的靜態(tài)查找表。其平均查找長度:將長度為n的表均勻地分成b塊,每塊含有s個記錄,即b=n/s;又假設(shè)表中每個記錄的查找概率相等,則每塊查找概率為1/b,塊中每個記錄的

22、查找概率為1/s,若用順序查找確定所在塊,則分塊查找的平均查找長度為,ASL=(n/s+s)/2+1;若用折半查找確定所在塊,則分塊查找的平均查找長度為,ASLlog2(n/s+1)+s/2。4. 動態(tài)查找表:在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素,或者從查找表中刪除已存在的某個數(shù)據(jù)元素。1) 二叉排序樹:或者是一棵空樹;或者是具有下列性質(zhì)的二叉樹:1、若它的左子樹不空,則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;2、若它的右子樹不空,則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值;3、它的左、右子樹也分別為二叉排序樹。2) 平衡二叉樹(AVL樹):它或者是一棵空樹;或者是具有下列性質(zhì)的二叉

23、樹:它的左子樹和右子樹都是平衡二叉樹,且左子樹和右子樹的深度之差的絕對值不超過1。若將二叉樹上結(jié)點(diǎn)的平衡因子BF定義為該結(jié)點(diǎn)的左子樹的深度減去它的右子樹的深度,則平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能是 -1、0和1。只要二叉樹上有一個結(jié)點(diǎn)的平衡因子的絕對值大于1,則該二叉樹就是不平衡的。下面即四種情況分別為:左左、右右、左右、右左,每種情況又有兩個圖、,是該情況的最簡單的圖形,是該情況的一般的圖形。設(shè)x為最小不平衡子樹的根結(jié)點(diǎn),y為剛插入的點(diǎn)左左:即在x的左孩子a的左孩子c上插入一個結(jié)點(diǎn)y(該結(jié)點(diǎn)也可以是c,如圖),即y可以是c,也可以是c的左孩子(如圖),也可以是c的右孩子(不在畫出)。圖就

24、不用說了,結(jié)點(diǎn)x和結(jié)點(diǎn)a變換,則樹平衡了;那么圖就是樹中的一般情況了a結(jié)點(diǎn)有右孩子d,那要進(jìn)行x和a變換,那么a的右孩子放哪啊?很簡單,如圖放在x的左孩子上;分析:xd,da,所以d可作為x的左孩子,且可作為a的右孩子中的孩子。下邊這樣的類似情況不再一一分析,自己分析分析實(shí)現(xiàn):找到根結(jié)點(diǎn)x,與它的左孩子a進(jìn)行交換即可使二叉樹樹再次平衡;右右:即在x的右孩子a的右孩子c上插入一個結(jié)點(diǎn)y(該結(jié)點(diǎn)也可以是c,如圖),即y可以是c,也可以是c的右孩子(如圖),也可以是c的左孩子(不在畫出)。實(shí)現(xiàn):找到根結(jié)點(diǎn)x,與它的右孩子a進(jìn)行交換即可使二叉樹樹再次平衡;左右:即在x的左孩子a的右孩子c上插入一個結(jié)點(diǎn)

25、y(該結(jié)點(diǎn)也可以是c,如圖),即y可以是c,也可以是c的右孩子(如圖),也可以是c的左孩子(不在畫出)。這個左右和下邊的右左,稍微復(fù)雜了點(diǎn),需要進(jìn)行兩次交換,才能達(dá)到平衡,注意這時y是c的右孩子,最終y作為x的左孩子;若y是c的左孩子,最終y作為a的右孩子,畫圖分析一下下邊類似,不再敖述。實(shí)現(xiàn):找到根結(jié)點(diǎn)x,讓x的左孩子a與x的左孩子a的右孩子c進(jìn)行交換,然后再讓x與x此時的左孩子c進(jìn)行交換,最終達(dá)到平衡;右左:即在x的右孩子a的左孩子c上插入一個結(jié)點(diǎn)y(該結(jié)點(diǎn)也可以是c,如圖),即y可以是c,也可以是c的右孩子(如圖),也可以是c的左孩子(不在畫出)。實(shí)現(xiàn):找到根結(jié)點(diǎn)x,讓x的右孩子a與x的

26、右孩子a的左孩子c進(jìn)行交換,然后再讓x與x此時的右孩子c進(jìn)行交換,最終達(dá)到平衡; 上邊的四種情況包含了所有插入時導(dǎo)致不平衡的情況,上面給出的僅僅是一棵大樹中的最小不平衡子樹,一定要想清楚,別迷了!另外一定要注意這個交換操作,比如a與b交換(a在上,b在下),b一定要占據(jù)a的位置!什么意思?就是b要放在(覆蓋)儲存a的那塊內(nèi)存上,再通俗點(diǎn)說,若a是x的左孩子,則交換后b要做x的左孩子;這就是所謂的b占據(jù)a的位置!5. 哈希表:1) 構(gòu)造方法:a) 直接定址法:取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即H(key)=key或H(key) = akey + b,其中a和b為常數(shù)(這種散列函數(shù)叫做

27、自身函數(shù))。若其中H(key)中已經(jīng)有值了,就往下一個找,直到H(key)中沒有值了,就放進(jìn)去。b) 數(shù)字分析法:分析一組數(shù)據(jù),比如一組員工的出生年月日,這時我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同,這樣的話,出現(xiàn)沖突的幾率就會很大,但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大,如果用后面的數(shù)字來構(gòu)成散列地址,則沖突的幾率會明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律,盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。c) 平方取中法:當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時,可以先求出關(guān)鍵字的平方值,然后按需要取平方值的中間幾位作為哈希地址。這是因?yàn)椋浩椒胶笾虚g幾位和關(guān)鍵字中每一位都相關(guān)

28、,故不同關(guān)鍵字會以較高的概率產(chǎn)生不同的哈希地址。d) 折疊法:將關(guān)鍵字分割成位數(shù)相同的幾部分,最后一部分位數(shù)可以不同,然后取這幾部分的疊加和(去除進(jìn)位)作為散列地址。數(shù)位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一部分的最低位對齊,然后相加;間界疊加是從一端向另一端沿分割界來回折疊,然后對齊相加。e) 除留余數(shù)法:取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p=m。不僅可以對關(guān)鍵字直接取模,也可在折疊、平方取中等運(yùn)算之后取模。對p的選擇很重要,一般取素?cái)?shù)或m,若p選的不好,容易產(chǎn)生同義詞。2) 處理沖突方法:a)

29、開放定址法:Hi=(H(key) + di) MOD m,i=1,2,k(k=m-1),其中H(key)為散列函數(shù),m為散列表長,di為增量序列,可有下列三種取法:1.1. di=1,2,3,m-1,稱線性探測再散列;1.2. di=12,-12,22,-22,32,k2,(kL.r2.key),則將兩個記錄交換之,然后比較第二個記錄和第三個記錄的關(guān)鍵字。以此類推,直至第n-1個記錄和第n個記錄的關(guān)鍵字進(jìn)行過比較為止。5. 快速排序:通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分,其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小,則可分別對這兩部分記錄繼續(xù)進(jìn)行排序,以達(dá)到整個序列有序。6. 堆排序:只需要一個記錄大小的輔助空間,每個待排序的記錄僅占有一個存儲空間。

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!