資料結構期末復習重點
- 一、線性結構
- 1、串的模式匹配（區分目標串和模式串、nextval陣列值、KMP演算法匹配程序）
- 2、利用堆疊對運算式求值
- 二、非線性結構
- 1、樹與二叉樹
- 2、圖
- 三、查找與排序
- 1、查找
- 哈希表查找（哈希表的基本概念、3個因素、線性探測法解決沖突、哈希表的求解與建立）
- 用線性探測解決沖突的例題：
- 解題程序如下：
- 除留余數法:
- 采用除留余數法解決沖突例題：
- 2、排序
- 直接插入排序和折半查找（直接插入排序思想、折半查找的思想、直接插入排序和折半查找的求解程序）
- 直接插入排序思想：
- 折半查找的思想：（效率較高）
- 拓撲排序的思想：
一、線性結構
1、串的模式匹配（區分目標串和模式串、nextval陣列值、KMP演算法匹配程序）
2、利用堆疊對運算式求值
二、非線性結構
1、樹與二叉樹
（1）哈夫曼樹（思想）、哈夫曼編碼和帶權路徑長度求解
思想：在n0個帶權葉子節點構成的所有二叉樹中，帶權路徑長度WPL最小的二叉樹成為哈夫曼樹或者是最優二叉樹，
（2）二叉樹的先序、中序和后序遍歷的思想和求解，
先序（DLR）：先遍歷根，再遍歷左子樹，最后遍歷右子樹，
中序（LDR）：先遍歷左子樹，再遍歷根，最后遍歷右子樹，
后續（LRD）：先遍歷左子樹，再遍歷右子樹，最后遍歷根，
2、圖
（1）圖的存盤結構（鄰接矩陣表示、鄰接表表示、鄰接矩陣的特點（有向圖））
（2）圖的遍歷（DFS、BFS的演算法思想和結合某種存盤結構進行遍歷求解）
（3）圖的最短路徑（單源點）：Dijkstra演算法思想、最短路徑求解，求解時一定要給出求解步驟，
三、查找與排序
1、查找
哈希表查找（哈希表的基本概念、3個因素、線性探測法解決沖突、哈希表的求解與建立）
哈希表的基本概念：
哈希表（hash table）又稱三串列，其基本思路是，設要存盤的元素個數為n，設定一個長度為m（m>=n）的連續記憶體單元，以每個元素的關鍵字ki（0<=i<=n-1）為自變數，通過一個稱為哈希函式（hash function）的函式h（ki）吧ki映射為記憶體單元的地址（或下標）h（ki），并把該元素存盤在這個記憶體單元中，h（ki）也成為哈希地址（hash address），把如此構造的線性表存盤結構稱為哈希表，
三個因素：
①哈希函式，
②處理沖突的方法，
③哈希表的裝填因子，
哈希函式的好壞首先影響出現沖突的頻繁程度，
假定哈希函式是“均勻的”，即不同的哈希函式對同一組隨機的關鍵字，產生沖突的可能性相同，
對同一組關鍵字，設定相同的哈希函式，則不同的處理沖突的方法得到的哈希表不同，它的平均查找長度也不同，
若處理沖突的方法相同，其平均查找長度依賴于哈希表的裝填因子，
線性探測法
線性探測法是從發生沖突的地址（設為d）開始，依次探測d的下一個地址（當到達下標為m-1的哈希表表尾時，下一個探測的地址是表首地址0），直到找到一個空閑單元為止（當m≥n時一定能找到一個空閑單元），線性探測法的數學遞推描述公式為：
d0=h(k)
di=(di-1+1) mod m (1≤i≤m-1)
用線性探測解決沖突的例題：
解題程序如下：
構建哈希表：
除留余數法:
除留余數法是用關鍵字k除以某個不大于哈希表長度m的數p所得的余數作為希地址的方法，除留余數法的哈希函式h(k)為：
h(k)=k mod p (mod為求余運算，p≤m) ,p最好是質數（素數），
采用除留余數法解決沖突例題：
采用除留余數法哈希函式建立如下關鍵字集合的哈希表：{16,74,60,43,54,90,46,31,29,88,77}，
除留余數法的哈希函式為：
h(k)=k mod 13
對構造的哈希表采用線性探測法解決沖突，
解：h(16)=3，h(74)=9，h(60)=8，h(43)=4，
h(54)=2，h(90)=12，h(46)=7，h(31)=5，
h(29)=3 沖突
d0=3，d1=(3+1) mod 13=4 沖突
d2=(4+1) mod 13=5 仍沖突
d3=(5+1) mod 13=6
h(88)=10
h(77)=12 沖突
d0=12，d1=(12+1) mod 13=0
建立的哈希表ha[0…12]如下表所示，
2、排序
直接插入排序和折半查找（直接插入排序思想、折半查找的思想、直接插入排序和折半查找的求解程序）
直接插入排序思想：
假設待排序的記錄存放在陣列R[0…n-1]中，初始時，R[0]自成1個有序區，無序區為R[1…n-1]，從i=1起直至i=n-1為止，無序區的頭元素，與有序的最后一個元素比較，一次從后往前比較，符合條件插入有序區，知道無序區元素個數為0.
折半查找的思想：（效率較高）
折半查找時, 先求位于查找區間正中的物件的下標
mid，用其關鍵碼與給定值k比較：
Element[mid].key == k，查找成功；
Element[mid].key > k，把查找區間縮小到表的前
半部分，繼續折半查找；
Element[mid].key < k，把查找區間縮小到表的后半部分，繼續折半查找，
如果查找區間已縮小到一個物件，仍未找到想要查
找的物件，則查找失敗，
例如：
在關鍵字有序序列{2,4,7,9,10,14,18,26,32,40}中采用折半查找法查找關鍵字為7的元素，
折半查找的平均查找長度：
折半查找例題：
1、折半查找有序表（4，6，10，12，20，30，50，70，88，100），若查找表中元素38，則它將依次與表中哪些元素比較大小，查找結果是失敗，
答案選 C
2、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素 __________比較大小，
答案：28，6，12，20
拓撲排序的思想：
①從有向圖中選擇一個沒有前驅（入度為零）的定點并且輸出他，
②從圖中刪去該頂點，并且刪去從該頂點發出的全部有向邊，
③重復上述兩步，直到剩余的圖中不再存在沒有前驅的頂點為止，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/244253.html
標籤：其他
上一篇：通過Mycat分庫分表