查找算法總結(jié)-創(chuàng)新互聯(lián)

查找
對(duì)數(shù)值型關(guān)鍵字

成都創(chuàng)新互聯(lián)專業(yè)IDC數(shù)據(jù)服務(wù)器托管提供商，專業(yè)提供成都服務(wù)器托管，服務(wù)器租用，重慶服務(wù)器托管，重慶服務(wù)器托管，成都多線服務(wù)器托管等服務(wù)器托管服務(wù)。

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

對(duì)字符串型關(guān)鍵字

#define EQ(a,b) (!strcmp((a),(b)))
#define LT(a,b) (strcmp((a),(b))<0)
#define LQ(a,b) (strcmp((a),(b))<=0)

一、靜態(tài)查找表
存儲(chǔ)結(jié)構(gòu)

typedef *** KeyType;
typedef struct
{
? ? KeyType key;
} ElemType;
typedef struct
{
? ? ElemType *elem;
? ? int length;
} SSTable;

1.順序表的查找
1)思路：從前向后逐一比較，找到就返回位序，否則返回0

int Search_Seq(SSTable ST,KeyType x)
{
? ? for(int i=1; i<=ST.length; i++)
? ? {
? ? ? ? if(ST.elem[i].key==x)
? ? ? ? ? ? return i;
? ? }
? ? return 0;
}

2)思路：添加哨兵，從后向前比較，省略每次循環(huán)時(shí)的越界檢查

int Search_Seq(SSTable ST,KeyType x)
{
? ? ST.elem[0].key=x;
? ? for(int i=ST.length; ST.elem[i]!=x; i--);
? ? return i;
}//結(jié)構(gòu)化代碼，單入口單出口

2.有序表的查找
折半查找
1)

int Search_Bin(SSTable ST,KeyType x)
{
? ? int low=1,high=ST.length;
? ? while(low<=high)
? ? {
? ? ? ? int mid=(low+high)/2;
? ? ? ? if(ST.elem[mid].key==x)
? ? ? ? ? ? return mid;
? ? ? ? else if(ST.elem[mid].key>x)
? ? ? ? ? ? high=mid-1;
? ? ? ? else
? ? ? ? ? ? low=mid+1;
? ? }
? ? return 0;
}

int Search_Bin(SSTable ST,KeyType x)
{
? ? int low=1,high=ST.length;
? ? int isDetected=FALSE;
? ? while(low<=high&&isDetected==FALSE)
? ? {
? ? ? ? int mid=(low+high)/2;
? ? ? ? if(ST.elem[mid].key==x)
? ? ? ? ? ? isDetected=TRUE;
? ? ? ? else if(ST.elem[mid].key>x)
? ? ? ? ? ? high=mid-1;
? ? ? ? else
? ? ? ? ? ? low=mid+1;
? ? }
? ? if(isDetected==FALSE)
? ? ? ? return 0;
? ? else
? ? ? ? return mid;
}//結(jié)構(gòu)化代碼，單入口單出口

二、動(dòng)態(tài)查找表
1.二叉搜索樹(shù)
存儲(chǔ)結(jié)構(gòu)

typedef **** KeyType;
typedef struct
{
? ? KeyType key;
} ElemType;
typedef struct BiTNode
{
? ? ElemType data;
? ? struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
typedef BiTree BSTree;
typedef BiTNode BSTNode;

1)查找

遞歸思路：如果樹(shù)為空，查找失敗，返回NULL
否則，從根節(jié)點(diǎn)開(kāi)始，將x與根節(jié)點(diǎn)進(jìn)行比較
若x小于根節(jié)點(diǎn)，遞歸查找左子樹(shù)，并返回查找結(jié)果
若x大于根節(jié)點(diǎn)，遞歸查找右子樹(shù)，并返回查找結(jié)果
若x等于根節(jié)點(diǎn)，查找成功，返回根節(jié)點(diǎn)地址

BiTNode *BSTSearch(BSTree T,KeyType x)
{
? ? if(!T)
? ? ? ? return NULL;
? ? else
? ? {
? ? ? ? if(T->data.key>x)
? ? ? ? ? ? return BSTSearch(T->lchild,x);
? ? ? ? else if(T->data.keyrchild,x);
? ? ? ? else
? ? ? ? ? ? return T;
? ? }
}

非遞歸思路：p最初指向根節(jié)點(diǎn)，只要p不空且p所指結(jié)點(diǎn)不是所求
則根據(jù)比較結(jié)果令p變?yōu)楫?dāng)前結(jié)點(diǎn)的左孩子或右孩子。
如此重復(fù)則最終p空或者找到

BiTNode *BSTSearch(BSTree T,KeyType x)
{
? ? BiTNode *p=T;
? ? while(p&&!EQ(p->data.key,key))
? ? {
? ? ? ? if(LT(x,p->data.key))
? ? ? ? ? ? p=p->lchild;
? ? ? ? else
? ? ? ? ? ? p=p->rchild;
? ? }
? ? if(!p)
? ? ? ? return NULL;
? ? else
? ? ? ? return p;
}

