动态查找表试验报告材料

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

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

3、D是具有相同特性的数据元素的集合.每个数据元素含有类型相同的关键字, 可唯一标识数据元素.数据关系R:数据元素同属一个集合.根本操作P:In itDSTable(&DT);操作结果：构造一个空的动态查找表DT oDestroyDSTable(&DT);初始条件：动态查找表DT存在；操作结果：销毁动态查找表DT oSearchDSTable(DT, key);初始条件：动态查找表DT存在,key为和关键字类型相同的给定值；操作结果：假设DT中存在其关键字等于 key的数据元素,那么函数值为该元素的值或在表中的位置,否那么为“空.In sertDSTable(&DT, e)

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

5、archTable二动态查找表的特点二叉排序树是一种动态树表,其特点是,树的结构通常不是一资生成的,面是在查找过程中,当树中不存在关键字等于给定值的结点时再进行插入.新插入的结点一定是一个新添加的叶子结点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结 点.三算法设计#i nclude<stdio.h>#i nclude<malloc.h>#in clude<c oni o.h>#i nclude <cstdlib> #i nclude <iostream>typedef struct ElemTypeint key

6、; ElemType;typedef struct bit no de/二叉树的二叉链表存储表示ElemType data;struct bit node *lchild,*rchild;/ 左右孩子指针int len gth;bit no de,*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.key&g

