數(shù)據(jù)結構復習筆記

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結構復習筆記一、緒論1.數(shù)據(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ù)的邏輯結構：指數(shù)據(jù)之間的邏輯關系, 即指數(shù)據(jù)元素之間的關聯(lián)方式或鄰接關系7.數(shù)據(jù)的存儲結構：指數(shù)據(jù)在計算機中存儲的位置8.運算的集合：定義在邏輯結構上的一組操作9.數(shù)據(jù)結構: 按照某種邏輯關系組織起來的一批數(shù)據(jù), 按一定的存儲方法把它存儲在計算機中, 并在這些數(shù)據(jù)上定義了一個運算的集合10.邏輯結構分類：線性結構、集合、樹形

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

3、出19.算法與程序的區(qū)別：程序不一定滿足有窮性；程序是機器可執(zhí)行的語言編寫的20.算法評價：正確、簡單、可讀、健壯、高效21.算法分析方法：事后統(tǒng)計和事前分析、時間復雜度和空間復雜度22.影響算法時間代價的因素：輸入規(guī)模、算法效率、輸入順序、機器、設計者23.(1)O(log2n)O (n)O (nlog2n)O (n2)O (n3)O (2n)O (n!)二、線性表1.線性結構特點：唯一第一數(shù)據(jù)元素、唯一最后數(shù)據(jù)元素、其他數(shù)據(jù)元素僅有一個前趨和僅有一個后驅(qū)2.順序表的優(yōu)點：無需為表示數(shù)據(jù)元素之間的邏輯關系而增加額外存儲空間；可方便地隨機存取表中任一元素3.順序表的缺點：預先為數(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.順序表與鏈表：順序表結點總數(shù)大概確定，表中結點數(shù)目穩(wěn)定（插刪操作少）；鏈表結點數(shù)目不預知且動態(tài)變化三、棧和隊列1.棧的邏輯結構：允許插入和刪除的一端稱為棧頂，另一端稱為棧底，特點是后進先出或先進后出2.先進后出題：若abc順序入棧，a入棧后可以直接出棧3.隊列的邏輯結構：在一端進行插入操作（隊尾），而另一端進行刪除操作的線性表（隊頭），特點是先進先出4.隊滿判定條件：(rear+1) % QueueSize=front5.隊空判定條件：rear = front6遞歸算法設計方法：最小規(guī)模子問題、劃分子問題并求解、子問題解的合成4、 字符串和多維數(shù)組5、 樹和

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

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

8、; bt->data; /訪問根結點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)用的結束條件 else InOrder(bt->lchild); /中序遞歸遍歷bt的左子樹 cout << bt->data; /訪問根結點bt

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

10、隊列Q初始化；2.如果二叉樹非空，將根指針入隊；3.循環(huán)直到隊列Q為空 3.1 q=隊列Q的隊頭元素出隊； 3.2 訪問結點q的數(shù)據(jù)域； 3.3 若結點q存在左孩子，則將左孩子指針入隊； 3.4 若結點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)換二叉樹：相鄰兄弟加線、保留與第一子間連線刪去其它子結點間連線、根結點為軸心順時針轉(zhuǎn)動P16222. 樹的前序遍歷等價于二叉樹的前序遍歷23. 樹的后序遍歷等價于二叉樹的中序遍歷24. 森林轉(zhuǎn)換二叉樹：先將每棵樹轉(zhuǎn)換成二叉樹；從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子P169 25. 二叉樹轉(zhuǎn)換為樹或森林：P17226. 哈夫曼樹：給定一組具有

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

13、點最小邊，將所連待選結點加入到解集合中，直到待選集合為空4. 最小生成樹Kruscal算法：每次都選最小權邊（不構成回路），直到選擇n-1條邊為止5. 最短路徑Dijkstra算法：帶方向的Prim算法6. 關鍵路徑：在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. 散列表沖突解決方法：線性探測法、二次探測法、隨機探測法、拉鏈法5. 散列表平均查找長度8、 排序1. 排序的分類：內(nèi)排序（待排元

14、素在內(nèi)存中）、外排序（待排序元素部分在內(nèi)存中，需與外存多次交換）2. 起泡排序法：每次找最小值的放到待排隊首3. 選擇排序法：每次找最小值與待排隊首交換4. 最小堆：完全二叉樹，每個結點的值都小于或等于其左右孩子結點的值5. 最大堆：完全二叉樹，每個結點的值都大于或等于其左右孩子結點的值6. 將無序序列建成一個堆void sift ( int r , int k, int m ) /要篩選結點的編號為k，堆中最后一個結點的編號為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. 各種排序方法的比較排序方法平均情況最好情況最壞情況直接