《二叉排序树的操作课程设计报告剖析》由会员分享，可在线阅读，更多相关《二叉排序树的操作课程设计报告剖析（36页珍藏版）》请在金锄头文库上搜索。
1、内蒙古科技大学课程设计说明书内蒙古科技大学本科生课程设计说明书题 目：数据结构课程设计 二叉排序树的操作 学生姓名： 许闻杰学 号：1467159228专 业：软件工程班 级：14级软件2班指导教师：周李勇日 期：2016年 1月 8 日34内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目二叉排序树的操作指导教师周李勇时间2016.12016.1一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和
2、软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 创建二叉排序树v 输出二叉排序树v 在二叉排序树中查找给定值v 在二叉排序树中插入新结点v 在二叉排序树中删除给定值 并设计主函数测试该类（或类模板）。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行
3、4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等
4、编著，清华大学出版社 2007.23.数据结构:用面向对象方法与C+语言描述，殷人昆 主编，清华大学出版社 2007.6目 录内蒙古科技大学课程设计任务书I第一章 需求分析31.1引言31.2任务概述31.3数据描述31.4功能需求31.5任务计划4第二章概要设计52.1总体设计52.2数据类型设计（或数据结构设计）52.3接口设计 /函数声明52.4运行界面设计5第三章详细设计73.1输入模块设计73.2输出模块设计73.3查找模块设计7第四章测试分析84.1测试程序执行情况84.2出现的问题和解决的方法8第五章用户手册（可选）95.1使用说明95.2运行说明9第六章课程设计总结10附录：程
5、序代码11参考文献12致谢13第一章 需求分析1.1 引言二叉排序树的操作1.2 任务概述以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。1.3 数据描述以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：ADT BT数据对象root：先定义一个二叉树结点的结构体：typedef struct bstchar data;struct bst *left;struct bst *right;struct bst *father;BSTree,*BST;root是指向二叉树结点
6、的指针；1.4 功能需求创建二叉排序树输出二叉排序树在二叉排序树中查找给定值在二叉排序树中插入新结点在二叉排序树中删除给定值 并设计主函数测试该类（或类模板）。1.5 任务计划主程序流程图算法：主程序主要用运了switch结构，使得主程序更加方便的调用成员函数，各个成员函数间的关系也清晰明了。输入与功能相对应的序号执行功能是否存在开始结束否是 函数调用关系main 主程序显示菜单创建根节点插入结点查找结点删除结点中序遍历二叉排序树第二章 概要设计2.1 总体设计二叉排序树34系统功能结构567退出删除二排序叉树结点设置二叉排序树根结点添加二排序叉树结点查找给定的二叉树结点输出二排序叉树8910
7、1112131415161718系统的功能结构：设置二叉排序树根结点、添加二排序叉树结点、删除二排序叉树结点、查找给定的二叉树结点、输出二排序叉树、退出。功能说明：l 设置二叉排序树根结点：为新创建的二叉排序树创建根节点。l 添加二排序叉树结点：需要输入创建节点的数目，然后创建一定数目的二叉排序树结点。l 删除二排序叉树结点：给定一个数据(字母)，然后查找，找到后删除，否则，告知未找到，l 查找给定的二叉树结点：给定一个数据(字母)，然后查找，并给出提示。l 输出二排序叉树：按照先序遍历并输出二叉排序树的结点数据。l 退出：退出程序。2.2 数据类型设计（或数据结构设计）ADT BT数据对象r
8、oot：先定义一个二叉树结点的结构体：typedef struct bstchar data;struct bst *left;struct bst *right;struct bst *father;BSTree,*BST;root是指向二叉树结点的指针；数据关系：R=|V,CD, 表示由运算符P结合起来的表达式E基本操作：BST InitRoot()操作结果：为空二叉排序树创建一个根节点，输入一个字符型数据，将这个字符型数据存入结点的数据域中同时给左右孩子指针和父指针置空，并返回一个结点的基址给指针。void Inserter(root, key)初始条件：二叉排序树不为空，存在根节点；操
9、作结果：输入一个字符型数据，先寻找二叉排序树中是否有此数据，有则返回主菜单，没有则就二叉排序树的构造方法返回要插入旳数据应该插入位置的父节点地址，创建一个新结点，将这个字符型数据存入结点的数据域中，并将左右孩子指针置空，父指针指向父节点地址，然后返回主菜单。BSTree *SearchKey(root,key)初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，先寻找二叉排序树中是否有此数据的，有则返回次数据项的地址给指针变量，没有则就返回该数据按照二叉排序树规则，应该插入位置的父节点地址。void DeleteKey(root,key);初始条件：二叉排序树不为空，存在根节
10、点；操作结果：输入一个字符型数据，调用BSTree *SearchKey(root,key)函数，先寻找二叉排序树中是否有此数据的，有则返回次数据项的地址给指针变量，然后就此节点的特征分为四类：删除叶子节点；删除只有右孩子的节点；删除只有左孩子的节点；删除左右孩子都有的节点，根据结点类型进入不同删除模块，删除结点，修改相应二叉树结点指针，返回主菜单；没有则就返回提示语句“没有找到该数据”。void ChainTree_LDR(root)初始条件：二叉排序树不为空，存在根节点；操作结果：按照中序遍历并输出有序的数据序列。 ADT BTBT抽象数据类型的设计class BTprivate:BST
11、root;public:BT() :root(NULL) BST InitRoot();void Inserter(BSTree *t,char key);BSTree *SearchKey(BSTree *t,char key);void DeleteKey(BSTree *t,char key);void ChainTree_LDR(BSTree *bt);第三章 详细设计3.1 输入模块设计BSTree* BT:InitRoot()BST node;if(node=new BSTree)coutnode-data;node-left=NULL;node-right=NULL;node-f
12、ather=NULL;return node;/初始化根节点3.2 添加模块设计if(root=NULL)cout空树!禁止操作!;coutendl;elsecoutn;fflush(stdin);for(i=0;in;i+)coutkey;a.Inserter(root,key);fflush(stdin);3.3 输出模块设计coutendl;if(root=NULL)cout空树!禁止操作!;coutendl;elsea.ChainTree_LDR(root);coutendl;break;3.4 查找模块设计BSTree *key;coutkey2;key=a.SearchKey(root,key2);if(key-data=key2)cout二叉树中有此数据!;coutendl;elsecout二叉树中没有此数据!;coutendl;排序模块设计3.5 删除模块设计if(root=NULL)cout 空树!禁止操作!;coutendl;elsecout请输入你要删除
