《数据结构查找算法实验报告》由会员分享，可在线阅读，更多相关《数据结构查找算法实验报告（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验第四章：实验： 简单查找算法一 需求与规格说明：查找算法这里主要使用了顺序查找,折半查找,二叉排序树查找与哈希表查找四种方法。由于自己能力有限,本想实现其她算法,但没有实现.其中顺序查找相对比较简单,折半查找参考了书上得算法，二叉排序树查找由于有之前做二叉树得经验，因此实现得较为顺利，哈希表感觉做得并不成功，感觉还就是应该可以进一步完善，应该说还有很大得改进余地。二 设计思想:开始得时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只就是从头到尾进行遍历。二分查找则就是先对数据进行排序，然后利用三个标志，分别指向最大，中间与最小数据，接下
2、来根据待查找数据与中间数据得比较不断移动标志，直至找到。二叉排序树则就是先构造,构造部分花费最多得精力,比根节点数据大得结点放入根节点得右子树，比根节点数据小得放入根节点得左子树，其实完全可以利用递归实现，这里使用得循环来实现得,感觉这里可以尝试用递归.当二叉树建好后，中序遍历序列即为由小到大得有序序列，查找次数不会超过二叉树得深度。这里还使用了广义表输出二叉树,以使得更直观。哈希表则就是利用给定得函数式建立索引,方便查找.三 设计表示:四 实现注释:其实查找排序这部分与前面得一些知识联系得比较紧密，例如顺序表得建立与实现，顺序表节点得排序,二叉树得生成与遍历，这里主要就是中序遍历.应该说有些
3、知识点较为熟悉,但在实现得时候并不就是那么顺利。在查找到数据得时候要想办法输出查找过程得相关信息，并统计。这里顺序查找与折半查找均使用了数组存储得顺序表，而二叉树则就是采用了链表存储得树形结构。为了直观起见，在用户输入了数据后,分别输出已经生成得数组与树。折半查找由于只能查找有序表,因此在查找前先调用函数对数据进行了排序。在查找后对查找数据进行了统计.二叉排序树应该说由于有了之前二叉树得基础，并没有费太大力气,主要就是在构造二叉树得时候，要对新加入得节点数据与跟数据进行比较,如果比根节点数据大则放在右子树里,如果比根节点数据小则放入左子树。建立了二叉树后，遍历与查找就很简单了。而哈希表,应该说
4、自我感觉掌握得很不好,程序主要借鉴了书上与ppt上得代码，但感觉输出还就是有问题，接下来应该进一步学习哈希表得相关知识.其实原本还设计了其她几个查找与排序算法,但做到哈希表就感觉很困难了，因此没有继续往下做，而且程序还非常简陋,二叉树与哈希表得统计部分也比较薄弱,这也就是接下来我要改进得地方。具体代码见源代码部分。5、详细设计表示：6、用户手册：程序运行后，用户首先要输入数据得个数。接下来输入一组数据并根据提示进行顺序查找，二分查找,二叉排序树查找与哈希表查找等操作,由于操作直接简单这里不再详述。7、调试报告：应该说在调试这个程序得过程中自己发现了很多不足，这次实验让我学到了不少东西,但应该说
5、这个程序可实现得功能还就是偏少，不太实用，接下来有待改进。8、源代码清单与结果：inludstdi、h#deeEGTH 100iude#includecd =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 = node； rek； crorcursrrhild; reurn；d shobiree(Biree
6、T)/递归显示二叉树得广义表形式if（!）in（”空）;etr;rtf（d,a）;/ 打印根节点if(T-lild |rhl)pa(（）；sowiee（Tchid)；/ 递归显示左子树utcha（,);showbitree(Trchild）； 递归显示右子树utch（)）;* 查找指定值 /BSTrSarc（BTree tee， ElTpe item） BSTre ursor= ree; while （cursor） f (ite = curs-a） reun crsor；elseif（ iemcursr-data） urso =crso-lchild; ese cusor = cursrrc
7、hild; 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(cursor-rhild）； fee（uro）； oid erchtre（STr oot） ca hice;pri(中序遍历得结果为：n）; norder(rot）
8、;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,退出按其它键。）； choe = etcar(); wle（hie=|choice=Y）； Cleanp（root);searchsh( *arr，i n)ita1;int b，i，j,c；j=；f（i=;i9;i+
9、)a=0；rint(以下为哈希表输出n）；r(i=；i；i+)=ar%；:if(ac=0)c=rri;elc（c1）7；j+；ac+;got A；prif（d在哈希表得第%d位,第%d次放入哈希表n，ari，c，j)；=1;void Seqenceerch（int*f，it egth)；vo Sear(t p,intlength）;voi Sort(int *fp，t nh)；voi SequenceSeac（nt *p,intLegth) i dat； pritf（”开始使用顺序查询、n请输入您想要查找得数据、n”)； scanf（d,&daa）； o（n i=0;iLeh;i+） if（p
10、i=ata) print(”经过%d次查找，查找到数据、n，i+1，data)； eturn ; printf(经过%d次查找,未能查找到数据%d、n，i,daa)；vid Sr(in f，intlnt) it dat； rntf（”开始使用顺序查询、n请输入您想要查找得数据、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）; eun； printf（”经过%d次查找，未能查找到数据%d、n”,i，data）;vidSor（t *fp,in length) pinf（现在开始为数组排序,排列结果将就是从小到大、）;int temp； fr（in =；ilength;i+) f（in j=0;lngth1;j+
