数据结构查找算法实验报告

1、数据结构查找算法实验报告 数据结构实验报告 实验第四章： 实验： 简单查找算法 一需求与规格说明： 查找算法这里主要使用了顺序查找,折半查找,二叉排序树查找与哈希表查找四种方法。由于自己能力有限,本想实现其她算法,但没有实现.其中顺序查找相对比较简单,折半查找参考了书上得算法，二叉排序树查找由于有之前做二叉树得经验，因此实现得较为顺利，哈希表感觉做得并不成功，感觉还就是应该可以进一步完善，应该说还有很大得改进余地。 二设计思想: 开始得时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只就是从头到尾进行遍历。二分查找则就是先对数据进行排序，然后利用三个标志，

2、分别指向最大，中间与最小数据，接下来根据待查找数据与中间数据得比较不断移动标志，直至找到。二叉排序树则就是先构造,构造部分花费最多得精力,比根节点数据大得结点放入根节点得右子树，比根节点数据小得放入根节点得左子树，其实完全可以利用递归实现，这里使用得循环来实现得,感觉这里可以尝试用递归.当二叉树建好后，中序遍历序列即为由小到大得有序序列，查找次数不会超过二叉树得深度。这里还使用了广义表输出二叉树,以使得更直观。哈希表则就是利用给定得函数式建立索引,方便查找. 三设计表示: 四实现解释: 其实查找排序这部分与前面得一些知识联系得比较紧密，例如顺序表得建立与实现，顺序表节点得排序,二叉树得生成与遍

3、历，这里主要就是中序遍历.应该说有些知识点较为熟悉,但在实现得时候并不就是那么顺利。在查找到数据得时候要想办法输出查找过程得相关信息，并统计。这里顺序查找与折半查找均使用了数组存储得顺序表，而二叉树则就是采用了链表存储得树形结构。为了直观起见，在用户输入了数据后,分别输出已经生成得数组与树。折半查找由于只能查找有序表,因此在查找前先调用函数对数据进行了排序。 在查找后对查找数据进行了统计.二叉排序树应该说由于有了之前二叉树得基础，并没有费太大力气,主要就是在构造二叉树得时候，要对新加入得节点数据与跟数据进行比较,如果比根节点数据大则放在右子树里,如果比根节点数据小则放入左子树。建立了二叉树后，

4、遍历与查找就很简单了。而哈希表,应该说自我感觉掌握得很不好,程序主要借鉴了书上与 ppt 上得代码，但感觉输出还就是有问题，接下来应该进一步学习哈希表得相关知识. 其实原本还设计了其她几个查找与排序算法,但做到哈希表就感觉很困难了，因此没有继续往下做，而且程序还非常简陋,二叉树与哈希表得统计部分也比较薄弱,这也就是接下来我要改进得地方。 具体代码见源代码部分。 5、详细设计表示： 6、用户手册： 程序运行后，用户首先要输入数据得个数。接下来输入一组数据并根据提示进行顺序查找，二分查找,二叉排序树查找与哈希表查找等操作,由于操作直接简单这里不再详述。 7、调试报告： 应该说在调试这个程序得过程中

5、自己发现了很多不足，这次实验让我学到了不少东西,但应该说这个程序可实现得功能还就是偏少，不太实用，接下来有待改进。 8、源代码清单与结果： inlud stdi、h #dee egth 100 iude stdlb、h #include te、 #din inmt d' #defie oft d /* dfin nll 0l #def boo int #defie e deie se 0 defin len 10000 typedf int eemtye； tpedef sruc bstno emtype ta； struc bsnode *lhild, rchid； bstnd， s

6、ree; ype bstree tre; /* 插入新节点 / vid inser(stre re， emtye item） bsree ode = (stee)malloc(sizf（btode）); nde-da = iem； nodcd = noderild = u； f （！*tree） tee = node; els bsree ro = tre; wil （1) if （iem cro-daa） i (nul = curor-lcild） crsrlhld = nod； brea； usor = corlchil； else （nu sorrchld) ursorrchild =

7、node； rek； cror cursrrhild; reurn； d )t eerib(eeribohs/ 递归显示二叉树得广义表形式 if（!） in（'空）;etr; ;）a,d（ftr/ 点节根印打 if(t-lild |rhl) ；）（(ap sowiee（tchid)； / 递归显示左子树 ;),（ahctu showbitree(trchild）； 递归显示右子树 utch（)）; * 查找指定值 / bstr sarc（btree tee， eltpe item） bstre ursor = ree; while （cursor） f (ite = curs-a） r

8、eun crsor； else if （ iem cursr-data） urso = crso-lchild; ese cusor = cursrrchild; retun nul； * 中缀遍历 vod ior（btre e) bstee cusor = re; if （urso) inrder(curorlchid)； printf(oufmt, crsordt）; iorr（cursorrchild); / 回收资源 / oid cleaup(sree tee） btree curso = tree, tem nll； if (rsor） clenp（cuor-cld）； ceanup

9、(cursor-rhild）； fee（uro）； oid erchtre（str oot） ca hice; pri(中序遍历得结果为：n）; norder(rot）; itf（nn)； elemtype item; bree ret； / 二叉排序树得查找测试 */ o prtf(n 请输入查找数据:')； cnf（d， item）; getchar()； pritf（serhn、n); ret search(oot， tem)； if （nl = ret） ritf（查找失败！）； else prnt(查找成功!')； pintf（'n 继续测试按 y,退出按其它

