|
查找算法集：順序查找、二分查找、插值查找、動(dòng)態(tài)查找(數(shù)組實(shí)現(xiàn)、鏈表實(shí)現(xiàn)) // search.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "LinkTable.h" #define MAX_KEY 500 //------------------------------數(shù)組實(shí)現(xiàn)部分---------------------------------- /**//* 無序數(shù)組順序查找算法函數(shù)nsq_Order_Search<用數(shù)組實(shí)現(xiàn)> 參數(shù)描述： int array[] :被查找數(shù)組 int n :被查找數(shù)組元素個(gè)數(shù) int key :被查找的關(guān)鍵值 返回值: 如果沒有找到: nsq_Order_Search = -1 否則: nsq_Order_Search = key數(shù)組下標(biāo) */ int nsq_Order_Search(int array[],int n,int key) ...{ int i; array[n] = key; /**//*for循環(huán)后面的分號(hào)必不可少*/ for(i=0;key!=array[i];i++); return(i<n?i:-1); } /**//* 有序數(shù)組順序查找算法函數(shù)sq_Order_Search<用數(shù)組實(shí)現(xiàn)> 參數(shù)描述： int array[] :被查找數(shù)組 int n :被查找數(shù)組元素個(gè)數(shù) int key :被查找的關(guān)鍵值 返回值: 如果沒有找到: sq_Order_Search = -1 否則: sq_Order_Search = key數(shù)組下標(biāo) */ int sq_Order_Search(int array[],int n,int key) ...{ int i; array[n] = MAX_KEY; /**//*for循環(huán)后面的分號(hào)必不可少*/ for(i=0;key>array[i];i++); if(i<n && array[i] == key) return(i); else return(-1); } /**//* 有序數(shù)組二分查找算法函數(shù)sq_Dichotomy_Search0<用數(shù)組實(shí)現(xiàn)> 參數(shù)描述： int array[] :被查找數(shù)組 int n :被查找數(shù)組元素個(gè)數(shù) int key :被查找的關(guān)鍵值 返回值: 如果沒有找到: sq_Dichotomy_Search0 = -1 否則: sq_Dichotomy_Search0 = key數(shù)組下標(biāo) */ int sq_Dichotomy_Search0(int array[],int n,int key) ...{ int low,high,mid; low = 0; high = n - 1; while(low<=high) ...{ mid = (high+low)/2; if(array[mid] == key) return(mid); /**//*key>array[mid] 表明要求查找的值在[mid+1,high]*/ /**//*否則,在[low,mid-1]*/ if(key > array[mid]) low = mid + 1; else high = mid - 1; } return(-1); } /**//* 有序數(shù)組插值查找算法函數(shù)sq_Dichotomy_Search1<用數(shù)組實(shí)現(xiàn)> (插值查找算法是二分查找算法的改進(jìn)) 參數(shù)描述： int array[] :被查找數(shù)組 int n :被查找數(shù)組元素個(gè)數(shù) int key :被查找的關(guān)鍵值 返回值: 如果沒有找到: sq_Dichotomy_Search1 = -1 否則: sq_Dichotomy_Search1 = key數(shù)組下標(biāo) */ int sq_Dichotomy_Search1(int array[],int n,int key) ...{ int low,high, //二分?jǐn)?shù)組的上,下標(biāo) pos; //查找碼的大致(估算)位置 low = 0; high = n-1; while(low <= high) ...{ pos = (key-array[low])/(array[high]-array[low])*(high-low)+low; /**//*找到關(guān)鍵值,中途退出*/ if(key == array[pos]) return(pos); if(key > array[pos]) low = pos + 1; else high = pos - 1; } /**//*沒有找到,返回-1*/ return(-1); } //------------------------------數(shù)組實(shí)現(xiàn)部分---------------------------------- //------------------------------鏈表實(shí)現(xiàn)部分---------------------------------- /**//* 無序鏈表順序查找算法函數(shù)nlk_Order_Serach<用鏈表實(shí)現(xiàn)> [查找思想:遍歷鏈表的所有節(jié)點(diǎn)] 參數(shù)描述： Node *head :被查找鏈表的首指針 int key :被查找的關(guān)鍵值 返回值: 如果沒有找到: nlk_Order_Serach = NULL 否則: nlk_Order_Serach = 鍵值為key的節(jié)點(diǎn)的指針 */ Node *nlk_Order_Serach(Node *head,int key) ...{ for(;head!=NULL && head->data != key;head = head->link); return(head); } /**//* 有序鏈表順序查找算法函數(shù)lk_Order_Serach<用鏈表實(shí)現(xiàn)> [查找思想:依次遍歷鏈表的節(jié)點(diǎn),發(fā)現(xiàn)節(jié)點(diǎn)不在key的范圍時(shí)提前結(jié)束查找] 參數(shù)描述： Node *head :被查找鏈表的首指針 int key :被查找的關(guān)鍵值 返回值: 如果沒有找到: lk_Order_Serach = NULL 否則: lk_Order_Serach = 鍵值為key的節(jié)點(diǎn)的指針 */ Node *lk_Order_Search(Node *head,int key) ...{ for(;head!=NULL && head->data < key;head=head->link); /**//*當(dāng)遍歷指針為NULL或沒有找到鍵值為key的節(jié)點(diǎn),返回NULL(表明沒有找到)*/ /**//*否則,返回head(表明已經(jīng)找到)*/ return(head==NULL || head->data != key ? NULL : head); } /**//* 有序鏈表動(dòng)態(tài)查找算法函數(shù)lk_Dynamic_Search<用鏈表實(shí)現(xiàn)> [查找思想:依次遍歷鏈表的節(jié)點(diǎn),發(fā)現(xiàn)節(jié)點(diǎn)不在key的范圍時(shí)提前結(jié)束查找] 參數(shù)描述： Node *head: 被查找鏈表的首指針 Node **p; 鍵值為key的節(jié)點(diǎn)的前驅(qū)指針(回傳參數(shù)) Node **q: 鍵值為key的節(jié)點(diǎn)指針(回傳參數(shù)) int key : 被查找的關(guān)鍵值 注意: 當(dāng) *p == NULL 且 *q != NULL,鏈表的首節(jié)點(diǎn)鍵值為key 當(dāng) *p != NULL 且 *q != NULL,鏈表的中間(非首,尾)節(jié)點(diǎn)鍵值為key 當(dāng) *p != NULL 且 *q == NULL,鏈表的尾節(jié)點(diǎn)鍵值為key 當(dāng) *p == NULL 且 *q == NULL,鏈表是空鏈表 */ void lk_Dynamic_Search(Node *head,Node **p,Node **q,int key) ...{ Node *pre,*cur; pre = NULL; cur = head; for(;cur != NULL && cur->data < key;pre = cur,cur = cur->link) *p = pre; *q = cur; } /**//* 有序鏈表動(dòng)態(tài)插入算法函數(shù)lk_Dynamic_Insert<用鏈表實(shí)現(xiàn)> 參數(shù)描述： Node *head: 被插入鏈表的首指針 int key : 被插入的關(guān)鍵值 返回值: lk_Dynamic_Search = 插入鍵值為key的節(jié)點(diǎn)后的鏈表首指針 */ Node *lk_Dynamic_Insert(Node *head,int key) ...{ Node *x, //插入節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn) *y, //插入節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn) *p; //插入的節(jié)點(diǎn) p = (Node *)malloc(sizeof(Node)); p->data = key; p->link = NULL; lk_Dynamic_Search(head,&x,&y,key); if(x==NULL) ...{ p->link = x; head = p; } else ...{ p->link = x->link; x->link = p; } ListLinkTable(head,"插入節(jié)點(diǎn)"); return(head); } /**//* 有序鏈表動(dòng)態(tài)刪除算法函數(shù)lk_Dynamic_Delete<用鏈表實(shí)現(xiàn)> 參數(shù)描述： Node *head: 被刪除鏈表的首指針 int key : 被刪除的關(guān)鍵值 返回值: lk_Dynamic_Delete = 刪除鍵值為key的節(jié)點(diǎn)后的鏈表首指針 */ Node *lk_Dynamic_Delete(Node *head,int key) ...{ Node *x, //刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn) *y; //刪除的節(jié)點(diǎn) lk_Dynamic_Search(head,&x,&y,key); if(x==NULL) /**//*因?yàn)閤=NLLL時(shí),y指向首指針*/ head = y->link; else x->link = y->link; free(y); ListLinkTable(head,"刪除節(jié)點(diǎn)"); return(head); } //------------------------------鏈表實(shí)現(xiàn)部分---------------------------------- int main(int argc, char* argv[]) ...{ Node *head; //Node *p,*x,*y; int KEY; int count,i; //int result; KEY = 11; //PrintArrayValue(TestArray2,DEFAULT_ARRAY_SIZE,"原始"); //result = sq_Dichotomy_Search1(TestArray2,DEFAULT_ARRAY_SIZE,KEY); //printf("查找結(jié)果是：數(shù)組[%d] = %d ",result,TestArray2[result]); head = CreateLinkTable(DEFAULT_ARRAY_SIZE,TestArray2); ListLinkTable(head,"原始"); /**//* p = lk_Order_Search(head,KEY); if(p==NULL) printf(" 查找結(jié)果是：指定鏈表中沒有[數(shù)據(jù)域 = %d]的節(jié)點(diǎn)! ",KEY); else printf(" 查找結(jié)果是：節(jié)點(diǎn).Data = %d 節(jié)點(diǎn).Link = %d 節(jié)點(diǎn).Addr = %d ",p->data,p->link,p); */ printf("輸入插入節(jié)點(diǎn)的個(gè)數(shù)： "); scanf("%d",&count); for(i=0;i<count;i++) ...{ printf("輸入插入節(jié)點(diǎn)的數(shù)據(jù)域： "); scanf("%d",&KEY); lk_Dynamic_Insert(head,KEY); } do ...{ printf("輸入刪除節(jié)點(diǎn)的數(shù)據(jù)域： "); scanf("%d",&KEY); lk_Dynamic_Delete(head,KEY); }while(head!=NULL); printf(" 應(yīng)用程序正在運(yùn)行...... "); return 0; } |
|
|
