长沙学院课程设计利用二叉树对顺序表进行排序大学论文.doc

《长沙学院课程设计利用二叉树对顺序表进行排序大学论文.doc》由会员分享，可在线阅读，更多相关《长沙学院课程设计利用二叉树对顺序表进行排序大学论文.doc（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、长 沙 学 院课程设计说明书题目 利用二叉树对顺序表进行排序系(部)数学与计算机科学专业(班级)软件工程（2015级5班）姓名邝东学号B20150304513指导教师李运兰 刘钢钦起止日期2016.12.122016.12.23课程设计任务书课程名称：数据结构与算法设计题目：利用二叉排序树对顺序表进行排序。已知技术参数和设计要求：问题描述：利用二叉排序树对顺序表进行排序。基本要求：(1) 生成一个顺序表L;(2) 对所生成的顺序表L构造二叉排序树;(3) 利用栈结构实现中序遍历二叉排序树;(4) 中序遍历所构造的二叉排序树将记录由小到大输出。测试数据：用伪随机数产生程序产生，表长不小于20。选

2、作内容：用实现二叉排序树的插入和删除操作。设计工作量：40课时工作计划：理论课结束后两周进行课程设计，软件开发如下，一周完成。其中，两教学课时用于题目分析与介绍。其他教学可是用于程序设计。计划时间教学内容教学方式第16周，2课时项目说明及题目分析讲授与讨论第16周，20课时项目设计与实现现场指导第17周，20课时，项目实现与调试与答辩现场检查、报告、答辩注意事项n 提交文档 长沙学院课程设计任务书（每学生1份） 长沙学院课程设计鉴定表（每学生1份） 长沙学院课程设计说明书（每学生1份）指导教师签名： 日期： 2016.12.6 教研室主任签名： 日期：系主任签名： 日期：长沙学院课程设计鉴定表

3、姓名 邝东学号B20150304513专业软件工程班级15级5班设计题目利用二叉排序树对顺序表进行排序指导教师李运兰刘钢钦指导教师意见：评定等级： 教师签名： 日期： 答辩小组意见：评定等级：答辩小组长签名：日期：教研室意见：教研室主任签名： 日期： 系（部）意见：系主任签名：日期：说明课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类；2摘 要本次课程设计，依次运用了线性表，顺序栈，二叉树等知识，设计了一个利用二叉排序树对顺序表进行排序的程序，该程序是基于顺序表建立二叉排序树，通过在二叉树上插入，删除数据，再将二叉树上的数据存入栈中，然后输出，从而达到排序的功能。该程序生成的数据均为

4、伪随机数，其主要功能包括二叉树的建立、结点的插入与删除以及遍历输出。关键词： 插入、删除、二叉排序树、中序遍历 目 录摘 要I第1章 设计内容与要求11.1课程名称：数据结构与算法课程设计11.2设计要求1第2章 需求分析22.1功能模块22.2设计环境2第3章 概要设计33.1功能结构33.2系统流程图4第4章 详细设计与实现54.1新建二叉树模块54.2 插入模块54.3 删除模块64.4遍历模块7第5章 测试95.1新建模块测试95.2插入模块测试95.3删除模块测试105.4遍历模块测试11总 结12参考文献12附录 源代码13第1章 设计内容与要求1.1课程名称：数据结构与算法课程设

5、计设计题目：利用二叉排序树对顺序表进行排序1.2设计要求 具体要求：(1) 生成一个顺序表L;(2) 对所生成的顺序表L构造二叉排序树;(3) 利用栈结构实现中序遍历二叉排序树;(4) 中序遍历所构造的二叉排序树将记录由小到大输出。测试数据：用伪随机数产生程序产生，表长不小于20。选作内容：用实现二叉排序树的插入和删除操作。第2章 需求分析2.1功能模块为了解决为解决利用二叉排序树对顺序表进行排序，开发的系统，该系统包含4大功能模块，其中包含：二叉树的建立，结点的插入与删除和二叉树的中序遍历。建立模块，该模块能够在程序运行时利用伪随机数建立二叉树。插入模块，该模块能在二叉树上插入节点。删除模块

