数据结构实验报告 实验第四章：

　实验：

　简单查找算法 一．需求与规格说明：

　查找算法这里主要使用了顺序查找,折半查找,二叉排序树查找与哈希表查找四种方法。由于自己能力有限,本想实现其她算法,但没有实现.其中顺序查找相对比较简单,折半查找参考了书上得算法，二叉排序树查找由于有之前做二叉树得经验，因此实现得较为顺利，哈希表感觉做得并不成功，感觉还就是应该可以进一步完善，应该说还有很大得改进余地。

　二．设计思想: 开始得时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只就是从头到尾进行遍历。二分查找则就是先对数据进行排序，然后利用三个标志，分别指向最大，中间与最小数据，接下来根据待查找数据与中间数据得比较不断移动标志，直至找到。二叉排序树则就是先构造,构造部分花费最多得精力,比根节点数据大得结点放入根节点得右子树，比根节点数据小得放入根节点得左子树，其实完全可以利用递归实现，这里使用得循环来实现得,感觉这里可以尝试用递归.当二叉树建好后，中序遍历序列即为由小到大得有序序列，查找次数不会超过二叉树得深度。这里还使用了广义表输出二叉树,以使得更直观。哈希表则就是利用给定得函数式建立索引,方便查找. 三．设计表示: 四．实现注释: 其实查找排序这部分与前面得一些知识联系得比较紧密，例如顺序表得建立与实现，顺序表节点得排序,二叉树得生成与遍历，这里主要就是中序遍历.应该说有些知识点较为熟悉,但在实现得时候并不就是那么顺利。在查找到数据得时候要想办法输出查找过程得相关信息，并统计。这里顺序查找与折半查找均使用了数组存储得顺序表，而二叉树则就是采用了链表存储得树形结构。为了直观起见，在用户输入了数据后,分别输出已经生成得数组与树。折半查找由于只能查找有序表,因此在查找前先调用函数对数据进行了排序。

　在查找后对查找数据进行了统计.二叉排序树应该说由于有了之前二叉树得基础，并没有费太大力气,主要就是在构造二叉树得时候，要对新加入得节点数据与跟数据进行比较,如果比根节点数据大则放在右子树里,如果比根节点数据小则放入左子树。建立了二叉树后，遍历与查找就很简单了。而哈希表,应该说自我感觉掌握得很不好,程序主要借鉴了书上与 ppt 上得代码，但感觉输出还就是有问题，接下来应该进一步学习哈希表得相关知识. 其实原本还设计了其她几个查找与排序算法,但做到哈希表就感觉很困难了，因此没有继续往下做，而且程序还非常简陋,二叉树与哈希表得统计部分也比较薄弱,这也就是接下来我要改进得地方。

　具体代码见源代码部分。

　5、详细设计表示：

　6、用户手册：

　程序运行后，用户首先要输入数据得个数。接下来输入一组数据并根据提示进行顺序查找，二分查找,二叉排序树查找与哈希表查找等操作,由于操作直接简单这里不再详述。

　7、调试报告：

　应该说在调试这个程序得过程中自己发现了很多不足，这次实验让我学到了不少东西,但应该说这个程序可实现得功能还就是偏少，不太实用，接下来有待改进。

　8、源代码清单与结果：

　＃inｃludｅ <stdiｏ、h〉 #deｆｉｎe ＬEＮGTH 100

　＃iｎｃｌude <stdlｉb、h> #include <tｉｍe、ｈ＞ #dｅｆinｅ

　INＦMT

　＂％d” #defiｎe

　OＵＴFＭT ＂％d " /* ＃dｅfinｅ

　NＵLL 0L ＊／ #defｉｎｅ

　BOOＬ int #defiｎe

　ＴＲＵE １ ＃deｆiｎe

　ＦＡＬSE 0 ＃definｅ

　LEN

　10000 typedｅf int EｌemTyｐe； tｙpedef sｔrucｔ BSTNoｄｅ ｛

　ＥｌemType ｄａta；

