數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記

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

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

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

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；cu

5、rrent->next=p8.順序表與鏈表：順序表結(jié)點總數(shù)大概確定，表中結(jié)點數(shù)目穩(wěn)定（插刪操作少）；鏈表結(jié)點數(shù)目不預(yù)知且動態(tài)變化三、棧和隊列1.棧的邏輯結(jié)構(gòu)：允許插入和刪除的一端稱為棧頂，另一端稱為棧底，特點是后進(jìn)先出或先進(jìn)后出2.先進(jìn)后出題：若abc順序入棧，a入棧后可以直接出棧3.隊列的邏輯結(jié)構(gòu)：在一端進(jìn)行插入操作（隊尾），而另一端進(jìn)行刪除操作的線性表（隊頭），特點是先進(jìn)先出4.隊滿判定條件：(rear+1) % QueueSize=front5.隊空判定條件：rear = front6遞歸算法設(shè)計方法：最小規(guī)模子問題、劃分子問題并求解、子問題解的合成4、 字符串和多維數(shù)組5、 樹和

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

7、則有: n0n2113. 完全二叉樹性質(zhì)1：具有n個結(jié)點的完全二叉樹的深度為k=log2(n+1)取大整或k=log2n（取小整）+1(n>0)14. 完全二叉樹性質(zhì)2：序號i的結(jié)點，雙親結(jié)點的序號為i/2，左孩子的序號為2i，右孩子的序號為2i+115. 已知前序序列ABCDEFGHI和中序序列BCAEDGHFI畫出二叉樹16. 二叉樹前序遍歷遞歸算法 void BiTree<DataType> : PreOrder(BiNode<DataType> *bt) if (bt = NULL) return; /遞歸調(diào)用的結(jié)束條件 else cout <<

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

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

10、隊列Q初始化；2.如果二叉樹非空，將根指針入隊；3.循環(huán)直到隊列Q為空 3.1 q=隊列Q的隊頭元素出隊； 3.2 訪問結(jié)點q的數(shù)據(jù)域； 3.3 若結(jié)點q存在左孩子，則將左孩子指針入隊； 3.4 若結(jié)點q存在右孩子，則將右孩子指針入隊；void BinaryTree<Type>:LevelOrder ( ) SeqQueue qu; BinTreeNode *p=root; qu.Enter(p); while(!qu.IsEmpty( ) p=qu.Leave( ); cout<<p->data; if(p->leftChild) qu. Enter(p-

11、>leftChild); if(p->rightChild) qu. Leave(p->rightChild);20. 二叉樹中序線索化：將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索P11121. 樹轉(zhuǎn)換二叉樹：相鄰兄弟加線、保留與第一子間連線刪去其它子結(jié)點間連線、根結(jié)點為軸心順時針轉(zhuǎn)動P16222. 樹的前序遍歷等價于二叉樹的前序遍歷23. 樹的后序遍歷等價于二叉樹的中序遍歷24. 森林轉(zhuǎn)換二叉樹：先將每棵樹轉(zhuǎn)換成二叉樹；從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子P169 25. 二叉樹轉(zhuǎn)換為樹或森林：P17226. 哈夫曼樹：給定一組具有

12、確定權(quán)值的葉結(jié)點，帶權(quán)路徑長度最小的二叉樹,也稱最優(yōu)二叉樹27. 構(gòu)造哈夫曼數(shù)：初始化、選取與合并、刪除與加入、重復(fù)2和328. n個葉結(jié)點構(gòu)造出的哈夫曼樹中總的結(jié)點數(shù)為2n-129. 一組字符A, B, C, D, E, F, G出現(xiàn)的頻率分別是9, 11, 5, 7, 8, 2, 3，設(shè)計最經(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. 最小生成樹Prim算法：每次選擇解集合結(jié)點連接到待選集合結(jié)

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

14、素在內(nèi)存中）、外排序（待排序元素部分在內(nèi)存中，需與外存多次交換）2. 起泡排序法：每次找最小值的放到待排隊首3. 選擇排序法：每次找最小值與待排隊首交換4. 最小堆：完全二叉樹，每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值5. 最大堆：完全二叉樹，每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值6. 將無序序列建成一個堆void sift ( int r , int k, int m ) /要篩選結(jié)點的編號為k，堆中最后一個結(jié)點的編號為m i=k; j=2*i; while (j<=m ) if (j<m && rj<rj+1) j+; /左右孩子中取較大者 if (

15、ri>rj) break; else ri<=>rj; 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; i>n; 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)定排序：簡單插入排序、起泡排序和歸并排序9. 不穩(wěn)定排序：希爾排序、簡單選擇排序、快速排序和堆排序10. 各種排序方法的比較排序方法平均情況最好情況最壞情況直接