1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記一、緒論1.數(shù)據(jù)：能被計(jì)算機(jī)表示、存儲(chǔ)和加工處理的一切信息（數(shù)值型和非數(shù)值型）2.數(shù)據(jù)的基本單位：數(shù)據(jù)元素3.組成數(shù)據(jù)元素的不可分割的最小單位：數(shù)據(jù)項(xiàng)4.數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合5.數(shù)據(jù)類型：指定一種數(shù)據(jù)對(duì)象的類型6.數(shù)據(jù)的邏輯結(jié)構(gòu)：指數(shù)據(jù)之間的邏輯關(guān)系, 即指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或鄰接關(guān)系7.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：指數(shù)據(jù)在計(jì)算機(jī)中存儲(chǔ)的位置8.運(yùn)算的集合：定義在邏輯結(jié)構(gòu)上的一組操作9.數(shù)據(jù)結(jié)構(gòu): 按照某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù), 按一定的存儲(chǔ)方法把它存儲(chǔ)在計(jì)算機(jī)中, 并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合10.邏輯結(jié)構(gòu)分類：線性結(jié)構(gòu)、集合、樹(shù)形結(jié)構(gòu)、圖型或網(wǎng)狀結(jié)構(gòu)11.

2、線性結(jié)構(gòu)：僅一個(gè)開(kāi)始結(jié)點(diǎn)、僅一個(gè)終端結(jié)點(diǎn)；其它都是內(nèi)部結(jié)點(diǎn)，且都有且僅有一個(gè)前驅(qū)和一個(gè)后驅(qū)（一對(duì)一）12.集合：結(jié)構(gòu)中數(shù)據(jù)元素只具有“同屬于一個(gè)集合”的關(guān)系13.樹(shù)型結(jié)構(gòu)的特點(diǎn)：有且僅有一個(gè)根結(jié)點(diǎn)，其它結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)，對(duì)于非根結(jié)點(diǎn)都存在從根到該結(jié)點(diǎn)的一條路徑（一對(duì)多）14.圖型結(jié)構(gòu)的特點(diǎn)：結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系15.存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)16.順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：邏輯結(jié)構(gòu)上相鄰的兩個(gè)元素在物理結(jié)構(gòu)上也相鄰. 即前驅(qū)的結(jié)束是后繼的開(kāi)始17.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：存儲(chǔ)空間不連續(xù)，但保持了邏輯關(guān)系18.算法的五個(gè)特征：有窮性、確定性、可行性、輸入、輸出19.算法與程序的區(qū)別：

3、程序不一定滿足有窮性；程序是機(jī)器可執(zhí)行的語(yǔ)言編寫(xiě)的20.算法評(píng)價(jià)：正確、簡(jiǎn)單、可讀、健壯、高效21.算法分析方法：事后統(tǒng)計(jì)和事前分析、時(shí)間復(fù)雜度和空間復(fù)雜度22.影響算法時(shí)間代價(jià)的因素：輸入規(guī)模、算法效率、輸入順序、機(jī)器、設(shè)計(jì)者23.(1)O(log2n)O (n)O (nlog2n)O (n2)O (n3)O (2n)O (n!)二、線性表1.線性結(jié)構(gòu)特點(diǎn)：唯一第一數(shù)據(jù)元素、唯一最后數(shù)據(jù)元素、其他數(shù)據(jù)元素僅有一個(gè)前趨和僅有一個(gè)后驅(qū)2.順序表的優(yōu)點(diǎn)：無(wú)需為表示數(shù)據(jù)元素之間的邏輯關(guān)系而增加額外存儲(chǔ)空間；可方便地隨機(jī)存取表中任一元素3.順序表的缺點(diǎn)：預(yù)先為數(shù)據(jù)元素分配空間；插入和刪除時(shí)必須移動(dòng)大量

4、元素4.單鏈表的插入：newnodenext = pnext；pnext = newnode5.單鏈表的刪除：pnext = qnext；delete q6.雙向鏈表的刪除：current -prior-next= current -next；current -next-prior= current -prior；delete current7.雙向鏈表的插入：p-prior=current；p-next= current -next；current-next-prior=p；current-next=p8.順序表與鏈表：順序表結(jié)點(diǎn)總數(shù)大概確定，表中結(jié)點(diǎn)數(shù)目穩(wěn)定（插刪操作少）；鏈表結(jié)點(diǎn)數(shù)目不預(yù)

