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

真诚为您提供优质参考资料，若有不当之处，请指正。数据结构查找算法实验报告1/2真诚为您提供优质参考资料，若有不当之处，请指正。数据结构实验报告实验第四章：实验:简单查找算法需求和规格说明：查找算法这里主要使用了顺序查找，折半查找，二叉排序树查找和哈希表查找四种方法。由于自己能力有限，本想实现其他算法，但没有实现。其中顺序查找相对比较简单，折半查找参考了书上的算法，二叉排序树查找由于有之前做二叉树的经验，因此实现的较为顺利，哈希表感觉做的并不成功，感觉还是应该可以进一步完善，应该说还有很大的改进余地。设计思想：开始的时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树，以使得更直观。哈希表则是利用给定的函数式建立索引，方便查找。设计表示：实现注释：其实查找排序这部分和前面的一些知识联系的比较紧密，例如顺序表的建立和实现，顺序表节点的排序，二叉树的生成和遍历，这里主要是中序遍历。应该说有些知识点较为熟悉，但在实现的时候并不是那么顺利。在查找到数据的时候要想办法输出查找过程的相关信息，并统计。这里顺序查找和折半查找均使用了数组存储的顺序表，而二叉树则是采用了链表存储的树形结构。为了直观起见，在用户输入了数据后，分别输出已经生成的数组和树。折半查找由于只能查找有序表，因此在查找前先调用函数对数据进行了排序。在查找后对查找数据进行了统计。二叉排序树应该说由于有了之前二叉树的基础，并没有费太大力气，主要是在构造二叉树的时候，要对新加入的节点数据和跟数据进行比较，如果比根节点数据大则放在右子树里，如果比根节点数据小则放入左子树。建立了二叉树后，遍历和查找就很简单了。而哈希表，应该说自我感觉掌握的很不好，程序主要借鉴了书上和ppt上的代码，但感觉输出还是有问题，接下来应该进一步学习哈希表的相关知识。其实原本还设计了其他几个查找和排序算法，但做到哈希表就感觉很困难了，因此没有继续往下做，而且程序还非常简陋，二叉树和哈希表的统计部分也比较薄弱，这也是接下来我要改进的地方。具体代码见源代码部分。5.详细设计表示：6.用户手册：程序运行后，用户首先要输入数据的个数。接下来输入一组数据并根据提示进行顺序查找，二分查找，二叉排序树查找和哈希表查找等操作，由于操作直接简单这里不再详述。数据结构查找算法实验报告全文共13页，当前为第1页。数据结构查找算法实验报告全文共13页，当前为第1页。7.调试报告：应该说在调试这个程序的过程中自己发现了很多不足，这次实验让我学到了不少东西，但应该说这个程序可实现的功能还是偏少，不太实用，接下来有待改进。8.源代码清单和结果：#include<stdio.h>#defineLENGTH100#include<stdlib.h>#include<time.h>#defineINFMT"%d"#defineOUTFMT"%d"/*#defineNULL0L*/#defineBOOLint#defineTRUE1#defineFALSE0#defineLEN10000typedefintElemType;typedefstructBSTNode{ElemTypedata;structBSTNode*lchild,*rchild;}BSTNode,*BSTree;typedefBSTreeBiTree;/*插入新节点*/voidInsert(BSTree*tree,ElemTypeitem){BSTreenode=(BSTree)malloc(sizeof(BSTNode));node->data=item;node->lchild=node->rchild=NULL;if(!*tree)*tree=node;else{BSTreecursor=*tree;while(1){if(item<cursor->data){if(NULL==cursor->lchild)数据结构查找算法实验报告全文共13页，当前为第2页。数据结构查找算法实验报告全文共13页，当前为第2页。cursor->lchild=node;break;}cursor=cursor->lchild;}else{if(NULL==cursor->rchild){cursor->rchild=node;break;}cursor=cursor->rchild;}}}return;} void showbitree(BiTreeT)//递归显示二叉树的广义表形式{ if(!T) {printf("空");return;} printf("%d",T->data); //打印根节点 if(T->lchild||T->rchild) { putchar('('); showbitree(T->lchild); //递归显示左子树 putchar(','); showbitree(T->rchild); //递归显示右子树 putchar(')'); }}/*查找指定值*/BSTreeSearch(BSTreetree,ElemTypeitem){BSTreecursor=tree;数据结构查找算法实验报告全文共13页，当前为第3页。数据结构查找算法实验报告全文共13页，当前为第3页。{if(item==cursor->data)returncursor;elseif(item<cursor->data)cursor=cursor->lchild;elsecursor=cursor->rchild;}returnNULL;}/*中缀遍历*/voidInorder(BSTreetree){BSTreecursor=tree;if(cursor){Inorder(cursor->lchild);printf(OUTFMT,cursor->data);Inorder(cursor->rchild);}}/*回收资源*/voidCleanup(BSTreetree){BSTreecursor=tree,temp=NULL;if(cursor){Cleanup(cursor->lchild);Cleanup(cursor->rchild);free(cursor);}}voidsearchtree(BSTreeroot){charchoice;printf("中序遍历的结果为:\n");Inorder(root);数据结构查找算法实验报告全文共13页，当前为第4页。printf("\n\n");数据结构查找算法实验报告全文共13页，当前为第4页。ElemTypeitem;BSTreeret;/*二叉排序树的查找测试*/do{printf("\n请输入查找数据：");scanf("%d",&item);getchar();printf("Searching...\n");ret=Search(root,item);if(NULL==ret)printf("查找失败！");elseprintf("查找成功！");printf("\n继续测试按y，退出按其它键。\n");choice=getchar();}while(choice=='y'||choice=='Y');Cleanup(root);}searchhash(int*arr,intn){ inta[10]; intb,i,j,c; j=1; for(i=0;i<9;i++) a[i]=0; printf("以下为哈希表输出\n"); for(i=0;i<n;i++) { c=arr[i]%7;A: if(a[c]==0)a[c]=arr[i]; else{c=(c+1)%7;j++;a[c]++;gotoA;} printf("\n%d在哈希表的第%d位,第%d次放入哈希表\n",arr[i],c,j); j=1;}}voidSequenceSearch(int*fp,intLength);数据结构查找算法实验报告全文共13页，当前为第5页。voidSearch(int*fp,intleng数据结构查找算法实验报告全文共13页，当前为第5页。voidSort(int*fp,intlength);voidSequenceSearch(int*fp,intLength){intdata;printf("开始使用顺序查询.\n请输入你想要查找的数据.\n");scanf("%d",&data);for(inti=0;i<Length;i++)if(fp[i]==data){printf("经过%d次查找，查找到数据%d.\n",i+1,data);return;}printf("经过%d次查找，未能查找到数据%d.\n",i,data);}voidSearch(int*fp,intlength){intdata;printf("开始使用顺序查询.\n请输入你想要查找的数据.\n");scanf("%d",&data);printf("由于二分查找法要求数据是有序的，现在开始为数组排序.\n");Sort(fp,length);printf("数组现在已经是从小到大排列,下面将开始查找.\n");intbottom,top,middle;bottom=0;top=length;inti=0;while(bottom<=top){middle=(bottom+top)/2;i++;if(fp[middle]<data){bottom=middle+1;}elseif(fp[middle]>data)数据结构查找算法实验报告全文共13页，当前为第6页。数据结构查找算法实验报告全文共13页，当前为第6页。top=middle-1;}else{printf("经过%d次查找，查找到数据%d.\n",i,data);return;}}printf("经过%d次查找，未能查找到数据%d.\n",i,data);}voidSort(int*fp,intlength){printf("现在开始为数组排序，排列结果将是从小到大.\n");inttemp;for(inti=0;i<length;i++)for(intj=0;j<length-i-1;j++)if(fp[j]>fp[j+1]){temp=fp[j];fp[j]=fp[j+1];fp[j+1]=temp;}printf("排序完成!\n下面输出排序后的数组:\n");for(intk=0;k<length;k++){printf("%5d",fp[k]);}printf("\n");}structhash{intkey;intsi;};structhashhlist[11];inti,adr,sum,d;数据结构查找算法实验报告全文共数据结构查找算法实验报告全文共13页，当前为第7页。floataverage;voidchash(int*arr,intn){for(i=0;i<11;i++){hlist[i].key=0;hlist[i].si=0;}for(i=0;i<n;i++){sum=0;adr=(3*arr[i])%11;d=adr;if(hlist[adr].key==0){hlist[adr].key=arr[i];hlist[adr].si=1;}else{do{d=(d+(arr[i]*7)%10+1)%11;sum=sum+1;}while(hlist[d].key!=0);hlist[d].key=arr[i];hlist[d].si=sum+1;数据结构查找算法实验报告全文共数据结构查找算法实验报告全文共13页，当前为第8页。}}}voiddhash(int*arr,intn){printf("哈希表显示为:");for(i=0;i<11;i++)printf("%4d",i);printf("\n");printf("哈希表关键字:");for(i=0;i<11;i++)printf("%4d",hlist[i].key);printf("\n");printf("查找长度是:");for(i=0;i<11;i++)printf("%4d",hlist[i].si);printf("\n");average=0.0;for(i=0;i<11;i++)average=average+hlist[i].si;average=average/n;printf("平均长度:asl(%d)=%f\n",n,average);}voidmain()数据结构查找算法实验报告全文共13页，当前为第9页。数据结构查找算法实验报告全文共13页，当前为第9页。intcount;intarr[LENGTH];ElemTypeitem;charchoice;BSTreeroot=NULL,ret;/*必须赋予NULL值，否则出错*/BOOLfinish=FALSE;printf("请输入你的数据的个数:\n");scanf("%d",&count);printf("请输入%d个数据\n",count);for(inti=0;i<count;i++){scanf("%d",&arr[i]);item=arr[i];if(-10000!=item)Insert(&root,item);}printf("当前已经生成的数列：\n");for(i=0;i<count;i++){printf("%d",arr[i]);}printf("\n当前已经生成的二叉树：\n");showbitree(root);