數(shù)據(jù)結(jié)構(gòu)課程設(shè)計_查找_源代碼

1、#include<stdio.h>#include<stdlib.h>#include <fstream.h>#include <iostream.h>FILE *fp;/-折半查找-#define MAX 20int dataMAX;int binary_find(int key, int low, int high)int mid;if(low = high)if(datalow = key)return low;elsereturn -1;elsemid = (low + high) / 2;if(mid = low)mid+;if(key

2、 < datamid)return binary_find(key, low, mid - 1);elsereturn binary_find(key, mid, high);/Binary Searchint binary_search(int key)return binary_find(key, 0, MAX - 1);void zheban()int found;int value; if(fp=fopen("A.txt","r")=NULL)printf("cannot open filen"); for(int i=

3、0;i<MAX;i+)fscanf(fp,"%d",&datai);fclose(fp); printf("有序序列為：");for(i=0;i<MAX;i+)printf("%d ",datai); char y='y'while(y='y') printf("n請輸入查找值: ");scanf("%d", &value);if(value != -1)found = binary_search(value);if(found !=

4、-1)printf("找到查找值: %d位置為%dn", value, found+1);elseprintf("沒有找到查找值: %dn", value);elseexit(1);cout<<"是否繼續(xù)：y/n:"cin>>y; cout<<endl;/-斐波拉契查找-#include <stdio.h>void fibonacci(int *f)f0 = 1;f1 = 1;for(int i = 2;i < MAX;+i)fi = fi - 2 + fi - 1;int fib

5、onacci_search(int *a,int key,int n)int low = 0,high = n - 1;int mid = 0;int k = 0;int FMAX;fibonacci(F);while(n > Fk - 1) /計算出n在斐波那契中的數(shù)列+k;for(int i = n;i < Fk - 1;+i) /把數(shù)組補全ai = ahigh;while(low <= high)mid = low + Fk-1 - 1; /根據(jù)斐波那契數(shù)列進(jìn)行黃金分割if(amid > key)high = mid - 1;k = k - 1;else if(a

6、mid < key)low = mid + 1;k = k - 2;elseif(mid <= high) /如果為真則找到相應(yīng)的位置return mid;elsereturn -1;return -1;int Fibonacci()if(fp=fopen("A.txt","r")=NULL)printf("cannot open filen"); for(int i=0;i<MAX;i+)fscanf(fp,"%d",&datai);fclose(fp); printf("有序

7、序列為：n");for(i=0;i<MAX;i+)printf("%d ",datai);printf("n");int k;char y='y'while(y='y') printf("請輸入要查找的數(shù)字:n");scanf("%d",&k);int pos = fibonacci_search(data,k,MAX);if(pos != -1)printf("找到查找值: %d位置為%dn", k, pos+1);elseprintf(

8、"沒有找到查找值: %dn", k);cout<<"是否繼續(xù)：y/n:"cin>>y;return 0;/-二叉排序樹-struct node int data; struct node *rlink; struct node *llink;struct node *tree;/二叉樹排序的遍歷/*void preorder(struct node *tree) struct node *p; struct node *s5; int top; top=-1; p=tree; do while (p!=NULL) cout<

9、<" "<<endl; printf("%d",p->data); if ( p->rlink!=NULL) top=top+1; stop=p->rlink; p=p->llink; if( top!= -1) p=stop; top=top-1; while(p!=NULL)|(top!=-1);*/void inordertraverse(struct node *tree)if(tree)inordertraverse(tree->llink);cout<<tree->data&l

