《动态查找表实验报告》由会员分享，可在线阅读，更多相关《动态查找表实验报告（16页珍藏版）》请在金锄头文库上搜索。
1、动态查找表实验报告一.1 、实验概要实验项目名称: 抽象数据类型的实现实验项目性质: 设计性实验所属课程名称: 数据结构实验计划学时: 62、 实验目的对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。 进而达到熟练地运用本课程中的基础知识及技术的目的。实验要求如下：1参加实验的学生应首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。 若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时
2、，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。所用软件环境或工具：DEV-C+5可视化编程环境.3.动态查找表的抽象数据类型 ADT DynamicSearchTable 数据对象D：D是
3、具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一 标识数据元素。数据关系R：数据元素同属一个集合。基本操作P：InitDSTable(&DT);操作结果：构造一个空的动态查找表DT。DestroyDSTable(&DT);初始条件：动态查找表DT存在；操作结果：销毁动态查找表DT。SearchDSTable(DT, key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否 则为精选文档“空”。InsertDSTable(&DT, e);初始条件：动态查找表DT存在，
4、e为待插入的数据元素；操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。DeleteDSTable(&T, key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；操作结果：若DT中存在其关键字等于key的数据元素，则删除之。TraverseDSTable(DT, Visit();初始条件：动态查找表DT存在，Visit是对结点操作的应用函数；操作结果：按某种次序对DT的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。 ADT DynamicSearchTable二. 动态查找表的特点二叉排序树是一种动态树表，其特点是
5、，树的结构通常不是一资生成的，面是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。三. 算法设计#include#include#include#include #include typedef struct ElemTypeint key;ElemType;typedef struct bitnode /二叉树的二叉链表存储表示 ElemType data;struct bitnode *lchild,*rchild; /左右孩子指针int length;bitnode,
6、*bitree;bitree Search(bitree T,ElemType e,bitree f,bitree &p)/在二叉排序树中查找数据if(!T) 精选文档p=f;return NULL; /查找不成功else if(T-data.key=e.key)p=T;return T; /查找成功else if(T-data.keye.key) return Search(T-lchild,e,T,p);else return Search(T-rchild,e,T,p);/在二叉排序树中查找数据void Insert(bitree &T,ElemType e) /在二叉排序树中插入数据b
7、itree p,s;if (!Search(T,e,NULL,p)/查找不成功 s=(bitree)malloc(sizeof(bitnode);s-data=e; s-lchild=s-rchild=NULL; if (!p) T=s; /被插入结点*s为新的根结点 else if (e.keydata.key) p-lchild=s; /被插结点*s为左孩子else p-rchild=s; /被插结点*s为右孩子 return ;else return ; void Init(bitree &T)/构造一个动态查找表T int x; int i; int n; ElemType e;pri
8、ntf(请输入结点个数: );scanf(%d,&x);for(i=1;ilchild)DestoryTree(T-lchild); if(T-rchild)DestoryTree(T-rchild);free(T);T=NULL;void Delete(bitree &p)/从二叉排序树中删除结点p，并重接它的左或右子树bitree q,s;if(!p-rchild) /右子树空，只需重接它的左子树 q=p;p=p-lchild;free(q);q=NULL;else if(!p-lchild) /左子树空，只需重接它的右子树q=p;p=p-rchild;free(q);q=NULL;els
9、e /左右子树均不空q=p; s=p-lchild;while(s-rchild)/向右走到尽头q=s;s=s-rchild;p-data=s-data;/将被删结点的前驱s的内容直接替代该结点的内容精选文档if(q!=p)/若被删除结点的左子树的右子树不为空q-rchild=s-lchild; /重接*q的右子树elseq-lchild=s-lchild; /重接*q的左子树free(s); s=NULL; /删除结点void Deletebit(bitree &T,int n)/删除二叉排序树中的数据if(!T)return ; /不存在关键字等于n的数据元素elseif(T-data.k
10、ey=n)return(Delete(T); /找到关键字等于n的数据元素并删除它else if(T-data.keyn)Deletebit(T-lchild,n); /继续在左子树中删除else Deletebit(T-rchild,n); /继续在右子树中删除return;void Xianxu(bitree T) /先序遍历if (T!=NULL) printf(%dt,T-data.key); Xianxu (T-lchild); Xianxu (T-rchild);void Zhongxu(bitree T)/中序遍历if(T!=NULL)Zhongxu (T-lchild); pr
11、intf(%dt, T-data.key);Zhongxu (T-rchild);精选文档void Houxu(bitree T)/后序遍历if(T!=NULL)Houxu (T-lchild);Houxu (T-rchild);printf(%dt, T-data.key);int main()bitree T=NULL,p;ElemType e;int n;int h;char c; do printf(*n);printf(* *n);printf(* 动态查找表 *n);printf(* 1. 建立二叉排序树 *n);printf(* 2. 二叉排序树查找元素 *n);printf(* 3. 二叉排序树插入元素 *n);printf(* 4. 二叉排序树删除元素 *n);printf(* 5. 遍历二叉排序树 *n);printf(* 6. 销毁二叉排序树 *n);