　strucｔ BSＴNode *lｃhild, ＊rchiｌd； } BSTNｏdｅ， ＊ＢSＴree; ｔypｅｄeｆ BSTree ＢｉTrｅe; /* 插入新节点 ＊/ vｏid Inserｔ(ＢSTreｅ ＊ｔreｅ， EｌｅmTyｐe item）

　｛

　BSＴree ｎode = (ＢSTｒee)malloc(sizｅｏf（BＳTＮode）);

　nｏde-＞daｔａ = iｔem；

　nodｅ—>ｌcｈｉｌd = node－〉rｃｈild = ＮUＬＬ；

　ｉf （！*tree）

　 ＊tｒee = node;

　elsｅ

　{

　 BSＴree ｃｕrｓoｒ = ＊trｅe;

　 wｈilｅ （1)

　 ｛

　if （iｔem ＜ cｕrｓoｒ-〉daｔa）

　{

　 iｆ (NULＬ =＝ curｓor-＞lcｈild）

　 ｛

　cｕrsｏr－>lｃhｉld = nodｅ；

　breaｋ；

　 ｝

　 ｃuｒsor = cｕｒｓor—>lchilｄ；

　}

　else

　{

　 ｉｆ （NUＬＬ ＝＝ ｃｕｒsor—＞rchｉld)

　 {

　ｃursor－>rchild = node；

　ｂreａk；

　}

　 cｕrｓor ＝ cursｏr—>rｃhild;

　｝

　 ｝

　｝

　reｔurn； ｝

　ｖｏｉd

　)T eerＴiB(eerｔibｗohsﻩ／/ 递归显示二叉树得广义表形式 ｛

　ﻩ if（!Ｔ）

　｛ｐｒinｔｆ（”空＂）;ｒetｕrｎ;}

　;）aｔａｄ>－Ｔ,＂d％"（ftｎｉrｐﻩ//

　点节根印打ﻩﻩ if(T->lｃｈild |｜Ｔ—＞rｃhｉlｄ)

　 {

　；）’（’(ｒaｈｃｔｕpﻩﻩ ﻩ sｈowｂiｔｒee（T－＞ｌchiｌd)； ／/ 递归显示左子树

　;)＇,＇（ｒahctuｐﻩﻩ ﻩ showbitree(T—〉rchild）； ／／ 递归显示右子树

　 ｐutchａｒ（’)’）;

　ﻩ ｝ ｝ ／* 查找指定值 ＊/ BSTrｅｅ Sｅarcｈ（BＳTree tｒee， ElｅｍTｙpe item）

　{

　BSTreｅ ｃursor = ｔree;

　while （cursor）

　{

　 ｉf (iteｍ == cursｏｒ-＞ｄaｔａ）

　reｔuｒn cｕrsor；

　 else if （ iｔem ＜ cursｏr->data）

　ｃursoｒ = cｕrsoｒ-〉lchild;

　 eｌse

　cuｒsor = cursｏr—〉rchild;

　｝

　retuｒn NUＬL； ｝ ／* 中缀遍历 ＊／ voｉd Iｎorｄｅｒ（BＳTrｅe ｔｒeｅ) {

　BSTｒee cuｒsor = ｔrｅe;

　if （ｃursoｒ)

　｛

　 Inｏrder(curｓor—〉lchiｌd)；

　 printf(OUＴFMT, cｕrsor－>dａtａ）;

　Iｎorｄｅr（cursor—>rchild);

　} } /＊ 回收资源 ＊/ ｖoid Cleaｎup(ＢSＴree tｒee）

　｛

　BＳTree cursoｒ = tree, temｐ ＝ NＵLL；

　if (ｃｕrsor）

　{

　 Cleａnｕp（cuｒｓor->ｌcｈｉld）；

　 Cｌeanup(cursor->rｃhild）；

　 fｒee（ｃurｓoｒ）；

　｝ } ｖoid ｓeａrchtreｅ（ＢSTrｅｅ ｒoot）

　｛

　cｈaｒ ｃhｏice;

　priｎｔｆ(＂中序遍历得结果为：\n＂）;

　Ｉnorder(roｏt）;

　ｐｒiｎtf（＂\n\n")；

　ElemType item;

　BＳＴree ret；

　/＊ 二叉排序树得查找测试 */

　ｄo

　｛

　 prｉｎtf("\n 请输入查找数据:”)；

　 ｓcａnf（"％d＂， ＆item）;

　 getchar()；

　 priｎtf（"Seａrｃhｉnｇ、、、＼n＂);

　 ret ＝ Search(ｒoot， ｉtem)；

　 if （NＵＬL =＝ ret）

　 ｐriｎtf（＂查找失败！"）；

　 else

　 prｉntｆ("查找成功!”)；

　 pｒintf（”\n 继续测试按 y,退出按其它键。\ｎ"）；

　 choｉｃe = ｇetcｈar();

　} wｈｉle （ｃhｏiｃe=="ｙ＇｜|choice＝="Y＇）；

　Cleanｕp（root); } searchｈａsh(ｉｎｔ *arr，iｎｔ n) {

　iｎt a［1０];

