数据结构实习报告.doc

1、数据结构实习报告题目：假设叶子时排好序的，请编写一段完整的程序插入一个新的顶点到一棵 2-3 树中班级：F0203305 姓名：聂青阳 学号：5020339113 完成日期：2018 年 12 月 12 日一、 需求分析1. 演示以 2-3 树为数据结构存储的集合的插入运算。2. 为简便起见，演示用的集合中元素类型为正整数。3. 演示用程序采用键盘输入待插入元素的方式。4. 本程序特色之一为漂亮的树型输出。5. 当输入元素在集合中已存在时，将收到 false 返回值，并打印错误！二、 概要设计本实习报告的概要设计部分将不采用抽象数据类型的描述方式，而是根据实际，采用面向对象的 UML 语言描述

2、，并且考虑到泛型使用，所有的类均采用模板。以 UML 语言描述的概要设计图：由于篇幅限制，这里没有给出具体方法和字段的注释，在附件中的 Tree23.mdl(UML 格式文件，请使用 Rational Rose 打开 )和源代码中都有详细的描述。三、 详细设计1. Tree23 类template class Tree23protected:Tree23Node *root; /2-3树的根结点public:/构造函数Tree23 (Tree23Node *_root = NULL) root = _root;/析构函数void Destroy (void) coutDelTree();cou

3、t *node = new Tree23Node (data);Tree23Node *temp;if (root = NULL) root = node;else temp = root-InsertNode(node);if (temp != NULL) root = temp;return true;/打印所有结点void ShowAll() root-ShowTree();/搜索指定结点Tree23Node *Search(TYPE *d) if (root = NULL) return NULL;return root-Search(d);/检验当前结点是否存在bool IsExis

4、ting(Tree23Node *node) if (root = NULL) return false;if (root-Search(node) != NULL) return true;else return false;/树型打印本树virtual void formatPrint() if (root = NULL) coutformatPrint(false, “);2. Tree23Node 类template class Tree23Nodeprotected:char *name; /结点名称TYPE *data; /结点数据域TYPE *lmax; /左子树最大结点值TYP