查找最小元素:
最左端點(diǎn)
查找大元素:
最右端點(diǎn)

2)插入
非遞歸思路：先查找是否重復(fù)，無(wú)重復(fù)則插入，插入位置是最后一個(gè)所走節(jié)點(diǎn)的孩子
查找過(guò)程中同時(shí)記錄所走節(jié)點(diǎn)和其父節(jié)點(diǎn)f，無(wú)重復(fù)時(shí)新開(kāi)辟節(jié)點(diǎn)放到f孩子上
要注意引用型參數(shù)

Status BSTInsert(BSTree &T,ElemType e)
{
? ? BSTNode *p=T,*f=NULL;
? ? while(p!=NULL&&!EQ(p->data.key,e.key))
? ? {
? ? ? ? f=p;
? ? ? ? if(LT(e.key,p->data.key))
? ? ? ? ? ? p=p->lchild;
? ? ? ? else
? ? ? ? ? ? p=p->rchild;
? ? }
? ? if(p==NULL)
? ? {
? ? ? ? BiTNode *q=new BiTNode;
? ? ? ? q->data=e;
? ? ? ? q->lchild=NULL;
? ? ? ? q->rchild=NULL;
? ? ? ? if(!f)
? ? ? ? ? ? T=q;
? ? ? ? if(LT(e.key,f->data.key))
? ? ? ? ? ? f->lchild=q;
? ? ? ? else
? ? ? ? ? ? f->rchild=q;
? ? ? ? return OK;
? ? }
? ? else
? ? ? ? return ERROR;
}

遞歸思路：與根節(jié)點(diǎn)比較，相等則不插入，否則，轉(zhuǎn)換為左或右子樹(shù)中的插入
遞歸邊界：發(fā)現(xiàn)重復(fù)不遞歸，返回ERROR；到達(dá)空樹(shù)不遞歸，直接開(kāi)辟節(jié)點(diǎn)
T為引用型參數(shù)是拼接的關(guān)鍵
S

tatus BSTInsert(BSTree &T,ElemType e)
{
? ? if(!T)
? ? {
? ? ? ? BSTNode *p=new BSTNode;
? ? ? ? p->data=e;
? ? ? ? p->rchild=NULL;
? ? ? ? p->lchild=NULL;
? ? ? ? T=p;
? ? ? ? return OK;
? ? }
? ? else if(EQ(e.key,T->data.key))
? ? ? ? return ERROR;
? ? else if(LT(e.key,T->data.key))
? ? ? ? BSTInsert(T->lchild,e);
? ? else
? ? ? ? BSTInsert(T->rchild,e);
}

3)創(chuàng)建

Status CreateBST(BSTree &T)
{
? ? T=NULL;
? ? while(InputElem(e)<=0)
? ? {
? ? ? ? if(BSTInsert(T,e)==ERROR)
? ? ? ? ? ? return ERROR;
? ? ? ? else
? ? ? ? ? ? InputElem(e);
? ? }
}

4)刪除
思路：刪除葉子節(jié)點(diǎn)：直接刪除
刪除只有一個(gè)子樹(shù)的節(jié)點(diǎn)：直接將子樹(shù)接到被刪除節(jié)點(diǎn)的雙親指針上
刪除有兩個(gè)子樹(shù)的節(jié)點(diǎn)：將左子樹(shù)大或右子樹(shù)最小移至刪除位置，
歸結(jié)為刪除左子樹(shù)大或者右子樹(shù)最小節(jié)點(diǎn)，這兩類節(jié)點(diǎn)至多有一個(gè)孩子