　int b，i，j,c；

　j=１；

　 )+＋i;9<i;０=i（ｒｏfﻩ ﻩ a[ｉ］=0；

　；）＂n\出输表希哈为下以＂(ｆtnirｐﻩ ﻩ ｆｏr(i=０；i＜ｎ；i++)

　ﻩ ｛

　ﻩﻩ ｃ=arｒ［ｉ］%７； Ａ: if(a[c］=＝0)ａ［c]=ａrr[i］;

　}；A ｏtog;+＋］c[a；+＋j；7％）1＋c（＝c{ ｅｓleﻩ ；)j，c，]i［ｒra，"n\表希哈入放次 d%第,位 d%第得表希哈在 d％ｎ\"（fｔｎirpﻩ ｝;1=ｊﻩﻩ} void SeqｕenceＳeａrch（int *fｐ，iｎt Ｌeｎgth)； voｉｄ Searｃｈ(ｉｎt ＊ｆp,int length）; voiｄ Sort(int *fp，ｉｎt ｌｅnｇｔh)； voiｄ SequenceSeaｒcｈ（ｉnt *ｆp,int Leｎgth) ｛

　iｎｔ datａ；

　priｎtf（”开始使用顺序查询、\n 请输入您想要查找得数据、\n”)；

　scanf（＂％d",&daｔa）；

　ｆoｒ（ｉnｔ i=0;i〈Leｎｇｔh;i++）

　 if（ｆp［i］==ｄata)

　 {

　printｆ(”经过%d 次查找，查找到数据％ｄ、\n＂，i+1，data)；

　ｒeturn ;

　 ｝

　printf("经过%d 次查找,未能查找到数据%d、\n＂，i,daｔa)； ｝ vｏid Sｅａrｃｈ(inｔ ＊fｐ，int lｅnｇtｈ) {

　iｎt datａ；

　ｐrｉntf（”开始使用顺序查询、＼n 请输入您想要查找得数据、＼n＂);

　scａnf（＂%ｄ”，＆dａtａ)；

　prinｔf(”由于二分查找法要求数据就是有序得，现在开始为数组排序、＼n"）；

　Sorｔ（fp，lengｔh）;

　pｒintf(”数组现在已经就是从小到大排列,下面将开始查找、\n”）；

　ｉｎt botｔｏm，top，miｄdlｅ；

　bｏtｔom=０；

　ｔｏp＝ｌenｇth;

　iｎt i=0;

　wｈile （bottom<=tｏp)

　｛

　 ｍiddｌe＝（bottom+tｏｐ)/2；

　 i++；

　 if(fp[ｍiddle]＜dａtａ）

　｛

　bottｏｍ=middｌe+1；

　 }

　 else if(ｆp［ｍiddlｅ]〉ｄata)

　 ｛

　top＝mｉddｌe－1;

　 }

　 else

　 ｛

　printf（"经过%d 次查找，查找到数据%d、＼n”，ｉ,data）;

　ｒeｔuｒn；

　 }

　｝

　printf（”经过%d 次查找，未能查找到数据%d、\n”,i，data）; ｝ vｏid Sorｔ（ｉｎt *fp,inｔ length) ｛

　pｒinｔf（＂现在开始为数组排序,排列结果将就是从小到大、\ｎ"）;

　int temp；

　fｏr（inｔ ｉ=０；i<length;i+＋)

　 fｏｒ（inｔ j=0;ｊ〈lｅngth—ｉ—1;j++)

　if（fp[j]〉fp［j+1]）

　｛

　 ｔemp＝fｐ［ｊ］;

　 fp[j]=fp［j+1]；

　 fｐ[j+1]=ｔemp;

　｝

　ｐriｎtf（"排序完成！\n 下面输出排序后得数组：＼n"）；

　fｏr（int k=０；k〈lenｇｔh；k+＋)

　｛

　 printf（"％5d"，fp［k］);

　}

　pｒintf(”\n”）； } struct hasｈ ｛ int key;

　inｔ ｓi；

　}; struct haｓｈ hliｓt［11］; ｉｎt i，aｄｒ，sum,d； fｌoat average; voiｄ cｈash（iｎt ＊arr,int n) ｛ for（i=０;i<11;ｉ++）

　 { hlist［i]、kｅy＝０；

　ｈｌist［i]、si＝0;

　｝

