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

1、#include#include#include#includeFILE*fp;/#defineMAX20intdataMAX;intbinary_find(intkey,intlow,inthigh)intmid;if(low=high)if(datalow=key)returnlow;elsereturn-1;elsemid=(low+high)/2;if(mid=low)mid+;if(keydatamid)returnbinary_find(key,low,mid-1);elsereturnbinary_find(key,mid,high);/BinarySearchintbinary

2、_search(intkey)returnbinary_find(key,0,MAX-1);voidzheban()intfound;intvalue;if(fp=fopen(A.txt,r)=NULL)printf(cannotopenfilen);for(inti=0;iMAX;i+)fscanf(fp,%d,&datai);fclose(fp);printf(有序序列為：)；for(i=0;iMAX;i+)printf(%d,datai);chary=y;while(y=y)printf(n請輸入查找值:);scanf(%d,&value);if(value!=-1)found=bina

3、ry_search(value);if(found!=-1)printf(找到查找值:%d位置為%dn,value,found+1);elseprintf(沒有找到查找值:dn,value);elseexit(1);couty;coutendl;/斐波拉契查找#includevoidfibonacci(int*f)f0=1;f1=1;for(inti=2;iFk-1)/計算出n在斐波那契中的數(shù)列+k;for(inti=n;iFk-1;+i)/把數(shù)組補(bǔ)全ai=ahigh；while(lowkey)high=mid-1;k=k-1;elseif(amidkey)low=mid+1;k=k-2;el

4、seif(mid=high)如果為真則找到相應(yīng)的位置returnmid;elsereturn-1;return-1;intFibonacci。if(fp=fopen(A.txt,r)=NULL)printf(cannotopenfilen);for(inti=0;iMAX;i+)fscanf(fp,%d,&datai);fclose(fp);printf(有序序列為：n);for(i=0;iMAX;i+)printf(%d,datai);printf(n);intk;chary=y;while(y=y)printf(請輸入要查找的數(shù)字:n);scanf(%d,&k);intpos=fibona