void DeleteBST(BiTree &T,KeyType key)
{
? ? BSTBode *p=T,*f=NULL;
? ? while(p!=NULL&&!EQ(key,p->data.key))
? ? {
? ? ? ? f=p;
? ? ? ? if(LT(key,p->data.key))
? ? ? ? ? ? p=p->lchild;
? ? ? ? else
? ? ? ? ? ? p=p->rchild;
? ? }
? ? if(!p)
? ? ? ? return;
? ? if(!p->lchild&&!p->rchild) ?//p若為葉子節(jié)點(diǎn)
? ? {
? ? ? ? if(!f) ? ? //p為根節(jié)點(diǎn)
? ? ? ? {
? ? ? ? ? ? free(p);
? ? ? ? ? ? p=NULL;
? ? ? ? ? ? T=NULL;
? ? ? ? }
? ? ? ? else if(f->lchild==p)
? ? ? ? {
? ? ? ? ? ? f->lchild=p;
? ? ? ? ? ? free(p);
? ? ? ? ? ? p=NULL;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? f->rchild=p;
? ? ? ? ? ? free(p);
? ? ? ? ? ? p=NULL;
? ? ? ? }
? ? }
? ? if(!p->lchild) ? ?//若左孩子為空，p只有右孩子
? ? {
? ? ? ? if(!f) ? ?//p為根節(jié)點(diǎn)
? ? ? ? {
? ? ? ? ? ? T=p->rchild;
? ? ? ? ? ? free(p);
? ? ? ? ? ? p=NULL;
? ? ? ? }
? ? ? ? else if(f->lchild==p)
? ? ? ? {
? ? ? ? ? ? f->lchild=p->rchild;
? ? ? ? ? ? free(p);
? ? ? ? ? ? p=NULL;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? f->rchild=p->rchild;
? ? ? ? ? ? free(p);
? ? ? ? ? ? p=NULL;
? ? ? ? }
? ? }
? ? if(!p->rchild) ? //p右孩子為空，只有左孩子
? ? {
? ? ? ? if(!f)
? ? ? ? {
? ? ? ? ? ? T=p->lchild;
? ? ? ? ? ? free(p);
? ? ? ? ? ? p=NULL;
? ? ? ? }
? ? ? ? else if(f->lchild==p)
? ? ? ? {
? ? ? ? ? ? f->lchild=p->lchild;
? ? ? ? ? ? free(p);
? ? ? ? ? ? p=NULL;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? f->rchild=p->lchild;
? ? ? ? ? ? free(p);
? ? ? ? ? ? p=NULL;
? ? ? ? }
? ? }
? ? if(p->lchild&&p->rchild)
? ? {
? ? ? ? BSTNode *q=p->lchild;
? ? ? ? f=p;
? ? ? ? while(q->rchild) ? //q為p左子樹(shù)的大值，最多有一個(gè)左節(jié)點(diǎn)
? ? ? ? {
? ? ? ? ? ? f=q;
? ? ? ? ? ? q=q->rchild;
? ? ? ? }
? ? ? ? p->data=q->data;
? ? ? ? if(f->lchild==q)
? ? ? ? {
? ? ? ? ? ? f->lchild=q->lchild;
? ? ? ? ? ? free(q);
? ? ? ? ? ? q=NULL;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? f->rchild=q->lchild;
? ? ? ? ? ? free(q);
? ? ? ? ? ? q=NULL;
? ? ? ? }
? ? }
}

2.平衡二叉樹(shù)
任意節(jié)點(diǎn)的平衡因子（左右子樹(shù)深度之差）的絕對(duì)值不超過(guò)1

3.B-樹(shù)和B+樹(shù)
一顆m階的B樹(shù)是空樹(shù)，或是滿足下列特性的m叉樹(shù)：
(1)樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)(m-1個(gè)關(guān)鍵字)
(2) 根結(jié)點(diǎn)或者為葉子結(jié)點(diǎn)或者至少有兩棵子樹(shù)
(3)根之外所有非終端結(jié)點(diǎn)至少有ceil(m/2)棵子樹(shù)
(4) 非終端結(jié)點(diǎn)包含信息(n, A0,K1,A1,K1,A2,...,Kn ,An)
Ki為關(guān)鍵字,有序; Ai為指向子樹(shù)根結(jié)點(diǎn)的指針,且Ai所指子樹(shù)中所有結(jié)點(diǎn)關(guān)鍵字均介于Ki-1和Ki之間.(n(5)葉結(jié)點(diǎn)出現(xiàn)在同一層上,不帶信息,相當(dāng)于查找失敗結(jié)點(diǎn)

哈希查找

哈希表：根據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法，將一組關(guān)鍵字映象到一組有限的連續(xù)的存儲(chǔ)空間上，以關(guān)鍵字對(duì)應(yīng)的Hash函數(shù)值作存儲(chǔ)地址，如此所得的查找表稱為哈希表
查找性能：依賴于Hash函數(shù)與沖突處理方法的質(zhì)量
1.哈希函數(shù)
2.沖突處理方法
3.哈希表裝填因子(飽和度):n/m,n為記錄數(shù)，m為表長(zhǎng)

構(gòu)建哈希表的方法：
1.線性函數(shù)：H(key)=a*key+b
2.除留取余法：H(key)=key%P P通常為大于表長(zhǎng)的最小素?cái)?shù)
3.數(shù)字分析法
4.平方取中法
5.折疊法
6.隨機(jī)數(shù)法

處理沖突方法：
1.開(kāi)放定址法
2.線性探測(cè)再散列
3.二次探測(cè)再散列
4.鏈地址法沖突的記錄構(gòu)成一個(gè)鏈表，哈希表存其頭指針

哈希查找過(guò)程：遇空則失敗
Step1:對(duì)關(guān)鍵字 K, 計(jì)算哈希函數(shù)值i = Hash(K);
Step2:若 H[i] 為空則查找失敗,返回;
Step3:若 H[i].key = K則查找成功,返回i;
Step4:否則 , 據(jù)沖突處理方法確定下一地址 Hi
Step5:轉(zhuǎn)到Step2重復(fù)

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文名稱：查找算法總結(jié)-創(chuàng)新互聯(lián)
分享地址：http://weahome.cn/article/dpegej.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

查找算法總結(jié)-創(chuàng)新互聯(lián)

其他資訊

網(wǎng)站制作

企業(yè)服務(wù)

網(wǎng)站建設(shè)

服務(wù)器托管