查找:就是根據(jù)給定的某個值,在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素(或記錄)
查找表按照操作方式分為兩大種:靜態(tài)查找表和動態(tài)查找表.
靜態(tài)查找表:只做查找操作的查找表.它的主要操作有:
1.查詢某個'特定的'數(shù)據(jù)元素是否在查找表中
2.檢索某個'特定的'數(shù)據(jù)元素和各種屬性
動態(tài)查找表:在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素,或者從查找表中刪除已經(jīng)存在的某個數(shù)據(jù)元素.注意操作:
1.查找時插入數(shù)據(jù)元素
2.查找時刪除數(shù)據(jù)元素
2.順序表查找
順序查找又叫線性查找,是最基本的查找技術(shù),它的查找過程是:從表中第一個(或最后一個)記錄開始,逐個進行記錄的關(guān)鍵字和給定值比較,若某個記錄的關(guān)鍵字和給定值相等,則查找成功,找到所查的記錄;如果直到最后一個(或第一個)記錄,其關(guān)鍵字和給定值比較都不等時,則表中沒有所查的記錄,查找不成功
查找表算法:
//順序查找,a為數(shù)組,n為要查找的數(shù)組個數(shù),key為要查找的關(guān)鍵字
int Sequential_Search(int *a,int n,int key){
int i;
for (i = i; i <= n; i++){
if (a[i] == key)
return i;
}
return 0;
}
順序表查找優(yōu)化
設(shè)置哨兵,可以解決每次讓i與n作比較
int Sequetial_Search2 (int *a,int n,int key){
int i;
a[0] = key;//設(shè)置a[0]為關(guān)鍵字,我們稱為"哨兵"
i = n;//循環(huán)從數(shù)組尾部開始
while(a[i] != key){{
i--;
}
return i ;//返回0則說明查找失敗
}
順序查找技術(shù)有很大的缺點,n很大事,查找效率極為低下,優(yōu)點是,算法簡單,對靜態(tài)查找表的記錄沒有任何要求,在一些小型數(shù)據(jù)的查找,也是可以適用的
3.有序表查找
1.折半查找
折半查找技術(shù),又稱為二分查找,他的前提是線性表中的記錄必須是關(guān)鍵碼有序(通常從小到達有序),線性表必須采用順序存儲.折半查找的基本思想是:在有序表中,取中間記錄作比較對象,若給定值與中間記錄的關(guān)鍵字相等,則查找成功;若給定值小于中間記錄的關(guān)鍵字,則在中間記錄的關(guān)鍵字,則在中間記錄的左半?yún)^(qū)繼續(xù)查找;若給定值大于中間記錄的關(guān)鍵字,則在中間記錄的右半?yún)^(qū)繼續(xù)查找.不斷重復(fù)上述過程,直到查找成功,或所有查找區(qū)域無記錄,查找失敗為止.
有序表數(shù)組{0,1,16,24,35,47,59,62,73,88,99},除0下標外共10個數(shù)字對它進行查找是否存在62這個樹
//折半查找
int Binary_Search (int *a, int n ,int key){
int low,high,mid;
low = 0;//定義最低下標為記錄首位
high = n;//定義最高下標為記錄末位
while(low <=hight){
mid = (low + high) / 2;//折半
if (key < a[mid])//若查找值比中指小
high = mid - 1;//最高下標調(diào)整到中位下標小一位
else if (key > a[mid])//若查找值比中值大
low = mid + 1;//最低下標調(diào)整到中位下標大衣位
else
return mid;//若相等則說明mid即為查找到的位置
}
return 0;
}
1.程序開始運行,參數(shù)a={0,1,16,24,35,47,59,62,73,88,99},n=10,key= 62,第3~5行,此時low-1,high = 10
2.mid = (0+ 10) / 2 = 5,a[5] =47 < key,所以執(zhí)行第12行 low = 5+1 = 6
3.mid = (6+ 10)/2 = 8,a[8] = 73> key,所以執(zhí)行第10行,high= 8 - 1= 7
4.mid =(6 + 7)/ 2 = 6 ,a[6] = 59< key,執(zhí)行第12行.low = 6+1=7
2.插值查找
你一定會想,為什么非得折半,為什么不可以四分之一或者更多那.這一點算法數(shù)學(xué)家已經(jīng)考慮了,而且還改進了折半查找的算法
折半查找代碼的第八句,我們使用等式變換后得到:
mid = (low + high) / 2 = low + 1 * (hight - low)/ 2,算法數(shù)學(xué)家將1/2進行改進,得到
........啥,,你問我怎么改的,來,過來~,靠近點,看我不打死你,這樣就沒人知道我也不會了
那現(xiàn)在不問了吧,咱們接著往下扯,呸~咱們接著往下學(xué)
//插值查找
int Interpolation_Search (int *a, int n ,int key){
int low,high,mid; low = 0;//定義最低下標為記錄首位
high = n;//定義最高下標為記錄末位
while(low <=hight){
**mid = low +( key - a[low]) * (high - low) /a[high] - a[low];**//插值查找
if (key < a[mid])//若查找值比中指小
high = mid - 1;//最高下標調(diào)整到中位下標小一位
else if (key > a[mid])//若查找值比中值大
low = mid + 1;//最低下標調(diào)整到中位下標大衣位
else
return mid;//若相等則說明mid即為查找到的位置
}
return 0;
}
3.斐波那契查找
斐波那契查找,利用黃金分割的原來來實現(xiàn)的,黃金分割哦~
提起斐波那契數(shù)列,一定會想到那個經(jīng)典的兔子生兔子的命題,就不詳細介紹了
//斐波那契查找
int Fibonacci_Search(int * a, int n , int key){
int low, high, mid, i, k;
low = 0;//定義最低下標為記錄首位
high = n;//定義最高下標為記錄首位
k = 0;
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; //最高下標調(diào)整到分隔下標mid - 1處
k =k - 1;//斐波那契數(shù)列下標-1
}
else if(key > a[mid]){ //若查找記錄大于當前分隔記錄
low = mid + 1;//最低下標調(diào)整到分隔下標+ 1處
k = k + 2;
}else{
if (mid < = n) {
return mid; //若相等則說明mid即為查找到的位置
}else{
return n;//若mid > n,說明是補全數(shù)組,返回n
}
}
}
return 0;
}
4.二叉排序樹
對集合{21,28,14,32,25,18,11,30,19,15}做查找,我們打算創(chuàng)建此集合時就考慮二叉樹結(jié)構(gòu),而且是排序好的二叉樹,集合的第一個元素21,做根結(jié)點,比他小的為左子樹,大的為右子數(shù)
我們對他進行中序遍歷,即可得到一個有序的序列{11,14,15,19,18,21,25,28,30,32},所有我們通常稱他為二叉排序樹
二叉排序樹,又稱為二叉查找樹.它或者是一棵空樹,或者是具有下列性質(zhì)的二叉樹
- 1.若它的左子樹不空,則左子樹上所有結(jié)點的值均小于它的根結(jié)構(gòu)的值
- 2.若它的右子樹不空,則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值
- 3.它的左,右子樹也分別為二叉排序樹
左子樹結(jié)點一定比其雙親結(jié)點小,右子樹結(jié)點一定比其雙親結(jié)點大
5.二叉排序樹查找操作
//二叉樹定義
typedef struct BitNode //結(jié)點結(jié)構(gòu)
{
int data; //結(jié)點數(shù)據(jù)
struct BitNode *lchild,*rchild;//左右孩子指針
}BitNode , *BiTree;
//二叉排序樹的查找實現(xiàn)
//遞歸查找二叉排序樹T中是否存在key
//指針f指向T的雙親,其初始調(diào)用值為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ù)查找
}
由圖可以看成,使用二叉樹查找只需要三步即可,而使用有序的數(shù)組需要10步
6.二叉排序樹的刪除操作
我們對刪除結(jié)點三種情況的分析
1.葉子結(jié)點
2.僅有左或右子樹的結(jié)點
-
3.左右子樹都有的結(jié)點
//若二叉排序樹中存在關(guān)鍵字等于key的數(shù)據(jù)元素,則刪除該數(shù)據(jù)元素結(jié)點 //并返回TRUE ,否則返回FALSE Status DeleteBST (BiTree *T, int key){ if (!T) //不存在關(guān)鍵字等于key的數(shù)據(jù)元素 return FALSE; else{ if (key == (*T )->data) //找到關(guān)鍵字等于key的數(shù)據(jù)元素 return Delete(T); else if (key < (*T) -> data) return DeleteBST(&(*T) -> lchild, key); else return DeleteBST(@&(*T) -> rchild ,key); } } //重點來了 ...... Status Delete(BiTree *p ) { BiTree q,s; if ((*p) -> rchild == NULL) //右子樹空則只需要重接它的左子樹 q = *p; *p = (*p) -> rchild; free(q); else{ //左右子樹均不空 q = *p; s = (*p) -> lchild; while (s -> rchild) { //轉(zhuǎn)左,然后向右到盡頭(找待刪結(jié)點的前驅(qū)) q = s; s = s -> rchild; } (*p) -> data = s -> data; //s指向被刪除結(jié)點的直接前驅(qū) if (q != *p) q -> rchild = s -> lchild; //重接q的右子樹 else q -> lchild = s -> lchild;//重接q的左子樹 free(s); } return TRUE; }
如果前面的代碼,看不下去的話,這里是重點!!!!!
思路:被刪除結(jié)點A的左子樹的最右結(jié)點或A的右子樹的最左結(jié)點作為替代A的結(jié)點,并修改相應(yīng)的最左或最右結(jié)點的父節(jié)點的指針
7.平衡二叉樹
平衡二叉樹是一種**二叉排序樹**,其中每一個節(jié)點的左子樹和右子樹的高度差至多等于1,那么平衡二叉樹的平衡因子只可能是-1,0和1
我們將二叉樹上結(jié)點的左子樹深度減去右子數(shù)深度的值稱為平衡因子
距離插入節(jié)點最近的,且平衡因子的絕對值大于1的結(jié)點為根的子樹,我們稱為最小不平衡子樹
當新插入結(jié)點37時,距離它最近的平衡因子絕對值超過1的結(jié)點是58(即它的左子樹高度2減去右子數(shù)高度0),所有從58開始以下的子樹為最小不平衡子樹
8.平衡二叉樹實現(xiàn)原理
數(shù)組a[10] = {3,2,1,4,5,6,7,10,9,8}需要構(gòu)建平衡二叉樹