10、t;<" "inordertraverse(tree->rlink); struct node *find(struct node *tree, int x) /二叉排序樹的查找算法 int f; struct node *p,*q; p=tree; f=0; q=( struct node *)malloc(sizeof (struct node); while(!f)&&(p!=NULL) if(p->data=x) f=1; else if(x<p->data) p=p->llink; else p=p->rl

11、ink; if(f) q=p; else q->data=NULL; return(q); struct node *findparents(struct node *tree, int x) /二叉排序樹雙親節(jié)點的查找算法 int f; struct node *p,*q,*r; p=tree; f=0; q=( struct node *)malloc(sizeof (struct node); r=( struct node *)malloc(sizeof (struct node); r=NULL; while(!f)&&(p!=NULL) if(p->da

12、ta=x) f=1; else r=p; if(x<p->data) p=p->llink; else p=p->rlink; if(f) q=p; else q->data=NULL; return(r); struct node *insertree(struct node *tree, int x ) /插入 struct node *p,*q; if(tree=NULL) p= (struct node *)malloc(sizeof(struct node); p->data=x; p->rlink=NULL; p->llink=NUL

13、L; tree=p; else p=tree; while(p!=NULL) q=p; if (x<p->data) p=p->llink; else p=p->rlink; p=(struct node *)malloc(sizeof(struct node); p->data=x; p->rlink=NULL; p->llink=NULL; if (x<q->data) q->llink=p; else q->rlink=p; return tree;void detree(struct node *t, struct no

14、de *f, struct node *p) /刪除 struct node *q,*s; int boo; boo=0; if(p->llink=NULL)|(p->rlink=NULL) if(p->llink=NULL) if(p=t) t=p->rlink; else s=p->rlink; boo=1; else if(p=t) t=p->llink; else s=p->llink; boo=1; else q=p; s=q->rlink; while(s->llink!=NULL) q=s; s=s->llink; s-

15、>llink=p->llink; if (q!=p) q->llink=s->rlink; s->rlink=p->rlink; if (p=t) t=s; else boo=1; if (boo=1) if(p=f->llink) f->llink=s; else f->rlink=s; free(p);/*void modify(struct node *tree,int x, int y) struct node *f,*p; p=find(tree, x); f=findparents(tree, x); detree(tree,

16、f, p); insertree(tree, y ); preorder(tree) ;*/-散列法-#define HashSize 53int data2MAX;typedef struct /*哈希表線性探測再散列數(shù)據(jù)類型定義*/ int key; /*關(guān)鍵字*/ int si; /*插入成功時的次數(shù)*/ HashTable1; typedef struct Ha /*哈希表鏈地址法數(shù)據(jù)類型定義*/ int elem; /*數(shù)據(jù)項*/ struct Ha *next2; /*指向下一個結(jié)點的指針*/ HashTable2; typedef struct /*哈希表二次探測再散列法數(shù)據(jù)類型

17、定義*/ int elemHashSize; /*表中儲存數(shù)據(jù)元素的數(shù)組*/ int count; /*表中儲存數(shù)據(jù)元素的個數(shù)*/ int size; /*哈希表的尺寸*/ HashTable3; void CreateHashTable1(HashTable1 *H,int *a,int num) /*哈希表線性探測再散列*/ int i,d,cnt; for(i=0; i<HashSize; i+) /*給新哈希表初始化數(shù)據(jù)*/ Hi.key=0; Hi.si=0; for(i=0; i<num; i+) cnt=1; d=ai%HashSize; /*構(gòu)造哈希函數(shù)*/ if(

18、Hd.key=0) /*無沖突時，直接插入數(shù)據(jù)*/ Hd.key=ai; Hd.si=cnt; else /*有沖突時，進(jìn)行沖突處理后再插入*/ do d=(d+1)%HashSize; cnt+; while(Hd.key!=0); Hd.key=ai; Hd.si=cnt; printf("n線性再探索哈希表已建成!n"); int Collision(int p,int c) /*二次探測再散列法解決沖突*/ int i,q; i=c/2+1; while(i < HashSize) if(c%2=0) /*增量為正數(shù)時*/ c+; q=(p+i*i)%Hash

19、Size; if(q>=0) return q; else i=c/2+1; else /*增量為負(fù)數(shù)時*/ q=(p-i*i)%HashSize; c+; if(q>=0) return q; else i=c/2+1; return (-1); void CreateHash3(HashTable3 *h,int *a,int num) /二次探測再散列構(gòu)造哈希表 int i,p=-1,c,pp; for(i=0; i<num; i+) c=0; p=ai%HashSize; /*哈希函數(shù)*/ pp=p; while(h->elempp!=0) /*發(fā)生沖突*/ p

20、p=Collision(p,c); c+; if(pp<0) /*沖突無法處理*/ printf("第%d個記錄無法解決沖突n",i+1); continue; h->elempp=ai; h->count+; printf("第%d個記錄沖突次數(shù)為%dn",i+1,c); printf("nn此哈希表容量為%d,當(dāng)前表內(nèi)存儲的記錄個數(shù)%d.n",num,h->count); void CreateHashTable2(HashTable2 *H,int *a,int num) int key,i; HashT

21、able2 *q,*qq; q=NULL; for (i=0; i<HashSize; i+) /*對哈希表進(jìn)行初始化*/ Hi.elem = 0; Hi.next2=NULL; for (i=0; i<num; i+) key=ai%HashSize; if(Hkey.elem=0) Hkey.elem=ai; else if(q!=NULL) /*若該位置已有數(shù)據(jù)*/ qq=q; q=q+1; q->elem=ai; /*添加到已存在的結(jié)點后面*/ q->next2=qq->next2; qq->next2=q; else q=(HashTable2*)

22、malloc(sizeof(HashTable2); if(!q) printf("申請內(nèi)存失敗!請重新運行程序n"); exit(1); q->elem=ai; /*添加到首結(jié)點后面*/ q->next2=Hkey.next2; Hkey.next2=q; printf("鏈表探索哈希表已建成!n"); void SearchHash1(HashTable1 *h,int data) int d,i; d=data%HashSize; /*哈希函數(shù)*/ i=d; if(hd.key=data) /*一次查找成功*/ printf("

23、;數(shù)字%d的查找次數(shù)為：%dn",hd.key,hd.si); else while(i<HashSize && hd.key!=data ) d=(d+1)%HashSize; i+=1; if(i<HashSize) printf("數(shù)字%d的查找次數(shù)為：%d.n",hd.key,hd.si); else printf("沒有查找到你所輸入的數(shù)n"); void SearchHash3(HashTable3 *h,int data) /哈希表二次探索再散列查找 int c=0,p,pp; p=data%HashS

24、ize; pp=p; while(h->elempp)!=data && pp!=-1) pp=Collision(p,c); c+; if(h->elempp!=0)&&(h->elempp)=data) printf("n查找成功!n查找沖突次數(shù)為%d.n",c);else printf("n沒有查到此數(shù)!n"); int SearchHash2(HashTable2 *h,int data,int num) int d,cnt=1; HashTable2 *q; d=data%HashSize; /

25、*哈希函數(shù)*/ q=&hd; if(q->elem=0) /*該位置上沒有數(shù)據(jù)元素*/ printf("沒有找到你要查找的那個數(shù)n"); return 0; while(q!=NULL) if(q->elem=data) printf("數(shù)字%d的查找次數(shù)為：%dn",data,cnt); return 0; else if(q->next2!=NULL) q=q->next2; cnt+; else printf("沒有找到你要查找的那個數(shù)n"); return 0; return 0; printf

26、("n");void GetIn() if(fp=fopen("B.txt","r")=NULL)printf("cannot open filen"); for(int i=0;i<MAX;i+)fscanf(fp,"%d",&data2i);fclose(fp); printf("序列為：n");for(i=0;i<MAX;i+)printf("%d ",data2i);printf("n");void main

27、menu();void menu1() int m; cout<<"tt 靜態(tài)查找 "<<endl; cout<<"tt "<<endl; cout<<"tt 1.折半查找 "<<endl; cout<<"tt "<<endl; cout<<"tt 2.斐波拉契查找 "<<endl; cout<<"tt "<<endl; cout&l

28、t;<"tt 3.退出靜態(tài)查找 "<<endl; cout<<"tt "<<endl;cout<<"請選擇："cin>>m;while(m<1|m>3) cout<<"輸入有誤，請重新輸入！"cin>>m;switch(m)case 1:zheban();menu1();break;case 2:Fibonacci();menu1();break;case 3:cout<<"退出靜態(tài)查找！&q

29、uot;<<endl; mainmenu();void menu2()int m; cout<<"tt 動態(tài)查找 "<<endl; cout<<"tt "<<endl; cout<<"tt 1.建立二叉排序樹 "<<endl; cout<<"tt "<<endl; cout<<"tt 2.二叉排序樹查找 "<<endl; cout<<"tt &

30、quot;<<endl; cout<<"tt 3.二叉排序樹插入 "<<endl; cout<<"tt "<<endl; cout<<"tt 4.二叉排序樹刪除 "<<endl; cout<<"tt "<<endl; cout<<"tt 5.退出動態(tài)查找 "<<endl; cout<<"tt "<<endl;cout<

31、;<"請選擇："cin>>m;while(m<1|m>5) cout<<"輸入有誤，請重新輸入:"cin>>m;switch(m)case 1:tree=(struct node*)malloc(sizeof(struct node); tree =NULL; cout<<"輸入二叉排序樹的節(jié)點，以-1結(jié)束"<<endl; while(1) int y; cin>>y; if(-1=y) break; tree=insertree(tree,y)

32、; cout<<"中序遍歷：" inordertraverse(tree);cout<<endl; menu2();break;case 2 : /查找 int x; cout<<"請輸入您要查找的數(shù)值："<<endl; cin>>x; if(find(tree, x)->data=x) cout<<"已找到您要查找的值"<<find(tree,x)->data<<endl; else cout<<"未找到

33、您要查找的值!"<<endl; ;menu2();break;case 3 : /插入 int x; cout<<"請輸入您要插入的數(shù)值"<<endl; cin>>x; insertree(tree, x ); cout<<"中序遍歷：" inordertraverse(tree) ;cout<<endl; ;menu2();break; case 4: /刪除 cout<<"請輸入您要刪除的數(shù)據(jù)"<<endl; struct n

34、ode *f,*p; int x; cin>>x; p=find(tree, x); f=findparents(tree, x); detree(tree, f, p); cout<<"中序遍歷：" inordertraverse(tree) ;cout<<endl;menu2(); break; case 5: cout<<"退出動態(tài)查找！"<<endl; mainmenu();void menu3() int m,d,i; HashTable1 hash1HashSize; HashTab

35、le2 hash2HashSize; HashTable3 * ha; /*定義三種類型的哈希表*/ ha=(HashTable3 *)malloc(sizeof(HashTable3); for(i=0; i<HashSize; i+) /*哈希表的初始化*/ ha->elemi=0; ha->count=0; ha->size=HashSize; while(1) cout<<"tt 散列法查找 "<<endl; cout<<"tt "<<endl; cout<<&q

36、uot;tt 1.從文件中讀出數(shù)據(jù)并輸出 "<<endl; cout<<"tt "<<endl; cout<<"tt 2.線性再散列建立哈希表 "<<endl; cout<<"tt "<<endl; cout<<"tt 3.二次探測再散列建立哈希表 "<<endl; cout<<"tt "<<endl; cout<<"tt 4.鏈地址

37、法建立哈希表 "<<endl; cout<<"tt "<<endl; cout<<"tt 5.線性再散列法查找 "<<endl; cout<<"tt "<<endl; cout<<"tt 6.二次探測再散列法查找 "<<endl; cout<<"tt "<<endl; cout<<"tt 7.鏈地址法查找 "<<endl; cout<<"tt "<<endl; cout<<"tt 8.退出散列法查找 "<<endl; cout<<"tt "<<endl;cout<<"請選擇："cin>>m;while(m<1|m>8) cout<<