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

1、桂林电孑科被火玲编号：139GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY数据结构与算法课程设计说明书动态查找表学 院：海洋信息工程学院专 业： 计算机科学与技术学生姓名：学 号：指导教师：2015年 6月26 日动态查找表学生姓名：银杰指导老师：王晓莹摘要本课程设计说明书系统地阐述了我使用C语言在Code:Blocks软件编写的动态查找表程序的整个过程，编写的环境是win7 64位操作系统。根据题目要求，编写动态查找表使用二叉排序树，即二叉链表作为存储结构。该程序具有建立数据功能、具有数据查找功能、具有数据插入功能、具有数据删除功能等基本功能操作。关键词

2、：动态查找表，Code:Blocks 软件， win7 64 位操作系统，C#dynamic lookup tableAuthor :yinjieTutor :WangxiaoyingAbstractThis 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 wi

3、n7 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 wor

4、ds:dynamic lookup table, Code:Blocks software,win7 64 bit operating system， C引言 1查找的基本概念1小结 1题目 1第1 章程序的构图设计21.1 动态查询表： 21.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

5、(4)二叉排序树的插入模块 9(5)多态查找表删除模块 10(6)二叉排序树的中序遍历模块 12第3 章 程序测试和运行 123.1 程序测试 123.2 程序运行 131、主界面 132、建立二叉排序树模块界面 133、二叉排序树查找模块界面 144、二叉排序树插入模块界面 145、二叉排序树删除模块界面 146、退出程序的界面 14总结 15程序完成情况 15有待改进之处 15课程设计期间的收获 15附录源代码如下 17桂林电子科技大学课程设计说明书引言查找的基本概念查找又称为检索，就是从一个数据元素集合中找出某个特定的数据元素。查找是数 据处理中最为常用的一种操作，查找算法的优劣对整个软

6、件系统的效率影响很大，尤其 当所涉及的数据量较大时，更是如此。在一个数据集合中进行查找操作可选用的方法与 该数据元素集合的存储结构有很大关系。查找是根据某个给定的值，在数据元素构成的集合中确定是否在这样一个数据元素，它的关键字等于给定值的关键字。要进行查找，必须明确要查找对象的特征，也就是要查找元素的关键值。如果在数 据集合中能找到与给定值相等的关键字， 则该关键字所属的数据元素就是所要查找的数 据元素，此时称该查找成功；如果查遍了整个数据元素集合也未能找到与给定值相等的 关键字，则称该查找失败。小结当然对于这个说明书，我不可能做得至善至美，但是一些基本的格式内容还是符合 要求的。首先，我对查

7、找表进行一个简要的概述。 然后，我就查找表进行了详细的分析, 这是设计中很重要的一步。接下来，我把查找表中所有的设计简明清晰地展现出来，并 把我在设计中遇到的问题和分析解决问题的办法做了分析。最后，在结论中，我对自己 的课程设计做了总体的评价同时简述了我在这次课程设计中的收获和经验。题目选题十二：动态查找表【问题描述】利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。【任务要求】算法输入：指定一组数据。算法输出：显示二叉排序树的中序遍历结果、查找成功与否的信息、插入和删除后 的中序遍历结果（排序结果）。算法要点：二叉排序树建立方法、动态查找方法 ，对树进行中序遍历

