数据结构 查找 课程设计最新Word文件下载.docx
《数据结构 查找 课程设计最新Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构 查找 课程设计最新Word文件下载.docx（22页珍藏版）》请在冰点文库上搜索。
因此，在研究各种查找方法时，首先必须弄清楚这些方法所需的数据结构，特别是存储结构。
下面分别就线性表、树表和哈希表三种数据结构的查找来讨论查找表的表示和操作实现的方法。
目录
一实践目的与要求-4-
1.1实践目的-4-
1.2实践要求-4-
二顺序查找的分析、程序、及运行结果-4-
2.1系统简介-4-
2.2设计思路-4-
2.3顺序查找算法描述-5-
2.4运行结果-6-
三折半查找的分析、程序、及运行结果-6-
3.1系统简介-6-
3.2设计思路-6-
3.3折半查找算法描述-7-
3.4运行结果-8-
四二叉排序树查找的分析、程序、及运行结果-8-
4.1系统简介-8-
4.2设计思路-8-
4.3二叉排序树算法描述-9-
4.4运行结果-11-
五哈希查找的分析、程序、及运行结果-12-
5.1系统简介-12-
5.2设计思路-12-
5.3哈希查找算法描述-13-
5.4运行结果-15-
六致谢-15-
七附录：
-16-
八参考文献-19-
一实践目的与要求
1.1实践目的
1）掌握各种查找算法的思想及其使用条件；
2）掌握上机实现各种查找算法的基本思想；
3）熟练掌握二叉排序树的构造和查找方法；
4）掌握散列表存储结构的思想，能选择合适的散列表函数，实现不同冲突处理方法的散列表的查找与建立；
1.2实践要求
1）掌握实践是算法。
2）上机运行程序，保存和打印运行结果，并结合程序进行分析。
3）注意理解折半查找的适用条件。
4）建立二叉排序树、散列表是相同元素的处理。
5）比较各种查找算法的各自特点，能够结合实际情况选择合适的查找方式。
二顺序查找的分析、程序、及运行结果
2.1系统简介
一次输入顺序表中的各个元素，然后进行关键字查找。
如果存在则返回待查元素的位置。
2.2设计思路
1）顺序查找的思想
对于给定的关键字K，从表中的一端开始，逐个进行数据元素的关键字和给定值的比较，若当前扫描到的关键字与K相等则查找成功；
若扫描结束后，仍未找到关键字等于K的节点，则查找失败。
建立一个顺序表，数据元素从下标为1的单元开始放入，下标为0的元素起哨兵作用，将待查的关键字存入下标为0的单元，顺序表从后向前查找，若直到下标为0时才找到关键字则说明查找失败，若不到下标为0时就找到关键字，则查找成功。
2.3顺序查找算法描述
/*顺序表结构体定义*/
typedefstruct
{
keytypekey[maxsize];
intlen;
}stable;
/*建立线性表*/
stablecreate_s（stabler）
inti,j=0,k=1;
printf（"
请输入顺序表元素，要为整形，用空格分开，-99为结束标志：
\n"
）;
scanf（"
%d"
&
i）;
while（i!
=-99）
{
j++;
r.key[k]=i;
k++;
scanf（"
}
r.len=j;
returnr;
}
/*顺序表查找*/
intsearch_s（keytypek,stable*r）
intj;
j=r->
len;
r->
key[0]=k;
while（r->
key[j]!
=k）
j--;
returnj;
2.4运行结果
三折半查找的分析、程序、及运行结果
3.1系统简介
一次输入顺序表中的各个元素，然后进行关键字查找。
如果存在则返回待查元素的位置，否则显示不存在。
3.2设计思路
1）折半查找的基本思想
设查找表中的元素存放在数组r中，数据元素的下标范围为[low,high],查找的关键字值为key，中间元素的下标为mid=（low+high）/2,（向下取整），令key与r[mid]的关键字比较：
若key=r[mid].key,查找成功，下标为m的记录即为所求，返回mid。
若key<
r[mid].key,所要找的记录只能在左半部分记录中，在对左半部分记录中，再对左半部分使用折半查找法继续进行查找，搜索区间缩小一半。
若key>
r[mid].key,所要找的记录只能在右半部分记录中，在对右半部分记录中，再对右半部分使用折半查找法继续进行查找，搜索区间缩小一半。
重复上述过程，直到找到查找表中某个数据元素的关键字的值等于给定的值key说明查找成功，若出现low的值大于high的情况，说明查找不成功。
建立一个有序表，数据元素从下标为1的单元开始放入。
实现查找算法时，首先将low赋值为1，high等于最后一个数据元素的下标，然后将给定的关键字与查找区间[low,high]中间的数据元素的关键字比较，实现查找过程。
3.3折半查找算法描述
/*折半查找*/
intsearch_bin（keytypek,stable*r）
intlow,high,mid;
low=1;
high=r->
while（low<
=high）
mid=（low+high）/2;
if（k==r->
key[mid]）
returnmid;
elseif（k<
r->
high=mid-1;
elselow=mid+1;
return0;
3.4运行结果
四二叉排序树查找的分析、程序、及运行结果
4.1系统简介
依次输入关键字并建立二叉排序树，实现二叉排序树的插入和查找功能。
4.2设计思路
1）二叉排序树的基本思想
二叉排序树就是将原来的数据根据大小构成一棵二叉树，二叉树中的所有节点数据满足一定的大小关系，所有的左自述中的节点均比根节点小，所有的右子树的节点均比根结点大。
二叉排序树查找是指按照二叉排序树中结点的关系进行查找，查找的关键字首先同根结点比较，如果相等则查找成功；
如果比根结点小，则在左子树中查找；
如果比根结点大，则在右子树中查找。
这种查找方法可以快速缩小查找范围，大大减小查找关键字的比较次数，从而提高查找效率。
2）算法分析
算法的关键过程实际上就是二叉排序树的创建和查找两个步骤。
首先创建一个根结点，第二步就是将其他结点不断插入到二叉树中的合适位置。
二叉排序树进行结点插入时，首先要为结点寻找合适的位置插入。
这个过程实际上就是关键字不断比较的过程。
如果比根结点小，则在左子树中插入；
如果比根结点大，则在右子树中插入。
然后在二叉排序树中查找关键字的结点存在。
4.3二叉排序树算法描述
/*二叉排序树结构体定义*/
typedefstructbsnode
keytypedata;
structbsnode*lchild;
structbsnode*rchild;
}bnode;
bnode*bsp;
bnodebst;
/*为关键字key建立一个二叉排序树结点*/
bnode*createbst（keytypekey）
bnode*s;
s=（bnode*）malloc（sizeof（bst））;
s->
data=key;
lchild=s->
rchild=NULL;
return（s）;
/*将s指向的结点插入到t指向的二叉树中*/
bnode*bstinsert（bnode*t,bnode*s）
bnode*q,*p;
if（t==NULL）
return（s）;
else
p=t;
q=NULL;
while（p）
{
q=p;
if（s->
data==p->
data）
{
printf（"
这个数（%d）已存在"
s->
data）;
return（t）;
}
data<
p->
p=p->
lchild;
elsep=p->
rchild;
}
if（s->
q->
q->
lchild=s;
elseq->
rchild=s;
return（t）;
/*输出二叉排序树*/
voidbstprint（bnode*t）
if（t）
bstprint（t->
lchild）;
printf（"
%d->
"
t->
rchild）;
/*在二叉排序树中查找关键字*/
voidsearch（bnode*t,keytypex）
bnode*p;
error\n"
return;
if（p->
data==x）
searchsuccess!
return;
elseif（x<
if（!
p）
printf（"
%dnotexist!
x）;
4.4运行结果
五哈希查找的分析、程序、及运行结果
5.1系统简介
依次输入关键字并建立哈希表，进行关键字查找。
5.2设计思路
1）哈希表查找基本思想
它是通过记录中的关键字值key为自变量，通过，某一个特定的函数h计算出函数值h（key）作为存储地址，而查找时也用这个函数h进行计算，获得所要查找关键字所在记录的存储位置。
除留余数法是用关键字key除以某个正整数M，所得余数作为哈希地址的方法。
哈希函数h（key）=key%M，一般M的取值为不大于表长的质数。
用开放地址法解决冲突，形成下一个地址的形式时
Hi=（h（key）+di）%Mi=1,2,.....kk（k<
=m-1）
H（key）为哈希函数；
M为正整数；
di为增量序列；
m为表长。
线性探测再散列是将开放地址法中的增量序列di设定为从1开始一直到表长减1的整数序列：
1，2，3，……m-1
2）算法分析
算法的关键过程实际上就是Hash表的创建和查找两个步骤。
其中查找时利用除留余数法构造哈希函数h，计算出函数值获得所要查找的关键字的存储位置。
若存储位置对应的数据元素的值和查找关键字相等，则查找成功，否则，采用线性探测法从关键字的哈希地址开始向后扫描，直到找到与关键字相等的数据元素，查找成功；
若查找到最后还没找到关键字，则查找失败，不存在与关键字相等的数据元素。
5.3哈希查找算法描述
/*哈希表结构体定义*/
typedefstruct
keytypekey;
intcn;
}hashtable;
/*哈希函数*/
inth（keytypekey）
return（key%m）;
/*哈希表查找函数*/
inthashsearch（hashtableht[],keytypekey）
intd,i;
i=0;
d=h（key）;
ht[d].cn=0;
while（（ht[d].key!
=key）&
&
（ht[d].key!
=0）&
（i<
hm））
i++;
ht[d].cn++;
d=（d+i）%m;
if（i>
=hm）
printf（"
哈希表已满"
return（unsucess）;
return（d）;
/*插入函数查找不成功就将key插入哈希表*/
inthashinsert（hashtableht[],keytypekey）
intd;
d=hashsearch（ht,key）;
if（ht[d].key==0）
ht[d].key=key;
return（sucess）;
else
unsuccess!
return（unsucess）;
/*建立哈希表函数*/
voidhashcreate（hashtableht[]）
inti,n;
keytypekey1;
请输入元素个数要小于表长%d:
hm）;
scanf（"
n）;
请输入元素关键字：
for（i=0;
i<
n;
i++）
key1）;
hashinsert（ht,key1）;
5.4运行结果
六致谢
从接受课题到现在完成课程设计报告,衷心的感谢我们的指导余云老师给予了精心的指导和热情的帮助,从老师那里学到了很多知识，尤其在课题设计的前期准备阶段和我们在编写程序中遇到的问题,余老师给予了纠正和提出了许多宝贵的设计意见,使我们对整个课程设计的流程比较清楚做起来也方便多了，老师在百忙之中抽出时间为我们提供了很多很及时的帮助,这样使得我得以顺利的完成本次课程设计,老师渊博的知识,敏锐的思路和实事求是的工作作风给我们留下了深刻的印象,这将使我终身受益,谨此向老师表示衷心的感谢和崇高的敬意，同时还感谢那些在各个方面给过我帮助的人，谢谢大家！
#include<
stdio.h>
malloc.h>
#definekeytypeint
#definemaxsize100
#definehm20
#definem19
#definefree0
#definesucess1
#defineunsucess0
voidmain（）
stablea;
bnode*t,*s;
hashtableht[hm];
inti=0,k,n;
intflag=1;
t=NULL;
while（flag）
请输入查找方式:
\n"
**1——顺序查找**\n"
**2——折半查找**\n"
**3——在二叉排序树中查找**\n"
**4——哈希查找**\n"
**5——退出**\n"
switch（n）
case1:
a=create_s（a）;
while（i!
=-1）
{
printf（"
\n输入待查关键字：
scanf（"
k=search_s（i,&
a）;
if（i==-1）break;
if（k==0）
{
printf（"
顺序表中待查元素不存在\n"
}
else
顺序表中待查元素位置是：
k）;
}break;
case2:
a=create_s（a）;
k=search_bin（i,&
case3:
请输入二叉排序树中元素以0结束\n"
scanf（"
key）;
while（key!
=0）
s=createbst（key）;
t=bstinsert（t,s）;
scanf（"
建立二叉排序树是：
bstprint（t）;
\n请输入待查元素：
search（t,key）;
\n\n"
break;
case4:
for（i=0;
hm;
ht[i].key=0;
建立哈希表：
hashcreate（ht）;
\n输入待查关键字（-1时结束）：
if（key==-1）break;
i=hashsearch（ht,key）;
if（ht[i].key==key）
哈希表中存在此元素位置是：
%d\n"
i）;
else
哈希表中不存在此元素\n"
}
}
case5:
flag=0;
break;
default:
输入错误请选择正确操作！
八参考文献
[1]严蔚敏，吴伟民编著，数据结构（C语言版）。
北京：
清华大学出版社，1997
[2]刘光然主编，数据结构实践训练教程。
天京：
南开大学出版社，2009.4
[3]李建学，李光元，吴春芳编著，数据结构课程设计案例精编——用C/C++描述。
清华大学出版社，2007
[4]严蔚敏，陈文博，数据结构。
机械工业出版社，1990
[5]唐策善，黄刘生，数据结构。
中国科技大学出版社，1992
[6]张国锋，C++语言及其程序设计教程。
电子工业出版社，1992
升级会员 