//第八章 查找
?
//基于線性表的查找

// 1.順序查找法
//思想:所給的關鍵字和表中元素的關鍵字逐個比較
分為:設置監視哨和不設監視哨
監視哨:r[0]防止越界

//2.折半查找法
要求:順序儲存結構(不能鏈表),按照關鍵字大小有序排列(正序和逆序)
思想:利用mid=(high+low)/2(整數). 判斷條件:low<=high;

//3.分塊查找法
要求:列表分為子表,最后一個子表長度可以不滿;索引表每個索引對應每個塊(子表)的起始位置,記錄每個塊的最大(最小)
的關鍵字;索引表按照關鍵字有序排列

//基于樹的查找法

//二叉排序樹:元素大小:左子樹,根,右子樹,遞歸定義
二叉排序樹的刪除略顯復雜:
1.不存在,不動
2.存在
2.1.葉子節點:直接刪,free掉
2.2只有左右子樹一支:孩子改到刪去位置(孩子變為雙親),free
2.3.左右孩子都有:
2.3.1處理1:
?? ?利用中序遍歷算法找到將要刪除結點p的直接前驅s,p左子樹變為其雙親的左孩子,右子樹變為其前驅s的右孩子?
2.3.2處理2:?
?? ?直接刪除結點p,p的前驅s代替p,free(s),s的左孩子為s的雙親的右孩子,p的右孩子為s的右孩子
?? ?
//平衡二叉排序樹:左子樹右子樹高度絕對值之差小于等于1
插入算法:LL,RR,LR,RL型

//計算式查找法:hash

//hash:
1.數字分析法:選擇合適位數的分布均勻的關鍵字?
2.平方取中法:求關鍵字平方值,取中間,重復概率低?
3.分段疊加法:折疊法,移位法
4.除留余數法:取余除數為小于等于表長的最大素數?
5.偽隨機數法:
?? ?
處理沖突!:
1.開放地址法(再散列法):
1.1.線性探測再散列:di = 1,2,3......
1.2.二次探測再散列:di = 1^2, -1^2, 2^2, -2^2,......?
1.3.偽隨機探測再散列: ...

2.再哈希法
3.鏈地址法:
4.建立公共溢出區:分為基本表和溢出表

總結

以上是生活随笔為你收集整理的数据结构-查找-总结归纳知识点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。