第一篇：数据结构课程设计：动态查找表
编号： 139
数据结构与算法课程设计
说明书
动态查找表
学
院：
海洋信息工程学院
专
业：
计算机科学与技术
学生姓名：
学
号：
指导教师：
2015年月 26 日
动态查找表
学生姓名：银杰
指导老师：王晓莹
摘 要
本课程设计说明书系统地阐述了我使用C语言在Code::Blocks软件编写的动态查找表程序的整个过程，编写的环境是win7 64位操作系统。根据题目要求，编写动态查找表使用二叉排序树，即二叉链表作为存储结构。该程序具有建立数据功能、具有数据查找功能、具有数据插入功能、具有数据删除功能等基本功能操作。
关键词：动态查找表，Code::Blocks软件，win7 64位操作系统，C#
dynamic lookup table
Author :yinjie
Tutor :Wangxiaoying
Abstract
This course design specification system to explain the whole process of using C language in Code:: Blocks software written in the dynamic look-up table program, the preparation of the environment is win7 64 bit operating system.According to the topic request, the preparation of the dynamic look-up table using the two fork sort tree, that is, the two binary list as the storage structure.The program has the function of building data, data searching, data insertion, data deletion and so on.Key words:dynamic lookup table, Code::Blocks software,win7 64 bit operating system，C #
目 录
引言.........................................................................................................................................................................1 查找的基本概念.................................................................................................................................................1 小结.....................................................................................................................................................................1 题目.....................................................................................................................................................................1 第1章 程序的构图设计.....................................................................................................................................2 1.1动态查询表：...............................................................................................................................................2 1.2程序功能流程图：.......................................................................................................................................2(1)、主函数模块............................................................................................................................................2(2)、二叉排序树的生成................................................................................................................................3(3)、二叉排序树的查找模块........................................................................................................................4(4)、二叉排序树的插入模块........................................................................................................................4(5)、二叉排序树删除连接模块....................................................................................................................5(6)、二叉排序树的删除模块........................................................................................................................5(7)、二叉排序树的遍历模块........................................................................................................................6 第2章 详细设计的程序.....................................................................................................................................6 各函数模块.........................................................................................................................................................6(1)主函数模块................................................................................................................................................6(2)二叉排序树的生成模块............................................................................................................................8(3)二叉排序树的查找模块............................................................................................................................8(4)二叉排序树的插入模块............................................................................................................................9(5)多态查找表删除模块..............................................................................................................................10(6)二叉排序树的中序遍历模块..................................................................................................................12 第3章 程序测试和运行.....................................................................................................................................12 3.1 程序测试....................................................................................................................................................12 3.2 程序运行....................................................................................................................................................13
1、主界面
...................................................................................................................................................13
2、建立二叉排序树模块界面.....................................................................................................................13
3、二叉排序树查找模块界面.....................................................................................................................14
4、二叉排序树插入模块界面.....................................................................................................................14
5、二叉排序树删除模块界面
...................................................................................................................14
6、退出程序的界面.....................................................................................................................................14 总 结.....................................................................................................................................................................15 程序完成情况...................................................................................................................................................15 有待改进之处...................................................................................................................................................15 课程设计期间的收获.......................................................................................................................................15 附录源代码如下...................................................................................................................................................17
桂林电子科技大学课程设计说明书
引言
查找的基本概念
查找又称为检索，就是从一个数据元素集合中找出某个特定的数据元素。查找是数据处理中最为常用的一种操作，查找算法的优劣对整个软件系统的效率影响很大，尤其当所涉及的数据量较大时，更是如此。在一个数据集合中进行查找操作可选用的方法与该数据元素集合的存储结构有很大关系。
查找是根据某个给定的值，在数据元素构成的集合中确定是否在这样一个数据元素，它的关键字等于给定值的关键字。
要进行查找，必须明确要查找对象的特征，也就是要查找元素的关键值。如果在数据集合中能找到与给定值相等的关键字，则该关键字所属的数据元素就是所要查找的数据元素，此时称该查找成功；如果查遍了整个数据元素集合也未能找到与给定值相等的关键字，则称该查找失败。小结
当然对于这个说明书，我不可能做得至善至美，但是一些基本的格式内容还是符合要求的。首先，我对查找表进行一个简要的概述。然后，我就查找表进行了详细的分析，这是设计中很重要的一步。接下来，我把查找表中所有的设计简明清晰地展现出来，并把我在设计中遇到的问题和分析解决问题的办法做了分析。最后，在结论中，我对自己的课程设计做了总体的评价同时简述了我在这次课程设计中的收获和经验。
题目
选题十二：动态查找表
【问题描述】
利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。【任务要求】
算法输入：指定一组数据。
桂林电子科技大学课程设计说明书
算法输出：显示二叉排序树的中序遍历结果、查找成功与否的信息、插入和删除后的中序遍历结果(排序结果)。
算法要点：二叉排序树建立方法、动态查找方法,对树进行中序遍历。【测试数据】
自行设定，注意边界等特殊情况。
第1章 程序的构图设计
1.1动态查询表：
依照输入的一组数据{56,80,65,20}所得的二叉排序树如下（a）所示：当插入11的时候就如（b）所示。
562065801
156206580
（a）
（b）1.2程序功能流程图：
(1)、主函数模块
桂林电子科技大学课程设计说明书
开始打印输出动态表的6个功能选择栏do循环输入选择号hSwitch(h)执行对应函数模块程序退出结束
(2)、二叉排序树的生成
开始输入数据个数Xfor循环输入X个数据调用插入函数Insert二叉树建成结束
桂林电子科技大学课程设计说明书
(3)、二叉排序树的查找模块
开始二叉排序树是否为空否根结点关键字？key是大于递归返回在左子树查找递归返回等于小于在右子树查找查找失败查找成功结束
(4)、二叉排序树的插入模块
开始调用查询函数Search()是否查询成功否被插入结点*s为新的根结点是插入的节点根结点<被插结点*s为左孩子插入成功结束
>被插结点*s为右孩子
桂林电子科技大学课程设计说明书
(5)、二叉排序树删除连接模块
开始左右子树是否为空是While循环否向右走到尽头重接它的左右子树将被删结点的前驱s的内容直接替代该结点的内容被删除结点的左子树的右子树是否为空否重接*q的右子树是重接*q的左子树连接成功结束(6)、二叉排序树的删除模块
开始输入要删除的的数据是否存在关键字等于n的数据元素否调用删除的连接函数Delete()结束返回是找到关键字并删除
桂林电子科技大学课程设计说明书
(7)、二叉排序树的遍历模块
开始二叉树根是否为空否对左子树按中序遍历进行访问根结点对右子树按中序遍历进行遍历完成结束是递归调用
第2章 详细设计的程序
各函数模块
(1)主函数模块：
用主函数main()来实现。主要是通过设计一个do()函数并让主函数调用它来显示主菜单，让用户选择操作。在do()函数中，我应用了switch-case语句来进行选择，是个比较简单实现的模块。最后若选择“5”退出循环。否则继续循环。主要代码如下：
int main(){
bitree T=NULL,p;ElemType e;int n;int h;char c;
do{
printf(“********************************************************n”);
桂林电子科技大学课程设计说明书
printf(“*
*n”);
printf(“*
动态查找表
*n”);
printf(“*
1.建立二叉排序树
*n”);
printf(“*
2.二叉排序树查找元素
*n”);
printf(“*
3.二叉排序树插入元素
*n”);
printf(“*
4.二叉排序树删除元素
*n”);
printf(“*
5.退出
*n”);
printf(“*
*n”);
printf(“********************************************************n”);
printf(“请输入你的选择: n”);
scanf(“%d”,&h);
switch(h)
{
case 1:Init(T);printf(“中序遍历二叉排序树: ”);Zhongxu(T);printf(“n”);
break;
case 2:printf(“请输入要查找的数据:n”);scanf(“%d”,&n);e.key=n;
if(Search(T,e,NULL,p))
printf(“数据已经存在!n”);
else
{ printf(“数据不存在!n”);}
break;
case 3:printf(“请输入要插入的数据:n”);scanf(“%d”,&n);e.key=n;
if(Search(T,e,NULL,p))
printf(“已经存在!n”);
else{Insert(T, e);printf(“成功插入!n”);printf(“中序遍历二叉排序树: ”);Zhongxu(T);printf(“n”);}
break;
case 4:printf(“请输入要删除的数据:n”);scanf(“%d”,&n);e.key=n;
if(Search(T,e,NULL,p))
{ Deletebit(T,n);printf(“已经成功删除!n”);printf(“中序遍历二叉排序
桂林电子科技大学课程设计说明书
树: ”);Zhongxu(T);printf(“n”);}
else printf(“数据不存在!n”);
break;
case 5:printf(“退出！n”);
break;
default:printf(“选择错误，重新开始!n”);
}
} while(h!=5);}(2)二叉排序树的生成模块：
二叉排序树的生成，是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插到当前已经生成的二叉排序树中。主要代码如下：
void Init(bitree &T)//构造一个动态查找表T {
int x;int i;int n;
ElemType e;printf(“请输入结点个数: ”);scanf(“%d”,&x);
for(i=1;i<=x;i++)
{
printf(“第%d个结点数据值:”,i);scanf(“%d”,&n);
e.key=n;Insert(T,e);
}
printf(“二叉排序树已经建立!n”);}
(3)二叉排序树的查找模块： 二叉排序树的查找方法如下。当二叉排序树为空时，查找失败。
当二叉排序树根结点的关键字等于key时，查找成功。
桂林电子科技大学课程设计说明书
当二叉排序树根结点的关键字大于key时，从根结点的左子树中以同样方法进行查找。当二叉树根结点的关键字小于key时，从根结点的右子树以同样方法进行查找。显然，该过程是一个递归过程，下面给出这一算法的实现。
主要代码：
bitree Search(bitree T,ElemType e,bitree f,bitree &p)//在二叉排序树中查找数据 {
if(!T)
{
p=f;
return NULL;
}//查找不成功
else if(T->data.key==e.key)
{
p=T;return T;
} //查找成功
else if(T->data.key>e.key)
return Search(T->lchild,e,T,p);
else return Search(T->rchild,e,T,p);}//在二叉排序树中查找数据(4)二叉排序树的插入模块：
若要将一个关键字值为key的结点t插到二叉排序树中，只需要使该结点插入后，二叉排序树中的元素依然按照原来的规律排列即可。二叉排序树的插入方法如下。
若二叉排序树是空树，则key称为二叉排序树的根。
若二叉排序树为非空，则将key与二叉排序树的根结点进行比较：如果key的值等于根结点的值，则停止插入；如果key的值小于根结点的值，则将key插到左子树；如果key的值大于根结点的值，则将key插到右子树中。主要代码如下：
void Insert(bitree &T,ElemType e)//在二叉排序树中插入数据
桂林电子科技大学课程设计说明书
{
bitree p,s;
if(!Search(T,e,NULL,p))//查找不成功
{
s=(bitree)malloc(sizeof(bitnode));
s->data=e;s->lchild=s->rchild=NULL;
if(!p)T=s;//被插入结点*s为新的根结点
else if(e.key
data.key)
p->lchild=s;//被插结点*s为左孩子
else
p->rchild=s;//被插结点*s为右孩子
} }(5)多态查找表删除模块：
从二叉排序树中删除一个结点，不能简单地把以该结点为根的子树都删除，只能删除掉该结点，并且还应该保证删除后所得到的二叉树依然满足二叉树的性质不变。也就是说，在二叉排序树中删除一个结点相当于删除有序序列中的一个结点。
假设要删除的结点为P，其双亲结点为F，同时假设结点P是结点F的左孩子（右孩子的情况类似）。删除操作首先要确定被删结点P是否在二叉排序树中。若不在，则不做任何操作；若在，分为以下三种情况讨论。若P为叶子结点，可直接将其删除。
若结点P只有左子树，或只有右子树，则可将P的左子树或右子树直接改为其双亲结点F的左子树或右子树。
若P既有左子树，又有右子树此时有两种处理方法。
方法1：首先找到结点P在中序序列中的直接前驱结点S，然后用结点P的左子树改为F的左子树，而将P的右子树改为S的右子树。
方法2：首先找到结点P在中序序列中的直接前驱结点s，然后用结点s的值替代结点p的值，再将结点s删除，原结点s的左子树改为s的双亲结点q的右子树。主要代码如下：
桂林电子科技大学课程设计说明书
void Delete(bitree &p)//从二叉排序树中删除结点p，并重接它的左或右子树 {
bitree q,s;
if(!p->rchild)//右子树空，只需重接它的左子树
{
q=p;p=p->lchild;free(q);q=NULL;
}
else if(!p->lchild)//左子树空，只需重接它的右子树
{
q=p;p=p->rchild;free(q);q=NULL;
}
else{//左右子树均不空
q=p;s=p->lchild;
while(s->rchild)//向右走到尽头
{
q=s;s=s->rchild;
}
p->data=s->data;//将被删结点的前驱s的内容直接替代该结点的内容
if(q!=p)//若被删除结点的左子树的右子树不为空
q->rchild=s->lchild;//重接*q的右子树
else
q->lchild=s->lchild;//重接*q的左子树
free(s);s=NULL;
} }//删除结点
void Deletebit(bitree &T,int n)//删除二叉排序树中的数据 {
if(!T)return;//不存在关键字等于n的数据元素
桂林电子科技大学课程设计说明书
else{
if(T->data.key==n)return(Delete(T));//找到关键字等于n的数据元素并删除它
else if(T->data.key>n)Deletebit(T->lchild,n);//继续在左子树中删除
else Deletebit(T->rchild,n);//继续在右子树中删除
} }
(6)二叉排序树的中序遍历模块：
中序遍历二叉树定义：若二叉树根为空，则返回；否则，中序遍历左子树；访问根结点；中序遍历右子树。主要代码如下：
void Zhongxu(bitree T)//中序遍历 {
if(T!=NULL)
{
Zhongxu(T->lchild);
printf(“%d ”,T->data.key);
Zhongxu(T->rchild);
} }
第3章 程序测试和运行
3.1 程序测试
程序测试是程序质量保证的主要活动之一，在程序编写的过程中，在各个阶段都有可能存在错误和缺陷。通过测试是可以发现程序设计中存在的种种问题，并可以及时改正。避免在程序运行时才出现不必要的错误。测试是质量保证一个临界和决定惩罚，它提供对程序说明、设计和编码的最终评审。是发现程序缺陷和错误的有力手段。根据系统设计目标和功能，对系统进行测试。
桂林电子科技大学课程设计说明书
1、功能性
（1）程序实现的主要功能，包括查询，插入，删除等。
（2）题目要求的输入输出字段，以及题目要求的输入限制。
2、可靠性
程序正确实现了对动态查找表的查询、插入、删除等各种功能。
3、易用性
现有程序实现了如下易用性：
（1）查询，插入，删除，操作相关提示信息的一致性，可理解性
（2）输入限制的正确性
（3）输入限制提示信息的正确性，可理解性，一致性
（4）界面排版简洁完整 3.2 程序运行
1、主界面 ：
2、建立二叉排序树模块界面 ：
桂林电子科技大学课程设计说明书
3、二叉排序树查找模块界面 ：
4、二叉排序树插入模块界面 ：
5、二叉排序树删除模块界面 ：
6、退出程序的界面 ：
桂林电子科技大学课程设计说明书
总 结
程序完成情况
在编写程序写课程设计的时间里，虽然历经重重困难和挫折，但是在我自己的努力和老师的帮助下终于完成了动态查找表的设计。尽管该程序在功能和性能上可能还有一些缺陷，但是我已经完成了课程设计的任务和目标，达到了题目基本要求，成功完成了算法与数据结构课程设计。有待改进之处
有待改进：
1、我在编写程序的时候，用的是C++格式去保存编译的，用了C语言来编写，但是有一些C++的形式，当我用C来新建保存的时候却出现问题。所以程序我是用C++来新建保存的。
2、流程图画的不是很规范表准，在一些逻辑表达上不够简洁清晰。课程设计期间的收获
在完成此次的课程设计的过程中，我跨越了传统方式下的教与学的体制束缚，桂林电子科技大学课程设计说明书
通过自己的思考和设计，培养了自学能力和动手能力。并且由原先的被动的接受知识转换为主动的寻求知识，这可以说是学习方法上的一个很大的突破。在以往的传统的学习模式下，我们可能会记住很多的书本知识，但是通过课程设计，我们学会了如何将学到的知识转化为自己的东西，学会了怎么更好的处理知识和实践相结合的问题。
通过这次课程设计，我认识到数据结构与算法是计算机科学的基础课程，是我们学习的核心课程。我对数据结构和算法又有了新的认识。数据结构的研究不仅涉及到计算机软件，而且和计算机硬件的研究也有着密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便使查找和存取数据元素更为方便。可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一个核心内容，是从事计算机科学研究及其应用的人必须掌握的重要内容。
这次的课程设计有效的培养了我们独立思考的能力，提高了我们的动手操作水平。在具体设计中，我们巩固了上学期所学的数据结构与算法的理论知识，进一步提高了自己的编程能力。这也是课程设计的目的所在。通过编程实践，不仅开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力，更充分锻炼了我们的编程能力。
在这次课程设计中我也知道了的编程能力不强，有很多程序与算法是借鉴别人的，我想只要我有自己写程序，并且结合他人的程序算法，把程序完成，那我还是学习到东西了的。
在课程设计中我体会到：一个好的程序应该是一个高内聚低耦合的程序。而要做出一个好的程序则应该通过对算法与其数据结构的时间复杂度和空间复杂度进行实现与改进。然而，实际上很难做到十全十美，原因是各要求有时相互制约，要节约算法的执行时间往往要以牺牲更多的存储空间为代价：而为了节省存储空间又可能要以更多的时间为代价。因此，只能根据具体情况有所侧重：如果程序的使用次数较少，则应该力求算法简单易懂；如果程序反复多次使用，则应该尽可能选用快速算法或者设置为内联函数；如果解决问题的数据量极大，但是机器的内存空间不是很充足，则在编写算法时应该考虑如何节省空间。
学习了《数据结构与算法》这门课，我们在编写程序时就应该注意到所编写程序的时间复杂度和空间复杂度，以及是否运用了良好的算法，而不是只是象以前编写程序时单纯使用C++的知识。我们要充分考虑程序的性能，从而编写出更好的程序。
桂林电子科技大学课程设计说明书
在设计报告的写作过程中我也学到了做任何事情都要有的心态，首先我明白了做学问要一丝不苟，对于出现的任何问题都不要轻视，要通过正确的途径去解决，在做事情的过程中要有耐心和毅力，不要一遇到困难就打退堂鼓，只要坚持下去就可以找到思路去解决问题的，在遇到问题时，有必要向老师和同学请教，合作沟通的意义是巨大的。
在这次课程设计中，我认识到了自己的不足之处同时我也收获了很多知识和经验，在今后的学习中，我一定勤于思考，并灵活运用所学知识，多进行编程实践。在总结反思和编程训练中，不断提升自己的编程能力。相信在我的努力下，我的程序设计水平一定会不断提高。
参考文献
[1]数据结构与算法/汪沁，奚李峰主编.-北京：清华大学出版社，2012.9（第8章 查找）
[2]百度文库>专业资料>IT/计算机>计算机软件及应用>动态查找表实验报告
http://wenku.baidu.com/link?url=crizbdK6WO86YXeSJWwkHNdXpaxUDkRJnoShcVDJqBfGO03Cbk6LAdVwBYHxE82kYHkuIjC1HFCiOrSiEWJXOOspWGIo3PNSDjbeY1jHbJu
附录源代码如下：
数据结构与算法的课程设计1.cpp
第二篇：数据结构课程设计-查找排序
查找及排序算法实现
一、实验目的
1、熟练掌握二叉排序树查找算法及C语言描述。
2、熟练掌握折半查找算法及C语言描述。
3、熟练掌握简单选择排序算法及C语言描述。
4、熟练掌握简单插入排序算法及C语言描述。
5、熟练掌握冒泡（起泡）排序算法及C语言描述。
6、了解各种查找及排序算法的优缺点、实用性及应用。
7、将理论与实际相结合，切实提高自己的逻辑能力和动手能力。
二、设计内容
1.折半查找算法
折半查找算法的思路：
初始状态：假设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值，初始时，令low=0,high=n-1,mid=(low+high)/2 让key与mid指向的记录比较
若key==r[mid].key，查找成功,算法结束；若key
起泡排序的思路：
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即L.r[1].key>L.r[2].key），则将两个记录交换之，然后比较【第二个记录和第三个记录】的关键字。以此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称做第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。一般地，第i躺起泡排序是从L.r[1]到L.r[n-i+1]以此比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程需进行k(1<=k 首先以一个元素为基准，从一个方向开始扫描，比如从左至右扫描，以a[0]为基准，接下来从a[0]...a[9] 中找出最小的元素，将其与a[0]交换，然后将基准位置右 移一位，重复上面的动作，比如，以a[1]为基准，找出a[1]至a[9]中最小的，将其与a[1]交换，一直进行到基准位置移到数组最后一个元素时排序结束（此时基准左边所有元素均递增有序，而基准为最后一个元素，故完成排序）。4.直接插入排序算法 直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的，记录数增1的有序表。 一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r[1...i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1....i].在自i-1起往前搜索的过程中，可以同时后移记录。 整个排序过程为进行n-1躺插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止 三、程序源代码 1.二叉排序树的创建、遍历和查找删除算法 #include void Insert(Tree &T,KeyType key){ if(!T){ T=new LNode;T->data=key;T->lchild=T->rchild=NULL;} else } { } if(key } int num;char c;while(scanf(“%d”,&num)){ } Insert(T,num);c=getchar();if(c=='n')return;void In_Order(Tree T)//中序遍历 { if(T){ In_Order(T->lchild);printf(“%d ”,T->data);} In_Order(T->rchild);} void Delete(Tree &p){ Tree q,s;if(!p->rchild){ q = p;p=p->lchild;free(q);} else if(!p->lchild){ } q = p;p=p->rchild;free(q); else { } q = p;s = p->lchild;while(s->rchild){ } q = s;s = s->rchild;p->data = s->data;if(q!=p)q->rchild = s->lchild;else q->lchild = s->lchild;free(s);} void DelNode(Tree &T,KeyType key){ } if(!T){ printf(“n该结点不存在n”);return;} else { } if(key == T->data)Delete(T);else if(key < T->data)DelNode(T->lchild, key);else DelNode(T->rchild,key);Tree Search(Tree T,KeyType key)//二叉排序树查找 { if(!T){ } printf(“该结点不存在”);return 0;else if(key == T->data)return T;else if(key < T->data) return(Search(T->lchild, key));else return(Search(T->rchild, key));} int main()//主函数 { Tree T,p;T=NULL;KeyType x; printf(“请输入二叉树各结点：n”); CreatTree(T); printf(“中序遍历为：n”);In_Order(T);printf(“n请输入要查找和删除的结点：n”);scanf(“%d”,&x);p=Search(T, x);if(p){ } DelNode(T, x);printf(“中序遍历为：n”);In_Order(T); } 2、冒泡排序和折半查找算法 #include int BubbleSort(int c[]){ int i,t,j;for(i=0;i<9;i++){ } for(j=0;j<9-i;j++){ } if(c[j]>c[j+1]){ } t=c[j];c[j]=c[j+1];c[j+1]=t; printf(“n您所输入的数字的升序排列是:nn”);for(i=0;i<10;i++){ printf(“%d”,c[i]);printf(“ ”);} return 1;} //折半查找 int BinarySearch(int b[]){ } int t,mid;int i=0;int j=9;printf(“nn请输入您要查找的数字：”);scanf(“%d”, &t);while(i<=j){ mid=i+(j-i)/2; } return 1;if(t==b[mid]){ printf(“n您要查找的数字的排列位置是：%dn”,mid+1);break;} else if(t int main(int argc,char *argv[]){ int a[10];printf(“请您输入数据:nn”);for(int i=0;i<10;i++){ scanf(“%d”,&a[i]); } } BubbleSort(a);BinarySearch(a);return 0; 3、简单选择排序和简单插入排序算法 #include int i,j,min,p,key,k; for(i=0;i { key=0; min=a[i]; } for(j=i;j if(a[j] if(key==1){a[p]=a[i]; a[i]=min;} for(k=0;k printf(“%d ”,a[k]);printf(“n”); return 1;} int InserSort(int*a,int n){ int i,j,k;for(i=2;i<=n;i++){ a[0]=a[i];for(j=1;j { if(a[j]>a[i]){for(k=i;k>j;k--) a[k]=a[k-1]; a[k]=a[0]; } } break;} } for(j=1;j<=n;j++){ } printf(“%d ”,a[j]);printf(“n”);return 1;int main(){ int a[80],i,n,b;printf(“请输入关键字的个数：”);scanf(“%d”,&n);printf(“排序类型：n”);printf(“1.选择排序n”);printf(“2.插入排序n”);printf(“请选择：”);scanf(“%d”,&b);switch(b){ case 1: printf(“请输入关键字：n”);for(i=0;i SelectionSort(a,n); return 1; break; case 2: printf(“请输入关键字：n”); for(i=1;i<=n;i++){ scanf(“%d”,&a[i]);} printf(“插入排序的流程以及结果：n”); InserSort(a,n);return 1; } break;}while(a!=0); 四、实验运行结果 1.二叉排序树的创建、遍历和查找删除算法 2、冒泡排序和折半查找算法 3、简单选择排序和简单插入排序算法 七、心得体会 通过本次的数据结构课程设计报告，掌握了查找和排序的几种基本排序算法，了解了他们各自的特点和优缺点，完成了对于他们C语言的描述和实际应用，对他们有了一个更加具体、深刻的认识，同时也锻炼了我们的逻辑思维能力和动手实践能力，使我们受益匪浅，给我们今后的计算机专业课程学习带来很大的帮助。 武汉理工大学《数据结构》课程设计说明书 课程设计任务书 学生姓名： 刘颖 专业班级： 计科1003班 指导教师： 谭新明 工作单位： 计算机科学系 题 目: 哈希表的设计与实现 初始条件： 针对某个集体（比如你所在的班级）中的“人名”设计并实现一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 （1）假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。 （2）哈希函数用除留余数法构造 （3）用伪随机探测再散列法处理冲突。 （4）测试用例见严蔚敏《数据结构习题集(C语言版)》p166。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1.问题描述 简述题目要解决的问题是什么。2.设计 存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计； 3.调试报告 调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4.经验和体会（包括对算法改进的设想） 5.附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。 说明： 1.设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。2.凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。 时间安排： 1、6月15日～6月21日完成。2、6月22日上午和下午在实验中心检查程序、交课程设计报告、源程序（U盘）。 指导教师签名： 2012年6月14日 系主任（或责任教师）签名： 年 月 日 武汉理工大学《数据结构》课程设计说明书 目录 1问题分析和任务定义...............................................3 1.1问题描述.......................................................3 1.2问题分析.......................................................3 2开发平台.........................................................3 3数据类型和系统设计...............................................3 3.1存储结构设计...................................................3 3.2主要算法设计...................................................4 3.2.1姓名结构体数组初始化.........................................4 3.2.2获取关键码...................................................5 3.2.3哈希表结构体数组初始化.......................................5 3.2.4构造哈希表...................................................5 3.2.5打印哈希表...................................................6 3.2.6在哈希表中查找姓名...........................................6 4调试结果与运行情况分析...........................................8 4.1程序运行结果...................................................8 4.2运行情况分析...................................................9 4.3算法的时间复杂度...............................................9 5自我评价与总结...................................................9 6参考文献........................................................10 7附：源代码......................................................11 武汉理工大学《数据结构》课程设计说明书 哈希表的设计与实现 1问题分析和任务定义 1.1问题描述 设计哈希表，要求用除留余数法构造哈希函数，用伪随机探测再散列法处理冲突，使平均查找长度的上限为2。待填入哈希表的人名共有30个，且为中国人姓名的汉语拼音形式。 1.2问题分析 （1）待填入哈希表的人名有30个，平均查找长度的上限为2。用除留余数法构造哈希表，用伪随机探测再散列法处理冲突，完成相应的建立和查表程序。 （2）人名为汉语拼音形式，最长不超过20个字符。 （3）查找成功时，显示姓名、关键字、初散列值、再散列值、哈希表中的位置及查找长度；查找失败时，显示无此记录。 （4）可多次查找，继续查找输入1，退退出输入0。 2开发平台 系统：Windows 7 开发工具：Visual studio 2008 语言：C++ 3数据类型和系统设计 3.1 存储结构设计 typedef struct { int key; char *p;}NAME; 武汉理工大学《数据结构》课程设计说明书 typedef struct { int key;//关键字 int hash;//初始地址 int reha;//再散列值 char *p;//名字 int l;//查找长度 }HASH;3.2主要算法设计 3.2.1 NAME（结构体数组）初始化 NAME a[30];a[0].p=“wangjunzhe”;a[1].p=“mahaiping”;a[2].p=“luozijian”;a[3].p=“luoxiangzhou”;a[4].p=“zhangkai”;a[5].p=“fengyuyang”;a[6].p=“wuzhenzhen”;a[7].p=“haokaiqi”;a[8].p=“caopu”;a[9].p=“liuying”;a[10].p=“cuijuan”;a[11].p=“hanqianqiqn”;a[12].p=“lixiaoyu”;a[13].p=“caoyingnan”;a[14].p=“jinbaoyu”;a[15].p=“zhaduo”;a[16].p=“wenbo”;a[17].p=“cuichangwei”;a[18].p=“zhangqiu”;a[19].p=“luopeng”;a[20].p=“hudie”;a[21].p=“xieshanshan”;a[22].p=“liming”;a[23].p=“zhangshuai”;a[24].p=“qiuyajun”;a[25].p=“yanruibin”;a[26].p=“jiangwei”;a[27].p=“fangzhaohua”;a[28].p=“yujia”; 武汉理工大学《数据结构》课程设计说明书 a[29].p=“liuzhenzhen”;3.2.2获取关键码 字符串的各个字符所对应的ASCII码相加，所得的整数做为关键字。 int i,s,r;for(i=0;i<30;i++){ s=0;for(r=0;*(a[i].p+r)!=' ';r++) { s+=*(a[i].p+r); a[i].key=s; } } 3.2.3 HASH(结构体数组)初始化 HASH h[40];for(i=0;i<40;i++){ h[i].key=0;h[i].hash=0;h[i].reha=0;h[i].p=“ ”;h[i].l=0;} 3.2.4构造哈希表 for(i=0;i<30;i++){ int sum=0;int hi=(a[i].key)%37;//哈希函数 int hj=(7*a[i].key)%10+1;//再散列函数 if(h[hi].l==0)//如果不冲突 { h[hi].key=a[i].key;h[hi].hash=(a[i].key)%37;h[hi].reha=(7*a[i].key)%10+1;h[hi].p=a[i].p; 武汉理工大学《数据结构》课程设计说明书 h[hi].l=1; } else //冲突 { int finh;//最终地址 do { finh=(hi+hj)%40;//伪随机探测再散列法处理冲突 hi=finh;sum=sum+1;//查找次数加 }while(h[hi].l!=0); h[hi].key=a[i].key; h[hi].hash=(a[i].key)%37; h[hi].reha=(7*a[i].key)%10+1;h[hi].p=a[i].p;h[hi].l=sum+1; } } 3.2.5打印哈希表 float average=0;cout<<“关键码 初散列 再散列 哈希地址 查找次数 姓名”< for(i=0;i<40;i++)average+=h[i].l;average/=30;cout<<“平均查找长度：ASL=”< int m;do //m=1,继续查找；m=0,退出查找 { char *f=new char[20];int key=0,n=0,g,l=1,adr;cout<<“请输入姓名的拼音:”< 武汉理工大学《数据结构》课程设计说明书 { n+=*(f+g); key=n; } adr=key%37;//哈希函数求初散列值 if(h[adr].key==key)//分3种情况进行判断 { cout<<“关键字:”< cout<<“初散列值为:”< cout<<“再散列值为:”< cout<<“表中位置为:”< int finh;//最终地址 int sign=0; do { finh=(adr+7*key%10+1)%40;//再散列法处理冲突 adr=finh;l=l+1;//查找次数加 if(h[adr].key==0) { sign=1; cout<<“无此记录!”< } if(h[adr].key==key) { sign=1;cout<<“关键字:”< } }while(sign==0);} cout<<“继续查询请输入,退出请输入：”< 武汉理工大学《数据结构》课程设计说明书 4调试结果与运行情况分析 4.1程序运行结果 武汉理工大学《数据结构》课程设计说明书 4.2运行情况分析 哈希表的输出与预期相同且正确，并查找了“liuying”、“jiangwei”、“huangxiao”三个姓名，分别代表查找一次、多次后成功及查找不成功的情况，且查找结果正确。 4.3算法的时间复杂度 O(n)5自我评价与总结 经过这次课程设计的学习，让我明白了编写程序的思路是很重要的，不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在编写一个程序之前，如果脑袋里面没有思路，根本就不可能编出好的程序。就算能编出程序来，相信编出的程序的逻辑性也不会很强，因为是想到什么就编什么，不系统。因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个完整的程序。在上机实验之前，最好将程序编写好在草稿纸上，这样在编译的时候也比较有效率。 课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前一个必不少的过程．“千里之行始于足下”，通过这次课程设计，武汉理工大学《数据结构》课程设计说明书 我深深体会到这句千古 名言的真正含义。今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳 健地在社会大潮中奔跑打下坚实的基础。数据结构，是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。这一门课的内容不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。通过这次哈希表的设计，我在多方面都有所提高。 在这次课程设计的过程中，我也遇到了很多难题。在种种的困难中，我明白了耐心在编写程序时的重要性。如果你没有耐心就肯定编不出好的程序，特别是在调试的过程中。我们初次写的程序在电脑上调试的时候也许会出项几百个错误，这时候我们应该耐心的检查出错的地方和原因，并予以改正，而不是抱怨自己写的程序太烂错误太多，就此放弃。相信再强的人也不可能一次就能编译成功，总会有一些问题出现。其实只要有耐心，就会发现，在修改了一个错误之后，其它有的错误也会跟着消失，所以在编译的时候一定要有耐心。通过这次课程设计，我认识到了自己动手实践的弱势，特别是在编程方面，知道了计算机的实践操作是很重要的，只有通过上机编程才能充分的了解自己的不足。而自己完成了这样的课程设计，也是对自己实力的检测，使我对以后的学习也充满了信心和期待。这次的课程设计，更是让我深刻认识到自己在学习中的不足，同时也找到了克服这些不足的方法，这也是一笔很大的资源。 数据结构是一门比较难的课程，需要花很多的时间去练习和实践。要想把这门课程学好学精不是一件容易的事，但是相信事在人为，只要肯下功夫就一定能学好。总的来说，这次程序设计让我获益匪浅，相信在以后的学习生活中我也能从中获得启发。在以后的时间中，我们应该利用更多的时间去上机 实验，加强自学的能力，多编写程序，相信不久后我们的编程能力都会有很大的提高能设计 出更多的更有创新的作品。 我认为我的设计优点在于只是用了简单的面向过程编程，而没有用面向对象的类的设计。类在用于比较大的程序设计时会显露较大的优势，而在此反而会增加不必要的麻烦。我的设计缺点在于不是面向大众的，即不能由用户在运行时输入姓名，只能通过在代码中的修改达到效果。 这个课题的另一种方法是使用模板类，这样做可以使程序的结构看起来更整洁简明，各种方法的相关函数一览无余；在主函数中直接调用定义在模版类中的函数，使读者可以很快明白主函数做了哪些工作，程序运行后会有哪些输入输出。 6.参考文献 1.《数据结构（用面向对象方法与C++语言描述）》（第2版）清华大学出版社 2.《C++ Primer(中文版)》（第4版）人民邮电出版社 武汉理工大学《数据结构》课程设计说明书 7.附：源代码 #include int key; char *p;}NAME;NAME a[30];a[0].p=“wangjunzhe”;a[1].p=“mahaiping”;a[2].p=“luozijian”;a[3].p=“luoxiangzhou”;a[4].p=“zhangkai”;a[5].p=“fengyuyang”;a[6].p=“wuzhenzhen”;a[7].p=“haokaiqi”;a[8].p=“caopu”;a[9].p=“liuying”;a[10].p=“cuijuan”;a[11].p=“hanqianqiqn”;a[12].p=“lixiaoyu”;a[13].p=“caoyingnan”;a[14].p=“jinbaoyu”;a[15].p=“zhaduo”;a[16].p=“wenbo”;a[17].p=“cuichangwei”;a[18].p=“zhangqiu”;a[19].p=“luopeng”;a[20].p=“hudie”;a[21].p=“xieshanshan”;a[22].p=“liming”;a[23].p=“zhangshuai”;a[24].p=“qiuyajun”;a[25].p=“yanruibin”;a[26].p=“jiangwei”;a[27].p=“fangzhaohua”;a[28].p=“yujia”;a[29].p=“liuzhenzhen”;int i,s,r; 武汉理工大学《数据结构》课程设计说明书 for(i=0;i<30;i++){ s=0;for(r=0;*(a[i].p+r)!=' ';r++) { s+=*(a[i].p+r); a[i].key=s; } } typedef struct { int key;//关键字 int hash;//初始地址 int reha;//再散列值 char *p;//名字 int l;//查找长度 }HASH;HASH h[40];for(i=0;i<40;i++){ h[i].key=0;h[i].hash=0;h[i].reha=0;h[i].p=“";h[i].l=0;} for(i=0;i<30;i++){ int sum=0;int hi=(a[i].key)%37;//哈希函数 int hj=(7*a[i].key)%10+1;//再散列函数 if(h[hi].l==0)//如果不冲突 { h[hi].key=a[i].key; h[hi].hash=(a[i].key)%37; h[hi].reha=(7*a[i].key)%10+1;h[hi].p=a[i].p;h[hi].l=1; } else //冲突 { int finh;//最终地址 武汉理工大学《数据结构》课程设计说明书 do { finh=(hi+hj)%40;//伪随机探测再散列法处理冲突 hi=finh;sum=sum+1;//查找次数加 1 }while(h[hi].l!=0); h[hi].key=a[i].key; h[hi].hash=(a[i].key)%37; h[hi].reha=(7*a[i].key)%10+1;h[hi].p=a[i].p;h[hi].l=sum+1; } } float average=0;cout<<”关键码初散列再散列哈希地址查找次数姓名“< for(i=0;i<40;i++)average+=h[i].l;average/=30;cout<<”平均查找长度：ASL=“< n+=*(f+g); key=n; } adr=key%37;//哈希函数求初散列值 if(h[adr].key==key)//分3种情况进行判断 { cout<<”关键字:“< cout<<”初散列值为:“< cout<<”再散列值为:“< 武汉理工大学《数据结构》课程设计说明书 cout<<”表中位置为:“< int finh;//最终地址 int sign=0; do { finh=(adr+7*key%10+1)%40;//再散列法处理冲突 adr=finh;l=l+1;//查找次数加 if(h[adr].key==0) { sign=1; cout<<”无此记录!“< } if(h[adr].key==key) { sign=1;cout<<”关键字:“< } }while(sign==0);} cout<<”继续查询请输入,退出请输入："< 数据结构实验 实验一 静态查找表中的查找 一、实验目的： 1、理解静态查找表的概念 2、掌握顺序查找和折半查找算法及其实现方法 3、理解顺序查找和折半查找的特点，学会分析算法的性能 二、实验内容： 1、按关键字从小到大顺序输入一组记录构造查找表，并且输出该查找表； 2、给定一个关键字值，对所构造的查找表分别进行顺序查找和折半查找，输出查找的结果以及查找过程中“比较”操作的执行次数。 三、实验要求： 1、查找表的长度、查找表中的记录和待查找的关键字值要从终端输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、输出信息中要标明所采用的查找方法类型。 实验二 基于二叉排序树的查找 一、实验目的： 1、理解动态查找表和二叉排序树的概念 2、掌握二叉排序树的构造算法及其实现方法 3、掌握二叉排序树的查找算法及其实现方法 二、实验内容： 1、输入一组记录构造一颗二叉排序树，并且输出这棵二叉排序树的中序序列； 2、给定一个关键字值，对所构造的二叉排序树进行查找，并输出查找的结果。 三、实验要求： 1、二叉排序树中的记录和待查找的关键字值要从终端输入； 2、输入的记录格式为(整数，序号)，例如(3, 2)表示关键字值为3，输入序号为2的记录； 3、算法要具有较好的健壮性，对错误操作要做适当处理。 四、程序实现： (1)实现顺序查找表和折半查找表： #include int key[MAX_LENGTH]; int length;}stable; int seqserch(stable ST,int key,int &count){ int i; for(i=ST.length;i>0;i--) { count++; if(ST.key[i]==key) return i; } return 0;} int binserch(stable ST,int key,int &count){ int low=1,high=ST.length,mid; while(low<=high) { count++; mid=(low+high)/2; if(ST.key[mid]==key) return mid; else if(key high=mid-1; else low=mid+1; } return 0;} main(){ stable ST1; int a,b,k,x,count1=0,count2=0,temp=0; ST1.length=0; printf(“请按从小到大的顺序输入查找表数据：(-1代表结束！)n”); for(a=0;a { scanf(“%d”,&temp); if(temp!=-1) { ST1.key[a]=temp; ST1.length++; } else break; } printf(“输入数据为：n”); for(b=0;b { printf(“%d ”,ST1.key[b]); } printf(“n请输入要查找的数据：”); scanf(“%d”,&k); a=seqserch(ST1,k,count1)+1; printf(“n顺序查找： 该数据的位置在第：%d个n”,a); printf(“查找次数为：%dnn”,count1-1); a=binserch(ST1,k,count2)+1; printf(“折半查找： 该数据的位置在第：%d个n”,a); printf(“查找次数为：%dn”,count2-1);}（2）二叉排序树的查找： #include typedef struct node { int data; int key; struct node *left,*right;}bitnode,*bittree; void serchbst(bittree T,bittree *F,bittree *C,int data){ while(T!=NULL) { if(T->data==data) { *C=T; break; } else if(data { *F=T; T=T->left; } else { *F=T; T=T->right; } } return 0;} int insertbst(bittree *T,int key,int data){ bittree F=NULL,C=NULL,s; serchbst(*T,&F,&C,data); if(C!=NULL)return 0; s=(bittree)malloc(sizeof(bitnode)); s->data=data; s->key=key; s->left=s->right=NULL; if(F==NULL)*T=s; else if(data F->left=s; else F->right=s; return 1;} void creatbst(bittree *T){ int key,data;*T=NULL; printf(“请输入数据以构造二叉排序树：(数据格式为:m n(-1000,-1000)代表结束)n”); scanf(“%d%d”,&key,&data); while(key!=-1000 || data!=-1000) { insertbst(T,key,data); scanf(“%d%d”,&key,&data); } } void midTraverse(bittree T){ if(T!=NULL) { midTraverse(T->left); printf(“(%d,%d)”,T->key,T->data); midTraverse(T->right); } } main(){ bittree T=NULL,C=NULL,F=NULL; int key,data,temp; creatbst(&T); printf(“此二叉树的中序序列为：”); midTraverse(T); printf(“n请输入要查找的关键字：”); scanf(“%d”,&data); serchbst(T,&F,&C,data); printf(“此关键字的数据为：%dn”,C->key);} 五、实现结果： (1)顺序查找和折半查找： (2)二叉树排序树查找： 六、实验之心得体会： （1）在这次实验中，我基本上掌握了顺序查找、折半查找和二叉排序树查找的基本思想和实现方法，让我体会到了写程序时，不仅要考虑是否能够调试出结果，还要考虑程序实现的效率，这是一个编程人员必须要具备的一项总要的素质。 （2）通过这次实验，让我体会到同样的数据在不同的查询方法下有着不同的查询效率，就拿实验一来说，用顺序查找法在12个数据中查找一个关键字需要的查找的次数为8次，但是，如果折半查找法却只要两次，由此可以看出，我们在查找时不仅要考虑查找的实现，还要考虑查找的效率和查找所用的时间。 （3）用二叉排序树查找效率也比较高，只要你输入相应的关键字，就可已找到所需要的数据，就我个人看来，用二叉排序树的效率要比顺序查找和折半查找的效率更高，查询的速度更快。 实验题9.1 设计一个程序exp9-1.cpp，输出在顺序表{3，6，2，10，1，8，5，7，4，9}中采用顺序方法找关键字5的过程。程序如下： //文件名:exp9-1.cpp #include KeyType key; //KeyType为关键字的数据类型 //其他数据 //定义表中最多记录个数 InfoType data; } NodeType;typedef NodeType SeqList[MAXL]; //顺序表类型 int SeqSearch(SeqList R,int n,KeyType k)//顺序查找算法 { int i=0; while(i { } printf(“%d ”,R[i].key);i++; //从表头往后找 if(i>=n)return-1; else } void main(){ SeqList R;{ } printf(“%d”,R[i].key);return i; } int n=10,i;KeyType k=5;int a[]={3,6,2,10,1,8,5,7,4,9};for(i=0;i //建立顺序表 printf(“关键字序列:”);for(i=0;i 截图如下： 实验题9.2 设计一个程序exp9-2.cpp，输出在顺序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找关键字9的过程。 程序如下： //文件名:exp9-2.cpp #include //定义表中最多记录个数 KeyType key; //KeyType为关键字的数据类型 InfoType data; //其他数据 } NodeType;typedef NodeType SeqList[MAXL]; //顺序表类型 int BinSearch(SeqList R,int n,KeyType k)//二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high) { mid=(low+high)/2;printf(“ 第%d 次 比 较 :在[%d,%d]R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid; if(R[mid].key>k) //继续在R[low..mid-1]中查找 high=mid-1; else low=mid+1; //继续在R[mid+1..high]中查找 } return-1;} void main(){ SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i //建立顺序表 R[i].key=a[i];printf(“关键字序列:”);for(i=0;i 比 较 元 素 中 } else printf(“元素%d的位置是%dn”,k,i);printf(“元素%d不在表中n”,k); 截图如下： 实验题9.3 设计一个程序exp9-3.cpp，输出在顺序表{8，14，6，9，10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分块查找法查找（每块的块长为5，共5块）关键字46的过程。 程序如下： //文件名:exp9-3.cpp #include KeyType key; //KeyType为关键字的数据类型 //定义表中最多记录个数 //定义索引表的最大长度 InfoType data; //其他数据 } NodeType;typedef NodeType SeqList[MAXL];typedef struct { KeyType key;int link; //KeyType为关键字的类型 //指向分块的起始下标 //顺序表类型 } IdxType;typedef IdxType IDX[MAXI]; //索引表类型 int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)//分块查找算法 { int low=0,high=m-1,mid,i,count1=0,count2=0;int b=n/m; //b为每块的记录个数 printf(“二分查找n”);while(low<=high) //在索引表中进行二分查找,找到的位置存放在low中 { mid=(low+high)/2;printf(“ 第%d 次 比 较 :在[%d,%d] 中 比 较 元R[%d]:%dn”,count1+1,low,high,mid,R[mid].key); if(I[mid].key>=k) high=mid-1; else low=mid+1; count1++; //累计在索引表中的比较次数 } if(low //在索引表中查找成功后,再在线性表中进行顺序查找 { printf(“比较%d次,在第%d块中查找元素%dn”,count1,low,k); i=I[low].link; printf(“顺序查找:n ”); while(i<=I[low].link+b-1 && R[i].key!=k) { i++;count2++; printf(“%d ”,R[i].key);} //count2累计在顺序表对应块中的比较次数 printf(“n”); printf(“比较%d次,在顺序表中查找元素%dn”,count2,k); if(i<=I[low].link+b-1) return i; else return-1;} 素 } return-1;void main(){ } SeqList R;KeyType k=46;IDX I;int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;for(i=0;i<25;i++)R[i].key=a[i]; //建立顺序表 I[0].key=14;I[0].link=0;I[1].key=34;I[1].link=4;I[2].key=66;I[2].link=10;I[3].key=85;I[3].link=15;I[4].key=100;I[4].link=20;if((i=IdxSearch(I,5,R,25,k))!=-1)else printf(“元素%d不在表中n”,k);printf(“元素%d的位置是%dn”,k,i);printf(“n”); 截图如下：第三篇：数据结构课程设计之姓名哈希表的建立及查找
第四篇：数据结构实验报告-静态查找表中的查找
第五篇：数据结构查找实验报告
点击咨询 