动态查找表实验报告一.1 、实验概要实验项目名称: 抽象数据类型的实现实验项目性质: 设计性实验所属课程名称: 数据结构实验计划学时: 62、实验目的对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。

通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。

进而达到熟练地运用本课程中的基础知识及技术的目的。

实验要求如下：1．参加实验的学生应首先了解设计的任务，然后根据自己的基础和能力从中选择一题。

一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。

若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。

2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。

3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。

注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。

4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。

所用软件环境或工具：DEV-C++5可视化编程环境.3.动态查找表的抽象数据类型ADT DynamicSearchTable {数据对象D：D是具有相同特性的数据元素的集合。

每个数据元素含有类型相同的关键字，可唯一标识数据元素。

数据关系R：数据元素同属一个集合。

基本操作P：InitDSTable(&DT);操作结果：构造一个空的动态查找表DT。

DestroyDSTable(&DT);初始条件：动态查找表DT存在；操作结果：销毁动态查找表DT。

SearchDSTable(DT, key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。

InsertDSTable(&DT, e);初始条件：动态查找表DT存在，e为待插入的数据元素；操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。

DeleteDSTable(&T, key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；操作结果：若DT中存在其关键字等于key的数据元素，则删除之。

TraverseDSTable(DT, Visit());初始条件：动态查找表DT存在，Visit是对结点操作的应用函数；操作结果：按某种次序对DT的每个结点调用函数visit()一次且至多一次。

一旦visit()失败，则操作失败。

} ADT DynamicSearchTable二.动态查找表的特点二叉排序树是一种动态树表，其特点是，树的结构通常不是一资生成的，面是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。

新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

三.算法设计#include<stdio.h>#include<malloc.h>#include<conio.h>#include <cstdlib>#include <iostream>typedef struct ElemType{int key;}ElemType;typedef struct bitnode{ //二叉树的二叉链表存储表示ElemType data;struct bitnode *lchild,*rchild; //左右孩子指针int length;}bitnode,*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>e.key)return Search(T->lchild,e,T,p);elsereturn Search(T->rchild,e,T,p);}//在二叉排序树中查找数据void Insert(bitree &T,ElemType e) //在二叉排序树中插入数据{bitree 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.key<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("请输入结点个数: ");scanf("%d",&x);for(i=1;i<=x;i++){printf("第%d个结点数据值:",i);scanf("%d",&n);e.key=n;Insert(T,e);}printf("二叉排序树已经建立!\n");}void Destory(bitree T)//后序遍历二叉树，销毁动态查找表T{if(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=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=s->lchild; //重接*q的左子树free(s);s=NULL;}} //删除结点void Deletebit(bitree &T,int n)//删除二叉排序树中的数据{if(!T)return ; //不存在关键字等于n的数据元素else{if(T->data.key==n)return(Delete(T)); //找到关键字等于n的数据元素并删除它else if(T->data.key>n)Deletebit(T->lchild,n); //继续在左子树中删除elseDeletebit(T->rchild,n); //继续在右子树中删除return;}}void Xianxu(bitree T) //先序遍历{if (T!=NULL){printf("%d\t",T->data.key);Xianxu (T->lchild);Xianxu (T->rchild);}}void Zhongxu(bitree T)//中序遍历{if(T!=NULL){Zhongxu (T->lchild);printf("%d\t", T->data.key);Zhongxu (T->rchild);}}void Houxu(bitree T)//后序遍历{if(T!=NULL){Houxu (T->lchild);Houxu (T->rchild);printf("%d\t", 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"); printf("* 7. 退出*\n"); printf("* *\n"); printf("***********************************************************\n");printf("请输入你的选择: \n");scanf("%d",&h);switch(h){case 1:Init(T);break;case 2:char a;printf("请输入要查找的数据:\n");scanf("%d",&n);e.key=n;if(Search(T,e,NULL,p))printf("数据已经存在!\n");else{ printf("数据不存在!\n");}break;case 3:printf("请输入要插入的数据:\n");scanf("%d",&n);e.key=n;if(Search(T,e,NULL,p))printf("已经存在!\n");else{Insert(T, e);printf("成功插入!\n");}break;case 4:printf("请输入要删除的数据:\n");scanf("%d",&n);e.key=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"); printf("* 遍历二叉排序树*\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: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);}四.调试主页面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,99（2）查找26，26存在则输出（3）插入100（4）删除56和99,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则销毁失败五.实验总结这次实验难度不是很大，因为很多算法书本上有，而且我在图书馆里也找了几本数据结构算法实现的书，参考了很多，而且我选择了最简单的二叉树的存储结构来实现。