《数据结构》实验报告
题 目第11题：动态查找表
学 院 计算机学院
专 业 计算机科学与技术
班 别 XX级XX班
学 号 XXXXXXXX
姓 名 XXXXXX
老 师 XXXXX
成 绩
201X 年 XX 月 XX日
一、动态查找表
实验目的：动态查找表，实现抽象数据类型：二叉查找表。
实现以下操作：构造空表、销毁表、查找指定元素、插入新元素、删除指定元素、顺序遍历表中所有元素。实验软件：Dev C++
1、抽象数据类型动态查找表的定义如下：
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(&DT,key);
初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。
操作结果：若DT中存在其关键字等于key的数据元素，则删除之。
TraverseDSTable(DT,visit());
初始条件：动态查找表DT存在，visit是对结点操作的应用函数。
操作结果：按某种次序对DT的每个结点调用函数visit()一次且至多 一次，一旦visit()失败，则操作失败。
}ADT DynamicSearchTable
2、存储结构定义：
公用头文件DS0.h和宏定义:
#include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define N 10 /* 数据元素个数 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int KeyType; /* 设关键字域为整型 */
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
3、二叉排序树存储结构：
二叉排序树的类型BiTree定义如下：
typedef int KeyType; /* 设关键字域为整型 */
typedef struct
{
KeyType key;
int others;
}
ElemType; /* 数据元素类型 */
typedef ElemType TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}
BiTNode,*BiTree;
二、算法设计
Status InitDSTable(BiTree *DT)
{
*DT=NULL;
return OK;
}
void DestroyDSTable(BiTree *DT)
{
if(*DT)
{
if((*DT)->lchild)
DestroyDSTable(&(*DT)->lchild);
if((*DT)->rchild)
DestroyDSTable(&(*DT)->rchild);
free(*DT);
*DT=NULL;
}
}
BiTree SearchBST(BiTree T,KeyType key)
{
if((!T)||EQ(key,T->data.key)) return T;
else if LT(key,T->data.key)
return SearchBST(T->lchild,key);
else
return SearchBST(T->rchild,key);
}
void SearchBST1(BiTree *T,KeyType key,BiTree f,BiTree *p,Status *flag)
{
if(!*T)
{
*p=f;
*flag=FALSE;
}
else if EQ(key,(*T)->data.key)
{
*p=*T;
*flag=TRUE;
}
else if LT(key,(*T)->data.key)
SearchBST1(&(*T)->lchild,key,*T,p,flag);
else
SearchBST1(&(*T)->rchild,key,*T,p,flag);
}
Status InsertBST(BiTree *T, ElemType e)
{
BiTree p,s; Status flag;
SearchBST1(T,e.key,NULL,&p,&flag);
if(!flag)
{
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if(!p)
*T=s;
else if LT(e.key,p->data.key)
p->lchild=s;
else
p->rchild=s;
return TRUE;
}
else
return FALSE;
}
void Delete(BiTree *p)
{
BiTree q,s;
if(!(*p)->rchild)
{
q=*p;
*p=(*p)->lchild;
free(q);
}
else if(!(*p)->lchild)
{
q=*p;
*p=(*p)->rchild;
free(q);
}
else
{
q=*p;
s=(*p)->lchild;
while(s->rchild)
{
q=s;
s=s->rchild;
}
(*p)->data=s->data;
if(q!=*p)
q->rchild=s->lchild;
else
q->lchild=s->lchild;
free(s);
}
}
Status DeleteBST(BiTree *T,KeyType key)
{
if(!*T)
return FALSE; else
{
if EQ(key,(*T)->data.key)
Delete(T);
else if LT(key,(*T)->data.key)
DeleteBST(&(*T)->lchild,key);
else
DeleteBST(&(*T)->rchild,key);
return TRUE;
}
}
void TraverseDSTable(BiTree DT,void(*Visit)(ElemType))
{
if(DT)
{
TraverseDSTable(DT->lchild,Visit);
Visit(DT->data);
TraverseDSTable(DT->rchild,Visit);
}
}
三、编译过程
1、第一次编译是出现一大推错误，主要是一些粗心代码和逻辑错误：
2、
经过反复修改之后，慢慢减少Bug：缺了主函数。
3、最后终于编译成功！
四、测试代码
void print(ElemType c)
{
printf("(%d,%d) ",c.key,c.others);
}
int main()
{
char q;
BiTree dt,p;
int i,select;
KeyType j;
ElemType k;
ElemType
r[10]={{90,5},{24,2},{106,6},{3,8},{34,10},{48,12},{285,29},{22，74},{97,18},{140,20}};
InitDSTable(&dt);
for(i=0;i<10;i++)
InsertBST(&dt,r[i]);
C1: printf("——————————动态查找表——————————");
printf("\n\n");
printf("---------------------------------------------------------\n\n\n");
printf("1、遍历原有表\n\n");
printf("2、查找表内值\n\n");
printf("3、删除表内值\n\n");
printf("4、插入一个值\n\n");
printf("5、销毁表\n\n");
printf("6、退出演示系统");
printf("\n\n\n");
printf("请选择你所需要的操作（1~6）：");
scanf("%d",&select);
switch(select)
{
C2: case 1:printf("\n原有的表遍历如下：\n\n");
TraverseDSTable(dt,print);
printf("\n");
printf("请按任意键返回");
getchar();
getchar();
system("cls");
goto C1;
C3: case 2:printf("\n原有的表遍历如下：\n\n");
TraverseDSTable(dt,print);
printf("\n");
printf("\n请输入你要查找的值：");
scanf("%d",&j);
p=SearchBST(dt,j);
if(p)
{
printf("\n查找成功：");
printf("(%d,%d)",p->data.key,p->data.others);
//getchar();
getchar();
printf("\n是否继续查找？(Yes/No):");
q=getchar();
getchar();
if(q=='Y'||q=='y')
goto C3;
else
{
system("cls");
goto C1;
}
}
else
{
printf("查找失败，表中无此值，是否继续查找？(Yes/No):");
getchar();
q=getchar();
if(q=='Y'||q=='y')
goto C2;
else
{
system("cls");
goto C1;
}
}
C4: case 3:printf("\n原有的表遍历如下：\n\n");
TraverseDSTable(dt,print);
printf("\n");
printf("\n请输入你要删除的值：");
scanf("%d",&j);
//getchar();
//q=getchar();
p=SearchBST(dt,j);
if(p)
{
printf("删除此值后：\n");
DeleteBST(&dt,j);
TraverseDSTable(dt,print);
printf("\n是否继续删除？(Yes/No):");
getchar();
q=getchar();
if(q=='Y'||q=='y')
goto C4;
else
{
system("cls");
goto C1;
}
}
else
{
printf("删除失败，表中无此值，请按任意键返回继续");
printf("\n");
getchar();
getchar();
goto C4;
}
C5: case 4:printf("\n原有的表遍历如下：\n\n");
TraverseDSTable(dt,print);
printf("\n");
printf("请输入你所要插入的值：");
scanf("%d",&k.key);
p=SearchBST(dt,k.key);
if(!p)
{
printf("插入此值后：\n");
k.others=k.others+(N+1);
InsertBST(&dt,k);
TraverseDSTable(dt,print);
printf("\n");
printf("是否继续插入新值？(Yes|No):");
getchar();
q=getchar();
if(q=='Y'||q=='y')
goto C5;
else
{
system("cls");
goto C1;
} }
else
{
printf("插入失败，表中已存在此值，请按任意键返回继续");
getchar();
getchar();
goto C5;
}
case 5:DestroyDSTable(&dt);
printf("销毁成功");
goto C2;
case 6:system("cls");
printf("\n\n\n——————————Exit System!——————————");
printf("\n\n\n————————~.~！Thank You！~.~————————");
printf("\n\n\n");
system("pause");
}
}
五、测试结果
测试数据：{90,5},{24,2},{106,6},{3,8},{34,10},{48,12},{285,29},{22，74},{97,18},{140,20}
1、实现表内原有值遍历，如下：
2、实现查找表内值；比如查找34，查找结果为（34,10）。
查找失败！
3、实现删除表中值；比如删除90，如下：
4、实现插入一个新值，插入99，结果如下：
5、实现销毁操作。
6、退出系统！
六、思考与小结
思考：根据知识总结，动态查找表跟静态查找表不一样的地方在于他有插入删除功能，这两大功能也是继查找功能后最大的功能，所以核心代码还是这两三个函数。在实现的过程中也是着重考虑这几个功能的实现。
小结：这些代码其实都不是原创，都是根据课本的伪代码看懂后稍加修改而写成的，这也是出现很多错误的原因，不过最终还是把错误都改完了，也实现了相应的操作，也算是对这动态查找表有了更深入的了解。
通过这次动手实验，对动态查找表的功能有较好的理解，调试过程确实很繁琐，但在运行中修改也是有很大收获的。