1.1课程名称：数据结构与算法课程设计 ................................................................................ 6 1.2 设计要求： ........................................................................................................................... 7 第2章 需求分析 .............................................................................................................................. 7
2.1设计目的 ................................................................................................................................ 7 2.2 设计环境 ........................................................................................................................... 8 第三章概要设计 .................................................................................................................................. 8
3.1 功能结构 ............................................................................................................................... 8 3.2函数的结构体 ........................................................................................................................ 9 3.3系统主要的函数 .................................................................................................................. 10 第四章详细设计 ................................................................................................................................ 11
4.1插入模块的设计 .................................................................................................................. 11 4.2删除模块的设计 .................................................................................................................. 12 4.3遍历模块设计 ...................................................................................................................... 13 4.4树型打印模块的设计 .......................................................................................................... 14 4.5重建二叉树模块的设计 ...................................................................................................... 15 第五章模块测试 ................................................................................................................................ 16
5.1插入模块测试 ...................................................................................................................... 16 5.2删除插入模块测试 .............................................................................................................. 17 5.3遍历模块测试 ...................................................................................................................... 18 5.4树型打印模块测试 .............................................................................................................. 19 5.5二叉排序树重建模块测试 .................................................................................................. 20 第六章总结 ........................................................................................................................................ 22 第七章附录源代码 ............................................................................................................................ 23
第1章 设计内容与要求
1.1课程名称：数据结构与算法课程设计
设计题目：利用二叉排序树对顺序表进行排序
问题描述：利用二叉排序树对顺序表进行排序。
6 / 31
1.2设计要求：
(1) 生成一个顺序表L;
(2) 对所生成的顺序表L构造二叉排序树; (3) 利用栈结构实现中序遍历二叉排序树;
(4) 中序遍历所构造的二叉排序树将记录由小到大输出。 测试数据：
用伪随机数产生程序产生，表长不小于20。 选作内容：
用实现二叉排序树的插入和删除操作。
第2章 需求分析
2.1设计目的
本次构造的是一个二叉排序树，主要的功能有二叉排序树的建立、节点的插入与删除，二叉树的中序遍历、树型打印、以及重建一个新的二叉排序树。
7 / 31
二叉排序树 系统主菜单 建立 插入 删除 树型打印 中序遍历 退出
图2.1系统功能模块图
2.2设计环境
Windows 10系统、visual studio2015下编译运行
第三章概要设计
3.1 功能结构
本程序主要实现的有七个功能，首先创建二叉排序树，完成后出现菜单界面，菜单界面的功能有：二叉排序树的插入、删除、中序遍历、树形输出、二叉排序树的重建、退出。
8 / 31
创建二叉树 Switch(1) 插入结点 Switch(2) 删除结点 Switch(3) 中序遍历 Switch(4) Exit(0)退出 Switch(5) 树型打印 Switch(6) 重建二叉树 图3.1主要功能结构流程图
3.2函数的结构体
typedef int keytype; typedef int valuetype; typedef int listtype;
///////////////////////////// struct linklist {
9 / 31
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 struct snode {
Selem data; //定义栈的存储的数据 struct snode *next; //栈的指针 }snode, *linkst;
typedef struct linkstack {
linkst top; //定义栈的栈顶指针 int count; //统计栈里面的元素 }linkstack;
3.3系统主要的函数
struct int_linklist*init(); // 初始化链式顺序表
void add(struct int_linklist*, int); //链式顺序表增加结点
void printf_list(struct int_linklist *); //输出已经创建好的顺序表 /////////////////////
void emptyMessage(char *); //输出错误的提示
void initstack(linkstack *); //初始化链式栈
void push_stacks(linkstack *, Selem ); //进栈函数
void pop_stacks(linkstack *,Selem&); //出栈函数
10 / 31