动态查找表实验报告

1、动态查找表实验报告1 、实验概要实验项目名称 实验项目性质 所属课程名称 实验计划学时2、实验目的抽象数据类型的实现设计性实验数据结构6对某个具体的抽象数据类型， 运用课程所学的知识和方法， 设计合理的数据结构， 并在 此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力， 发现学习中存在的问题。 进而达到熟练地运用本课程中的基础知识及技术的目的。实验要求如下：1参加实验的学生应首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。 若学生对 教材以外的相关题目较感兴趣， 希望选作实验的题目时，

2、 应征得指导教师的认可， 并写出明 确的抽象数据类型定义及说明。2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象 数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录 各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的 数据及相应的运行结果。所用软件环境或工具：DEV-C+5可视化编程环境.3. 动态查找表的抽象数据类型ADT DynamicSearchTable 数据对

3、象D: D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字， 可唯一标识数据元素。数据关系 R： 数据元素同属一个集合。 基本操作 P： InitDSTable(&DT);操作结果：构造一个空的动态查找表DT。DestroyDSTable(&DT);初始条件：动态查找表 DT 存在； 操作结果：销毁动态查找表DT。SearchDSTable(DT, key);初始条件：动态查找表 DT存在，key为和关键字类型相同的给定值；操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。InsertDSTable(&DT, e);初始条件：

4、动态查找表DT 存在， e 为待插入的数据元素；操作结果：若DT中不存在其关键字等于的数据元素，则插入e到DTDeleteDSTable(&T, key);初始条件：动态查找表 DT存在，key为和关键字类型相同的给定值； 操作结果：若DT中存在其关键字等于 key的数据元素，则删除之。TraverseDSTable(DT, Visit();初始条件：动态查找表DT存在，Visit是对结点操作的应用函数；操作结果：按某种次序对 DT 的每个结点调用函数 visit() 一次且至多一次。一旦 visit() 失败，则操作失败。 ADT DynamicSearchTable二. 动态查找表的特点二

5、叉排序树是一种动态树表， 其特点是， 树的结构通常不是一资生成的， 面是在查找过 程中，当树中不存在关键字等于给定值的结点时再进行插入。 新插入的结点一定是一个新添 加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结 点。三. 算法设计#include#include#include#include #include typedef struct ElemType int key;ElemType;typedef structbitnode建立二叉排序树*n); printf(*2.二叉排序树查找元素*n); printf(*3.二叉排序树插入元素*n); prin

6、tf(*4.二叉排序树删除元素*n); printf(*5. 遍 历 二叉排序树*n); printf(*6. 销 毁 二叉排序树*n);printf(*n); printf(* *n);printf(7. 退 出);printf( 请输入你的选择 : n); scanf(%d,&h);switch(h) case 1:Init(T); break; case 2:char a;printf( 请输入要查找的数据 :n); scanf(%d,&n);=n;if(Search(T,e,NULL,p)printf( 数据已经存在 !n); else printf( 数据不存在 !n);break;

7、case 3:printf( 请输入要插入的数据 :n); scanf(%d,&n);=n;if(Search(T,e,NULL,p) printf( 已经存在 !n);elseInsert(T, e);printf( 成功插入 !n);break;case 4:printf( 请输入要删除的数据 :n); scanf(%d,&n);=n;if(Search(T,e,NULL,p)Deletebit(T,n);printf( 已经成功删除 !n);else printf( 数据不存在 !n);break;case 5: int z; do printf(*n);printf(*n);print

8、f(*n);printf(*1.*n);printf(*2.*n);printf(*3.*n);printf(*4.*n);printf(*n);printf(*n);printf( 请输入你的选择 : n); scanf(%d,&z);switch(z)case 1:printf( 先序遍历二叉排序树 : Xianxu(T);printf(n);break;case 2:printf( 中序遍历二叉排序树 : );Zhongxu(T);printf(n);break;case 3:printf( 后序遍历二叉排序树 : ); Houxu(T); printf(n);break;case 4:

9、printf( 退出! 返回上级菜单！ n); break;default: printf( 选择错误，重新开始 !n); while(z!=4);break;case 6:printf( 确定是否要销毁二叉排序树 ?(y/n)n); scanf(n%c,&c);getch();if(c=y)Destory(T);printf( 所选数据已成功销毁 !n);getch();T = NULL; elseprintf( 所选数据销毁失败 !n);break;case 7:printf( 退出！ n); break;default: printf（ 选择错误，重新开始 !n）; while(h!=7

10、);四. 调试 主页面1. 建立二叉排序树输入十个数据： 10,15,26,96,82,37,46,50,61,03,992. 查找元素 : 26 存在则输出3. 插入元素：4. 删除元素： 56（不存在） 99 （存在）5. 遍历：跳入二级子菜单，里边分别有三种遍历方式可供选择，分别为先序，中序，后序6. 在子菜单中选择 4 退出则返回到上级菜单，即主页面7 销毁二叉树：先询问是否确认要销毁，输入 y 则销毁，输入 n 则销毁失败说明：1）输入十个数据： 10,15,26,96,82,37,46,50,61,03,992）查找 26，26 存在则输出（ 3）插入 1004）删除 56 和 9

11、9,56 不存在则输出“该数据不存在” ，99 存在则输出“成功删除”5）遍历：跳入二级子菜单，里边分别有三种遍历方式可供选择分别是 先序： 15,3,13,26,96,82,37,46,50,61,100中序： 3,13,15,26,37,46,50,100,61,82,96,后序： 13,3,100,61,50,46,37,82,96,26,15, 退出后则返回到上级菜单6）销毁二叉树：先询问是否确认要销毁，输入Y/y 则销毁，输入 N/n 则销毁失败五. 实验总结这次实验难度不是很大，因为很多算法书本上有，而且我在图书馆里也找了几本数据结 构算法实现的书， 参考了很多， 而且我选择了最简单的二叉树的存储结构来实现。 这次实验 使我认识到存储结构和算法实现之间的关连。存储结构决定算法的实现。不同的存储结构， 在算法的实现方面有很大差别。 例如你选择 B 树或键树的话相对于我来说就比较困难， 因为 掌握的不是很好。 很开心自己完成了这次实验， 因为这次实验让我多翻了几本书， 对动态查 找表有了比上课更深的认识， 除此之外， 我觉得更重要的是我掌握了一些从书上学不到的知 识，思想交流和一些处理大问题的一些好方法，就是把大问题模块