5、知且動(dòng)態(tài)變化三、棧和隊(duì)列1.棧的邏輯結(jié)構(gòu)：允許插入和刪除的一端稱為棧頂，另一端稱為棧底，特點(diǎn)是后進(jìn)先出或先進(jìn)后出2.先進(jìn)后出題：若abc順序入棧，a入棧后可以直接出棧3.隊(duì)列的邏輯結(jié)構(gòu)：在一端進(jìn)行插入操作（隊(duì)尾），而另一端進(jìn)行刪除操作的線性表（隊(duì)頭），特點(diǎn)是先進(jìn)先出4.隊(duì)滿判定條件：(rear+1) % QueueSize=front5.隊(duì)空判定條件：rear = front6遞歸算法設(shè)計(jì)方法：最小規(guī)模子問(wèn)題、劃分子問(wèn)題并求解、子問(wèn)題解的合成4、 字符串和多維數(shù)組5、 樹(shù)和二叉樹(shù)1. 結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)2. 樹(shù)的度：樹(shù)中各結(jié)點(diǎn)度的最大值3. 前序遍歷：根左右4. 中序遍歷：左根右

6、5. 后序遍歷：左右根6. 層序遍歷：按層從左到右遍歷7. 滿二叉樹(shù)：葉結(jié)點(diǎn)只出現(xiàn)在最下一層，只有度為0和度為2的結(jié)點(diǎn)8. 完全二叉樹(shù)：在滿二叉樹(shù)中，從最后一個(gè)結(jié)點(diǎn)開(kāi)始，連續(xù)去除任意個(gè)結(jié)點(diǎn)9. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù),該樹(shù)中所有結(jié)點(diǎn)度數(shù)之和為n-110. 二叉樹(shù)性質(zhì)1：二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i1）11. 二叉樹(shù)性質(zhì)2：一棵深度為k的二叉樹(shù)中，最多有2k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)12. 二叉樹(shù)性質(zhì)3：在一棵二叉樹(shù)中，如果葉結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有: n0n2113. 完全二叉樹(shù)性質(zhì)1：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k=log2(n+1)取大整或k=log2n（

7、取小整）+1(n0)14. 完全二叉樹(shù)性質(zhì)2：序號(hào)i的結(jié)點(diǎn)，雙親結(jié)點(diǎn)的序號(hào)為i/2，左孩子的序號(hào)為2i，右孩子的序號(hào)為2i+115. 已知前序序列ABCDEFGHI和中序序列BCAEDGHFI畫(huà)出二叉樹(shù)16. 二叉樹(shù)前序遍歷遞歸算法 void BiTree : PreOrder(BiNode *bt) if (bt = NULL) return; /遞歸調(diào)用的結(jié)束條件 else cout data; /訪問(wèn)根結(jié)點(diǎn)bt的數(shù)據(jù)域 PreOrder(bt-lchild); /前序遞歸遍歷bt的左子樹(shù) PreOrder(bt-rchild); /前序遞歸遍歷bt的右子樹(shù) 17. 二叉樹(shù)中序遍歷遞歸算法

8、void BiTree : InOrder (BiNode *bt) if (bt = NULL) return; /遞歸調(diào)用的結(jié)束條件 else InOrder(bt-lchild); /中序遞歸遍歷bt的左子樹(shù) cout data; /訪問(wèn)根結(jié)點(diǎn)bt的數(shù)據(jù)域 InOrder(bt-rchild); /中序遞歸遍歷bt的右子樹(shù) 18. 二叉樹(shù)后序遍歷遞歸算法void BiTree : PostOrder(BiNode *bt) if (bt = NULL) return; /遞歸調(diào)用的結(jié)束條件 else PostOrder(bt-lchild); /后序遞歸遍歷bt的左子樹(shù) PostOrde