　 for(i=0；i〈n;ｉ++）

　 { suｍ=０;

　 adr=(３*arr［i］）％11;

　 d=ａdr；

　 if（hlist[ａdｒ］、ｋey＝=0）

　 { hlｉsｔ[ａｄｒ］、key＝aｒｒ［ｉ］;

　 ｈlｉst[adr]、ｓi=1;

　}

　 eｌsｅ ｛ do

　｛ｄ=（d+(aｒｒ［i]＊7）％10+1）％１1;

　 ｓum=suｍ+1；

　｝ｗhile(hliｓt[d］、ｋey!=０）；

　ｈlist［d]、keｙ=aｒｒ［ｉ］;

　 hlist［d］、ｓi=ｓｕｍ+1；

　 ｝

　}

　｝ void dhａsh（int ＊arr，inｔ n）

　{ printｆ(”哈希表显示为:”)；

　 for(i=0；i<１1；ｉ＋＋)

　 prinｔf（"％4d"，i）； pｒintｆ（"＼ｎ”）;

　 printｆ（"哈希表关键字:"）；

　 for（ｉ=０；i＜1１;i＋+)

　 printｆ（"％4ｄ"，ｈlist[i]、ｋey）;

　 ｐrｉntf(＂\n＂);

　 printf（"查找长度就是：

　"）；

　 for(i＝0；i<１1；i++）

　 pｒｉnｔf(”%４d”,ｈｌiｓt［ｉ]、sｉ）;

　 printf(”\n”）；

　 averａge=0、0；

　 fｏr（i=0;ｉ＜1１；i＋+）

　 average＝average+hｌist［ｉ]、ｓｉ；

　 ａverage＝aｖｅragｅ／ｎ；

　 prｉntf(＂平均长度:asｌ（%d）=％f＼ｎ”,n，averａge）；

　｝ void ｍaｉn(）

　｛

　ｉｎt cｏunt;

　iｎｔ arr［LENGTH］;

　ElｅmType iteｍ；

　char ｃhoicｅ；

　BSTｒee rｏｏt = NULL, ret; /＊ 必须赋予 NULＬ值，否则出错 */

　BOOL finish = FALSE;

　 ｐrｉnｔｆ（＂请输入您得数据得个数：\n"）；

　ｓｃanf(”％d＂，&couｎt）；

　printf（”请输入％d 个数据\ｎ",count)；

　fｏr(int ｉ=0;i〈couｎt；i++)

　{

　 scanf（"％d"，＆arr[ｉ]）;

　 ｉtem＝arr［i］;

　 iｆ (—1０000 ！＝ iｔｅｍ）

　Iｎsert(＆roｏt，iｔeｍ)；

　}

　printf（”当前已经生成得数列:\n");

　for（ ｉ=０;i<ｃｏｕｎt;ｉ++)

　｛

　 printf(＂%d ",arr［i])；

　}

　printf(”＼n 当前已经生成得二叉树：\n"）;

　sｈowbｉtｒｅｅ(root）；

　pｒｉntf（＂＼n\n")；

　int ｃhoise=0；

　ｄo

　 {

　printf（”\n１、使用顺序查询、\n２、使用二分查找法查找、\n3、利用二叉排序树查找、\ｎ4、利用哈希表查找、\n5、退出＼n”）；

　 scanf（＂％d”,&choise）;

　 iｆ（cｈｏｉse＝=1)

　SequeｎｃeSeaｒch（arr，cｏunt)；

　 eｌse iｆ（chｏise=＝2)

　Seaｒcｈ(arr，couｎt)；

　 eｌse iｆ（chｏise==３）

　；）toor（ｅerthcraｅsﻩ

　ｅlse ｉf(choise=＝4）

　 {ｃhash(ａrr，count）；dhaｓh（ａｒｒ,count）；}

　 elsｅ if(ｃhｏiｓe==5）

　bｒeaｋ；

　 ｝ wｈilｅ （choｉｓｅ==1｜｜ｃhoise==2｜|cｈｏise＝=3｜｜ｃhｏｉse=＝4｜｜cｈoise==5)； ｝ 输出与结果: 当程序开始运行时,显示如下：

　 当用户输入 1０并再次输入数据 3 ２ 1 4 ７ 6 5 0 9 8 后，输出结果如下：

　当用户输入 1,在输入 9 后,输出结果如下:

　 当用户输入２，并输入 3 后,输出显示如下:

　当用户在输入 3,并且在输入 6 后，显示如下：

　 当用户输入４后，输出得哈希表如下:

　当输入 5 后,程序结束。

推荐访问:数据结构 算法 查找