2015广工数据结构实验报告平衡二叉树.docx

数据结构设计性实验报告 课程名称_____数据结构实验 _ 题目名称 平衡二叉树 学生学院__ 计算机学院______ 专业班级_ 学 号____ ______ 学生姓名____ _ ___ 指导教师______ ____ 2015年6月14日   目录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc424061894 一、 设计任务、要求以及所用环境及工具 PAGEREF _Toc424061894 \h 4 HYPERLINK \l _Toc424061895 实验设计任务 PAGEREF _Toc424061895 \h 4 HYPERLINK \l _Toc424061896 实验要求 PAGEREF _Toc424061896 \h 4 HYPERLINK \l _Toc424061897 编程环境 PAGEREF _Toc424061897 \h 4 HYPERLINK \l _Toc424061898 抽象数据类型及接口简要描述 PAGEREF _Toc424061898 \h 5 HYPERLINK \l _Toc424061899 抽象数据类型 PAGEREF _Toc424061899 \h 5 HYPERLINK \l _Toc424061900 接口简要描述 PAGEREF _Toc424061900 \h 7 HYPERLINK \l _Toc424061901 算法设计 PAGEREF _Toc424061901 \h 8 HYPERLINK \l _Toc424061902 程序测试 PAGEREF _Toc424061902 \h 17 HYPERLINK \l _Toc424061903 测试代码 PAGEREF _Toc424061903 \h 17 HYPERLINK \l _Toc424061904 测试结果 PAGEREF _Toc424061904 \h 18 HYPERLINK \l _Toc424061905 测试分析 PAGEREF _Toc424061905 \h 20 HYPERLINK \l _Toc424061906 思考与小结 PAGEREF _Toc424061906 \h 21 设计任务、要求以及所用环境及工具 实验设计任务 以教材中讨论的各种抽象数据类型为对象，利用C语言的数据类型表示和实现其中某个抽象数据类型。可选的抽象数据类型如下表所列： 编号 抽象数据类型 基本难度 存储结构 1 栈和队列 1.0 顺序 和 链接 2 线性表 1.0 顺序 和 链接 3 哈希表 1.1 任选 4 二叉树 1.2 任选 5 堆 1.2 任选 6 二叉排序树 1.2 任选 7 平衡二叉树 1.3 任选 8 树 1.2 任选 9 并查集 1.2 任选 10 B树 1.4 任选 11 有向图 1.3 任选 12 无向图 1.3 任选 13 有向带权图 1.3 任选 注：如果基本操作数量较多，可选择实现其中一个基本操作子集。 实验要求 实验要求如下： 1．首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。 若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。 2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。 3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。 4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。 编程环境 本次实验设计采用C++语言，在Microsoft Visual Studio2010 IDE下完成。 所创建的项目类型Win32控制台应用程序： 抽象数据类型及接口简要描述 本次数据结构实验设计我选择的是二叉平衡树（AVL），使用C++面向对象编程语言实现。利用C++泛型编程技术完成AVL类AVLTree。 抽象数据类型 平衡二叉树结点的ADT为： template typename T class AVLTreeNode { public: T _key; //结点关键字 int _bf; //结点平衡因子 AVLTreeNode *_lchild ;