8、。【测试数据】自行设定，注意边界等特殊情况。第1章程序的构图设计a）所示：当插入11的时1.1 动态查询表:依照输入的一组数据56,80,65,20所得的二叉排序树如下（候就如（b）所示1.2 程序功能流程图:（1）、主函数模块(2)、二叉排序树的生成-k打印输心动态表 的6个功能选择栏do循环I输入连择号h结束开始输入数据个数X(3)、二叉排序树的查找模块(4)、二叉排序树的插入模块调用卡询函数 Search。否 * 被插入结点*s 为新的根结点J1是v.插入的节点<?>根结点A<_>被插结点*s被插结点*s.为左孩子为石孩子j1插入成功*(结束二查询成功(5)、二叉

9、排序树删除连接模块是一向右走到尽头While循环*重接它的 左右子树(6)、二叉排序树的删除模块输入要删除 的的数据调用删除的连接函数Delete()找到关键 字并删除(7)、二叉排序树的遍历模块开始一二叉树根是一.查为空.第2章详细设计的程序各函数模块(1)主函数模块：用主函数main()来实现。主要是通过设计一个do()函数并让主函数调用它来显示主菜单, 让用户选择操作。在do()函数中，我应用了 switch-case语句来进行选择，是个比较简单实现的模块。最后若选择“ 5”退出循环。否则继续循环。主要代码如下:int main()bitree T=NULL,p;ElemType e;i

10、nt n;int h;char c;doprintf("*n");printf("*n");printf("*动态查找表*n");printf("*1.建立二叉排序树*n");printf("*2.二叉排序树查找元素*n");printf("*3.二叉排序树插入元素*n");printf("*4.二叉排序树删除元素*n");printf("*5.退出*n");printf("*n");printf("*n&

11、quot;);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(&q

12、uot;数据不存在！n"); break;case 3:printf(”请输入要插入的数据：n");scanf("%d",&n);e.key=n;if(Search(T,e,NULL,p)printf("已经存在!n");elseInsert(T, e); printf("成 功插入!n");printf("中序遍历二叉排 序4i : ");Zhongxu(T);printf("n");break;case 4:printf("请输入要删除的数据：n&quo

13、t;);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!

14、=5);(2)二叉排序树的生成模块：二叉排序树的生成，是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入 算法将它插到当前已经生成的二叉排序树中。主要代码如下：void Init(bitree &T)构造一个动态查找表Tint x;int i;int n;ElemType e;printf("请输入结点个数：");scanf("%d",&x);for(i=1;i<=x;i+)print/第 个结点数据值 二i);scanf("%d",&n);e.key=n;Insert(T,e);printf(&

15、quot;二叉排序树已经建立!n");(3)二叉排序树的查找模块：二叉排序树的查找方法如下。当二叉排序树为空时，查找失败。当二叉排序树根结点的关键字等于key时，查找成功。当二叉排序树根结点的关键字大于key时，从根结点的左子树中以同样方法进行查找。当二叉树根结点的关键字小于key时，从根结点的右子树以同样方法进行查找。显然，该过程是一个递归过程，下面给出这一算法的实现。主要代码：bitree Search(bitree T,ElemType e,bitree f,bitree &p)施二叉排序树中查找数据if(!T)p=f；return NULL;查找不成功else if(

16、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与二叉排序树的根结点进行比较：如

17、果 key的值等于根 结点的值，则停止插入；如果key的值小于根结点的值，则将key插到左子树；如果key 的值大于根结点的值，则将key插到右子树中。主要代码如下：void Insert(bitree &T,ElemType e)/4二叉排序树中插入数据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<p->dat

18、a.key)p->lchild=s;/被插结点*s为左孩子elsep->rchild=s;/被插结点*s为右孩子(5)多态查找表删除模块：从二叉排序树中删除一个结点，不能简单地把以该结点为根的子树都删除，只能删除掉 该结点，并且还应该保证删除后所得到的二叉树依然满足二叉树的性质不变。也就是说，在二叉排序树中删除一个结点相当于删除有序序列中的一个结点。假设要删除的结点为P,其双亲结点为F,同时假设结点P是结点F的左孩子(右孩子 的情况类似)。删除操作首先要确定被删结点 P是否在二叉排序树中。若不在，则不做 任何操作；若在，分为以下三种情况讨论。若P为叶子结点，可直接将其删除。若结点P

19、只有左子树，或只有右子树，则可将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)/右子树空，只需重接它的左子

20、树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 的右子树elseq->l

