大数据的结构查找算法实验报告材料.docx
- 文档编号:2608466
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:18
- 大小:184.33KB
大数据的结构查找算法实验报告材料.docx
《大数据的结构查找算法实验报告材料.docx》由会员分享,可在线阅读,更多相关《大数据的结构查找算法实验报告材料.docx(18页珍藏版)》请在冰点文库上搜索。
大数据的结构查找算法实验报告材料
数据结构实验报告
实验第四章:
实验:
简单查找算法
一.需求和规格说明:
查找算法这里主要使用了顺序查找,折半查找,二叉排序树查找和哈希表查找四种方法。
由于自己能力有限,本想实现其他算法,但没有实现。
其中顺序查找相对比较简单,折半查找参考了书上的算法,二叉排序树查找由于有之前做二叉树的经验,因此实现的较为顺利,哈希表感觉做的并不成功,感觉还是应该可以进一步完善,应该说还有很大的改进余地。
二.设计思想:
开始的时候提示输入一组数据。
并存入一维数组中,接下来调用一系列查找算法对其进行处理。
顺序查找只是从头到尾进行遍历。
二分查找则是先对数据进行排序,然后利用三个标志,分别指向最大,中间和最小数据,接下来根据待查找数据和中间数据的比较不断移动标志,直至找到。
二叉排序树则是先构造,构造部分花费最多的精力,比根节点数据大的结点放入根节点的右子树,比根节点数据小的放入根节点的左子树,其实完全可以利用递归实现,这里使用的循环来实现的,感觉这里可以尝试用递归。
当二叉树建好后,中序遍历序列即为由小到大的有序序列,查找次数不会超过二叉树的深度。
这里还使用了广义表输出二叉树,以使得更直观。
哈希表则是利用给定的函数式建立索引,方便查找。
三.设计表示:
四.实现注释:
其实查找排序这部分和前面的一些知识联系的比较紧密,例如顺序表的建立和实现,顺序表节点的排序,二叉树的生成和遍历,这里主要是中序遍历。
应该说有些知识点较为熟悉,但在实现的时候并不是那么顺利。
在查找到数据的时候要想办法输出查找过程的相关信息,并统计。
这里顺序查找和折半查找均使用了数组存储的顺序表,而二叉树则是采用了链表存储的树形结构。
为了直观起见,在用户输入了数据后,分别输出已经生成的数组和树。
折半查找由于只能查找有序表,因此在查找前先调用函数对数据进行了排序。
在查找后对查找数据进行了统计。
二叉排序树应该说由于有了之前二叉树的基础,并没有费太大力气,主要是在构造二叉树的时候,要对新加入的节点数据和跟数据进行比较,如果比根节点数据大则放在右子树里,如果比根节点数据小则放入左子树。
建立了二叉树后,遍历和查找就很简单了。
而哈希表,应该说自我感觉掌握的很不好,程序主要借鉴了书上和ppt上的代码,但感觉输出还是有问题,接下来应该进一步学习哈希表的相关知识。
其实原本还设计了其他几个查找和排序算法,但做到哈希表就感觉很困难了,因此没有继续往下做,而且程序还非常简陋,二叉树和哈希表的统计部分也比较薄弱,这也是接下来我要改进的地方。
具体代码见源代码部分。
5.详细设计表示:
6.用户手册:
程序运行后,用户首先要输入数据的个数。
接下来输入一组数据并根据提示进行顺序查找,二分查找,二叉排序树查找和哈希表查找等操作,由于操作直接简单这里不再详述。
7.调试报告:
应该说在调试这个程序的过程中自己发现了很多不足,这次实验让我学到了不少东西,但应该说这个程序可实现的功能还是偏少,不太实用,接下来有待改进。
8.源代码清单和结果:
#include
#defineLENGTH100
#include
#include
#defineINFMT"%d"
#defineOUTFMT"%d"
/*#defineNULL0L*/
#defineBOOLint
#defineTRUE1
#defineFALSE0
#defineLEN10000
typedefintElemType;
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
{
if(NULL==cursor->lchild)
{
cursor->lchild=node;
break;
}
cursor=cursor->lchild;
}
else
{
if(NULL==cursor->rchild)
{
cursor->rchild=node;
break;
}
cursor=cursor->rchild;
}
}
}
return;
}
voidshowbitree(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;
while(cursor)
{
if(item==cursor->data)
returncursor;
elseif(item
cursor=cursor->lchild;
else
cursor=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);
printf("\n\n");
ElemTypeitem;
BSTreeret;
/*二叉排序树的查找测试*/
do
{
printf("\n请输入查找数据:
");
scanf("%d",&item);
getchar();
printf("Searching...\n");
ret=Search(root,item);
if(NULL==ret)
printf("查找失败!
");
else
printf("查找成功!
");
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 { 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); voidSearch(int*fp,intlength); voidSort(int*fp,intlength); voidSequenceSearch(int*fp,intLength) { intdata; printf("开始使用顺序查询.\n请输入你想要查找的数据.\n"); scanf("%d",&data); for(inti=0;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] { bottom=middle+1; } elseif(fp[middle]>data) { 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 for(intj=0;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 { printf("%5d",fp[k]); } printf("\n"); } structhash {intkey; intsi; }; structhashhlist[11]; inti,adr,sum,d; floataverage; voidchash(int*arr,intn) {for(i=0;i<11;i++) {hlist[i].key=0; hlist[i].si=0; } for(i=0;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; }} } 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() { intcount; intarr[LENGTH]; ElemTypeitem; charchoice; BSTreeroot=NULL,ret;/*必须赋予NULL值,否则出错*/ BOOLfinish=FALSE; printf("请输入你的数据的个数: \n"); scanf("%d",&count); printf("请输入%d个数据\n",count); for(inti=0;i { scanf("%d",&arr[i]); item=arr[i]; if(-10000! =item) Insert(&root,item); } printf("当前已经生成的数列: \n"); for(i=0;i { printf("%d",arr[i]); } printf("\n当前已经生成的二叉树: \n"); showbitree(root); printf("\n\n"); intchoise=0; do { printf("\n1.使用顺序查询.\n2.使用二分查找法查找.\n3.利用二叉排序树查找.\n4.利用哈希表查找.\n5.退出\n"); scanf("%d",&choise); if(choise==1) SequenceSearch(arr,count); elseif(choise==2) Search(arr,count); elseif(choise==3) searchtree(root); elseif(choise==4) {chash(arr,count);dhash(arr,count);} elseif(choise==5) break; }while(choise==1||choise==2||choise==3||choise==4||choise==5); } 输出和结果: 当程序开始运行时,显示如下: 当用户输入10并再次输入数据3214765098后,输出结果如下: 当用户输入1,在输入9后,输出结果如下: 当用户输入2,并输入3后,输出显示如下: 当用户在输入3,并且在输入6后,显示如下: 当用户输入4后,输出的哈希表如下: 当输入5后,程序结束。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 结构 查找 算法 实验 报告 材料
![提示](https://static.bingdoc.com/images/bang_tan.gif)