查找文档格式.docx
《查找文档格式.docx》由会员分享,可在线阅读,更多相关《查找文档格式.docx(17页珍藏版)》请在冰点文库上搜索。
![查找文档格式.docx](https://file1.bingdoc.com/fileroot1/2023-5/2/69e85fc5-7f53-4f2a-9dcf-3e22f283d1de/69e85fc5-7f53-4f2a-9dcf-3e22f283d1de1.gif)
(4)提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
2.需求分析
各种查找算法性能比较
①静态查找——折半查找和斐波拉契查找(有序)
②动态查找——二叉排序树的基本操作
任务:
编写算法实现对依次输入的关键字序列建立二叉排序树,并能实现二叉排序树的查找、插入和删除运算。
③散列法查找
在Hash查找方法中,散列函数构造方法多种多样,同时对于同一散列函数解决冲突的方法也可以不同。
两者是影响查询算法性能的关键因素。
对于几种典型的散列函数构造方法,做实验观察,不同的解决冲突方法对查询性能的影响。
3.1概要设计
使用了顺序查找,折半查找,二叉排序树查找和哈希表查找四种方法。
3.3调试分析
测试数据,测试输出的结果,时间复杂度分析,和每个模块设计和调试时存在问题的思考(问题是哪些?
问题如何解决?
),算法的改进设想。
3.4用户手册(略)
3.5测试结果(略)
4总结
查找算法较前几次实验比较简单,有部分查找算法的思想参考书上描述。
5、程序清单:
(见附录)
#include<
stdio.h>
#defineLENGTH100
stdlib.h>
time.h>
#defineINFMT"
%d"
#defineOUTFMT"
%d"
#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;
lchild=node->
rchild=NULL;
if(!
*tree)
*tree=node;
else
{
BSTreecursor=*tree;
while
(1)
if(item<
cursor->
data)
if(NULL==cursor->
lchild)
cursor->
lchild=node;
break;
}
cursor=cursor->
lchild;
rchild)
rchild=node;
rchild;
return;
}
voidshowbitree(BiTreeT)//递归显示二叉树的广义表形式
if(!
T)
{printf("
空"
);
printf("
T->
data);
//打印根节点
if(T->
lchild||T->
{
putchar('
('
showbitree(T->
lchild);
//递归显示左子树
'
rchild);
//递归显示右子树
)'
}
BSTreeSearch(BSTreetree,ElemTypeitem)//查找指定值
BSTreecursor=tree;
while(cursor)
if(item==cursor->
returncursor;
elseif(item<
returnNULL;
voidInorder(BSTreetree)//中缀遍历
if(cursor)
Inorder(cursor->
printf(OUTFMT,cursor->
voidCleanup(BSTreetree)//回收资源
Cleanup(cursor->
free(cursor);
voidsearchtree(BSTreeroot)
charchoice;
printf("
中序遍历的结果为:
\n"
Inorder(root);
\n\n"
ElemTypeitem;
BSTreeret;
//二叉排序树的查找测试
do
\n请输入查找数据:
"
scanf("
&
item);
getchar();
Searching...\n"
ret=Search(root,item);
if(NULL==ret)
查找失败!
查找成功!
\n继续测试按y,退出按其它键。
choice=getchar();
}while(choice=='
y'
||choice=='
Y'
Cleanup(root);
voidsearchhash(int*arr,intn)
inta[10];
inti,j,c;
j=1;
for(i=0;
i<
9;
i++)
a[i]=0;
以下为哈希表输出\n"
for(i=0;
n;
c=arr[i]%7;
A:
if(a[c]==0)a[c]=arr[i];
else{c=(c+1)%7;
j++;
a[c]++;
gotoA;
\n%d在哈希表的第%d位,第%d次放入哈希表\n"
arr[i],c,j);
voidSequenceSearch(int*fp,intLength)
intdata;
开始使用顺序查询.\n请输入你想要查找的数据.\n"
&
inti;
for(i=0;
Length;
if(fp[i]==data)
经过%d次查找,查找到数据%d.\n"
i+1,data);
return;
经过%d次查找,未能查找到数据%d.\n"
i,data);
voidSort(int*fp,intlength)
现在开始为数组排序,排列结果将是从小到大.\n"
inttemp;
for(inti=0;
length;
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;
排序完成!
\n下面输出排序后的数组:
for(intk=0;
k<
k++)
%5d"
fp[k]);
voidSearch(int*fp,intlength)
由于二分查找法要求数据是有序的,现在开始为数组排序.\n"
Sort(fp,length);
数组现在已经是从小到大排列,下面将开始查找.\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]>
top=middle-1;
structhash
{intkey;
intsi;
};
structhashhlist[11];
inti,adr,sum,d;
floataverage;
voidchash(int*arr,intn)
11;
hlist[i].key=0;
hlist[i].si=0;
{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("
哈希表显示为:
%4d"
i);
哈希表关键字:
hlist[i].key);
查找长度是:
"
hlist[i].si);
average=0.0;
average=average+hlist[i].si;
average=average/n;
平均长度:
asl(%d)=%f\n"
n,average);
intmain()
intcount;
intarr[LENGTH];
BSTreeroot=NULL,ret;
/*必须赋予NULL值,否则出错*/
BOOLfinish=FALSE;
请输入你的数据的个数:
count);
请输入%d个数据\n"
count);
count;
arr[i]);
item=arr[i];
if(-10000!
=item)
Insert(&
root,item);
当前已经生成的数列:
arr[i]);
\n当前已经生成的二叉树:
showbitree(root);
intchoise=0;
\n1.使用顺序查询.\n2.使用二分查找法查找.\n3.利用二叉排序树查找.\n4.利用哈希表查找.\n5.退出\n"
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)
}while(choise==1||choise==2||choise==3||choise==4||choise==5);
}6、参考文献1严蔚敏,吴伟民编著.数据结构(C语言版)--北京:
清华大学出版社,2007.2严蔚敏,吴伟民米宁编著.数据结构题集(C语言版)--北京:
清华大学出版社,2007.3网上搜索相关程序作为参考