数据结构实验报告

数据结构实验报告 一 题目要求 1 编程实现二叉排序树 包括生成 插入 删除 2 对二叉排序树进行先根 中根 和后根非递归遍历 3 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来 4 分别用二叉排序树和数组去存储一个班 50 人以上 的成员信息 至少包括学号 姓名 成绩 3 项 对比查找效率 并说明在什么情况下二叉排序树效率高 为什么 二 解决方案 对于前三个题目要求 我们用一个程序实现代码如下 include include include include Stack h 栈的头文件 没有用上 typedef int ElemType 数据类型 typedef int Status 返回值类型 定义二叉树结构 typedef struct BiTNode ElemType data 数据域 struct BiTNode lChild rChild 左右子树域 BiTNode BiTree int InsertBST BiTree T data key T lChild T rChild NULL return 1 else if keydata InsertBST T lChild key else if key T data InsertBST T rChild key else return 0 BiTree CreateBST int a int n 创建二叉树函数 BiTree bst NULL int i 0 while irChild 右子树为空 重接它的左子树 q T T T lChild free q else if T lChild 若左子树空 则重新接它的右子树 q T T T rChild else q T s T lChild while s rChild q s s s rChild T data s data s 指向被删除结点的前驱 if q T q rChild s lChild else q lChild s lChild free s return 1 删除函数 在 T 中 删除 key 元素 int DeleteBST BiTree else if key T data return Delete T else if keydata return DeleteBST T lChild key else return DeleteBST T rChild key int PosttreeDepth BiTree T 求深度 int hr hl max if T NULL hl PosttreeDepth T lChild hr PosttreeDepth T rChild max hl hr hl hr return max 1 else return 0 void printtree BiTree T int nlayer 打印二叉树 if T NULL return printtree T rChild nlayer 1 for int i 0 idata printtree T lChild nlayer 1 void PreOrderNoRec BiTree root 先序非递归遍历 BiTree p root BiTree stack 50 int num 0 while NULL p num 0 while NULL p printf d p data stack num p p p lChild num p stack num p p rChild printf n void InOrderNoRec BiTree root 中序非递归遍历 BiTree p root int num 0 BiTree stack 50 while NULL p num 0 while NULL p stack num p p p lChild num p stack num printf d p data p p rChild printf n void PostOrderNoRec BiTree root 后序非递归遍历 BiTree p root BiTree stack 50 int num 0 BiTree have visited NULL while NULL p num 0 while NULL p stack num p p p lChild p stack num 1 if NULL p rChild have visited p rChild printf d p data num have visited p p NULL else p p rChild printf n int main 主函数 printf 二叉排序树的实现 printf n int layer int i int num printf 输入节点个数 scanf d printf 依次输入这些整数 要不相等 int arr int malloc num sizeof int for i 0 ino no T name name T score score T lChild T rChild NULL return 1 else if nono InsertBST T lChild no score name else if key T data InsertBST T rChild no score name else return 0 其他含参函数也类似其他含参函数也类似 即可完成即可完成 50 个信息存储个信息存储 用数组存储用数组存储 50 个信息 查看以往代码个信息 查看以往代码 include include using namespace std class student private int num string name int ob1 int ob2 int ara public void set int a string b int c int d void show int average void student set int a string b int c int d num a name b ob1 c ob2 d ara c d 2 void student show cout 学号 num 姓名 name 科目一 ob1 科目二 ob2 平均成绩 ara endl int student average return ara int main cout 欢迎来到学生管理系统 endl cout 0 查询学号信息 endl cout 1 删除学号信息 endl cout 2 添加学号新信息 endl cout 3 按平均分降序显示所有学生信息 endl cout 4 退出 endl student ptr new student 21 ptr 1 set 1 小明 88 67 已存入的学生信息 ptr 2 set 2 小李 68 82 ptr 3 set 3 小王 68 62 ptr 4 set 4 小陈 79 82 ptr 5 set 5 小张 63 82 ptr 6 set 6 小红 68 73 ptr 7 set 7 小木 62 77 ptr 8 set 8 小添 65 86 ptr 9 set 9 小天 68 82 ptr 10 set 10 张三 88 82 ptr 11 set 11 李四 98 82 ptr 12 set 12 王五 88 81 ptr 13 set 13 小月 58 82 ptr 14 set 14 小鑫 78 80 ptr 15 set 15 小良 68 92 ptr 16 set 16 小成 68 82 ptr 17 set 17 小敏 98 92 ptr 18 set 18 小问 88 88 ptr 19 set 19 小文 48 82 ptr 20 set 20 小瑞 98 62 已存入的学生信息 int numlock int j 0 int i k m int q e r string w while 1 cout 按 0 1 2 3 4 进行操作 numlock switch numlock case 0 cout 输入想查询的学号 i if i j cout 该学号信息已被删除 endl break ptr i show break case 1 cout 输入想删除的学号 j delete j ptr cout 删除成功 endl break case 2 cout 输入想添加的学号信息 k if k j cout 该学号信息已经存在 添加失败 endl break cout 重新输入添加的学号 q cout 输入姓名 w cout 输入科目一的成绩 e cout 输入科目二的成绩 r ptr k set q w e r break case 3 for m 1 m 20 m for int n m 1 n 20 n if ptr m average ptr n average student a a ptr m ptr m ptr n ptr n a ptr m show break case 4 cout 谢谢使用 endl return 0 default cout number out of 0 to 4 endl break return 0 三 测试结果 二叉排序树储存数据界面 储存学生信息略 二叉排序树储存数据界面 储存学生信息略 创建二叉树 创建二叉树 插入节点 插入节点 删除节点 删除节点 非递归遍历 非递归遍历 退出 退出 数组储存学生信息界面数组储存学生信息界面 分析查找效率 分析查找效率 因为二叉树查找要创建二叉树 而数组查找只创建一个数组 二叉树的创建时 间比较长 所以对于数据量较少的情况下数组的查找效率比较高 但当数据量 增加时 二叉树的查找优势就显现出来 所以数据量越大的时候 二叉树的查 找效率越高 四 总结与改进 这个实验