2024年动态查找表实验报告

动态查找表试验报告一.1、试验概要试验项目名称:抽象数据类型的实现试验项目性质:设计性试验所属课程名称:数据结构试验计划学时:62、试验目标对某个详细的抽象数据类型，利用课程所学的知识和措施，设计合理的数据结构，并在此基础上实现该抽象数据类型的所有基本操作。通过本设计性试验，检查所学知识和能力，发觉学习中存在的问题。进而达成纯熟地利用本课程中的基础知识及技术的目标。试验要求如下：1．参加试验的学生应首先了解设计的任务，然后依照自己的基础和能力从中选择一题。一般来说，选择题目应以在要求的时间内能完成，并能得到应有的锻炼为标准。若学生对教材以外的有关题目较感兴趣，希望选作试验的题目时，应征得指引教师的认可，并写出明确的抽象数据类型定义及阐明。2.试验前要作好充足准备，包括：了解试验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。3.试验时严肃仔细，要严格按照要求独立进行设计，不能随意更改。注意观测并统计各种错误现象，纠正错误，使程序满足预定的要求，试验统计应作为试验报告的一部分。4.试验后要及时总结，写出试验报告，并附所打印的问题解答、程序清单，所输入的数据及对应的运行成果。所用软件环境或工具：DEV-C++5可视化编程环境.3.动态查找表的抽象数据类型

ADTDynamicSearchTable{

数据对象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()失败，则

操作失败。

}ADTDynamicSearchTable动态查找表的特点二叉排序树是一个动态树表，其特点是，树的结构一般不是一资生成的，面是在查找过程中，当树中不存在核心字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找途径上访问的最后一个结点的左孩子或右孩子结点。算法设计#include<stdio.h>#include<malloc.h>#include<conio.h>#include<cstdlib>#include<iostream>typedefstructElemType{ intkey;}ElemType;typedefstructbitnode{//二叉树的二叉链表存储表示 ElemTypedata; structbitnode*lchild,*rchild;//左右孩子指针 intlength;}bitnode,*bitree;bitreeSearch(bitreeT,ElemTypee,bitreef,bitree&p)//在二叉排序树中查找数据{ if(!T) { p=f; returnNULL; }//查找不成功 elseif(T->data.key==e.key) { p=T;returnT; }//查找成功 elseif(T->data.key>e.key) returnSearch(T->lchild,e,T,p); else returnSearch(T->rchild,e,T,p);}//在二叉排序树中查找数据voidInsert(bitree&T,ElemTypee)//在二叉排序树中插入数据{ bitreep,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为新的根结点 elseif(e.key<p->data.key)p->lchild=s;//被插结点*s为左孩子 elsep->rchild=s;//被插结点*s为右孩子 return; } elsereturn;}voidInit(bitree&T)//结构一个动态查找表T{intx;inti;intn;ElemTypee; printf("请输入结点个数:"); scanf("%d",&x); for(i=1;i<=x;i++) { printf("第%d个结点数据值:",i); scanf("%d",&n); e.key=n; Insert(T,e); }printf("二叉排序树已经建立!\n");}voidDestory(bitreeT)//后序遍历二叉树，销毁动态查找表T{ if(T) {if(T->lchild) DestoryTree(T->lchild);if(T->rchild) DestoryTree(T->rchild); free(T); T=NULL; }}voidDelete(bitree&p)//从二叉排序树中删除结点p，并重接它的左或右子树{ bitreeq,s; if(!p->rchild)//右子树空，只需重接它的左子树 { q=p; p=p->lchild; free(q); q=NULL; } elseif(!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的右子树 else q->lchild=s->lchild;//重接*q的左子树 free(s); s=NULL; }}//删除结点voidDeletebit(bitree&T,intn)//删除二叉排序树中的数据{ if(!T) return;//不存在核心字等于n的数据元素 else{ if(T->data.key==n) return(Delete(T));//找到核心字等于n的数据元素并删除它 elseif(T->data.key>n) Deletebit(T->lchild,n);//继续在左子树中删除 else Deletebit(T->rchild,n);//继续在右子树中删除 return; }}voidXianxu(bitreeT)//先序遍历{ if(T!=NULL) { printf("%d\t",T->data.key); Xianxu(T->lchild); Xianxu(T->rchild); }}voidZhongxu(bitreeT)//中序遍历{ if(T!=NULL) { Zhongxu(T->lchild); printf("%d\t",T->data.key); Zhongxu(T->rchild); }}voidHouxu(bitreeT)//后序遍历{ if(T!=NULL) { Houxu(T->lchild); Houxu(T->rchild); printf("%d\t",T->data.key); }}intmain(){ bitreeT=NULL,p; ElemTypee; intn; inth; charc;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) { case1: Init(T); break; case2:chara; printf("请输入要查找的数据:\n"); scanf("%d",&n); e.key=n; if(Search(T,e,NULL,p)) printf("数据已经存在!\n"); else { printf("数据不存在!\n"); } break; case3: printf("请输入要插入的数据:\n"); scanf("%d",&n); e.key=n; if(Search(T,e,NULL,p)) printf("已经存在!\n"); else { Insert(T,e); printf("成功插入!\n"); } break; case4: printf("请输入要删除的数据:\n"); scanf("%d",&n); e.key=n; if(Search(T,e,NULL,p)) { Deletebit(T,n); printf("已经成功删除!\n"); } elseprintf("数据不存在!\n"); break; case5:intz;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) {case1: printf("先序遍历二叉排序树:"); Xianxu(T); printf("\n"); break; case2: printf("中序遍历二叉排序树:"); Zhongxu(T); printf("\n"); break; case3: printf("后序遍历二叉排序树:"); Houxu(T); printf("\n"); break;case4: printf("退出!返回上级菜单！\n"); break; default:printf("选择错误，重新开始!\n");}}while(z!=4);break;case6: printf("确定是否要销毁二叉排序树?(y/n)\n");scanf("\n%c",&c); getch(); if(c=='y') { Destory(T); printf("所选数据已成功销毁!\n"); getch(); T=NULL;} else printf("所选数据销毁失败!\n"); break;case7: printf("退出！\n"); break; default:printf("选择错误，重新开始!\n"); }}while(h!=7);}调试主页面建立二叉排序树输入十个数据：10,15,26,96,82,37,46,50,61,03,99查找元素:26存在则输出插入元素：删除元素：56（不存在）99（存在）遍历：跳入二级子菜单，里边分别有三种遍历方式可供选择，分别为先序，中序，后序6.在子菜单中选择4退出则返回到上级菜单，即主页面7销毁二叉树：先问询是否确认要销毁，输入y则销毁