《数据结构课程设计报告二叉排序树实现集合的运算.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告二叉排序树实现集合的运算.doc（10页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计报告设计题目 二叉排序树实现集合的运算 班 级 信息管理1班 学 号 100502121 一 引言数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计程序中的数据采用“树形结构”作为其数据结构。而二叉排序树又是一种特殊的二叉树。本课程设中的二叉排序树是用来实现集合中的运算功能，一共要实现五项集合的基本的功能。它们分别是集合的元素判定，子集判定，交，并，差运算。实现这五项基本功能的目的是为了巩固和运用理论知识、锻炼
2、实践能力、构件合理知识结构和提高程序设计能力。二 正文1 需求分析1.1课程设计题目、任务及要求 （1） 用二叉排序树实现集合的元素判定，子集判定，集合的交，并，差的运算； （2） 集合的元素限整数； （3） 程序运行时要先显示题目，班级，学号，姓名，完成时间等信息。1.2 课程设计思想 a.用二叉排序树建立集合，然后用二叉排序树的算法实现集合的元素判定，子集判定，集合的交并差的运算；可见，要想完成集合的这些算法，最主要运用到了二叉排序树里面的查找算法，然后将数组与二叉排序树结合起来，来实现这些算法。b.查找函数采用递归的方式进行查找；对二叉排序树进行中序遍历采用递归函数的方式：在根结点不为空
3、的情况下，先访问左子树，再访问根结点，最后访问右子树。由于二叉排序树自身的性质，左子树小于根结点，而根结点小于右子树，所以中序遍历的结果是递增的。2 概要设计2.1 对二叉排序树的理解二叉排序树是一种动态数表。二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：（）每个结点都有一个作为搜索依据的关键码（key），所有结点的关键码互不相同；（）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；（）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；(4) 左、右子树本身又各是一棵；（5）左、右子树本身又各是一棵二叉排序树。2.2 建立二叉排序树（二叉链表做存
4、储结构）从空的二叉排序树开始，经过一系列的查找插入操作以后，生成一棵二叉排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。其过程可以描述为：BSTree createBST(int *iArr)/建立集合二叉排序树 BSTree t=NULL; /根结点KeyType key;int i=0;if(!*iArr)cinkey;while(key!=-1 & +ikey;for(i=1;ileft );cout keyright ); 详细设计和实现3.1主要功能模块设计 1.元素判定： 用查找的方法实现元素判定；
5、 BSTree searchBST(BSTree t,KeyType key) if(!t | key=t-key) return t; if(keykey) return searchBST(t-left,key); else return searchBST(t-right,key);改为返回指针，未找到时返回空指针 找到时返回所在位置，先判是不是空指针，非空了再判是不是相等了。2.子集判定：不懂怎么一个一个的来访问树结点，只好使个偷懒的方法啦，转成数组，再遍历数组，老师，别介意哦；只要在另一个集合中找到有没有与这个集合相等的元素就ok了。函数如下：int beyong(BSTree m,
6、BSTree n) int i,ArrayMaxElement=0inorder_btree2Arr(n,Array);for(i=1;i=*Array;i+)if(!searchBST(m,Arrayi) return 0;return 1;3.求并集：A+B=C中序遍历两个集合，先把A集合赋给C，然后把集合B的元素插入到C中就行了。void combineTree(BSTree A,BSTree B,BSTree &C)int i,ArrayMaxElement=0;inorder_btree2Arr(A,Array);C = createBST(Array);Array0=0;inord
7、er_btree2Arr(B,Array);for(i=1; i=*Array; i+) insertBST(C,Arrayi); 4.交集：AB=C 用查找的方法在B中查找A中的每一个元素，把查找到得元素构成一个新的新的集合C。 void joinTree(BSTree A,BSTree B,BSTree &C) int i,ArrayMaxElement=0,Array1MaxElement=0;inorder_btree2Arr(B,Array);for(i=1;i=*Array;i+)if(searchBST(A,Arrayi)Array10+; Array1Array10 = Arr
8、ayi;/求相交的所有元素if(Array10) C = createBST(Array1); /结果不空时 再组一个集合else C=NULL;5.求差集：A-B=C中序遍历A中的元素，在B中查找到这些元素，求出所有不属于B中的元素，在创建一颗二叉排序树集合C，把这些有元素放入到C中即可。void differencedTree(BSTree A,BSTree B,BSTree &C) int i,ArrayMaxElement=0,Array1MaxElement=0;inorder_btree2Arr(A,Array);for(i=1;i=*Array;i+)if(!searchBST(
9、B,Arrayi)Array10+; Array1Array10 = Arrayi;if(Array10) C = createBST(Array1); /结果不空时 再组一个集合else C=NULL;3.2主程序设计 根据题目要求，先输出题目，班级，姓名，日期等等； 然后实现题目的所要的一系列函数，调用着希望函数，实现所要求的集合的功能； 写了一个while循环，能够使程序反复执行下去。4 程序调试及操作 经过几天的反复调试和修改后，程序得以正常的运行，并实现所要求的函数的功能。 程序运行结果如下： 姓名，题目等的显示:集合的输入与中序遍历输出： 元素判定： 子集判定，交，并差的运算：三体
10、会与总结这次课程设计使我对数据结构认识深刻了许多，其中最深刻的是我理解了二叉排序树的含义和操作，同时也加深了对二叉树的理解。本课程设计运用了二叉排序树的创建、中序遍历、查找的功能。在进行搜索时，可以采用更好的搜索结构即动态搜索结构。在此次课设中，我遇到最大的一个问题是如何创建二叉排序树（还要结合不能提的要求来建立）以及怎样把集合与二叉排序树里联系起来来实现集合的一系列运算。通过查找资料，请教同学和老师，终于把它解决了。通过这一周课设，我已经学会用顺序表和二叉链表存储结构实现对二叉排序树的创建、中序遍历、查找、删除等操作。 但我同时也发现了自己许多不足之处。在这次可设中我同时用到了c语言和c+，
11、虽说有点不伦不类，但这更巩固了自己的C和C+的知识，呵呵，其实我知道这样不好，算是对自己的鼓励吧。 首先，对数据结构的掌握不够，虽然完成了课设，但是只用到了基本的结点及操作，在数据结构的选择上避重就轻，覆盖面较小，不能很好的体现各种数据结构的掌握度，同时也缺少了适当的锻炼，在这方面还需要去提高。 其次，在程序整体的设计上还不够完整，各模块可以适当增加内容，界面还可以更加人性化，这样整个程序才具有更强的美观性与实用性。 总而言之，这次课程设计给了我很大启发，我明白了，不管遇到什么困难，只抓住根源，不气馁，从不同方面，不同角度去攻破它，终究会成功，生活也是如此总而言之，这次课程设计给了我很大启发，我明白了，不管遇到什么问题，只要抓住根源，不气馁，从不同方面去攻破它，终究会成功，生活也是如此，风雨之后总会见彩虹！四参考文献1.曲朝阳等.数据结构.中国电力出版社,20072.唐发根.数据结构教程（第二版）.北京航空航天大学出版社,20043.潭浩强.程序设计.北京：清华大学出版社，20004.严蔚敏，吴伟民.数据结构.北京：清华大学出版,20015.殷人昆.数据结构.北京：清华大学出版社，20046.王晓东.数据结构与算法设计电子工业出版社 20027.陈慧南数据结构与算法 C+ 语言描述高等教育出版社 20058.窦延平等.数据结构与算法 C+上海交通大学出版社 2005
