查找表操作方式分為靜態(tài)查找和動態(tài)查找。
靜態(tài)查找表(Static Search Table): 只作查找操作的查找表;
- 1.查詢某個”特定的”數(shù)據(jù)元素是否在查找表中;
- 檢索某個"特定的"數(shù)據(jù)元素和各種屬性;
動態(tài)查找表(Dynamic Search Table): 在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素, 或者從查找表中刪除已經(jīng)存在的某個數(shù)據(jù)元素; 顯然動態(tài)查找表的操作就是2個動作
- 查找時插?入數(shù)據(jù)元素;
- 查找時刪除數(shù)據(jù)元素;
1、靜態(tài)查找
1.1、順序表查找
順序查找(Sequential Search), 又稱為線性查找. 是最基本的查找技術(shù). 它的查找過程: 從表中的第一個(或最后一個)記錄開始,逐個進?記錄關(guān)鍵字和給定值?比較;
- 1.若某個記錄的關(guān)鍵字和給定值相等,則查找成功,找到所查記錄;
- 如果直到最后一個(或第一個)記錄, 其關(guān)鍵字和給定值比較都不等 時, 則表中沒有所查的記錄,查找不成功;
代碼實現(xiàn)
- 如果直到最后一個(或第一個)記錄, 其關(guān)鍵字和給定值比較都不等 時, 則表中沒有所查的記錄,查找不成功;
int Sequential_Search(int *a,int n,int key){
for (int i = 1; i <= n ; i++)
if (a[i] == key)
return i;
return 0;
}
上面的代碼是可以優(yōu)化的，因為for循環(huán)每次都要比較 i<=n，我們可以減少這步，只需要將給定值存在起始位，從末尾開始查起。
代碼實現(xiàn)：
int Sequential_Search2(int *a,int n,int key){
int i;
//設置a[0]為關(guān)鍵字值,稱為'哨兵'
a[0] = key;
//循環(huán)從數(shù)組尾部開始
i = n;
while (a[i] != key) {
i--;
}
//返回0,則說明查找失敗
return i;
}
1.2、折半查找
折半查找(Binary Search)技術(shù),又稱為二分查找。
它的前提是線性表中的記錄必須是關(guān)鍵碼有序(通常是從小到大有序),線性 表必須采用順序存儲;
折半查找的基本思想是:
- 在有序表中,取中間記錄作為?較對象,若給定值與中間記錄的關(guān)鍵字相等則查找成功;
- 若給定值小于中間的記錄關(guān)鍵字,則在中間記錄的左半?yún)^(qū)繼續(xù)查找;
- 若給定值大于中間的記錄關(guān)鍵字,則在中間記錄的右半?yún)^(qū)繼續(xù)查找;
- 不斷重復以上的過程,直到查找成功,或所有查找區(qū)域無記錄,查找失敗為止。
代碼實現(xiàn)：
int Binary_Search(int *a,int n,int key){
int low,high,mid;
//定義最低下標為記錄首位
low = 1;
//定義最高下標為記錄末位
high = n;
while (low <= high) {
//折半計算
mid = (low + high) /2;
if (key < a[mid]) {
//若key比a[mid] 小,則將最高下標調(diào)整到中位下標小一位;
high = mid-1;
}else if(key > a[mid]){
//若key比a[mid] 大,則將最低下標調(diào)整到中位下標大一位;
low = mid+1;
}else
//若相等則說明mid即為查找到的位置;
return mid;
}
return 0;
}
1.3、插值查找
插值查找是根據(jù)查找的關(guān)鍵字key 與查找表中最大最小記錄的關(guān)鍵字比較后的查找方法,其核心就是在于插值的計算公式: (key - a[low]) / (a[high] - a[low]).
代碼實現(xiàn)：
int Interpolation_Search(int *a,int n,int key){
int low,high,mid;
low = 1;
high = n;
while (low <= high) {
//插值
mid = low+ (high-low)*(key-a[low])/(a[high]-a[low]);
if (key < a[mid]) {
//若key比a[mid]插值小,則將最高下標調(diào)整到插值下標小一位;
high = mid-1;
}else if(key > a[mid]){
//若key比a[mid]插值 大,則將最低下標調(diào)整到插值下標大一位;
low = mid+1;
}else
//若相等則說明mid即為查找到的位置;
return mid;
}
return 0;
}
1.4、斐波拉契查找
斐波拉契查找利用了黃金分割的原理來實現(xiàn)。
代碼實現(xiàn)：
int F[100]; /* 斐波那契數(shù)列 */
int Fibonacci_Search(int *a,int n,int key){
int low,high,mid,i,k;
//最低下標為記錄的首位;
low = 1;
//最高下標為記錄的末位;
high = n;
k = 0;
//1.計算n為斐波拉契數(shù)列的位置;
while (n > F[k]-1) {
k++;
}
//2.將數(shù)組a不滿的位置補全值;
for(i = n;i < F[k]-1;i++)
a[i] = a[n];
//3.
while (low <= high) {
//計算當前分隔的下標;
mid = low+F[k-1]-1;
if (key < a[mid]) {
//若查找的記錄小于當前分隔記錄;
//將最高下標調(diào)整到分隔下標mid-1處;
high = mid-1;
//斐波拉契數(shù)列下標減1位;
k = k-1;
}else if(key > a[mid]){
//若查找的記錄大于當前的分隔記錄;
//最低下標調(diào)整到分隔下標mid+1處
low = mid+1;
//斐波拉契數(shù)列下標減2位;
k = k-2;
}else{
if (mid <= n) {
//若相等則說明,mid即為查找的位置;
return mid;
}else
{
//若mid>n,說明是補全數(shù)值,返回n;
return n;
}
}
}
return 0;
}
2、動態(tài)查找
二叉排序樹(Binary Sort Tree),又稱為二叉查找樹. 它或者是一顆空樹.或者是一顆具有下列性質(zhì)的二叉樹。
- 若它的左子樹不空,則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值;
- 若它的右子樹不空,則右子樹上的所有結(jié)點的值均大于它的根結(jié)點的值;
- 它的左右子樹也分別是?叉排序樹。
代碼實現(xiàn)：
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;
//二叉樹的二叉鏈表結(jié)點結(jié)構(gòu)定義
//結(jié)點結(jié)構(gòu)
typedef struct BiTNode
{
//結(jié)點數(shù)據(jù)
int data;
//左右孩子指針
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//1.二叉排序樹--查找
/*
遞歸查找二叉排序樹T中,是否存在key;
指針f指向T的雙親,器初始值為NULL;
若查找成功,則指針p指向該數(shù)據(jù)元素的結(jié)點,并且返回TRUE;
若指針p指向查找路徑上訪問的最后一個結(jié)點則返回FALSE;
*/
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->lchild, key, T, p); /* 在左子樹中繼續(xù)查找 */
else
return SearchBST(T->rchild, key, T, p); /* 在右子樹中繼續(xù)查找 */
}
//2.二叉排序樹-插入
/* 當二叉排序樹T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時， */
/* 插入key并返回TRUE，否則返回FALSE */
Status InsertBST(BiTree *T, int key) {
BiTree p,s;
//1.查找插入的值是否存在二叉樹中;查找失敗則->
if (!SearchBST(*T, key, NULL, &p)) {
//2.初始化結(jié)點s,并將key賦值給s,將s的左右孩子結(jié)點暫時設置為NULL
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
//3.
if (!p) {
//如果p為空,則將s作為二叉樹新的根結(jié)點;
*T = s;
}else if(key < p->data){
//如果key<p->data,則將s插入為左孩子;
p->lchild = s;
}else
//如果key>p->data,則將s插入為右孩子;
p->rchild = s;
return TRUE;
}
return FALSE;
}
//3.從二叉排序樹中刪除結(jié)點p,并重接它的左或者右子樹;
Status Delete(BiTree *p){
BiTree temp,s;
if((*p)->rchild == NULL){
//情況1: 如果當前刪除的結(jié)點,右子樹為空.那么則只需要重新連接它的左子樹;
//①將結(jié)點p臨時存儲到temp中;
temp = *p;
//②將p指向到p的左子樹上;
*p = (*p)->lchild;
//③釋放需要刪除的temp結(jié)點;
free(temp);
}else if((*p)->lchild == NULL){
//情況2:如果當前刪除的結(jié)點,左子樹為空.那么則只需要重新連接它的右子樹;
//①將結(jié)點p存儲到temp中;
temp = *p;
//②將p指向到p的右子樹上;
*p = (*p)->rchild;
//③釋放需要刪除的temp結(jié)點
free(temp);
}else{
//情況③:刪除的當前結(jié)點的左右子樹均不為空;
//①將結(jié)點p存儲到臨時變量temp, 并且讓結(jié)點s指向p的左子樹
temp = *p;
s = (*p)->lchild;
//②將s指針,向右到盡頭(目的是找到待刪結(jié)點的前驅(qū))
//-在待刪除的結(jié)點的左子樹中,從右邊找到直接前驅(qū)
//-使用`temp`保存好直接前驅(qū)的雙親結(jié)點
while (s->rchild) {
temp = s;
s = s->rchild;
}
//③將要刪除的結(jié)點p數(shù)據(jù)賦值成s->data;
(*p)->data = s->data;
//④重連子樹
//-如果temp 不等于p,則將S->lchild 賦值給temp->rchild
//-如果temp 等于p,則將S->lchild 賦值給temp->lchild
if(temp != *p)
temp->rchild = s->lchild;
else
temp->lchild = s->lchild;
//⑤刪除s指向的結(jié)點; free(s)
free(s);
}
return TRUE;
}
//4.查找結(jié)點,并將其在二叉排序中刪除;
/* 若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時，則刪除該數(shù)據(jù)元素結(jié)點, */
/* 并返回TRUE；否則返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{
//不存在關(guān)鍵字等于key的數(shù)據(jù)元素
if(!*T)
return FALSE;
else
{
//找到關(guān)鍵字等于key的數(shù)據(jù)元素
if (key==(*T)->data)
return Delete(T);
else if (key<(*T)->data)
//關(guān)鍵字key小于當前結(jié)點,則縮小查找范圍到它的左子樹;
return DeleteBST(&(*T)->lchild,key);
else
//關(guān)鍵字key大于當前結(jié)點,則縮小查找范圍到它的右子樹;
return DeleteBST(&(*T)->rchild,key);
}
}