5、cci_search(data,k,MAX);if(pos!=-1)printf(找到查找值:%d位置為%dn,k,pos+1);elseprintf(沒有找到查找值:dn,k);couty;return0;/二叉排序樹structnodeintdata;structnode*rlink;structnode*llink;structnode*tree;/二叉樹排序的遍歷/*voidpreorder(structnode*tree)structnode*p;structnode*s5;inttop;top=-1;p=tree;dowhile(p!=NULL)coutdata);if(p-rli

6、nk!=NULL)top=top+1;stop=p-rlink;p=p-llink;if(top!=-1)p=stop;top=top-1;while(p!=NULL)|(top!=-1);*/voidinordertraverse(structnode*tree)if(tree)inordertraverse(tree-llink);coutdatarlink);structnode*find(structnode*tree,intx)二叉排序樹的查找算法intf;structnode*p,*q;p=tree;f=0;q=(structnode*)malloc(sizeof(structno

7、de);while(!f)&(p!=NULL)if(p-data=x)f=1;elseif(xdata)p=p-llink;elsep=p-rlink;if(f)q=p;elseq-data=NULL;return(q);structnode*findparents(structnode*tree,intx)二叉排序樹雙親節(jié)點的查找算法intf;structnode*p,*q,*r;p=tree;f=0;q=(structnode*)malloc(sizeof(structnode);r=(structnode*)malloc(sizeof(structnode);r=NULL;while(!

8、f)&(p!=NULL)if(p-data=x)f=1;elser=p;if(xdata)p=p-llink;elsep=p-rlink;if(f)q=p;elseq-data=NULL;return(r);structnode*insertree(structnode*tree,intx)/structnode*p,*q;if(tree=NULL)p=(structnode*)malloc(sizeof(structnode);p-data=x;p-rlink=NULL;p-llink=NULL;tree=p;elsep=tree;while(p!=NULL)q=p;if(xdata)p=p

9、-llink;elsep=p-rlink;p=(structnode*)malloc(sizeof(structnode);p-data=x;p-rlink=NULL;p-llink=NULL;if(xdata)q-llink=p;elseq-rlink=p;returntree;voiddetree(structnode*t,structnode*f,structnode*p)/structnode*q,*s;intboo;boo=0;if(p-llink=NULL)|(p-rlink=NULL)if(p-llink=NULL)if(p=t)t=p-rlink;elses=p-rlink;b

10、oo=1;elseif(p=t)t=p-llink;elses=p-llink;boo=1;elseq=p;s=q-rlink;while(s-llink!=NULL)q=s；s=s-llink;s-llink=p-llink;if(q!=p)q-llink=s-rlink;s-rlink=p-rlink;if(P=t)t=s;elseboo=1;if(boo=1)if(p=f-llink)f-llink=s;elsef-rlink=s;free(p);/*voidmodify(structnode*tree,intx,inty)structnode*f,*p;p=find(tree,x);f

11、=findparents(tree,x);detree(tree,f,p);insertree(tree,y);preorder(tree);*/散列法#defineHashSize53intdata2MAX;typedefstruct/*哈希表線性探測再散列數(shù)據(jù)類型定義*/intkey;/*關(guān)鍵字*/intsi;/*插入成功時的次數(shù)*/HashTablel;typedefstructHa/*哈希表鏈地址法數(shù)據(jù)類型定義*/intelem;/*數(shù)據(jù)項*/structHa*next2;/*指向下一個結(jié)點的指針*/HashTable2;typedefstruct/*哈希表二次探測再散列法數(shù)據(jù)類型定義

12、*/intelemHashSize;/*表中儲存數(shù)據(jù)元素的數(shù)組*/intcount;/*表中儲存數(shù)據(jù)元素的個數(shù)*/intsize;/*哈希表的尺寸*/HashTable3;voidCreateHashTable1(HashTable1*H,int*a,intnum)/*哈希表線性探測再散列*/inti,d,cnt;for(i=0;iHashSize;i+)/*給新哈希表初始化數(shù)據(jù)*/Hi.key=0;Hi.si=0;for(i=0;inum;i+)cnt=1;d=ai%HashSize;/*構(gòu)造哈希函數(shù)*/if(Hd.key=0)/*無沖突時，直接插入數(shù)據(jù)*/Hd.key=ai;Hd.si=c

13、nt;else/*有沖突時，進(jìn)行沖突處理后再插入*/dod=(d+1)%HashSize;cnt+;while(Hd.key!=0);Hd.key=ai;Hd.si=cnt;printf(n線性再探索哈希表已建成!n);intCollision(intp,intc)/*二次探測再散列法解決沖突*/inti,q;i=c/2+1;while(i=0)returnq;elsei=c/2+1;else/*增量為負(fù)數(shù)時*/q=(p-i*i)%HashSize;C+;if(q=0)returnq;elsei=c/2+1;return(-1);voidCreateHash3(HashTable3*h,int

14、*a,intnum)/二次探測再散列構(gòu)造哈希表inti,p=-1,c,pp;for(i=0;ielempp!=0)/*發(fā)生沖突*/pp=Collision(p,c);c+;if(ppelempp=ai;h-count+;printf(,第d個記錄沖突次數(shù)為dn,i+1,c);printf(nn此哈希表容量為d,當(dāng)前表內(nèi)存儲的記錄個數(shù)d.n,num,h-count);voidCreateHashTable2(HashTable2*H,int*a,intnum)intkey,i;HashTable2*q,*qq;q=NULL;for(i=0;iHashSize;i+)/*對哈希表進(jìn)行初始化*/Hi

15、.elem=0;Hi.next2=NULL;for(i=0;ielem=ai;/*添加到已存在的結(jié)點后面*/TOC o 1-5 h zq-next2=qq-next2;qq-next2=q;elseq=(HashTable2*)malloc(sizeof(HashTable2);if(!q)printf(1W請內(nèi)存失敗!請重新運行程序n);exit(1);q-elem=ai;/*添加到首結(jié)點后面*/q-next2=Hkey.next2;Hkey.next2=q;printf(鏈表探索哈希表已建成!n);voidSearchHash1(HashTable1*h,intdata)intd,i;d=

16、data%HashSize;/*哈希函數(shù)*/i=d;if(hd.key=data)/*一次查找成功*/printf(數(shù)字d的查找次數(shù)為：dn,hd.key,hd.si);elsewhile(iHashSize&hd.key!=data)d=(d+1)%HashSize;i+=1;if(ielempp)!=data&pp!=-1)pp=Collision(p,c);c+;if(h-elempp!=0)&(h-elempp)=data)printf(n查找成功!n查找沖突次數(shù)為d.n,c);elseprintf(n沒有查到此數(shù)!n);intSearchHash2(HashTable2*h,intd

17、ata,intnum)intd,cnt=1;HashTable2*q;d=data%HashSize;/*哈希函數(shù)*/q=&hd;if(q-elem=0)/*該位置上沒有數(shù)據(jù)元素*/printf(“沒有找到你要查找的那個數(shù)n);return0;while(q!=NULL)if(q-elem=data)printf(數(shù)字d的查找次數(shù)為：dn,data,cnt);return0;elseif(q-next2!=NULL)q=q-next2;cnt+;elseprintf(“沒有找到你要查找的那個數(shù)n);return0;return0;printf(n);voidGetIn()if(fp=fopen

18、(B.txt,r)=NULL)printf(cannotopenfilen);for(inti=0;iMAX;i+)fscanf(fp,%d,&data2i);fclose(fp);printf(序列為：n);for(i=0;iMAX;i+)printf(%d,data2i);printf(n);voidmainmenu();voidmenu1()intm;coutttcoutttcoutttcoutttcoutttcoutttcoutttcouttt111.折半查找111112.斐波拉契查找111113.退出靜態(tài)查找1111靜態(tài)查找r1endl;endl;endl;endl;endl;end

19、l;endl;endl;coutm;while(m3)8am;switch(m)case1:zheban();menu1();break;case2:Fibonacci();menu1();break;case3:cout退出靜態(tài)查找！endl;mainmenu();voidmenu2()intm;coutttcoutttcoutttcoutttcoutttcoutttcoutttcoutttcoutttcoutttcoutttcouttt111.建立二叉排序樹111112.二叉排序樹查找111113.二叉排序樹插入111114.二叉排序樹刪除1111115.退出動態(tài)查找111動態(tài)查找r1en

20、dl;endl;endl;endl;endl;endl;endl;endl;endl;endl;endl;endl;coutm;while(m5)8am;switch(m)case1:tree=(structnode*)malloc(sizeof(structnode);tree=NULL;8a輸入二叉排序樹的節(jié)點，以-1結(jié)束y;if(-1=y)break;tree=insertree(tree,y);cout中序遍歷：；inordertraverse(tree);coutendl;menu2();break;:/查找intx;cout請輸入您要查找的數(shù)值：x;if(find(tree,x)-

21、data=x)coutE找到您要查找的值dataendl;elsecout未找到您要查找的值!endl;menu2();break;:插入intx;cout請輸入您要插入的數(shù)值“x;insertree(tree,x);cout中序遍歷：；inordertraverse(tree);coutendl;menu2();break;/刪除cout”請輸入您要刪除的數(shù)據(jù)“x;p=find(tree,x);f=findparents(tree,x);detree(tree,f,p);cout中序遍歷：；inordertraverse(tree);coutendl;menu2();break;cout退出動態(tài)查找！endl;mainmenu();voidmenu3()intm,d,i;HashTable1hash1HashSize;HashTable2hash2HashSize;HashTable3*ha;/*定義三種類型的哈希表*/ha=(HashTable3*)malloc(sizeof(HashTable3);for(i=0;ielemi=0;ha-count=0;ha-size=HashSize;while(1)coutttcoutttcouttt