数据结构课程设计-查找-源代码

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在斐波那契中的数列+k;for(inti=n;iFk-1;+i)/把数组补全ai=ahigh；while(lowkey)high=mid-1;k=k-1;elseif(amidkey)low=mid+1;k=k-2;el

4、seif(mid=high)如果为真则找到相应的位置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(请输入要查找的数字: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)二叉排序树双亲节点的查找算法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/*哈希表线性探测再散列数据类型定义*/intkey;/*关键字*/intsi;/*插入成功时的次数*/HashTablel;typedefstructHa/*哈希表链地址法数据类型定义*/intelem;/*数据项*/structHa*next2;/*指向下一个结点的指针*/HashTable2;typedefstruct/*哈希表二次探测再散列法数据类型定义

12、*/intelemHashSize;/*表中储存数据元素的数组*/intcount;/*表中储存数据元素的个数*/intsize;/*哈希表的尺寸*/HashTable3;voidCreateHashTable1(HashTable1*H,int*a,intnum)/*哈希表线性探测再散列*/inti,d,cnt;for(i=0;iHashSize;i+)/*给新哈希表初始化数据*/Hi.key=0;Hi.si=0;for(i=0;inum;i+)cnt=1;d=ai%HashSize;/*构造哈希函数*/if(Hd.key=0)/*无冲突时，直接插入数据*/Hd.key=ai;Hd.si=c

13、nt;else/*有冲突时，进行冲突处理后再插入*/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/*增量为负数时*/q=(p-i*i)%HashSize;C+;if(q=0)returnq;elsei=c/2+1;return(-1);voidCreateHash3(HashTable3*h,int

14、*a,intnum)/二次探测再散列构造哈希表inti,p=-1,c,pp;for(i=0;ielempp!=0)/*发生冲突*/pp=Collision(p,c);c+;if(ppelempp=ai;h-count+;printf(,第d个记录冲突次数为dn,i+1,c);printf(nn此哈希表容量为d,当前表内存储的记录个数d.n,num,h-count);voidCreateHashTable2(HashTable2*H,int*a,intnum)intkey,i;HashTable2*q,*qq;q=NULL;for(i=0;iHashSize;i+)/*对哈希表进行初始化*/Hi

15、.elem=0;Hi.next2=NULL;for(i=0;ielem=ai;/*添加到已存在的结点后面*/TOC o 1-5 h zq-next2=qq-next2;qq-next2=q;elseq=(HashTable2*)malloc(sizeof(HashTable2);if(!q)printf(1W请内存失败!请重新运行程序n);exit(1);q-elem=ai;/*添加到首结点后面*/q-next2=Hkey.next2;Hkey.next2=q;printf(链表探索哈希表已建成!n);voidSearchHash1(HashTable1*h,intdata)intd,i;d=

16、data%HashSize;/*哈希函数*/i=d;if(hd.key=data)/*一次查找成功*/printf(数字d的查找次数为：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查找冲突次数为d.n,c);elseprintf(n没有查到此数!n);intSearchHash2(HashTable2*h,intd

17、ata,intnum)intd,cnt=1;HashTable2*q;d=data%HashSize;/*哈希函数*/q=&hd;if(q-elem=0)/*该位置上没有数据元素*/printf(“没有找到你要查找的那个数n);return0;while(q!=NULL)if(q-elem=data)printf(数字d的查找次数为：dn,data,cnt);return0;elseif(q-next2!=NULL)q=q-next2;cnt+;elseprintf(“没有找到你要查找的那个数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.退出静态查找1111静态查找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退出静态查找！endl;mainmenu();voidmenu2()intm;coutttcoutttcoutttcoutttcoutttcoutttcoutttcoutttcoutttcoutttcoutttcouttt111.建立二叉排序树111112.二叉排序树查找111113.二叉排序树插入111114.二叉排序树删除1111115.退出动态查找111动态查找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输入二叉排序树的节点，以-1结束y;if(-1=y)break;tree=insertree(tree,y);cout中序遍历：；inordertraverse(tree);coutendl;menu2();break;:/查找intx;cout请输入您要查找的数值：x;if(find(tree,x)-

21、data=x)coutE找到您要查找的值dataendl;elsecout未找到您要查找的值!endl;menu2();break;:插入intx;cout请输入您要插入的数值“x;insertree(tree,x);cout中序遍历：；inordertraverse(tree);coutendl;menu2();break;/删除cout”请输入您要删除的数据“x;p=find(tree,x);f=findparents(tree,x);detree(tree,f,p);cout中序遍历：；inordertraverse(tree);coutendl;menu2();break;cout退出动态查找！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