数据结构实验报告题目：动态查找表学院计算机专业计算机科学与技术年级班别2009级 2 班学号3109005935学生姓名黄丽敏指导教师吴伟民成绩____________________2011年6月一. 动态查找表：抽象数据类型动态查找表的定义如下：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二. 存储结构定义：公用头文件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))二叉排序树存储结构：二叉排序树的类型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;三、算法设计：/* 操作结果: 构造一个空的动态查找表DT */Status InitDSTable(BiTree *DT){*DT=NULL;return OK;}/* 初始条件: 动态查找表DT存在。
操作结果: 销毁动态查找表DT */void DestroyDSTable(BiTree *DT) /* 同bo6-2.c */{if(*DT) /* 非空树*/{if((*DT)->lchild) /* 有左孩子*/DestroyDSTable(&(*DT)->lchild); /* 销毁左孩子子树*/if((*DT)->rchild) /* 有右孩子*/DestroyDSTable(&(*DT)->rchild); /* 销毁右孩子子树*/free(*DT); /* 释放根结点*/*DT=NULL; /* 空指针赋0 */}}/* 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，*//* 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。
*/BiTree SearchBST(BiTree T,KeyType1 key){if((!T)||EQ(key,T->data.key))return T; /* 查找结束*/else if LT(key,T->data.key) /* 在左子树中继续查找*/return SearchBST(T->lchild,key);elsereturn SearchBST(T->rchild,key); /* 在右子树中继续查找*/}/* 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找*//* 成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上*//* 访问的最后一个结点并返回FALSE,指针f指向T的双亲，其初始调用值为NULL */void SearchBST1(BiTree *T,KeyType1 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); /* 在左子树中继续查找*/elseSearchBST1(&(*T)->rchild,key,*T,p,flag); /* 在右子树中继续查找*/}/* 当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，*//* 否则返回FALSE。
*/Status InsertBST(BiTree *T, ElemType1 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; /* 被插结点*s为新的根结点*/else if LT(e.key,p->data.key)p->lchild=s; /* 被插结点*s为左孩子*/elsep->rchild=s; /* 被插结点*s为右孩子*/return TRUE;}elsereturn FALSE; /* 树中已有关键字相同的结点，不再插入*/}/* 从二叉排序树中删除结点p，并重接它的左或右子树。
*/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; /* s指向被删结点的＂前驱＂（将被删结点前驱的值取代被删结点的值）*/if(q!=*p)q->rchild=s->lchild; /* 重接*q的右子树*/elseq->lchild=s->lchild; /* 重接*q的左子树*/free(s);}}/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点，*//* 并返回TRUE；否则返回FALSE。
*/Status DeleteBST(BiTree *T,KeyType1 key){if(!*T) /* 不存在关键字等于key的数据元素*/return FALSE;else{if EQ(key,(*T)->data.key) /* 找到关键字等于key的数据元素*/Delete(T);else if LT(key,(*T)->data.key)DeleteBST(&(*T)->lchild,key);elseDeleteBST(&(*T)->rchild,key);return TRUE;}}/* 初始条件: 动态查找表DT存在，Visit是对结点操作的应用函数*//* 操作结果: 按关键字的顺序对DT的每个结点调用函数Visit()一次且至多一次*/void TraverseDSTable(BiTree DT,void(*Visit)(ElemType1)){if(DT){TraverseDSTable(DT->lchild,Visit); /* 先中序遍历左子树*/Visit(DT->data); /* 再访问根结点*/TraverseDSTable(DT->rchild,Visit); /* 最后中序遍历右子树*/}}四、编译：1.初次编译会出现很多错误，这主要是写程序时的粗心大意还有一些潜在的定于或逻辑错误，第一次运行如下：2.错误很多，经过一番调试才发现定义结构体时出了问题，有些没用到，有些重定义了，调试后如下：3.此时只剩下很少错误，很明显是i未定义，经过修改调试后编译通过。
五、测试void print(ElemType c) /*以下主函数调用*/{printf("(%d,%d) ",c.key,c.others);}Void main() /*用于测试二叉排序树的查找*/{char q;BiTree dt,p;int i,select;KeyType j;ElemType k;ElemTyper[10]={{45,1},{12,2},{53,3},{3,4},{37,5},{24,6},{100,7},{61,8},{90,9},{70,10}}; /* 测试数据*/InitDSTable(&dt); /* 构造空表*/for(i=0;i<10;i++)InsertBST(&dt,r[i]); /* 依次插入数据元素*/H1: printf("=============动态查找表演示系统===========");printf("\n");printf("1、遍历原有表\n");printf("2、查找表内值\n");printf("3、删除表内值\n");printf("4、插入一个值\n");printf("5、销毁表\n");printf("6、退出系统");printf("\n");printf("请选择你需要的操作（1~6）：");scanf("%d",&select);switch(select){H2: case 1:printf("原有的表遍历如下：\n");TraverseDSTable(dt,print);printf("\n");printf("按任意键返回.....");getchar();getchar();system("cls");goto H1;H3: case 2:printf("原有的表遍历如下：\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是否继续查找？(Y/N):");q=getchar();getchar();if(q=='Y'||q=='y')else{system("cls");goto H1;}}else{printf("查找失败，表中无此值，是否继续查找？(Y/N):");getchar();q=getchar();if(q=='Y'||q=='y')goto H2;else{system("cls");goto H1;}}H4: case 3:printf("原有的表遍历如下：\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是否继续删除？(Y/N):");getchar();q=getchar();if(q=='Y'||q=='y')goto H4;else{system("cls");goto H1;}else{printf("删除失败，表中无此值，请按任意键返回继续....");printf("\n");getchar();getchar();goto H4;}H5: case 4:printf("原有的表遍历如下：\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("是否继续插入新值？(Y|N):");getchar();q=getchar();if(q=='Y'||q=='y')goto H5;else{system("cls");goto H1;}}else{printf("插入失败，表中已存在此值，请按任意键返回继续....");getchar();getchar();goto H5;}case 5:DestroyDSTable(&dt);printf("销毁成功....");goto H2;case 6:system("cls");printf("\n\n\n\n\n\n\n\n\n============谢谢使用！============");printf("\n\n\n ");system("pause");}}说明：（1）、此二叉排序树以下面为原始测试数据：{45,1},{12,2},{53,3},{3,4},{37,5},{24,6},{100,7},{61,8},{90,9},{78,10}主界面如下：（2）、若选择‘1’，则显示遍历出来的二叉排序树动态查找表，如下图：（3）、若选择‘2’则提示用户输入要查找的值，若存在，则显示查找成功，若没有此值，则提示是否继续查找，如下图：（4）、若输入3，则提示用户输入想要删除的值，若存在此值，则显示删除后的表，若不存在此值，则显示删除失败，如下图：（5）、若选择‘4’，则提示用户输入一个想要插入的值，若表中无此元素，则显示插入后的表，若已存在，则提示插入失败，如下图：（6）、若选择‘5’，则销毁此表，并显示销毁之后的表，如下图：（7）、若选择‘6’，则退出系统，显示结束系统界面：六、二叉排序树查找分析：在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加1（或结点所在层次数），因此，和折半查找类似，与给定值比较的关键字个数不超过树的深度。