數(shù)據(jù)結(jié)構(gòu)之查找
查找概論
查找表
定義
查找表（Search Table）是同一類型的數(shù)據(jù)元素（或記錄）的集合哗魂。
查找表分類
靜態(tài)查找表
靜態(tài)查找表（Static Search Table）：只做查找操作的查找表。
它的主要操作有：
- 查找某個“特定的”數(shù)據(jù)元素是否存在于查找表中疏之。
- 檢索某個“特定的”數(shù)據(jù)元素和各種屬性。
動態(tài)查找表
動態(tài)查找表（Dynamic Search Table）：在查找過程中同時插入不存在的數(shù)據(jù)元素速挑，
或在查找過程中刪除已經(jīng)存在的數(shù)據(jù)元素谤牡。
它的主要操作有：
- 查找時插入數(shù)據(jù)元素。
- 查找時刪除數(shù)據(jù)元素姥宝。
關(guān)鍵字
關(guān)鍵字（Key）是數(shù)據(jù)元素中某個數(shù)據(jù)項的值翅萤，又稱為鍵值。（難理解）
若此關(guān)鍵字可以唯一地標識一個記錄腊满，則稱此關(guān)鍵字為主關(guān)鍵字（Primary key）套么。
可以識別多個數(shù)據(jù)元素（或記錄）的關(guān)鍵字，是次關(guān)鍵字（Secondary Key）碳蛋。
意思是根據(jù)次關(guān)鍵字可以查詢到多條數(shù)據(jù)元素嗎胚泌？
查找定義
查找（Searching）是根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定
值的數(shù)據(jù)元素（或記錄）疮蹦。
若查找到了數(shù)據(jù)元素诸迟，則查找成功；否則愕乎，查找失敗阵苇。
查找結(jié)構(gòu)
面向查找操作的數(shù)據(jù)結(jié)構(gòu)叫做查找結(jié)構(gòu)。
順序表查找
概念
順序表查找（Sequential Search）又叫線性查找感论，是最基本的查找技術(shù)绅项。它的查找過程是：
從表中第一個（或最后一個）記錄開始，逐個比較記錄的關(guān)鍵字和給定值比肄。
若某個記錄的關(guān)鍵字和給定值相等快耿，則查找成功。
若一直查找到最后一個（或第一個）記錄芳绩，其關(guān)鍵字都不等于給定值掀亥，則查找失敗。
代碼
int Sequential_search(int *a, int n, int key)
{
int i;
for(i = 1; i < n; i++){
if(a[i] == key){
return i;
}
}
return 0;
}
順序表查找代碼優(yōu)化
int Sequential_search(int *a, int n, int key)
{
int i;
a[0] = key;
i = 1;
while(a[i] != key){
i--;
}
return i; // 當i等于0時查找失敗
}
或
int Sequential_search(int *a, int n, int key)
{
int i;
a[n-1] = key;
while(a[i] != key){
i++;
}
return i; // 當i等于n-1時查找失敗
}
時間復雜度
$O(n)$
有序表查找
折半查找
摘抄
一看就懂的知識點妥色，一般不再打字記錄筆記搪花，直接摘抄書本。
代碼
int Binary_search(int *a, int n, int key)
{
int low, high, mid;
low = 1;
high = n;
while(low <= high){
/*1*/ mid = (low + high) / 2;
if(key > a[mid]){
low = mid + 1;
}else if(key < a[mid]){
high = mid - 1;
}else{
return mid;
}
}
/*2*/ return 0;
}
第1行嘹害，取值相當于PHP中的 floor 函數(shù)撮竿。
第2行，查找結(jié)果不是 mid 就是查找失敗笔呀。這說明幢踏，若查找表中存在要
查找的關(guān)鍵字，那么該關(guān)鍵字的位置一定是某個中間位置许师。不能理解這點房蝉。
差值查找
差值計算公式
$key-a[low]\over a[high]-a[low]$
這個公式是如何得到的僚匆？
代碼
int Binary_search(int *a, int n, int key)
{
int low, high, mid;
low = 1;
high = n;
while(low <= high){
mid = (key - a[low]) / (a[high] - a[low]);
if(key > a[mid]){
low = mid + 1;
}else if(key < a[mid]){
high = mid - 1;
}else{
return mid;
}
}
/*2*/ return 0;
}
時間復雜度
$O(logn)$
斐波那契查找
代碼
int Fibonacci_Search(int *a, int n, int key)
{
int low, high, mid, i, k;
low = 1;
high = n;
k = 0;
/*1*/ while(n>F[k]-1){ // 計算n位于斐波那契數(shù)列的位置
k++;
}
for(i = n; i < F[k]-1; i++){ // 將不滿的數(shù)值補全
a[i] = a[n];
}
while(low <= high){
mid = low + F[k-1] - 1; // 計算當前分隔的下標
if(key < a[mid]){
high = mid - 1;
/*2*/ k = k -1; // 斐波那契數(shù)列下標減一位
}else if(key > a[mid]){
low = mid + 1;
/*3*/ k = k - 2; // 斐波那契數(shù)列下標減二位
}else{
if(mid <= n){
return mid; // 若相等則說明mid即為查找到的位置
}else{
return n; // 若mid>n說明是補全數(shù)值，返回n
}
}
}
return 0;
}
理解不了第1行搭幻、第2行白热、第3行。
摘抄
不理解上圖中的范圍個數(shù)是怎么得到的粗卜。
這個圖好像有助于理解某些東西。
線性索引查找
摘抄
概念
稠密索引
概念
對于稠密索引的的索引表纳击，索引項一定是按照關(guān)鍵碼有序的排列琐驴。
分塊索引
概念
時間復雜度（不懂）
倒排索引
概念
存儲技巧
二叉排序樹
二叉排序樹查找操作代碼
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
if(!T){
*p = f;
return FALSE;
}else if(key == T->data){
*p = T;
return TRUE;
}else if(key > T->data){
return SearchBST(T->rchild, key, T, p);
}else{
return SearchBST(T->lchild, key, T, p);
}
}
二叉排序樹插入操作代碼
二叉排序樹插入操作代碼
Status InsertBST(BiTree *T, int key)
{
BiTree p, s;
if(!SearchBST(*T, key, NULL, &p)){
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
if(!p){
*T = s;
}else if(key > p->data){
p->rchild = s;
}else{
p->lchild = s;
}
return TRUE;
}else{
return FALSE;
}
}
如果查找到的是葉子結(jié)點昙读，插入新的結(jié)點很容易。
如果查找到的不是葉子結(jié)點，假如此結(jié)點剛好有左右孩子結(jié)點枫绅，如何插入新的結(jié)點？
查找停止的情況有兩種：找到了和關(guān)鍵字匹配的記錄港庄；查找失敗甸祭。第二種情況，必然
是遍歷到了葉子結(jié)點善已。好不能透徹地理解這點灼捂，只能大概不確定地得出這樣的結(jié)論。
創(chuàng)建二叉排序樹代碼
int CreateBST(void)
{
int i;
int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
BiTree T = NULL;
for(i = 0; i < 10; i++){
InsertBST(T, a[i]);
}
return 0;
}
二叉排序樹刪除操作代碼
代碼
Status Delete(BiTree *p)
{
BiTree q, s;
if((*p)->rchild == NULL){
q = *p;
*p = (*p)->lchild;
free(q);
}else if((*p)->lchild == NULL){
q = *p;
*p = (*p)->rchild;
free(q);
}else{
q = *p;
s = (*p)->lchild;
while(s->rchild){
q = s;
s = s->rchild;
}
(*p)->data = s->data;
if(q != *p){
q->rchild = s->lchild;
}else{
q->lchild = s->lchild;
}
free(s);
}
}
二叉排序樹刪除結(jié)點代碼
Status DeleteBST(BiTree *T, int key)
{
if(!*T){
return FALSE;
}else{
if(key == (*T)->data){
return Delete(T);
}else if(key < (*T)->data){
return DeleteBST(&(*T)->lchild, key);
}else{
return DeleteBST(&(*T)->rchild, key);
}
}
}
刪除操作有四種情況：
- 要刪除的結(jié)點是葉子結(jié)點换团。
- 要刪除的結(jié)點有左孩子悉稠。
- 要刪除的結(jié)點有右孩子。
- 要刪除的結(jié)點有左右孩子艘包。理解不了這種情況的代碼的猛。
代碼解讀
摘抄
概念
平衡二叉樹（AVL樹）
概念
平衡二叉樹
平衡二叉樹（Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree），
是一種二叉排序樹想虎，其中每一個結(jié)點的左子樹和右子樹的高度差至多等于1卦尊。
平衡因子
平衡二叉樹上的結(jié)點的左子樹減去右子樹的得到的差值，叫做平衡因子（Balance Factor）舌厨。
平衡因子可能的值是 -1岂却，0 和 1。
書中認為圖3中邓线，結(jié)點58的左子樹的高度是2淌友，我認為是3。
最小不平衡子樹
距離插入結(jié)點最近的骇陈、平衡因子的絕對值大于 1 的結(jié)點為根的子樹震庭，叫做最小不平衡子樹。
什么叫插入結(jié)點你雌？是指插入新結(jié)點的那個位置嗎器联？
結(jié)點58的左子樹的高度二汛，我認為是3。
平衡二叉樹實現(xiàn)算法代碼
旋轉(zhuǎn)操作
樹的結(jié)點結(jié)構(gòu)
typedef struct BiTNode
{
int data;
int bf; // 結(jié)點的平衡因子
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
右旋轉(zhuǎn)操作代碼
void R_Rotate(BiTree *p)
{
BiTree L;
L = (*p)->lchild; // L指向p的左子樹根結(jié)點
(*p)->lchild = L->rchild; // L的右子樹掛結(jié)為p的左子樹
L->rchild = (*p);
*p = L; // P指向新的根結(jié)點
}
左旋操作代碼
void L_Rotate(BiTree *p)
{
BiTree R;
R = (*p)->rchild; // R指向p的右子樹根結(jié)點
(*p)->rchild = R->lchild; // R的左子樹掛接為p的右子樹
R->lchild = (*p);
*p = R; // p指向新的根結(jié)點
}
理解不了拨拓。按照我的思路肴颊，p 是 R->lchild 的左子樹，可是這和左旋轉(zhuǎn)
后的結(jié)果不吻合渣磷。
重新畫了幾次婿着，根據(jù)代碼，可以得到預期效果圖了醋界【顾危可是，L 的右子樹為何
會變成 p 的左子樹形纺？
旋轉(zhuǎn)操作的關(guān)鍵在于：第一步的時候丘侠，原樹拆成了兩棵樹。旋轉(zhuǎn)過程見紙質(zhì)筆記逐样。
左平衡旋轉(zhuǎn)處理函數(shù)代碼
代碼
#define LH +1; // 左高
#define EH 0; // 等高
#define RH -1; // 右高
void LeftBalance(BiTree *T)
{
BiTree L, Lr;
L = (*T)->lchild; // L指向T的左子樹根結(jié)點
switch(L->bf){
case LH:
/*1*/ (*T)->bf = L->bf = EH;
R_Rotate(T);
break;
case RH:
Lr = L->rchild; // Lr指向T的左孩子的右子樹的根
switch(Lr->bf){ // 修改T及其左孩子的平衡因子
case LH:
(*T)->bf = RH;
L->bf = EH;
break;
case EH:
(*T)->bf = L->bf = EH;
break;
case RH:
(*T)->bf = EH;
L->bf = LH;
break;
}
Lr->bf = EH;
L_Rotate(&(*T)->lchild); // 對T的左子樹作左旋平衡處理
R_Rotate(T); // 對T做右旋平衡處理
}
}
代碼解讀
主函數(shù)代碼
代碼
Status InsertAVL(BiTree *T, int e, Status *taller)
{
if(!T){
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = e;
(*T)->lchild = (*T)->rchild = NULL;
(*T)->bf = EH;
*taller = TRUE;
}else{
if(e = (*T)->data){
*taller = FALSE;
return FALSE;
}
if(e <(*T)->data){
if(!InsertAVL(&(*T)->lchild, e, taller)){
return FALSE;
}
if(taller){
switch((*T)->bf){
case LH:
LeftBalance(T);
*taller = FALSE;
break;
case EH:
(*T)->bf = LH;
*taller = TRUE;
break;
case RH:
(*T)->bf = EH;
*taller = FALSE;
break;
}
}
}else{
if(!InsertAVL(&(*T)->rchild, e, taller)){
return FALSE;
}
if(*taller){
switch((*T)->bf){
case LH:
(*T)->bf = EH;
*taller = FALSE;
break;
case EH:
(*T)->bf = RH;
*taller = TRUE;
break;
case RH:
RightBalance(T);
*taller = FALSE;
break;
}
}
}
}
return TRUE;
}
代碼解讀
《大話數(shù)據(jù)結(jié)構(gòu)》中的代碼蜗字，好像有很多錯誤，只可以當作逼真的偽代碼去看待脂新。
多路查找樹（B樹）
摘抄
必要性
要操作的數(shù)據(jù)非常大挪捕，大到無法在內(nèi)存中處理。
定義
多路查找樹（multi-way search tree）的每一個結(jié)點的孩子數(shù)可以多于兩個戏羽，且每一個結(jié)點
處可以存儲多個元素担神。元素之間存在某種特定的排序關(guān)系。
2-3樹
概念
2-3樹的插入實現(xiàn)
2-3樹的刪除實現(xiàn)
可以理解這些方法能夠保證刪除的元素在被刪除后始花，新樹仍然是2-3樹妄讯，但不明白這么做的規(guī)律性，
更無能力用代碼實現(xiàn)刪除操作酷宵。
2-3-4樹
概念
2-3-4樹的插入和刪除
B樹
概念與性質(zhì)
減少內(nèi)存與外存交換數(shù)據(jù)的頻率的原因
B+樹
產(chǎn)生原因--優(yōu)化B樹
概念
與B樹的對比
散列查找表概述
摘抄
定義
散列表查找步驟
1.存儲時亥贸，通過散列函數(shù)計算記錄的散列地址，并按該存儲地址存儲這條記錄浇垦。
2.查找時炕置，通過相同的散列函數(shù)計算記錄的散列地址，并按該散列地址讀取記錄男韧。
散列表適用場景
1.最適合的求解問題是查找與給定關(guān)鍵字等值的記錄朴摊。
2.同樣的關(guān)鍵字對應很多記錄的問題，不適合用散列表查找此虑。
3.范圍查找甚纲，不適合用散列表查找。
沖突
散列函數(shù)的構(gòu)造方法
設計好的散列函數(shù)的原則
1.計算簡單朦前。
2.散列地址分布均勻介杆。這和“使用連續(xù)的存儲空間存儲記錄”有關(guān)嗎鹃操？
直接定址法
概念
優(yōu)缺點
數(shù)字分析法
只強調(diào)了抽取，對散列函數(shù)并無固定要求春哨。
平方取中法
折疊法
存儲標簽id時荆隘，我常用的方法是，存儲“1,2,3,4”這樣的字段赴背。有人提出椰拒，
計算這4個標簽ID的“位運算”，存儲“位運算”的結(jié)果凰荚。具體應用方法已經(jīng)
忘記耸三。這也是折疊法。它們都減少了占用的存儲空間浇揩。
除留余數(shù)法
隨機數(shù)法
處理散列沖突的方法
摘抄
開放定址法
再散列函數(shù)法
存儲的時候，是否應該記錄解決沖突使用的散列函數(shù)憨颠？若不記錄胳徽，讀取
數(shù)據(jù)的時候，如何計算存儲時候的地址爽彤？
鏈接地址法
公共溢出法
散列表查找實現(xiàn)
代碼
散列表結(jié)構(gòu)
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct
{
int *elem; // 數(shù)據(jù)元素存儲基址
int count; // 當前數(shù)據(jù)元素個數(shù)
}HashTable;
int m = 0; // 散列表表長养盗，全局變量
散列表初始化
Status InitHashTable(HashTable *H)
{
int i;
m = HASHSIZE;
H->count = m;
H->elem = (int *)malloc(m*sizeof(int));
for(i = 0; i < m; i++){
H->elem[i] = NULLKEY;
}
return OK;
}
散列函數(shù)
int Hash(int key)
{
return key % m;
}
插入操作
void InsertHash(HashTable *H, int key)
{
int addr = Hash(key); // 求散列地址
while(H->elem[addr] != NULLKEY)
addr = (addr + 1) % m;
H->elem[addr] = key;
}
查詢操作
void SearchHash(HashTable *H, int key)
{
int addr = Hash(key);
while(H->elem[addr] != key){
addr = (addr + 1) % m;
if(H->elem[addr] != key || addr == Hash(key))
{
return UNSUCCESS;
}
}
return SUCCESS;
}
if(H->elem[addr] != key || addr == Hash(key)) 中的 addr == Hash(key) 說明
循環(huán)回到原點，我不理解這點适篙。
if(H->elem[addr] != key || addr == Hash(key))
{
return UNSUCCESS;
}
這塊代碼是否有問題往核？
當 H->elem[addr] != key 成立時，應該繼續(xù)計算哈希地址嚷节。
散列表查找性能分析
喜歡我的文章請關(guān)注公眾號
ganggangwudao或掃描個人主頁的微信二維碼聂儒，謝謝！
我篤信“寫作可以促進思考”硫痰，會以自己面臨的問題為思考素材衩婚，寫成文字，堅持每天推文效斑。
如果可以和大家共同探討非春，就更開心了。
