7.1概述

7.1.1查找的基本概念

1.關(guān)鍵碼

關(guān)鍵碼：可以標(biāo)識(shí)一個(gè)記錄的某個(gè)數(shù)據(jù)項(xiàng)。?
?鍵值：關(guān)鍵碼的值。
?主關(guān)鍵碼：可以唯一地標(biāo)識(shí)一個(gè)記錄的關(guān)鍵碼。
?次關(guān)鍵碼：不能唯一地標(biāo)識(shí)一個(gè)記錄的關(guān)鍵碼

2.查找

查找 ：在具有相同類型的記錄構(gòu)成的集合中找出滿足給定條件的記錄。?
?給定的查找條件可能是多種多樣的，為便于討論，把查找條件限制為“匹配”，即查找關(guān)鍵碼等于給定值的記錄。?

查找的結(jié)果 ：若在查找集合中找到了與給定值相匹配的記錄，則稱查找成功；否則，稱查找失敗

靜態(tài)查找 ：不涉及插入和刪除操作的查找 。
?動(dòng)態(tài)查找 ：涉及插入和刪除操作的查找。

靜態(tài)查找適用于：查找集合一經(jīng)生成，便只對(duì)其進(jìn)行查找，而不進(jìn)行插入和刪除操作，或經(jīng)過(guò)一段時(shí)間的查找之后，集中地進(jìn)行插入和刪除等修改操作；
動(dòng)態(tài)查找適用于：查找與插入和刪除操作在同一個(gè)階段進(jìn)行，例如當(dāng)查找成功時(shí)，要?jiǎng)h除查找到的記錄，當(dāng)查找不成功時(shí)，要插入被查找的記錄。

查找結(jié)構(gòu) ：面向查找操作的數(shù)據(jù)結(jié)構(gòu) ，即查找基于的數(shù)據(jù)結(jié)構(gòu)。

?線性表：適用于靜態(tài)查找，主要采用順序查找技術(shù)和折半查找技術(shù)。
?樹(shù)表：適用于動(dòng)態(tài)查找，主要采用二叉排序樹(shù)的查找技術(shù)。
?散列表：靜態(tài)查找和動(dòng)態(tài)查找均適用，主要采用散列技術(shù)。?

7.2線性表的查找順序

1.順序查找

基本思想：從線性表的一端向另一端逐個(gè)將關(guān)鍵碼與給定值進(jìn)行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個(gè)表檢測(cè)完仍未找到與給定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。

int SeqSearch1(int r[ ], int n, int k)
//數(shù)組r[1] ~ r[n]存放查找集合
{ ??
? ? ?i = n;
? ? ?while (i > 0 && r[i] != k)
? ? ? ? ?i--;
? ? ?return i;
}

順序查找的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：算法簡(jiǎn)單而且使用面廣

對(duì)表中記錄的存儲(chǔ)沒(méi)有任何要求，順序存儲(chǔ)和鏈接存儲(chǔ)均可；
對(duì)表中記錄的有序性也沒(méi)有要求，無(wú)論記錄是否按關(guān)鍵碼有序均可。

缺點(diǎn)：平均查找長(zhǎng)度較大，特別是當(dāng)待查找集合中元素較多時(shí)，查找效率較低。

2.折半查找

基本思想：在有序表中，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過(guò)程，直到查找成功，或所查找的區(qū)域無(wú)記錄，查找失敗。

折半查找——非遞推算法

int BinSearch1(int r[ ], int n, int k)
{ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//數(shù)組r[1] ~ r[n]存放查找集合
? ? low = 1; high = n;
? ? while (low <= high) ? ? ? ? ? ? ? ? ??
? ? {
? ? ? ?mid = (low + high) / 2; ? ? ? ? ? ?
? ? ? ?if (k < r[mid]) ?high = mid - 1;
? ? ? ?else if (k > r[mid]) ?low = mid + 1;?
? ? ? ? ? ? ? else return mid;
? ? }
? ? return 0;
}

折半查找——遞推算法

int BinSearch2(int r[ ], int low, int high, int k)
{ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//數(shù)組r[1] ~ r[n]存放查找集合
? ? if (low > high) return 0; ?
? ? else {
? ? ? ?mid = (low + high) / 2;
? ? ? ?if (k < r[mid])?
? ? ? ? ? ?return BinSearch2(r, low, mid-1, k);
? ? ? ?else ?if (k > r[mid])?
? ? ? ? ? ? ? ? ? ?return BinSearch2(r, mid+1, high, k);?
? ? ? ? ? ? ? ?else return mid;
? ? ?}

?}

折半查找判定樹(shù)

