《利用二叉排序树对顺序表进行排序》由会员分享，可在线阅读，更多相关《利用二叉排序树对顺序表进行排序（31页珍藏版）》请在金锄头文库上搜索。
1、 1 / 31 长 沙 学 院 课程设计说明书 题目 利用二叉排序树对顺序表进行排序 系(部) 专业(班级) 姓名 学号 指导教师 起止日期 2015.12.82015.12.15 2 / 31 课程设计任务书 课程名称：课程名称：数据结构与算法课程设计 设计题目：设计题目： 为了充分调动学生的学习积极性与主动性，适应不同兴趣、不同程度的学生对课程设计的要求， 本课程设计提供四个任选题。每个学生可以根据本人的兴趣及能力选择教师指定的选题，也可以自定 其他的选题。 1、一元多项式计算问题 2、迷宫问题 3、利用二叉排序树对顺序表进行排序 4、交通咨询系统 5、内部排序算法的比较 已知技术参数和设
2、计要求：已知技术参数和设计要求： 需求说明及要求 题目三：利用二叉排序树对顺序表进行排序 问题描述： 利用二叉排序树对顺序表进行排序。 基本要求： (1) 生成一个顺序表 L; (2) 对所生成的顺序表 L 构造二叉排序树; (3) 利用栈结构实现中序遍历二叉排序树; (4) 中序遍历所构造的二叉排序树将记录由小到大输出。 测试数据： 用伪随机数产生程序产生，表长不小于 20。 选作内容： 用实现二叉排序树的插入和删除操作。 各阶段具体要求：各阶段具体要求： 1、需求分析阶段 熟悉系统业务，从业务中抽取出系统的需求，形成完善的需求说明书。 2、系统设计阶段 根据需求，进行程序设计，包括定义系统
3、的界面、定义系统数据的存储方式等，形成完 3 / 31 善的设计说明书。 3、编码实现阶段 （1）完成代码编写 （2）要求代码编写规范 4、系统测试阶段 （1）完成功能调试 （2）要求完成必要的测试工作 5、交付实施阶段 （1）提交可正常执行的系统 （2）提交系统需求说明书、设计说明书、程序代码 （3）撰写课程设计报告书 （4）要求规范地书写文档 设计工作量：设计工作量： （1）软件设计：完成问题陈述中所提到的所有需求功能。 （2）论文：要求撰写不少于 3000 字的文档，详细说明各阶段具体要求。 工作计划：工作计划： 数据结构课程设计总学时数为2 周，其进度及时间大致分配如下： 序号 设计内
4、容 天数 1 分析问题，给出数学模型，选择数据结构 1 2 设计算法，给出算法描述 2 3 给出源程序清单 1 4 编辑、编译、调试源程序 5 5 编写课程设计报告 1 总 计 10 注意事项注意事项 提交文档提交文档 长沙学院课程设计任务书（每学生 1 份） 长沙学院课程设计鉴定表（每学生 1 份） 长沙学院课程设计说明书（每学生 1 份） 指导教师签名： 日期： 教研室主任签名： 日期： 系主任签名： 日期： 4 / 31 长沙学院课程设计鉴定表 姓名学号 专业班级 设计题目利用二叉排序树对顺序表进行排序指导教师 指导教师意见： 评定等级： 教师签名： 日期： 答辩小组意见： 评定等级：
5、答辩小组长签名： 日期： 教研室意见： 教研室主任签名： 日期： 系（部）意见： 系主任签名： 日期： 说明 课程设计成绩分“优秀” 、 “良好” 、 “及格” 、 “不及格”四类； 5 / 31 摘要摘要 数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据 结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结 构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，是 基于链式顺序表建立二叉排序树。主要功能有建立、重建、插入、删除以及遍历。 关键词：关键词：二叉排序树、中序遍历、插入结点、删除结点 目录 第 1 章设计内容与要求
6、 .7 6 / 31 1.1 课程名称：数据结构与算法课程设计 .7 1.2 设计要求： 7 第 2 章需求分析 .8 2.1 设计目的 .8 2.2 设计环境 8 第三章 概要设计 .9 3.1 功能结构 9 3.2 函数的结构体 .10 3.3 系统主要的函数 .10 第四章 详细设计 .12 4.1 插入模块的设计 .12 4.2 删除模块的设计 .13 4.3 遍历模块设计 .14 4.4 树型打印模块的设计 .15 4.5 重建二叉树模块的设计 .15 第五章 模块测试 .16 5.1 插入模块测试 .16 5.2 删除插入模块测试 .17 5.3 遍历模块测试 .18 5.4 树型
7、打印模块测试 .19 5.5 二叉排序树重建模块测试 .20 第六章 总结 .22 第七章 附录源代码 .23 第第 1 章章设计内容与要求设计内容与要求 1.11.1 课程名称：数据结构与算法课程设计课程名称：数据结构与算法课程设计 设计题目：设计题目： 利用二叉排序树对顺序表进行排序利用二叉排序树对顺序表进行排序 问题描述：利用二叉排序树对顺序表进行排序。 7 / 31 1.21.2 设计要求：设计要求： (1) 生成一个顺序表 L; (2) 对所生成的顺序表 L 构造二叉排序树; (3) 利用栈结构实现中序遍历二叉排序树; (4) 中序遍历所构造的二叉排序树将记录由小到大输出。 测试数据
8、： 用伪随机数产生程序产生，表长不小于 20。 选作内容： 用实现二叉排序树的插入和删除操作。 第第 2 章章需求分析需求分析 2.12.1 设计目的设计目的 本次构造的是一个二叉排序树，主要的功能有二叉排序树的建立、节点的插入与删除，二叉树的中 序遍历、树型打印、以及重建一个新的二叉排序树。 8 / 31 二叉排序树 系统主菜单 建 立 退 出 中 序 遍 历 树 型 打 印 删 除 插 入 图 2.1 系统功能模块图 2.22.2 设计环境设计环境 Windows 10 系统、visual studio2015 下编译运行 第三章第三章 概要设计概要设计 3.13.1 功能结构功能结构 本
9、程序主要实现的有七个功能，首先创建二叉排序树，完成后出现菜单界面，菜单界面的功能 有：二叉排序树的插入、删除、中序遍历、树形输出、二叉排序树的重建、退出。 9 / 31 创建二叉树 Switch(1) 插入结点 删除结点 重建二叉树 树型打印 Exit(0)退出 中序遍历 Switch(2) Switch(3) Switch(4) Switch(5) Switch(6) 图 3.1 主要功能结构流程图 3.23.2 函数的结构体函数的结构体 typedef int keytype; typedef int valuetype; typedef int listtype; / 10 / 31 s
10、truct linklist struct linklist *next; int element; /参数的数值 ; /顺序表结点的结构体 struct int_linklist struct linklist *head; /顺序表的头结点的定义 int counts; /对顺序表的元素的多少进行统计 ; / typedef struct BSTNode keytype data; /存放关键字的data struct BSTNode *lchild, *rchild; /定义二叉排序树的指针 BTNode, *Btree; / typedef Btree Selem; typedef s
11、truct snode Selem data; /定义栈的存储的数据 struct snode *next; /栈的指针 snode, *linkst; typedef struct linkstack linkst top; /定义栈的栈顶指针 int count; /统计栈里面的元素 linkstack; 3.33.3 系统主要的函数系统主要的函数 struct int_linklist*init(); / 初始化链式顺序表 void add(struct int_linklist*, int); /链式顺序表增加结点 void printf_list(struct int_linklis
12、t *); /输出已经创建好的顺序表 / void emptyMessage(char *); /输出错误的提示 void initstack(linkstack *); /初始化链式栈 void push_stacks(linkstack *, Selem ); /进栈函数 void pop_stacks(linkstack *,Selem 11 / 31 /出栈函数 bool empty_stack(linkstack *); /判断栈是否为空的函数 / BTNode *init_BSTree(Btree); /初始化二叉排序树 Btree BSTree_fund(); /建立一个二叉排序
13、树的函数 bool Search_BSTree(Btree, keytype, BTNode /判断该值是否在二叉树存在 bool insert_BSTree(Btree /插入一个数值，返回0或1，判断是否插入成功 bool Delete_BSTree(Btree /删除函数，找到要删除的数值，调用delete_value(Btree /删除这个结点 void inoder_rec(Btree); /中序非递归遍历二叉排序树 void PrintTree(Btree, int); /按树状图就行输出 / void menu(Btree); /函数的菜单界面 第四章第四章 详细设计详细设计 4
14、.14.1 插入模块的设计插入模块的设计 bool Search_BSTree(Btree tree, keytype value, Btree /子节点等于根节点 while (child) /如果子节点child不为空，则执行下面代码 if (value = child-data) /如果值等于child-data，则表示找到，返回1 return 1; 12 / 31 else if (value data) /如果该值小于child-data，则向左子树进行查找 parents = child; /parents纪录child结点的上一个结点，相当于记录父节点 child = chil
15、d-lchild; else parents = child; child = child-rchild; return 0; /如果不执行上面一段代码，或者没有找到，返回0 / bool insert_BSTree(Btree /定义指针 if (!Search_BSTree(tree, value, parents, child) /如果二叉排序树找不到该值，则插入 Btree S = (BTNode*)malloc(sizeof(BTNode); /申请一个结构体空间 S-data = value; /赋值 S-lchild = NULL; S-rchild = NULL; if (!tree) tree = S; /如果tree为空，则tree为s，设置根结点 else if (value data) /如果value data，就插入到左子树 par
