数据结构课程设计：动态查找表_数据结构动态查找表

数据结构课程设计：动态查找表由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构动态查找表”。

编号： 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 proce 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 程序运行....................................................................................................................................................131、主界面

...................................................................................................................................................132、建立二叉排序树模块界面.....................................................................................................................133、二叉排序树查找模块界面.....................................................................................................................144、二叉排序树插入模块界面.....................................................................................................................145、二叉排序树删除模块界面

...................................................................................................................146、退出程序的界面.....................................................................................................................................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为右孩子

桂林电子科技大学课程设计说明书

(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

{

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