一、靜態(tài)查找表
（1）順序表的查找
? ? ? ? ?1）順序表查找的結(jié)構(gòu)
typedef struct{
ElemType * elem; //存儲(chǔ)空間基址
int length; //表長(zhǎng)
}SSTable;
順序查找的過程：從表中最后一個(gè)記錄開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較。（也就是說，在查找到時(shí)候從最后一個(gè)元素開始查找，在這個(gè)表中位置為0的位置空著，留給你要查找的元素）
在順序表的查找中，需要有一個(gè)“哨兵”負(fù)責(zé)擔(dān)任監(jiān)視哨的任務(wù)。
ST.elem[0].key = key;
//判斷查找的元素（也就是位置0放的位置）是不是和值相等2）查找的性能分析
查找的操作其實(shí)很簡(jiǎn)單，就是將你要找的值與表中元素一一比較，若不符合，則向前查找，直到找到或者表空為止。
因此順序查找表的長(zhǎng)度為：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【其中i = 1】
可以看做是：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
（2）有序表的查找
有序表的查找，可以從小到大，或者從大到小。我們一般默認(rèn)是從小到大查找。
1）折半查找
折半查找，查找方式有三個(gè)指針：low,high和mid。其中mid指示區(qū)間的中間位置，即mid=[(high+low)/2]
1.若key與中間元素相等，則查找成功，返回該元素的存儲(chǔ)位置，即mid；
2.若key與中間元素不相等，則所需查找的元素只能在中間元素以外的前半部分或后半部分。（至? ? ?于是前半部分還是后半部分要看key與mid所指向元素的大小關(guān)系）
? ?a.在查找表升序排列的情況下，若給定值key大于中間元素則所查找的元素只可能在后半部分。? ? ? ?此時(shí)讓low=mid+1；
? ?b.若給定值key小于中間元素則所查找的元素只可能在前半部分。此時(shí)讓high=mid-1；
//折半查找
int Search Bin(SSTable L,ElemType key){
low = 1,high = ST.length;
while(low <= high){
mid=(low+high)/2; //取中間位置
if(L.elem[mid]==key)
return mid; //查找成功返回所在的位置
else if(L.elem[mid]>key){ //從前部分查找
high=mid-1;
}
else
low=mid+1; //從后部分查找
}
return 0; //失敗返回0
}
二、索引順序表的查找
索引順序表也就是分塊查找，許多情況下可能遇到這樣的表：整個(gè)表中未必有序，但若劃分成若干塊后，每一塊中的所有元素均大于或小于其后面的所有元素，稱這種特性為分塊有序，因此可以為該順序表建立一個(gè)索引表，索引表中為每一塊設(shè)置設(shè)置一索引項(xiàng)，每一索引項(xiàng)包括兩部分：該塊的起始地址和該塊中最大(或最小)關(guān)鍵字的值（或是所限定的最大（?。╆P(guān)鍵字）。將這些索引項(xiàng)按順序排列成一有序表，即為索引表。
三、二叉排序樹和平衡二叉樹
二叉樹定義：
二叉排序樹（又名二叉查找樹）或者是一棵空樹；或者是具有以下性質(zhì)的二叉樹：
1）若它的左子樹不為空，則左子樹上所有結(jié)點(diǎn)的值均小于它根節(jié)點(diǎn)的值
2）若它的右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值均大于它根節(jié)點(diǎn)的值
3）它的左右子樹也分別為二叉排序樹
簡(jiǎn)單來說就是：左比根小，右比根大
1）二叉排序樹的構(gòu)造過程
首先我們使用畫圖的方式來描繪一下二叉排序樹的插入過程，如圖，我們要在一棵空的二叉排序樹中插入一個(gè)數(shù)組6,2,7,4,0,3,1,5，如圖所示：
??首先我們插入第一個(gè)元素6，此時(shí)二叉排序樹中還沒有任何一個(gè)節(jié)點(diǎn)，因此我們應(yīng)該新建一個(gè)節(jié)點(diǎn)，并將6存儲(chǔ)進(jìn)去，并將6認(rèn)定為根節(jié)點(diǎn)，如圖所示：
??之后我們插入第二個(gè)元素2，此時(shí)二叉排序樹已經(jīng)不是一個(gè)空樹了，因此我們需要首先找到適合它的位置，我們將2和6進(jìn)行對(duì)比，判斷誰大誰小，我們發(fā)現(xiàn)2更小，因此2應(yīng)該被插入在6的左子樹中，之后我們將2和根節(jié)點(diǎn)6的左子樹進(jìn)行對(duì)比，發(fā)現(xiàn)6的左子樹是空的，因此這時(shí)我們將2存放在6的左子樹根節(jié)點(diǎn)位置，如圖所示：
??之后是元素7,7顯然大于6，因此我們要將7放在6的右子樹中，經(jīng)過探尋我們發(fā)現(xiàn)6的右子樹根節(jié)點(diǎn)也是空的，因此我們需要將7放在右子樹的根節(jié)點(diǎn)上，如圖所示：
??之后是元素4，我們首先將4和6對(duì)比，發(fā)現(xiàn)4是小于6的，因此4應(yīng)該位于6的左子樹上，之后我們將4和6的左子樹根節(jié)點(diǎn)進(jìn)行對(duì)比，發(fā)現(xiàn)4是大于2的，因此4應(yīng)該被放在2的右子樹上，而2的右子樹為空，因此4直接被放置在2的右子樹根節(jié)點(diǎn)上，如圖所示：
??之后是元素0，首先我們將0和元素6進(jìn)行對(duì)比，發(fā)現(xiàn)0是小于元素6的，因此應(yīng)該被放置在6的左子樹上，之后我們將0和6的左子樹根節(jié)點(diǎn)進(jìn)行對(duì)比，發(fā)現(xiàn)其小于2，因此0應(yīng)該被放置在2的左子樹上，這時(shí)我們發(fā)現(xiàn)0是小于2的，因此0應(yīng)該被放置在2的左子樹上，同時(shí)我們發(fā)現(xiàn)2的左子樹為空，因此我們將0放置在2的左子樹根節(jié)點(diǎn)上，如圖所示：
??之后是元素3，我們發(fā)現(xiàn)元素3是小于6的，因此3應(yīng)該被放置在6的左子樹上，而這時(shí)我們就開始研究6的左子樹，3大于2，因此3應(yīng)該被放置在2的右子樹上，這時(shí)我們開始研究2的右子樹，而3是小于2的右子樹根節(jié)點(diǎn)4的，因此3應(yīng)該放置在4的左子樹上，我們發(fā)現(xiàn)4的左子樹為空，因此我們將3放置在4的左子樹根節(jié)點(diǎn)上，如圖所示：
??之后是元素1，首先我們將1和6進(jìn)行對(duì)比，發(fā)現(xiàn)1是小于6的，因此1應(yīng)該被放置在6的左子樹上，而1又小于2，因此應(yīng)該被放置在2的左子樹上，而1又大于0，因此應(yīng)該被放置在0的右子樹上，0的右子樹為空，因此1應(yīng)該被放置在0的右子樹根節(jié)點(diǎn)上，如圖所示：
??之后我們研究最后一個(gè)元素5,5小于根節(jié)點(diǎn)6，因此我們應(yīng)該將5放置在6的左子樹上，而5大于2，因此我們應(yīng)該將5放置在2的右子樹上，5大于4，因此5應(yīng)該被放置在4的右子樹上，4的右子樹為空，因此我們將5放置在4的右子樹根節(jié)點(diǎn)上，如圖所示：
整個(gè)的過程都是從中序這個(gè)節(jié)點(diǎn)前驅(qū)替代
2）平衡二叉樹
定義：
左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過1
方法：
從一組數(shù)中選三個(gè)，由小到大排序，取中間為新根，小的放左邊，大的放右邊
調(diào)之前：有左邊，將左調(diào)到右
? ? ? ? ? ? ? 有右邊，將右調(diào)到左
比如：
將它調(diào)整一下：
四、哈希表
不想比較，直接用函數(shù)。
根據(jù)關(guān)鍵碼值（Key Value）直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。
哈希表通過「鍵 key 」和「映射函數(shù) Hash(key) 」計(jì)算出對(duì)應(yīng)的「值 value」，把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做「哈希函數(shù)（散列函數(shù)）」，存放記錄的數(shù)組叫做「哈希表（散列表）」。
哈希表的關(guān)鍵思想是使用哈希函數(shù)，將鍵 key 映射到對(duì)應(yīng)表的某個(gè)區(qū)塊中。我們可以將算法思想分為兩個(gè)部分：
1.向哈希表中插入一個(gè)關(guān)鍵碼值：哈希函數(shù)決定該關(guān)鍵字的對(duì)應(yīng)值應(yīng)該存放到表中的哪個(gè)區(qū)塊，并將對(duì)應(yīng)值存放到該區(qū)塊中。
2.在哈希表中搜索一個(gè)關(guān)鍵碼值：使用相同的哈希函數(shù)從哈希表中查找對(duì)應(yīng)的區(qū)塊，并在特定的區(qū)塊搜索該關(guān)鍵字對(duì)應(yīng)的值。
構(gòu)造方法
直接定址法
除留余數(shù)法
數(shù)字分析法
平方取中法
折疊法
處理沖突方法
開放定址法：
先開n個(gè)房間，利用線性放入，如果找x在下面寫上比較次數(shù)
比如：依次插入9? ?11? ?23? ?19? ?54
用數(shù)字除以表長(zhǎng)取余數(shù)即可文章來源：http://www.zghlxwxcb.cn/news/detail-813079.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-813079.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)第九章的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