7、t;e.key)return Search(T->lchild,e,T,p); elsereturn Search(T->rchild,e,T,p);/在二叉排序树中查找数据void In sert(bitree &T,ElemType e)在二叉排序树中插入数据bitree p,s;if (!Search(T,e,NULL,p) 查找不成功s=(bitree)malloc(sizeof(bit no de); s->data=e;s->lchild=s->rchild=NULL;if (!p) T=s;被插入结点*s为新的根结点else if (e.ke

8、y<p->data.key)p->lchild=s;被插结点*s为左孩子elsep->rchild=s;被插结点*s为右孩子return ;else return ;void Init(bitree &T)/构造一个动态查找表 T int x;int i;int n;ElemType e;printf("请输入结点个数:");sca nf("%d", &x);for(i=1;i<=x;i+)printf("第%d个结点数据值:",i);sca nf("%d",&

9、n);e.key=n;In sert(T,e);printf("二叉排序树已经建立!n");void Destory(bitree T)/后序遍历二叉树,销毁动态查找表Tif(T)if(T->lchild)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=

10、p->lchild;free(q);q=NULL;else if(!p->lchild) /左子树空,只需重接它的右子树q=p;p=p->rchild;free(q);q=NULL;else/左右子树均不空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

11、=s->lchild;/重接 *q 的左子树free(s);s=NULL; /删除结点 void Deletebit(bitree &T,i nt n)删除二叉排序树中的数据if(!T)return ; 不存在关键字等于n的数据元素elseif(T->data.key=n)return(Delete(T); /找到关键字等于n的数据元素并删除它 else if(T->data.key >n)Deletebit(T->lchild, n);/继续在左子树中删除elseDeletebit(T->rchild, n);/继续在右子树中删除return; v

12、oid Xia nxu(bitree T) / 先序遍历if (T!=NULL)prin tf("%dt",T->data.key);Xianxu (T->lchild);Xia nxu (T->rchild);void Zhongxu(bitree T)/中序遍历if(T!=NULL)Zhongxu (T->lchild);prin tf("%dt", T->data.key);Zhon gxu (T->rchild);void Houxu(bitree T) 后序遍历if(T!=NULL)Houxu (T->

13、lchild);Houxu (T->rchild);printf("%dt", T->data.key);int main() bitree T=NULL,p;ElemType e;int n;int h; char c;doprin tf("*n")prin tf("*n");prin tf("*动态查找表*n");prin tf("*1.建立二叉排序树*n");prin tf("*2.二叉排序树查找元素*n");prin tf("*3.二叉排序树插入

14、元素*n");prin tf("*4.二叉排序树删除元素*n");prin tf("*5.遍历二叉排序树*n");prin tf("*6销毁二叉排序树*n");prin tf("*7.退出*n");prin tf("*n");prin tf("*n")printf("请输入你的选择：n"); scan f("%d",&h);switch(h)case 1:Ini t(T);break;case 2:char a;pri

15、ntf("请输入要查找的数据:n"); sca nf("%d",&n);e.key=n;if(Search(T,e,NULL,p)printf("数据已经存在!n"); elseprintf("数据不存在!n");break;case 3:printf("请输入要插入的数据:n"); sca nf("%d",&n);e.key=n;if(Search(T,e,NULL,p) printf("已经存在!n");elseIn sert(T, e

16、);printf("成功插入!n");break;case 4:printf("请输入要删除的数据:n"); sca nf("%d",&n);e.key=n;if(Search(T,e,NULL,p)Deletebit(T, n);printf("已经成功删除!n");else printf("数据不存在!n"); break;case 5:in t z;do *n");printf(prin tf("* prin tf("* prin tf("*

17、 prin tf("* prin tf("* prin tf("* prin tf("*遍历二叉排序树1. 先序遍历二叉排序树2. 中序遍历二叉排序树3. 后序遍历二叉排序树4. 退出* n");* n");*n");*n");*n");*n");*n");printf(* n");printf"请输入你的选择:n"scan f("%d", &z);switch(z)case 1:printf("先序遍历二叉排序树:&

18、quot;);Xia nxu(T);prin tf("n");break;case 2:printf("中序遍历二叉排序树:");Zhon gxu(T);prin tf("n");break;case 3:printf("后序遍历二叉排序树：");Houxu(T);prin tf("n");break;case 4:printf("退出!返回上级菜单！ n");break;default:printf("选择错误,重新开始!n"); while(z!=4)

19、;break;case 6:printf("确定是否要销毁二叉排序树?(y/n)n"); sca nf("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

20、(h!=7);四调试主页面si-|Q|X-MJ1查花二 二二 动立叉叉叉历毁出 建二二二遍销退5S元元元请输入你的选择:狗拼音半i建立二叉排序树输入十个数据：10,15,26,96,82,37,46,50,61,03,99董示素聾WW诽排 查叉ittyt叉叉 态二 二二 动立X叉叉历毁岀 建二二二9 05 & 627 &0139 1 1 2 07 8 3 4 s G 0 _ 一 二 »» " _ =ffiffiQ1M1A值值!a加数数数敖数数敷魏数第 詐点点点H点点点点点器 £?士口士口士 口 ± 口 士口士 口士口士曰 士日吆

21、 聲个个个个个个个个加 1234567891 L请主卑事2查找元素：26存在那么输出请输入你的选扌勒2请输入要查找的数据匕26型週三宰童空3.插入元素:r7jESi-m番输入要插入的数据；106成功插入！4.删除元素：56 不存在 99 存在诲输入你的选择； 萨输入要删除的数据三数据不存在t7,退旳请输入你的选择：备输入要删除的数据：已经成功删除*5遍历：跳入二级子菜单,里边分别有三种遍历方式可供选择,分别为先序,中序,后序请输入你的选择,5*12遍历二叉排序树 先库遍历二更排理榊 中序遍历二叉吊树:窗三編4退由KKXHXXEXXXKilCMKXMEiMKXiMXXEXHJiCMXKUXMXXKHXXEXXXXiMXXJMXXXXHXKXMEXJiCMHX/MJIXHJCMX晴输入你的选择：6.在子菜单中选择 4退出那么返回到上级菜单,即主页面7销毁二叉树：先询问是否确认要销毁,输入y那么销毁,输入n那么销毁失败说明:(1) 输入十个数据:10,15,26,96,82,37,46,50,61,03,