21、child=s->lchild;/ 重接*q 的左子树free(s);s=NULL;删除结点void Deletebit(bitree &T,int n)删除二叉排序树中的数据 if(!T)return;/不存在关键字等于n的数据元素elseif(T->data.key=n)return(Delete(T);/找到关键字等于n的数据元素并删除它else if(T->data.key>n)Deletebit(T->lchild,n); 继续在左子树中删除else Deletebit(T->rchild,n);/继续在右子树中删除(6)二叉排序树的中序遍

22、历模块：中序遍历二叉树定义：若二叉树根为空，则返回；否则，中序遍历左子树；访问根结点;中序遍历右子树。主要代码如下：void Zhongxu(bitree T)/中序遍历if(T!=NULL)Zhongxu (T->lchild);printf("%d ”,T->data.key);Zhongxu (T->rchild);第3章程序测试和运行3.1程序测试程序测试是程序质量保证的主要活动之一，在程序编写的过程中，在各个阶段都有 可能存在错误和缺陷。通过测试是可以发现程序设计中存在的种种问题，并可以及时改 正。避免在程序运行时才出现不必要的错误。测试是质量保证一个临界

23、和决定惩罚，它 提供对程序说明、设计和编码的最终评审。是发现程序缺陷和错误的有力手段。根据系统设计目标和功能，对系统进行测试。1、功能性(1)程序实现的主要功能，包括查询，插入，删除等。(2)题目要求的输入输出字段，以及题目要求的输入限制。2、可靠性程序正确实现了对动态查找表的查询、插入、删除等各种功能。3、易用性现有程序实现了如下易用性：(1)查询，插入，删除，操作相关提示信息的一致性，可理解性(2)输入限制的正确性(3)输入限制提示信息的正确性，可理解性，一致性(4)界面排版简洁完整3.2程序运行1、主界面：n【m5与算法的球性徵计黄拂a物与幅现津唐设计1臼血元元元 翳入除 寸 h -IC

24、jlE!;! 婚立曼叉出 天建二二二退*请输入你的选择:2、建立二叉排序树模块界面 ：睛输入你的选择;3、二叉排序树查找模块界面 ：请输入你的选择;3输入要查找的数据：20数据已经存在？4、二叉排序树插入模块界面：KM* 箕*MififiMKHMntMHHHIfJitKItJCIfJtJCXKJOtJtMiMi* * itiMKKMXMltHMIflltKhtJC请输入你的选择：;青输入要插入的数据：11乐功插入？巾序遛历二叉排序树：11 20 56 65 865、二叉排序树删除模块界面 ：请输入祢的选择：褊人要删除的数据：20整座功删除一巾序通历二叉排序树：11 56 65 806、退出程序

25、的界面，青输入你的选择;，择错误，重新开始，元元元 ©除找一查叉,-4下* *七' 土方- TT叉叉叉+. 建二二二退1.请输入你的选择士退出！Process iretm*ned 团 <0x0> execution t. ime : 7.297 s Pi*£s：s： amy ksy t口 心tmtiriuE.程序完成情况在编写程序写课程设计的时间里，虽然历经重重困难和挫折，但是在我自己的努力 和老师的帮助下终于完成了动态查找表的设计。尽管该程序在功能和性能上可能还有一 些缺陷，但是我已经完成了课程设计的任务和目标，达到了题目基本要求，成功完成了 算法与数

26、据结构课程设计。有待改进之处有待改进：1、我在编写程序的时候，用的是C+略式去保存编译的，用了 C语言来编写，但是 有一些C+勺形式，当我用C来新建保存的时候却出现问题。所以程序我是用 C+球新 建保存的。2、流程图画的不是很规范表准，在一些逻辑表达上不够简洁清晰。课程设计期间的收获在完成此次的课程设计的过程中，我跨越了传统方式下的教与学的体制束缚， 通过自己的思考和设计，培养了自学能力和动手能力。并且由原先的被动的接受知识转 换为主动的寻求知识，这可以说是学习方法上的一个很大的突破。在以往的传统的学习 模式下，我们可能会记住很多的书本知识，但是通过课程设计，我们学会了如何将学到 的知识转化为

27、自己的东西，学会了怎么更好的处理知识和实践相结合的问题。通过这次课程设计，我认识到数据结构与算法是计算机科学的基础课程，是我们学 习的核心课程。我对数据结构和算法又有了新的认识。数据结构的研究不仅涉及到计算 机软件，而且和计算机硬件的研究也有着密切的关系，无论是编译程序还是操作系统， 都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数 据，以便使查找和存取数据元素更为方便。可以认为数据结构是介于数学、计算机硬件 和计算机软件三者之间的一个核心内容， 是从事计算机科学研究及其应用的人必须掌握 的重要内容。这次的课程设计有效的培养了我们独立思考的能力，提高了我们的动手操作水平。 在具体设计中，我们巩固了上学期所学的数据结构与算法的理论知识，进一步提高了自 己的编程能力。这也是课程设计的目的所在。通过编程实践，不仅开发了自己的逻辑思 维能力，培养了分析问题、解决问题的能力，更充分锻炼了我们的编程能力。在这次课程设计中我