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