判定樹(shù)：折半查找的過(guò)程可以用二叉樹(shù)來(lái)描述，樹(shù)中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)有序表中的一個(gè)記錄，結(jié)點(diǎn)的值為該記錄在表中的位置。通常稱這個(gè)描述折半查找過(guò)程的二叉樹(shù)為折半查找判定樹(shù)，簡(jiǎn)稱判定樹(shù)。

判定樹(shù)的構(gòu)造方法

⑴ 當(dāng)n=0時(shí)，折半查找判定樹(shù)為空；
⑵ 當(dāng)n＞0時(shí)，折半查找判定樹(shù)的根結(jié)點(diǎn)是有序表中序號(hào)為mid=(n+1)/2的記錄，根結(jié)點(diǎn)的左子樹(shù)是與有序表r[1] ~ r[mid-1]相對(duì)應(yīng)的折半查找判定樹(shù)，根結(jié)點(diǎn)的右子樹(shù)是與r[mid+1] ~ r[n]相對(duì)應(yīng)的折半查找判定樹(shù)。?

7.3數(shù)表的查找技術(shù)

1.二叉查找樹(shù)

二叉排序樹(shù)（也稱二叉查找樹(shù)）：或者是一棵空的二叉樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：
⑴ 若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；
⑵ 若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；
⑶ 它的左右子樹(shù)也都是二叉排序樹(shù)。

二叉樹(shù)的構(gòu)造算法

BiSortTree::BiSortTree(int r[ ], int n)
{ ? ??
? ? for (i = 0; i < n; i++)
? ? {
? ? ? ?s = new BiNode<int>;?
? ? ? ?s->data = r[i];
? ? ? ?s->lchild = s->rchild = NULL;
? ? ? ?InsertBST(root, s);
? ? }
}

小結(jié)

一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列;
每次插入的新結(jié)點(diǎn)都是二叉排序樹(shù)上新的葉子結(jié)點(diǎn);
找到插入位置后，不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針；
在左子樹(shù)/右子樹(shù)的查找過(guò)程與在整棵樹(shù)上查找過(guò)程相同；
新插入的結(jié)點(diǎn)沒(méi)有破壞原有結(jié)點(diǎn)之間的關(guān)系。

二叉排序樹(shù)的查找

BiNode *BiSortTree::SearchBST(BiNode<int> *root, int k)
{
? ? if (root == NULL)
? ? return NULL；
? ? else if (root->data == k)?
? ? ? ? ? ? ? return root;
? ? ? ? ? ?else if (k < root->data)?
? ? ? ? ? ? ? ? ? ? ? return SearchBST(root->lchild, k);
? ? ? ? ? ? ? ? ? else return SearchBST(root->rchild, k);
}

2.平衡二叉樹(shù)

平衡二叉樹(shù)：或者是一棵空的二叉排序樹(shù)，或者是具有下列性質(zhì)的二叉排序樹(shù)：
⑴ 根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的深度最多相差1;
⑵ 根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)也都是平衡二叉樹(shù)。

7.4散列表的查找技術(shù)

散列的基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵碼之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系。這樣，不經(jīng)過(guò)比較，一次讀取就能得到所查元素的查找方法。

散列表：采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)的存儲(chǔ)空間稱為散列表。

散列函數(shù)：將關(guān)鍵碼映射為散列表中適當(dāng)存儲(chǔ)位置的函數(shù)。

散列技術(shù)一般不適用于允許多個(gè)記錄有同樣關(guān)鍵碼的情況。散列方法也不適用于范圍查找，換言之，在散列表中，我們不可能找到最大或最小關(guān)鍵碼的記錄，也不可能找到在某一范圍內(nèi)的記錄。

散列技術(shù)的關(guān)鍵問(wèn)題：
⑴ 散列函數(shù)的設(shè)計(jì)。如何設(shè)計(jì)一個(gè)簡(jiǎn)單、均勻、存儲(chǔ)利用率高的散列函數(shù)。
⑵ 沖突的處理。如何采取合適的處理沖突方法來(lái)解決沖突。

沖突：對(duì)于兩個(gè)不同關(guān)鍵碼ki≠kj，有H(ki)＝H(kj)，即兩個(gè)不同的記錄需要存放在同一個(gè)存儲(chǔ)位置,ki和kj相對(duì)于H稱做同義詞。

設(shè)計(jì)散列函數(shù)一般應(yīng)遵循以下原則：
⑴ 計(jì)算簡(jiǎn)單。散列函數(shù)不應(yīng)該有很大的計(jì)算量，否則會(huì)降低查找效率。
⑵ 函數(shù)值即散列地址分布均勻。函數(shù)值要盡量均勻散布在地址空間，這樣才能保證存儲(chǔ)空間的有效利用并減少?zèng)_突。

總結(jié)

以上是生活随笔為你收集整理的第七章 查找技术的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。