9、r(bt-rchild); /后序遞歸遍歷bt的右子樹(shù) cout data; /訪問(wèn)根結(jié)點(diǎn)bt的數(shù)據(jù)域 19. 二叉樹(shù)層次遍歷算法1.隊(duì)列Q初始化；2.如果二叉樹(shù)非空，將根指針入隊(duì)；3.循環(huán)直到隊(duì)列Q為空 3.1 q=隊(duì)列Q的隊(duì)頭元素出隊(duì)； 3.2 訪問(wèn)結(jié)點(diǎn)q的數(shù)據(jù)域； 3.3 若結(jié)點(diǎn)q存在左孩子，則將左孩子指針入隊(duì)； 3.4 若結(jié)點(diǎn)q存在右孩子，則將右孩子指針入隊(duì)；void BinaryTree:LevelOrder ( ) SeqQueue qu; BinTreeNode *p=root; qu.Enter(p); while(!qu.IsEmpty( ) p=qu.Leave( ); c

10、outdata; if(p-leftChild) qu. Enter(p-leftChild); if(p-rightChild) qu. Leave(p-rightChild);20. 二叉樹(shù)中序線索化：將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索P11121. 樹(shù)轉(zhuǎn)換二叉樹(shù)：相鄰兄弟加線、保留與第一子間連線刪去其它子結(jié)點(diǎn)間連線、根結(jié)點(diǎn)為軸心順時(shí)針轉(zhuǎn)動(dòng)P16222. 樹(shù)的前序遍歷等價(jià)于二叉樹(shù)的前序遍歷23. 樹(shù)的后序遍歷等價(jià)于二叉樹(shù)的中序遍歷24. 森林轉(zhuǎn)換二叉樹(shù)：先將每棵樹(shù)轉(zhuǎn)換成二叉樹(shù)；從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子P169 25. 二叉樹(shù)轉(zhuǎn)換

11、為樹(shù)或森林：P17226. 哈夫曼樹(shù)：給定一組具有確定權(quán)值的葉結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù),也稱最優(yōu)二叉樹(shù)27. 構(gòu)造哈夫曼數(shù)：初始化、選取與合并、刪除與加入、重復(fù)2和328. n個(gè)葉結(jié)點(diǎn)構(gòu)造出的哈夫曼樹(shù)中總的結(jié)點(diǎn)數(shù)為2n-129. 一組字符A, B, C, D, E, F, G出現(xiàn)的頻率分別是9, 11, 5, 7, 8, 2, 3，設(shè)計(jì)最經(jīng)濟(jì)的編碼方案 30. 字符集a,b,c,d,e,f,g,h出現(xiàn)概率分別是0.14, 0.08, 0.11, 0.23, 0.29, 0.05, 0.03, 0.076、 圖1. 網(wǎng)圖的鄰接表P712. 圖的遍歷：深度優(yōu)先遍歷和廣度優(yōu)先遍歷3. 最小生成

12、樹(shù)Prim算法：每次選擇解集合結(jié)點(diǎn)連接到待選集合結(jié)點(diǎn)最小邊，將所連待選結(jié)點(diǎn)加入到解集合中，直到待選集合為空4. 最小生成樹(shù)Kruscal算法：每次都選最小權(quán)邊（不構(gòu)成回路），直到選擇n-1條邊為止5. 最短路徑Dijkstra算法：帶方向的Prim算法6. 關(guān)鍵路徑：在AOE網(wǎng)中，從始點(diǎn)到終點(diǎn)具有最大路徑長(zhǎng)度（該路徑上的各個(gè)活動(dòng)所持續(xù)的時(shí)間之和）的路徑7、 查找1. 二叉樹(shù)的插入與刪除2. 平衡二叉查找數(shù)：LR型調(diào)整、LL型調(diào)整、RR型調(diào)整、RL型調(diào)整3. 散列表的建立：散列函數(shù)H(key)=key mod A4. 散列表沖突解決方法：線性探測(cè)法、二次探測(cè)法、隨機(jī)探測(cè)法、拉鏈法5. 散列表平均

13、查找長(zhǎng)度8、 排序1. 排序的分類：內(nèi)排序（待排元素在內(nèi)存中）、外排序（待排序元素部分在內(nèi)存中，需與外存多次交換）2. 起泡排序法：每次找最小值的放到待排隊(duì)首3. 選擇排序法：每次找最小值與待排隊(duì)首交換4. 最小堆：完全二叉樹(shù)，每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值5. 最大堆：完全二叉樹(shù)，每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值6. 將無(wú)序序列建成一個(gè)堆void sift ( int r , int k, int m ) /要篩選結(jié)點(diǎn)的編號(hào)為k，堆中最后一個(gè)結(jié)點(diǎn)的編號(hào)為m i=k; j=2*i; while (j=m ) if (jm & rjrj) break; else rirj;

14、 i=j; j=2*i; void rSort ( int r, int n) for (i=n/2; i=1; i-) /初建最大堆 sift(r, i, n) ; for (i=1; in; i+ ) r1 rn-i+1; /移走堆頂 sift(r, 1, n-i); /重建堆 7. 歸并排序：初始排序碼 52 33 65 80 73 23 29第一趟歸并 33 52 65 80 23 73 29第二趟歸并 33 52 65 80 23 29 73第三趟歸并 23 29 33 52 65 73 808. 穩(wěn)定排序：簡(jiǎn)單插入排序、起泡排序和歸并排序9. 不穩(wěn)定排序：希爾排序、簡(jiǎn)單選擇排序、快速排序和堆排序10. 各種排序方法的比