数据结构课程设计(1850).doc

数 据 结 构课程设计 题 目：二叉排序树院 系：信息工程学院班 级：信息10本1指导老师：安强强日 期：2012年1月10日表11 二叉排序树课程设计任务书课程设计情况课程设计名称二叉排序树指导教师姓名安强强职称讲师需学生数5人组长葛守瑜成员霍小丽、罗健、陈亚维、韦丽田各成员主要负责内容葛守瑜：编写程序代码并参与模块设计。韦丽田：程序模块设计并参与设计目标。 罗 健：课程设计总结并参与详细设计，并整理文档。陈亚维：详细设计并参与模块设计。霍小丽：课程设计目标并参与详细设计。 目 录1课程设计目标.1 1.1 问题描述.1 1.2 问题分析.1 1.3 需求分析.12.概要设计.2 2.1 方案确定.2 2.2 程序设计模块.2 2.3 设计连接图.3 2.4 程序功能描述.33.详细设计.5 3.1 方法设计.5 3.2 整体程序流程图.164.程序清单.175.程序测试与运行结果.226.课程设计总结.291、 课程设计目标1 问题描述编写一C语言程序，其功能是建立一个二叉排序树，对二叉排序树进行查找，遍历及最终运行结果进行打印等相关操作。2 问题分析首先,选择合适的存储结构构造二叉排序树，对该程序可以分为几个模块进行分析，每个模块在该程序中的作用进行了解。最后用设计连接图将各模块之间的联系连接起来，以方便我们更容易理解。然后,该程序需要一个详细的设计流程图来表示各个步骤所完成的先后顺序，（如，对二叉排序树进行插入，查找及进行中序遍历并输出打印结果）。最后,按流程图进行编写二叉排序树的程序，输出结果，并将最终的打印结果显示出。3. 需求分析 本次实验设计主要是建立二叉排序树,要实现二叉排序树的中序遍历,二叉排序树的查找,二叉排序树的插入及二叉排序树的更新建立.设计需求上我们需要掌握以下几点:(1).设计需求部分1. 写出本次实验的详细设计方案。2. 画出该次程序的流程图。3. 分析该次程序的程序清单,进行程序测试并输出运行结果。4. 对该次程序中个函数的功能分析结果。5. 对该次实验完成后有总结。(2).设计大纲1. 了解, 分析这次实验的主要问题。2. 讨论解决问题的方案。3. 分配组员的个人任务。4. 进行各部分的整合、修改、完善。5. 进行这次实验的总体报告实验总结。二、概要设计1、方案确定 二叉排序树这个课题要求实现许多功能，我们可遵循结构化程序设计思想来进行本函数一系列的设计,应运用自顶向下，逐步细化的方法执行。本程序可以分为五个小问题：二叉排序树的插入，二叉排序树的建立，二叉排序树的中序遍历，二叉排序树的查找。我们要逐个解决，从而完成整个程序。 2、程序设计模块 该程序可划分为四个模块: 主函数模块main（） 从键盘上输入一组数据，建立一个二叉排序树； 二叉排序树的建立模块BSTree CreateBST(BSTree *bst)建立二叉排序树的链表结构并将其初始化为一个空树；从键盘上依次读入n个关键字并每遇到一关键字就建立一个新的结点； 依次用InsertBST（插入函数）使结点逐个插入到一生成的二叉排序树； 返回根结点T； 二叉排序树的中序遍历模块void OutputBintree(BSTree p)判断根结点是否为空，假如不是空值，则访问左子树，遍历左子树；以左子树为根结点，依次调用OutputBintree（）函数；访问并遍历右子树；二叉排序树的查找模块int SearchBST(BSTree bst,int sea_key)在根指针p所指二叉排序树中非递归查找关键字等于 key 的数据元素； 计算根结点的个数，计算长度；若成功，count+,否则返回count=0； 3、 设计连接图二叉排序树的链表建立模块二叉排序树的结点插入二叉排序树建立模块二叉排序树中序遍历模块二叉排序树查找模块动态查找模块主函数模块二叉排序树 图- 1图3-14. 程序功能描述： insertbst(bstree *bst,int key)函数数据对象：可以是任意类型的数据，但必须属于同一个数据对象；函数功能：二叉排序树结点的插入及左右孩子的定义； 二叉排序树链表结构的建立；基本操作: if(*bst=NULL)：树的判断； if(keykey):关键字和左孩子的判断。BSTree CreateBST(BSTree *bst)函数数据对象：一个集合，该集合中的所有元素具有相同的特性；数据关系：若D为空，则为空树。若D中仅含有一个数据元素，则R为空集,否则R=H，H为如下二元关系：（1） 在D中存在唯一的称为根的数据元素 p它在关系H中没有前驱；（2） 除p外，D中每个结点在关系H下有且仅有一个前驱。基本操作：CreateBST(BSTree *bst)；功能描述：以key为关键字，输入一组有序数，建立一个二叉排序树。void OutputBintree(BSTree p)函数数据对象：不同类型的数据，但必须同属于一个数据对象；函数功能：以根结点是否为空值为线索，分别访问并遍历左右子树，从而完成对整棵树的中序遍历；基本操作：树BSTree：if(p=NULL):根结点的判断； Output Bintree():输出二叉树。nt SearchBST(BSTree bst,int sea_key)函数数据对象：可以是不同的数据类型，但必须同属于一个数据对象；函数功能：用指针p查找二叉排序树中的关键字key；基本操作：插入指向树根结点的指针*p；if(sea-keykey):根结点与关键字的判断。三、详细设计1、方法设计A. 建立二叉排序树（1）将二叉树初始化为一棵空树，每读入一个元素，就建立一个新的结点，并插入到当前已生成的二叉排序树中，即通过多次调用二叉排序树的插入新结点来实现。 Void CreateBST(BSTree *bst) KeyType key; *bst=NULL; Scanf(%d,&key); While(key!=ENDKEY) InsertBST(bst,key); Scanf(%d,&key); B. 二叉排序树的插入 （1）.若二叉排序树是空树，则S成为二叉排序树的根； （2）.若二叉排序树非空，则S.key与二叉排序树根节点的关键字进行比较； a.如果key的值等于根节点的值，则停止插入； b.如果key的值小于根节点的值,则将插入左子树； c.如果key的值大于根节点的值,则将插入右子树。开始创建二叉排序树空二叉树是插入数为根结点否关键字大于根结点是插入右子树否插入左子树结束图3-2void InsertBST(BSTree *bst,int key)BSTree s;if(*bst=NULL)s=(BSTree)malloc(sizeof(BSTNode);s-key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;else if(keykey)InsertBST(&(*bst)-lchild),key);else if(key(*bst)-key)InsertBST(&(*bst)-rchild),key);B二叉排序树的更新建立 将二叉排序树初始化为一棵空树，然后逐个读入元素，每读入一个元素，就建立一个新的结点，并插入到当前已生成的二叉排序树中，即通过多次调用二叉排序树的插入新结点的算法实现； 开始*bst=NULL输入keykey!=ENDKEY调用InsertBST输入keygetchar()return *bst结束是否图3-3BSTree CreateBST(BSTree *bst)int key;*bst=NULL;scanf(%d,&key);while(key!=ENDKEY)InsertBST(bst,key);scanf(%d,&key);getchar();return *bst;二叉排序树的中序遍历输出如果二叉排序树非空，先遍历二叉排序树的左子树，再访问根结点，再中序遍历右子树，最后将遍历结果输出； 开始呢输入二叉排序树shu树二叉排序树为空结束是否调用OutputBintree，输出左子树调用OutputBintree，输出右子树打印根结点图3-4void OutputBintree(BSTree p)/*中序遍历二叉排序树，p为指向二叉排序树根结点的指针*/if(p!=NULL)OutputBintree(p-lchild);printf(%4d,p-key);OutputBintree(p-rchild);二叉排序树的查找（非递归）将待查关键字key与根结点关键字p进行比较 (比较次数记为count)，如果：（1） . key=p:则返回根结点地址；（2） . Keyp:则进一步查右子树。若查找失败，比较次数为count；如查找成功，则比较次数为count+1。 开始(p!=NULL)&(p-key!=sea_key)输入cout=0 p=bst是否否否p=NULL是是cout+Sea_keykey printf(count)cout+P=p-rchildprinf(count+1)p=p-lchildreturn 0结束图3-5int SearchBST(BSTree bst,int sea_key)BSTNode *p;int count=0;p=bst;while(p!=NULL)&(p-key!=sea_key)if(sea_keykey)count+;p=p-lchild;elsecount+;p=p-rchild;if(p=NULL)printf(查找失败，比较次数为%d次,count);return 0;elseprintf(查找成功，比较次数为%d次,count+1);return 0;F. 动态查找主程序在main函数中调用void DynamicSearch()int sea_key,key;BSTree p,bst;char dynamic_func_choice;printf(按一定数序输入数字建立排序二叉树(以-1结束)n); CreateBST(&bst); printf(请输入数字n); for(;) printf(1代表中序遍历 2代表查找关键字 3代表退出n); dynamic_func_choice=getchar(); getchar(); if(dynamic_func_choice=3) printf(是否需要继续二叉树排序n); printf(1代表继续 0代表退出n); printf(请输入正确的操作选项(0-1)n); break; switch(dynamic_func_choice) case1: printf(创建成功按中序遍历输出n); OutputBintree(bst); printf(n); break; case 2: printf(请输入要查找的关键字:); scanf(%d,&sea_key); getchar(); SearchBST(bst,sea_key); printf(n); break; default: printf(没有此选项n); break; void main() char func_choice;printf(请输入正确的操作选项(0-1)n);printf(1代表继续 0代表退出n);func_choice=getchar();getchar();while(func_choice!=0)switch(func_choice)case1:printf(开始建立二叉排序树n);DynamicSearch();break;case0:func_choice=0;break;default:printf(n请输入正确的操作选项(0-1); func_choice=getchar();getchar();、2、 整体程序流程图开 始建 立二叉排序树二叉排序树结点插入是*bst=NULL否否是key=(*bst)-key右子树插入关键字左子树插入关键字 p!=null&p-key=key否查找失败是否sea-keykey是count+;p-rchild;count+;p-lchild; 结 束图3-6四、程序清单#include#include#include#define ENDKEY -1typedef struct nodeint key;struct node *lchild,*rchild;BSTNode,*BSTree;/*二叉排序树的结点插入递归算法*/void InsertBST(BSTree *bst,int key)BSTree s;if(*bst=NULL)s=(BSTree)malloc(sizeof(BSTNode);s-key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;else if(keykey)InsertBST(&(*bst)-lchild),key);else if(key(*bst)-key)InsertBST(&(*bst)-rchild),key);/*二叉排序树的更新建立*/BSTree CreateBST(BSTree *bst)int key;*bst=NULL;scanf(%d,&key);while(key!=ENDKEY)InsertBST(bst,key);scanf(%d,&key);getchar();return *bst;/*中序二叉排序树的中序遍历输出*/void OutputBintree(BSTree p)/*中序遍历二叉排序树，p为指向二叉排序树根结点的指针*/if(p!=NULL)OutputBintree(p-lchild);printf(%4d,p-key);OutputBintree(p-rchild);/*二叉排序树查找*/int SearchBST(BSTree bst,int sea_key)BSTNode *p;int count=0;p=bst;while(p!=NULL)&(p-key!=sea_key)if(sea_keykey)count+;p=p-lchild;elsecount+;p=p-rchild;if(p=NULL)printf(查找失败，比较次数为%d次,count);return 0;elseprintf(查找成功，比较次数为%d次,count+1);return 0;/*动态查找主程序*/void DynamicSearch()int sea_key,key;BSTree p,bst;char dynamic_func_choice;printf(按一定数序输入数字建立排序二叉树(以-1结束)n); CreateBST(&bst); printf(请输入数字n); for(;) printf(1代表中序遍历 2代表查找关键字 3代表退出n); dynamic_func_choice=getchar(); getchar(); if(dynamic_func_choice=3) printf(是否需要继续二叉树排序n); printf(1代表继续 0代表退出n); printf(请输入正确的操作选项(0-1)n); break; switch(dynamic_func_choice) case1: printf(创建成功按中序遍历输出n); OutputBintree(bst); printf(n); break; case 2: printf(请输入要查找的关键字:); scanf(%d,&sea_key); getchar(); SearchBST(bst,sea_key); printf(n); break; default: printf(没有此选项n); break; void main() char func_choice;printf(请输入正确的操作选项(0-1)n);printf(1代表继续 0代表退出n);func_choice=getchar();getchar();while(func_choice!=0)switch(func_choice)case1:printf(开始建立二叉排序树n);DynamicSearch();break;case0:func_choice=0;break;default:printf(n请输入正确的操作选项(0-1); func_choice=getchar();getchar();5、 程序测试与运行结果1. 程序运行时菜单显示如下：图5-12. 输入1，继续以上程序：图5-23. 当输入的二叉排序树序列为：24,73,56,63,45,17,20,8，-1时，创建二叉排序树，并输出结果如下：图5-34. 输入1，继续中序遍历，并输出结果如下：图5-45. 输入2，查找关键字56，并输出结果如下：图5-56. 输入3，结束程序：图5-67. 输入0，退出程序：图5-76、 课程设计总结 通过这次的课程设计使我们充分了解了二叉排序树的建立、插入、查找、中序遍历以及动态查找的基本原理，并可以编写出其程序。虽然说程序不是很完美的，但是总体上完成了老师的要求，当然这只能相对于我们这些初学者来说。除了课本上仅有的知识外，我们还借用了一些其他书上比较好的算法思想，以至于让我们的课程设计更加完美。在这次课程设计中，让我们深知仅仅掌握课本上的知识是远远不够的。在刚开始编程时，让我们感觉到自己不知道应该从哪里下手。在操作时，常常会遇到一些棘手的问题难以解决，但经过我们组员的不断思考、共同努力，尝试着去更改出现问题的程序，直至程序可以正常运行输出。开始很困难，但在老师和同学们的帮助下，我们了解了很多操作，使后面变得更容易操作。在此非常感谢我们的指导老师安强强老师，为我们认真辅导，让我们对数据结构这门课程有了深一步的了解。与此同时，老师教给我们如何分析问题，怎样写算法，写算法应该注意什么问题以及怎样修改程序中的问题。并且指出我们算法中的不足，让我们加以修改。 看到我们一起完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学习书本知识中得到的。29 参考文献 朱站立 数据结构（C语言版）M. 北京：西安交通大学出版社，2004 耿国华 数据结构（C语言版）M北京：高等教育出版社，2010 冯雁 陈越 数据结构课程设计（C语言版）M. 北京：浙江大学出版社，2007 致 谢本次课程设计在进行过程中得到安强强老师的悉心指导。安老师多次帮助我们分析思路，开拓视角，在我们遇到困难时给予我们最大的支持和鼓励。安老师严谨求实的治学态度，踏实坚韧的工作精神，使我们的课程设计顺利完成。在此，谨向安老师致以诚挚的谢意和崇高的敬意。同时感谢我们班的同学以及舍友，在写课程设计期间他们在学习上给我们提供了莫大的支持和帮助。最后感谢评委老师能在百忙之中对我们的课程设计进行审查，由于我们的知识有限不足之处在所难免，还请各位评委指正。答辩记录表12 课程设计答辩记录答辩人全组人员院（系）班级信息10本1题目名称二叉排序树指导教师安强强组员葛守瑜、陈亚维、霍小丽、罗健、韦丽田答辩日期2012年01月10日答辩地点二号实验楼信管实验室 答辩记录：在以下部分记录学生所展示的课程设计成果是否完整和规范，对课程设计的介绍是否简要和准确，答辩教师提出的问题以及学生回答的情况。形 式 ：对全体小组成员进行提问。考核内容： 1.二叉排序树的建立实现； 2.二叉排序树相关操作的实现； 3.课程设计报告； 4.答辩：回答问题。问答提纲：问题1：二叉树与二叉排序树的区别？答：二叉树是每个结点最多有两个子树的有序树。通常子数的跟被作为“左子树”和“右子树”。二叉树常被用作二叉查找树和二叉堆。二叉树的每个结点至多只有两棵子树（不存在度大于二的结点），二叉树的子树有左右之分，次序不能颠倒。二叉排序树是一种动态查找表。二叉排序树又称二叉查找树。它或者是一棵空树；或者是具有下列性质的树：（1）若左子树不空，则左子树上所有的结点的值均小于它根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它根点的值；（3）左右子树也分别为二叉排序树。问题2：如何判断一个二叉树是否为二叉排序树?答：若一棵二叉树中所有左子树的权值小于根结点，且所有右子树的权值大于根结点，则这棵树为二叉排序树，否则为二叉树。问题3:二叉排序树的存储结构有? 二叉排序树的顺序存储结构和链式存储结构有什么不同？答:存储结构有：顺序存储和链式存储结构. 两种结构的不同点：顺序存储结构在内存中是一快地址连续的存储单元，可以随机访问其中的元素，顺序存储结构的主要优点是节省存储空间，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。