数据结构各种查找的课程设计报告.docx
《数据结构各种查找的课程设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构各种查找的课程设计报告.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构各种查找的课程设计报告
课程设计（论文）任务书
软件学院 学 院 专 业 班
一、课程设计（论文）题目各种查找算法演示
二、课程设计（论文）工作自2009年12月28日起至2010年1月2日止。
三、课程设计（论文）地点:
多媒体实验室（5-302,303）
四、课程设计（论文）内容要求：
1．本课程设计的目的
（1）熟练掌握C语言的基本知识和技能；
（2）掌握各种查找（顺序、二分法、二叉排序树、哈希）方法及适用场合，并能在解决实际问题时灵活应用。
（3）巩固在散列查找时解决冲突的方法及特点；
（5）培养分析、解决问题的能力；提高学生的科技论文写作能力。
2．课程设计的任务及要求
1）基本要求：
（1）设计一个的菜单将在实现的功能显示出来，并有选择提示；
（2）分别实现顺序、二分法、二叉排序树、哈希表的查找
（3）哈希表可选取其中任一种方法实现；
（4）二叉排序树必须实现构建、查找、插入、删除四个基本操作
（5）输出各种排序的结果并进行比较。
2）创新要求：
提高算法效率，降低时间复杂度和空间复杂度
3）课程设计论文编写要求
（1）要按照课程设计模板的规格书写课程设计论文
（2）论文包括目录、正文、心得体会、参考文献等
（3）课程设计论文用B5纸统一打印，装订按学校的统一要求完成
4）答辩与评分标准：
（1）完成原理分析：
20分；
（2）完成设计过程：
40分；
（3）完成调试：
20分；
（4）回答问题：
20分。
5）参考文献：
（1）严蔚敏，吴伟民.数据结构.北京：
清华大学出版社，2006.
（2）严蔚敏、吴伟民、米宁.数据结构题集。
北京：
清华大学出版社，2006.
（3）谭浩强.C程序设计（第二版）作者：
清华大学出版社，2006.
6）课程设计进度安排
内容天数 地点
构思及收集资料2 图书馆
编程设计与调试5 实验室
撰写论文3 图书馆、实验室
学生签名：
2009年12月28日
课程设计（论文）评审意见
（1）完成原理分析（20分）：
优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（2）设计分析 （20分）：
优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（3）完成调试 （20分）：
优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（4）翻译能力 （20分）：
优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（5）回答问题 （20分）：
优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（6）格式规范性及考勤是否降等级：
是（ ）、否（ ）
评阅人：
职称：
讲师
2010年1月3日
目 录
一、问题描述4
二、内容简介5
2.1基本要求：
5
2.2.算法思想：
5
2.3.模块划分：
6
2.4.数据结构：
6
2.5.源程序：
7
2.6.测试情况：
11
三、小结14
四、参考文献15
一、问题描述
（1）设计一个的菜单将在实现的功能显示出来，并有选择提示；
（2）分别实现顺序、二分法、二叉排序树、哈希表的查找
（3）哈希表可选取其中任一种方法实现；
（4）二叉排序树必须实现构建、查找、插入、删除四个基本操作
输出各种排序的结果并进行比较。
二、
内容简介
2.1基本要求：
设计程序分别可以实现顺序查找、二分查找、二叉排序树查找和哈希表查找。
其中，哈希表查找只需要选择其中的一种，二叉排序树必须实现构建、查找、插入和删除四个基本操作。
能输出各种排序的结果并进行比较。
在运行结果中，可以选择各种查找方法，并且输入数据后能完成查找并输出结果。
2.2.算法思想：
利用主程序调用四个查找的子程序的绝对路径。
1主程序设计方法
用abcd代表四种子程序的查找调用。
例如假如用户输入a即代表用户希望通过顺序查找来找到结果。
程序段为：
case'a':
printf（"顺序查找：
\n"）;
system（"\"E:
\\sh\\tui\\Debug\\tui.exe\""）;break;
2子程序设计方法
（1）顺序查找
设置0号单元为哨兵从数组末尾逐次向前查找，返回数组下标。
当下标为0时说明查找失败，反之查找成功。
（2）折半查找
把low指针和high指针分别指向数组的上界和下界，Mid指针指向数组的中间位置。
把mid指针与所要查找的关键字比较，如果相等返回数组下标；当关键字大于mid指向的数据时，把mid+1赋值给low；小于时，把mid-1赋给high。
如此循环，当low=high时，循环停止，返回mid值；当返回值为0时，查找失败，否则成功。
（3）二叉树查找
二叉树查找的数据键入方式有两种：
手动查找，自动查找。
根据要查找的数据与“根结点”大小的比较来查找。
若数据小于根结点值则从左子树切入查找，若大于根结点则从右子树切入查找，假如等于根结点即表明查找到返回根结点的地址值。
若查找完毕没有找到该数据即返回空值。
（4）哈希表
用除留余数法创建哈希函数，当遇到冲突时用开放定址法的线性探测解决冲突问题。
把字符定义在数组中，再给定k值。
根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等则查找成功。
2.3.模块划分：
voidmain（）：
主函数，用来调用四个查找的子函数
system（"\"E:
\\sh\\tui\\Debug\\tui.exe\""）：
E盘中实现顺序查找的程序
system（"\"E:
\\sh\\zheban\\Debug\\zheban.exe\""）：
E盘中实现二分查找的程序
system（"\"E:
\\sh\\ert\\Debug\\ert.exe\""）：
E盘中实现二叉排序树查找的程序
system（"\"E:
\\sh\\gf\\Debug\\gf.exe\""）：
E盘中实现哈希查找的程序
voidInsert（BSTree*tree,ElemTypeitem）：
二叉排序树查找
voidCreateHashList（）：
哈希表查找
2.4.数据结构：
1.顺序查找----顺序存储结构
typedefintKeyType;
typedefstruct{
KeyType*elem;//数据元素存储空间基址，建表时按实际长度分配，0号单元留空
intlength;//表长度
}SSTable;//顺序表的存储结构
2.折半查找---顺序存储结构
typedefstruct
{intkey;
}RedType;//定义结构体RedType
typedefRedTypeElemType;//RedType型变量
typedefstruct
{ElemTypeelem[100];//表的空间大小
intlength;//表长度
}SSTable;
3.二叉树查找---链式存储结构
typedefintElemType;
typedefstructBSTNode//定义存储结构
{ElemTypedata;
structBSTNode*lchild,*rchild;
}BSTNode,*BSTree;
4.哈希表---链式存储结构
typedefstructNAME
{
char*py;//名字的拼音
intk;//拼音所对应的整数
}NAME;
NAMENameList[NAME_NO];
typedefstructhterm//哈希表
{
char*py;//名字的拼音
intk;//拼音所对应的整数
intsi;//查找长度
}HASH;
2.5.源程序：
#include
#include
#include
voidmain（）
{charm=0;
printf（"请选择查找方式：
a-顺序查找,b-二分查找,c-二叉排序树查找，d-哈希表查找：
"）;
scanf（"%c",&m）;
switch（m）
{case'a':
printf（"顺序查找：
\n"）;
system（"\"E:
\\sh\\tui\\Debug\\tui.exe\""）;break;
case'b':
printf（"二分查找：
\n"）;
system（"\"E:
\\sh\\zheban\\Debug\\zheban.exe\""）;break;
case'c':
printf（"二叉排序树查找：
\n"）;
system（"\"E:
\\sh\\ert\\Debug\\ert.exe\""）;break;
case'd':
printf（"哈希表查找：
\n"）;
system（"\"E:
\\sh\\gf\\Debug\\gf.exe\""）;break;
}
}//主函数
/*typedefstruct{//顺序查找
KeyType*elem;//数据元素存储空间基址，建表时按实际长度分配，0号单元留空
intlength;//表长度
}SSTable;//顺序表的存储结构
intSearch_Seq（SSTableST,KeyTypekey）{
inti;
ST.elem[0]=key;//“哨兵”，如果顺序表中不存在要查找的数据的话，则查找指针必
//定指向该哨兵
for（i=ST.length;ST.elem[i]!
=key;i--）
returni;//找到的话，则i!
=0,否则i=0}
voidmain（）
{inti,key;
SSTableT;
T.elem=（KeyType*）malloc（sizeof（KeyType））;
printf（"HowManyEntriesDoYouWantinput\n"）;//输入顺序表长度
scanf（"%d",&T.length）;
for（i=1;i<=T.length;i++）{
printf（"Pleaseinputthe%dthentries\n",i）;//一个一个的输入元素
scanf（"%d",&T.elem[i]）;
}for（i=1;i<=T.length;i++）
printf（"%5d",T.elem[i]）;//显示已经输入的所有数据
printf（"\nPleaseinputthedatayouwanttosearch\n"）;
scanf（"%d",&key）;}
typedefstruct{//折半查找
intkey;
}RedType;//定义一个包含关键字的结构体
typedefRedTypeElemType;
typedefstruct
{ElemTypeelem[100];//redtype结构体类型的数组
intlength;//表的长度
}SSTable;//定义一个
intSearch_Bin（SSTableST,intkey）{
//在有序表ST中折半查找其关键字等于key的数据元素。
//若找到，则函数值为该元素在表中的位置，否则为0。
intlow,high,mid;
low=1;high=ST.length;//置区间初值
while（low<=high）{
mid=（low+high）/2;
if（key==ST.elem[mid].key）returnmid;//找到待查元素
elseif（key//继续在前半区间进行查找
elselow=mid+1;//继续在后半区间进行查找
}return0;//顺序表中不存在待查元素
}//Search_Bin
voidmain（）
{SSTableT;
intkey,i=1;
intpostion;
intn=1;//记录输入的关键字个数
printf（"如果不想输入,则输入0，当此数的位置为0时，查找不到该数。
\n"）;
printf（"请输入第%d个数:
\n",n）;
scanf（"%d",&key）;
while（key!
=0）
{n++;
T.elem[i++].key=key;
printf（"请输入第%d个数,大于%d\n",n,T.elem[i-1].key）;
scanf（"%d",&key）;
T.length=i;
}printf（"请输入要查的数:
\n"）;
scanf（"%d",&key）;
postion=Search_Bin（T,key）;
printf（"此数的位置是：
%d\n",postion）;}
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（itemdata）
{if（NULL==cursor->lchild）
{cursor->lchild=node;
Break；}
cursor=cursor->lchild；}
else{
if（NULL==cursor->rchild）
{cursor->rchild=node;break;}
cursor=cursor->rchild;}
}
return;}
BSTreeSearch（BSTreetree,ElemTypeitem）
{BSTreecursor=tree;
while（cursor）{
if（item==cursor->data）returncursor;
elseif（itemdata）
cursor=cursor->lchild;
elsecursor=cursor->rchild;
}returnNULL;}
voidCreateHashList（）{//哈希表查找
inti;
for（i=0;i<=50;i++）{
HashList[i].py="";
HashList[i].k=0;
HashList[i].si=0;
}
for（i=0;i<=30;i++）
{intsum=0;
intadr=（NameList[i].k）%M;//哈希函数
intd=adr;
if（HashList[adr].si==0）//如果不冲突
{HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;}
else//冲突
{do{
d=（d+（（NameList[i].k））%10+1）%M;//伪散列
sum=sum+1;//查找次数加1
}while（HashList[d].k!
=0）;
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;*/
2.6.测试情况：
主界面
顺序查找界面
折半查找界面
二叉树查找界面
哈希表查找界面
三、小结
本次课程设计遇到的主要困难是四个查找算法的编写与运行。
有时程序虽写出来了，但运行时出现错误，经过改正后能运行了但结果不正确或没有运行结果。
因此，借助网络，查了很多相关的资料及文献。
它们给我的帮助和启发很大。
如：
不知道如何生成一个自动表，经过查资料，知道了可以在time.h函数中调用。
另一个难题是设计菜单程序，由于菜单程序的运行需要Graphics.h库函数，但此函数在VC6.0中打不开。
所以我就用了调用的方法即：
先写一个主程序，在其中通过绝对路径调用其他子程序，这样就解决了问题。
不足：
这次的设计中还有一些不足之处。
例如,主程序不能实现循环。
虽然采纳了同学的建议采用while语句，但这个语句基本上不起作用。
另外，在哈希表中只有固定的表，没有自动生成的表。
虽然尝试着写了，但老是出错，所以也就没有用。
体会：
1.首先对程序设计的步骤有了更深刻的了解。
2.对顺序查找，折半查找，二叉排序树及哈希表中的查找方法了解的更清楚了。
3.最大的收获是知道如何在C中实现子程序的调用。
4.体会到了集中精力去完成一份任务时所收获的成就感。
四、参考文献
[1]严蔚敏，吴伟民.数据结构.北京：
清华大学出版社，2006.
[2]严蔚敏、吴伟民、米宁.数据结构题集。
北京：
清华大学出版社，2006
[3]谭浩强.C程序设计（第二版）作者：
清华大学出版社，2006
升级会员 