10、键。）； choe = etcar(); wle （hie="|choice="y）； cleanp（root); searchsh( *arr，i n) it a1; int b，i，j,c； j=； )+i;9i;=i（f a=0； ；）n出输表希哈为下以(tnir r(i=；i；i+) =ar%； : if(ac=0)c=rri; ；a tog;+ca；+j；7）1c（c le ；)j，c，ira，n表希哈入放次 d%第,位 d%第得表希哈在 d（firp ;1= void seqenceerch（int *f，it egth)； vo sear(t p,int le

11、ngth）; voi sort(int *fp，t nh)； voi sequenceseac（nt *p,int legth) i dat； pritf（'开始使用顺序查询、n 请输入您想要查找得数据、n')； scanf（d,daa）； o（n i=0;ileh;i+） if（pi=ata) print('经过%d 次查找，查找到数据、n，i+1，data)； eturn ; printf(经过%d 次查找,未能查找到数据%d、n，i,daa)； vid sr(in f，int lnt) it dat； rntf（'开始使用顺序查询、n 请输入您想要查找得数

12、据、n); scnf（%'，dt)； prinf('由于二分查找法要求数据就是有序得，现在开始为数组排序、n）； sor（fp，lengh）; pintf('数组现在已经就是从小到大排列,下面将开始查找、n'）； t botm，top，midl； btom=； penth; it i=0; wile （bottom=tp) idde（bottom+t)/2； i+； if(fpiddledt） bott=midde+1； else if(piddlata) topmdde1; else printf（经过%d 次查找，查找到数据%d、n'，,data）;

13、 eun； printf（'经过%d 次查找，未能查找到数据%d、n',i，data）; vid sor（t *fp,in length) pinf（现在开始为数组排序,排列结果将就是从小到大、）; int temp； fr（in =；ilength;i+) f（in j=0;lngth1;j+) if（fpjfpj+1） empf; fpj=fpj+1； fj+1=emp; ritf（排序完成！n 下面输出排序后得数组：n）； fr（int k=；klenh；k+) printf（5d，fpk); pintf('n'）； struct has int key;

14、 in i； ; struct ha hlit11; t i，a，sum,d； foat average; voi cash（it arr,int n) for（i=;i11;+） hlisti、ky； isti、si0; for(i=0；in;+） su=; adr=(*arri）11; d=dr； if（hlistd、ey=0） hls、keya; lstadr、i=1; es do =（d+(ai7）10+1）1; um=su+1； hile(hlitd、ey!=）； listd、ke=a; hlistd、i=+1； void dhsh（int arr，in n） print('

15、哈希表显示为:')； for(i=0；i1；) prinf（4d，i）； pint（'）; print（哈希表关键字:）； for（=；i1;i+) print（4，listi、ey）; rntf(n); printf（查找长度就是： ）； for(i0；i1；i+） pnf('%d',it、s）; printf('n'）； averge=0、0； fr（i=0;1；i+） averageaverage+hist、； veragearag； prntf(平均长度:as（%d）=f',n，averge）； void an(） t cunt;

16、 i arrlength; elmtype ite； char hoic； bstee rt = null, ret; / 必须赋予 nul值，否则出错 */ bool finish = false; rn（请输入您得数据得个数：n）； anf('d，cout）； printf（'请输入d 个数据,count)； fr(int =0;icout；i+) scanf（d，arr）; temarri; i (1000 ！ i） isert(rot，ie)； printf（'当前已经生成得数列:n); for（ =;it;+) printf(%d ,arri)； printf('n 当前已经生成得二叉树：n）; sowbt(root）； pntf（nn)； int hoise=0； o printf（'n、使用顺序查询、n、使用二分查找法查找、n3、利用二叉排序树查找、4、利用哈希表查找、n5、退出n'）； scanf（d',choise）; i（cse=1) sequeeseach（arr，cunt)； ese i（chise=2) seac(arr，cout)； ese i（chise=） ；）toor（erthcras ls