6、，该模块能够删除二叉树上的节点。中序遍历模块，该模块能将二叉树从小到大输出。2.2设计环境 Windows 7系统、Dev c+ 4.9.9.2下编译运行第3章 概要设计3.1功能结构本程序主要实现的有六个功能，首先创建二叉排序树，完成后出现菜单界面，菜单界面的功能有：二叉排序树的插入、删除、中序遍历、二叉排序树的重建、退出。 开始 Switch 2 Switch 1 Switch 3 Switch 4 Switch 5新建二叉树增加结点删除结点中序遍历输入i结束 图3.1 功能结构图3.2系统流程图主要函数struct int_linklist*init();/ 初始化顺序表void add

7、(struct int_linklist*, int);/顺序表增加结点void printf_list(struct int_linklist *);/输出已经创建好的顺序表void initstack(linkstack *);/初始化栈void push_stacks(linkstack *, Selem );/进栈函数void pop_stacks(linkstack *,Selem&);/出栈函数bool empty_stack(linkstack *);/判断栈是否为空的函数BTNode *init_BSTree(Btree);/初始化二叉排序树Btree BSTree_fund(

8、);/建立一个二叉排序树的函数bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);/判断该值是否在二叉树存在bool insert_BSTree(Btree&, valuetype);/插入一个数值，返回0或1，判断是否插入成功bool Delete_BSTree(Btree&, keytype);/删除函数，找到要删除的数值，调用delete_value（）函数，返回0或1判断删除是否成功 void delete_value(Btree &tree);/删除结点void inoder_rec(Btree);/中序非递归遍历二叉排序树第4章