5、E *mmax; /中子树最大结点值TYPE *rmax; /右子树最大结点值，也是整棵树的最大结点值Tree23Node *lchild; /左子树指针Tree23Node *mchild; /中子树指针Tree23Node *rchild; /右子树指针Tree23Node *parent; /父结点指针public:/构造函数Tree23Node(TYPE *_data = NULL,Tree23Node *_lchild = NULL,Tree23Node *_mchild = NULL,Tree23Node *_rchild = NULL,Tree23Node *_parent =

6、NULL,TYPE *_lmax = NULL,TYPE *_mmax = NULL,TYPE *_rmax = NULL,char *_name = NULL) name = _name;if (name = NULL) name = new char1;name0 = 0;data = _data;lchild = _lchild;rchild = _rchild;mchild = _mchild;parent = _parent;lmax = _lmax;mmax = _mmax;rmax = _rmax;/析构函数void Destroy(void) cout *b) if (b =

7、NULL) return false;else if (*data GetData() return true;else return false;bool IsBelow(TYPE *b) if (b = NULL) return false;else if (*data mmax;/获得右子树最大结点值TYPE *GetRMax(void) if (IsLeaf() return data;return rmax;/获得数据域TYPE *GetData() return this-data;/设置父结点void SetParent(Tree23Node *p) parent = p;/判断

8、本结点是否为叶子结点bool IsLeaf() if (lchild = NULL else return false;/判断本结点是否为叶子的直接父结点bool IsLeafFather() if (!IsLeaf()if (lchild-IsLeaf() return true;return false;/判断本结点是否是根结点bool IsRoot() if (parent = NULL) return true;else return false;/在本树中搜索和参数d相同的结点，返回NULL表示没有找到Tree23Node *Search(TYPE *d) /coutSearch(d

9、);else if (*d Search(d);else if (rchild != NULL) return rchild-Search(d);else return NULL;Tree23Node *Search(Tree23Node *node) if (IsLeaf() if (*data = *node-GetData() return this;else return NULL;else if (node-IsBelow(lmax) return lchild-Search(node);else if (node-IsBelow(mmax) return mchild-Search

10、(node);else return rchild-Search(node);/删除以本结点为根的子树void DelTree() if (lchild != NULL) lchild-DelTree();if (mchild != NULL) mchild-DelTree();if (rchild != NULL) rchild-DelTree();this-Destroy();/在本树中插入一个结点，返回新的根结点指针.返回空指针表示根结点没有改变。Tree23Node *InsertNode(Tree23Node *node) Tree23Node *root = NULL;/如果是叶子

11、结点if (IsLeaf() /如果既是叶子结点是根结点if (IsRoot() if (node-IsBelow(this) root = new Tree23Node (NULL, node, this, NULL, NULL, node-GetData(), this-GetData(), this-GetData();else root = new Tree23Node (NULL, this, node, NULL, NULL, this-GetData(), node-GetData(), node-GetData();node-SetParent(root);this-SetPa

12、rent(root);/如果是叶子结点但不是根结点else root = this-parent-InsertTree(node);/如果该插在左子树上else if (node-IsBelow(GetLMax() root = lchild-InsertNode(node);/如果该插在中子树上else if (node-IsBelow(GetMMax() | rchild = NULL) root = mchild-InsertNode(node);/如果该插在右子树上else root = rchild-InsertNode(node);return root;/在本树中插入一棵子树Tr

13、ee23Node *InsertTree(Tree23Node *node) /如果当前结点未满三个子树，那么就在此结点上插入if (rchild = NULL) if (*node-GetRMax() GetRMax() rchild = mchild;mchild = lchild;lchild = node;node-SetParent(this);rmax = mmax;mmax = lmax;lmax = node-GetRMax();else if (*node-GetRMax() GetRMax() rchild = mchild;mchild = node;node-SetPa

14、rent(this);lmax = lchild-GetRMax();rmax = mmax;mmax = node-GetRMax();else rchild = node;node-SetParent(this);lmax = lchild-GetRMax();mmax = mchild-GetRMax();rmax = node-GetRMax();return NULL;/如果当前结点已满三棵子树，那么就两两拆开，把左半子树接于当前结点，右半交付于上一层父结点重新插入else Tree23Node *temp;Tree23Node *root;if (*node-GetRMax() G

15、etRMax() temp = new Tree23Node (NULL, mchild, rchild, NULL, NULL, mchild-GetRMax(), rchild-GetRMax(), rchild-GetRMax(), NULL);mchild-SetParent(temp);rchild-SetParent(temp);mchild = lchild;lchild = node;rchild = NULL;node-SetParent(this);lmax = node-GetRMax();rmax = mmax = lmax;else if (*node-GetRMax

16、() GetRMax() temp = new Tree23Node (NULL, mchild, rchild, NULL, NULL, mchild-GetRMax(), rchild-GetRMax(), rchild-GetRMax(), NULL);mchild-SetParent(temp);rchild-SetParent(temp);mchild = node;rchild = NULL;node-SetParent(this);mmax = rmax = node-GetRMax();else if (*node-GetRMax() GetRMax()temp = new T

17、ree23Node (NULL, node, rchild, NULL, NULL, node-GetRMax(), rchild-GetRMax(), rchild-GetRMax(), NULL);else temp = new Tree23Node (NULL, rchild, node, NULL, NULL, rchild-GetRMax(), node-GetRMax(), node-GetRMax(), NULL);rchild-SetParent(temp);node-SetParent(temp);rmax = mmax;rchild = NULL;/如果当前结点是根结点，那

18、么新建一结点作为根结点if (IsRoot() root = new Tree23Node (NULL, this, temp, NULL, NULL, this-GetRMax(), temp-GetRMax(), 0, NULL);this-parent = root;temp-SetParent(root);/否则把右半树交给父结点处理else root = parent-InsertTree(temp);return root;/打印当前结点信息void ShowNode() coutShowTree();if (mchild != NULL) mchild-ShowTree();if

19、 (rchild != NULL) rchild-ShowTree();/树型打印本结点为根的子树void formatPrint(bool isEnd, char *prefix) if (!this-IsRoot() coutformatPrint(!mchild, nextPrefix);if (mchild) mchild-formatPrint(!rchild, nextPrefix);if (rchild) rchild-formatPrint(true, nextPrefix);3. 测试主程序int _tmain(int argc, _TCHAR* argv)Tree23 t

20、= Tree23 ();char ans = y;int toInsert;while (ans != n General:Input(“请输入要插入的结点数据域的值：“, toInsert);if (!t.Insert(new int(toInsert) cout“此结点已存在，插入失败！“endl;General:pause();else cout“结点“toInsert“插入成功！“endl;t.formatPrint();General:pause();General:Input(“还要继续插入吗？（Y/N）“, ans);General:pause();四、 调试分析1. 2-3 树

21、的结构以前没有接触过，而且在存储方式上和一般的树不一样，所以无法重用已经编写好的 Tree 类，一切都是从头开始做，于是便使用了新的开发工具 Visual Studio .NET 2003，采用了最新的 Visual C+ 7.0，因此在语法上会有一些不一样，这个在最初的适应过程中占了比较多的时间。2. 最初只是考虑在插入结点的时候只要递归地调用 Insert 方法即可，后来发现当插入点的子树已经有三棵的时候还需要回溯到父结点重新执行插入动作，而此时的插入为插入子树，并非插入结点，于是便把这两个操作分开，分别为 InsertNode 和 InsertTree。3. 开始由于思路上不是非常清晰，

22、分类讨论插入结点情况时，造成好几处都忘记修改 lmax和 mmax 的值，造成许多不必要的麻烦。4. 由于把 Insert 的方法直接交给结点对象来做，于是在修改根结点的时候便会有一些麻烦，因为子结点无法直接修改根结点的指向，于是便想到使用 Insert 方法的返回值来传递被修改过的新根结点，最后令 Tree23 类对象的 root 域指向新根结点。5. 本算法正如教科书上所分析，最多进行了 2-3 树的深度次递归，所以时间复杂性为O(log2n)。但是由于算法的缘故，每个结点对象比原计划多出了一个 rmax 域，造成了空间复杂性的上升，但是并不增加空间耗费的级别。6. 由于在算法中出现了许多

23、层次的判断，所以不可避免地使得算法的效率并不是如理论上的那样快，但是比普通算法比起仍然要快许多，这个是由时间复杂性的级别决定的。五、 用户手册1. 本程序运行环境为控制台（Console ） ，执行文件为 2-3Tree.exe。2. 只需运行该程序便可看到演示结果。六、 说明本程序开发环境为 Microsoft Visual Studio .NET 2003，使用高级语言为 Visual C+ .NET 7.0。七、 附录源程序文件名清单：文件名 说明2-3Tree.cpp 主程序Stdafx.cpp 系统生成连接用文件Tree23.h 定义了 Tree23 类的头文件Tree23Node.h 定义了 Tree23Node 类的头文件Random.h 定义了随机数相关函数的头文件Stdafx.h 系统生成头文件