数据结构C语言实现顺序查找,折半查找,二叉排序树,哈希表实验原理(实验原理+程序代码+程序截图+实验小结

1、实验日期:2010-6-12教师签字:成绩学号：E30814013专业：网络工程姓名：张芸学号：E30814013专业：网络工程姓名：张芸实验报告实验目的：实现顺序查找，折半查找，二叉排序树，哈希表实验原理:顺序查找iiitSearch_Seq(SSTableST,KeyTypekey)/算法9.1/在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。mt1=0;ST.elemO.key=key;/”哨兵”for(i=ST.lengtli;ST.elemi.key!=key;-i);/从后往前找returni;/找不到时，i为0/Search_S

2、eq二叉排序树(BinarySortTree)乂称二叉查找(搜索)树(BinarySearchTree)o其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身又各是一棵二叉排序树。哈希表StatusSearcliHasli(HashTableH,HKeyTvpeK,int&p、mt&c)/算法9.17/在开放定址哈希表H中查找关键码为K的元素，/若查找成功，以p指示待查数据元素在表中位置，并返回SUCCESS；/否则，以p指示插入位置，并返回UNSUCCES

3、S,c用以计冲突次数，其初值置零，供建表插入时参考p=Hash(K);/求得哈希地址while(H.elemp.key!=NULLKEY)&/该位置中填有记录!equal(K,(H.elemp.key)/并且关键字不相等collision(p,-h-c);/求得下一探查地址pif(equal(K,(H.elemp.key)retuinSUCCESS;/查找成功，p返回待查数据元素位置elsel-euunUNSUCCESS;/查找不成功(H.elemp.kev=NULLKEY),p返回的是插入位置/SeaicliHash顺序查找#includevoidmain()inta10=1,2,34567

4、,8,90;inti,x,y;printf(“输入你要査找的数:n”);scanf(%d,&x);y=o；for(i=0;i10;i+)if(x=ai)y=i;printf(”你要查找的数(1在第个(1位置n”,x,i+1);break;if(y=O)printf(”无法找到你要査找的数n“);折半查找#include#defineN21voidmain(void)intaN;mtiaijium;mttop.bottomaiiid;mtflag=l;/如果在表列中找到数字，则值为1,否则为0mtloc=-l;/要查找的数在表列中的位置，如果loca-1表示表列中没有这个数;如果有这个数，则它的

5、值为所在的位置pimtfC你想在多少个数中进行折半查找，请输入(120)：”)；scanf(”d,&n);wlule(n20)prmtf(”你输入的数不正确，请重新输入。5”)；pmitf(“你想在多少个数中进行折半查找，请输入(1-20)：”)；scanf(%d&n);prmtf(请你输入一个整数al:”)；scanf(”d,&al);1=2;while(iai-l)i+;elsepnntf(“你输入的数不满足要求，请重新输入。输出表列pimtf(ii输出表列n”)；fbr(i=l;iatop)|(numatop或者numnum)若amidnimi,则num定在afbottom和amid范韦

6、I之内top=nud-l;nud=(top+bottom)/2;elseif(anndnum)/若anudnum,则num定在anud+l和atop范|制之内bottom=nud+l;nud=(top+bottom)/2;if(loc=-l)pnntf(M%d这个数在表列中没有找到。irnum);HE:Debugzheban.exe你想在多少个数中进行折半查找，请输入(1-20):10请你输入一个整数aLl：l请你豹入一个整数aL2：2请你豹入一个整数aL3：3请你豹入一个整数aL4：4请你豹入一个整数aL5：5请你豹入一个整数aL6：6请你鞠入一个整数aL7：7请你豹入一个整数aL8：8请你

7、鞠入一个整数aL9：9请你输入一个整数aL10：10输岀表列12345678910请你输入要查找的数：5botton=l,nid=5,aL5=5找到数5的位置5Pressanykeytocontinue.搜狗拼音半:nlI二叉排序树#include#include#include#defineINFMT”d”#defineOUTFMTM%d”/*#defiiieNULLOL*/#defineBOOLint#defineTRUE1#defineFALSE0#defineLEN10000tvpedefintElemType;tvpedefstmctBSTNodeElemTypedata;stmct

8、BSTNode*lcluld,*rcluld;BSTNode,*BSTree;/*插入新节点/voidInseit(BSTiee*tree,ElemTypeitem)BSTieenode=(BSTree)malloc(sizeof(BSTNode);node-data=item;node-lchild=node-rcliild=NULL;if(!*tiee)*tree=node;elseBSTreecursor=*tree;wliile(1)if(itemdata)if(NULL=cuisor-lchild)cuisor-lchild=node;break;cursor=cursor-lcli

9、ild;elseif(NULL=cuisor-icluld)cuisor-rchild=node;break;cursor=cursor-rcluld;return:/*查找指定值*/BSTreeSearch(BSTreetree,ElemTypeitem)BSTreecursor=tree;while(cursor)if(item=cursor-data)returncursor;elseif(itemdata)cursor=cursor-lchild;elsecursor=cursor-rchild;returnNULL;/*中缀遍历*/voidInorder(BSTieetree)BST

10、reecursor=tree;if(cursor)Iiioidei(cuisof-ichild);pnntf(OUTFMT.cuisor-data);Iiioidei(cuisof-ichild);/*回收资源*/voidCleaiiup(BSTreetiee)BSTreecursor=tree,temp=NULL;if(cursor)Cleanup(cursor-lchild);Cleanup(cuisor-rcluld);fiee(cuisor);voidmain()ElemTypeitem;chaichoice;BSTreeroot=NULL,let;/*必须赋予NULL值，否则出错*/

11、BOOLfiiush=FALSE;dopnntfC请输入数据（-10000结束）：n”）;wlule(1)scanf(INFMT.&item);if(-10000!=item)Insert(&root,item);elsebreak;pimtf(iiii创建完成n);Inorder(root);/*二叉排序树的查找测试*/do请输入查找数据：”);scanf(H%d,&item);getchai();printf(MSearching.iin);ret=Seaich(root,item);if(NULL=ret)prmtf(查找失败！”);elsepnntfC查找成功！J;pnntf(-n继续

12、测试按y,退出按其它键。iT);choice=getchai();while(choice=y|choice=,Y,);Cleanup(root);#iiicludevoidmain()inta10;mtbaj,c;J=l;fbr(i=0;i9;i+)a】=0；printf(iW输入5个数(非零)n”);for(i=0;i5;i+)sc3nfC%d”,&b);c=b%7;A:if(ac=O)ac=b;elsec=(c+1)%7j+；gotoA;pnntf(”d在哈希表的第d位，第d次放入哈希表n,b,c,j);J=l；,E:Debughaxi.exeM请输入5个数非零7?在哈希表的笫0位笫1次放入哈希表1414在哈希表的笫1位，笫2次放入哈希表33在哈希表的笫3位，笫1次放入哈希表55