9、 详细设计与实现4.1新建二叉树模块Btree BSTree_fund() struct int_linklist *lists = NULL;Btree tree = NULL;int n;lists = init();/初始化顺序表srand(unsigned)time(NULL); /伪随机函数的初始化printf(please input how many numbers:n);scanf_s(%d, &n); /输入要插入多少的数for (int i = 0; i head-next;while (p != NULL) insert_BSTree(tree, p-element);p

10、 = p-next;/调用insert_BSTree函数构造二叉树return tree;4.2 插入模块bool Search_BSTree(Btree tree, keytype value, Btree &parents, Btree &child) /寻找函数，判断二叉排序树中是否有该值，有返回1，无返回0child = tree;/子节点等于根节点while (child) /如果子节点child不为空，则执行下面代码if (value = child-data) /如果值等于child-data，则表示找到，返回1return 1;else if (value data) /如果该

11、值小于child-data，则向左子树进行查找parents = child; /parents纪录child结点的上一个结点，相当于记录父节点child = child-lchild;/将child的左孩子赋值给childelse /否则向右子树查找parents = child;/记录父节点child = child-rchild;/将child的右孩子赋值给childreturn 0; /如果没有找到该值则返回0bool insert_BSTree(Btree &tree, keytype value) Btree parents, child; /定义指针if (!Search_BST

12、ree(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，就插入到左子树parents-lchild = S;else parents-rchild = S; /反之，插

13、入到右子树return 1;4.3 删除模块bool Delete_BSTree(Btree &tree, keytype value) /删除函数if (!tree)return 0; /tree为空，则表示删除功能不能执行else if (value = tree-data) /如果找到与value值相同的指针，调用delete_value函数进行删除delete_value(tree);return 1;/删除成功else if (value data) /value小于结点的值，往左子树进行寻找return Delete_BSTree(tree-lchild, value);else

14、/否则向右子树寻找return Delete_BSTree(tree-rchild, value);/printf(%dn, tree-data);void delete_value(Btree &p) Btree q = NULL, s = NULL;if (p-lchild & p-rchild) /删除的结点，左右子树都不为空的情况q = p; s = p-lchild; /q记录,s设为删除结点的左结点while (s-rchild) q = s; s = s-rchild;/进行循环，找到最右边的那个结点p-data = s-data; /把找到的最右边结点的关键字赋值给p的关键字i

15、f (s-lchild) q-rchild = s-lchild; /挂接子树free(s); /删除s这个结点else if (p-lchild | p-rchild) /左右子数存在一个的情况 if (!p-rchild) /右子树为空，所以挂接到左子树q = p; p = p-lchild; free(q);else /左子树为空，所以挂接到右子树上q = p; p = p-rchild; free(q); else if (!p-lchild & !p-rchild) free(p);/左右都为空，直接删除4.4遍历模块void inoder_rec(Btree T) linkstac

16、k S ;initstack( &S);/初始化一个栈Selem e;Btree p = T;while (p | !(S.count = 0) /当栈不为空或者p不为空时执行while(p) push_stacks(&S, p); /p不为空，则进栈p = p-lchild; /对左子树进行遍历if(!empty_stack(&S) e = Get_top(S, e); /当栈不为空时，取栈顶，输出栈顶指针所指向的data值printf(%dn,e - data);pop_stacks(&S, p); /出栈，对右子树进行遍历p = p-rchild;第5章 测试5.1新建模块测试新建一个包

17、含20个伪随机数的二叉树5.2插入模块测试插入数据35，中序遍历查看结果。5.3删除模块测试删除数据31，中序遍历查看结果。5.4遍历模块测试直接中序遍历查看结果。总 结这次实训，我使用Dev C+这个程序设计了一个利用二叉排序树对顺序表进行排序的程序，它能够通过二叉排序树对顺序表进行插入，删除，排序等操作。通过这次学习，我对二叉排序树有了进一步的了解，学会了如何对一个二叉排序树进行插入、删除等操作，也进一步加深了我对顺序表和栈的理解。在实训之前，无论是顺序表、栈还是二叉树，我都处于一种一知半解的状态，因为这个学期我很少自己动手编写代码。编写的过程中也遇到了很多问题，有些解决了，有些没解决。比

18、如我想构造一个函数，将二叉树输出来，但是始终不得要领，最后只能放弃。编写代码的的过程中，我发现，对于一个比较复杂的问题，可以尝试把它变为两个来完成。比如，在删除节点这个问题上，我就将删除函数分为了两个函数，一个查找，一个删除。这样虽然看上去好像复杂了一些，但是实际上无论是程序的可读性，还是检查时的方便性都有了显著的提升。参考文献1 严蔚敏.数据结构C语音版.北京：清华大学出版社，1997.4（2014.11重印）附录 源代码#include#include#include#include/#includeunsigned int n = 30;typedef int keytype;typed

19、ef int valuetype;typedef int listtype;struct linklist struct linklist *next;int element;struct int_linklist struct linklist *head;int counts;typedef struct BSTNode keytype data;struct BSTNode *lchild, *rchild;BTNode, *Btree;typedef Btree Selem;typedef struct snode Selem data;struct snode *next;snode

20、, *linkst;typedef struct linkstack linkst top;int count;linkstack;struct int_linklist*init();/初始化顺序表 void add(struct int_linklist*, int); /顺序表增加节点 void printf_list(struct int_linklist *);/输出已经创好的顺序表 void initstack(linkstack *);/初始化栈 void push_stacks(linkstack *, Selem );/入栈函数 void pop_stacks(linksta

21、ck *,Selem&);/出栈函数 bool empty_stack(linkstack *);/判断栈是否为空 BTNode *init_BSTree(Btree);/初始化二叉排序树 Btree BSTree_fund();/建立一个二叉排序树的函数 bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);/判断该值是否在排序树中存在 bool insert_BSTree(Btree&, valuetype);/插入一个数 bool Delete_BSTree(Btree&, keytype);/删除函数 void delete_valu

22、e(Btree &tree);/删除节点 void inoder_rec(Btree);/中序非递归遍历二叉树 int main() int i;Btree tree = NULL;tree = BSTree_fund();while (1) printf(ttt*n); printf(ttt* 1.插入 n);printf(ttt* 2.删除 n);printf(ttt* 3.中序遍历 n);printf(ttt* 4.重建二叉树 n);printf(ttt* 5.退出 n);printf(ttt*nn);printf(请输入你需要的操作:n);scanf(%d, &i);switch (i

23、) case 1: keytype value;printf(请输入你要插入的数字:n);scanf(%d, &value);if (insert_BSTree(tree, value)printf(插入成功n);else printf(插入失败n );break;case 2: keytype key;printf(请输入你要删除的数字：n);scanf(%d, &key);if (Delete_BSTree(tree, key) printf(删除成功n);else printf(删除失败n ); break;case 3: inoder_rec(tree); printf(n); bre

24、ak;case 4: system(cls);tree = BSTree_fund(); if (tree)printf(重建成功n); else printf(重建失败n); break;case 5: exit(1); break;return 0;struct int_linklist* init() struct int_linklist*lists;lists = (struct int_linklist*)malloc(sizeof(struct int_linklist*);lists-head = (struct linklist*)malloc(sizeof(struct l

25、inklist);lists-head-element = -1;lists-counts = 0;lists-head-next = NULL;return lists;void add(struct int_linklist *lists, int value) struct linklist *p;p = (struct linklist *)malloc(sizeof(struct linklist);p-next = NULL;p-element = value;p-next = lists-head-next;lists-head-next = p;lists-counts+;vo

26、id printf_list(struct int_linklist *lists) struct linklist *p;p = lists-head-next;while (p != NULL) printf(%dn, p-element);p = p-next;void initstack(linkstack *stacks) stacks-top = (linkst)malloc(sizeof(snode);stacks-top = NULL;stacks-count = 0;Selem Get_top(linkstack stacks, Selem &e) e = stacks.to

27、p-data;return e;void push_stacks(linkstack *stacks, Selem e) linkst p = (linkst)malloc(sizeof(snode);p-data = e;p-next = stacks-top;stacks-top = p;stacks-count+;void pop_stacks(linkstack *stacks,Selem &e) linkst p;e = stacks-top-data;p = stacks-top;stacks-top = stacks-top-next;free(p);stacks-count-;

28、bool empty_stack(linkstack *stacks) if (stacks-count = 0)return 1;else return 0;BTNode *init_BSTree(Btree tree) Btree root = tree;return root;bool Search_BSTree(Btree tree, keytype value, Btree &parents, Btree &child) child = tree;while (child) if (value = child-data) return 1;else if (value data) p

29、arents = child;child = child-lchild;else parents = child;child = child-rchild;return 0;bool insert_BSTree(Btree &tree, keytype value) Btree parents, child;if (!Search_BSTree(tree, value, parents, child) Btree S = (BTNode*)malloc(sizeof(BTNode);S-data = value;S-lchild = NULL;S-rchild = NULL;if (!tree

30、) tree = S;else if (value data) parents-lchild = S;else parents-rchild = S;return 1;Btree BSTree_fund() int D; struct int_linklist *lists = NULL;Btree tree = NULL;int n;lists = init();srand(unsigned)time(NULL);printf(请输入随机数的个数:n);scanf(%d, &n);printf(%d个随机数为:n,n);for (int i=0; ihead-next;while (p !=

31、 NULL) insert_BSTree(tree, p-element);p = p-next;return tree;bool Delete_BSTree(Btree &tree, keytype value) if (!tree) return 0;else if (value = tree-data) delete_value(tree);return 1;else if (value data) return Delete_BSTree(tree-lchild, value);else return Delete_BSTree(tree-rchild, value);/printf(

32、%dn, tree-data);void delete_value(Btree &p) Btree q = NULL, s = NULL;if (p-lchild & p-rchild) q = p; s = p-lchild;while (s-rchild)q = s; s = s-rchild;p-data = s-data; if(s-lchild) q-rchild = s-lchild;free(s);else if (p-lchild | p-rchild) if (!p-rchild) q = p; p = p-lchild; free(q);else q = p; p = p-

33、rchild; free(q);else if (!p-lchild & !p-rchild) free(p);void inoder_rec(Btree T) linkstack S ;initstack( &S);Selem e;Btree p = T;while (p | !(S.count = 0) while(p) push_stacks(&S, p);p = p-lchild;if(!empty_stack(&S) e = Get_top(S, e);printf(%5d,e - data);pop_stacks(&S, p);p = p-rchild;图和表的格式参考图例编号为：章数.图序号 （a）始值加噪声时 （b）用离散Hopfield网络产生的访问路径 求解得的访问路径图1.2 10城市TSP计算机模拟结果