数据结构实验报告-动态查找表实验报告1

1、数据结构实验报告-动态查找表实验报告数据结构实验报告题目：动态查找表学院计算机专业计算机科学与技术年级班别2009级 2 班学号3109005935学生姓名黄丽敏指导教师吴伟民成绩_2011年6月 一. 动态查找表： 抽象数据类型动态查找表的定义如下：adt dynamicsearchtable数据对象d：d是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字数据关系r：数据元素同属一个集合。基本操作p：initdstable(&dt);操作结果：构造一个空的动态查找表dt。destroydstable(&dt)初始条件：动态查找表dt存在。操作结果：销毁动态

2、查找表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,

3、visit();初始条件：动态查找表dt存在，visit是对结点操作的应用函数。操作结果：按某种次序对dt的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败。adt dynamicsearchtable二. 存储结构定义：公用头文件ds0.h和宏定义:#include /* eof(=z或f6),null */#include#define true 1#define false 0#define ok 1#define n 10 /* 数据元素个数 */typedef int status; /* status是函数的类型,其值是函数结果状态代码，如ok等 *

4、/typedef int keytype; /* 设关键字域为整型 */#define eq(a,b) (a)=(b)#define lt(a,b) (a) 二叉排序树存储结构： 二叉排序树的类型bitree定义如下：typedef int keytype; /* 设关键字域为整型*/typedef structkeytype key;int others; elemtype; /* 数据元素类型*/typedef elemtype telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild; /*

5、 左右孩子指针*/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) /* 有右孩子*/de

6、stroydstable(&(*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-l

7、child,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

8、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;sta

9、tus 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; /* 树中已有关键字相同的结点，不再插入*/* 从

10、二叉排序树中删除结点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)-d

11、ata=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;elseif eq(key,(*t)-data.

12、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-lchil

13、d,visit); /* 先中序遍历左子树*/visit(dt-data); /* 再访问根结点*/ traversedstable(dt-rchild,visit); /* 最后中序遍历右子树*/ 四、编译：1.初次编译会出现很多错误，这主要是写程序时的粗心大意还有一些潜在的定于或逻辑错误，第一次运行如下：2.错误很多，经过一番调试才发现定义结构体时出了问题，有些没用到，有些重定义了，调试后如下：3.此时只剩下很少错误，很明显是i未定义，经过修改调试后编译通过。五、测试void print(elemtype c) /*以下主函数调用*/printf(%d,%d) ,c.key,c.other

14、s);void main() /*用于测试二叉排序树的查找*/char q;bitree dt,p;int i,select;keytype j;elemtype k;elemtype r10=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;iinsertbst(&dt,ri); /* 依次插入数据元素*/h1: printf(=动态查找表演示系统=);printf(n);printf(1、遍历原有表n);printf(2、查找表内值n);print

15、f(3、删除表内值n);printf(4、插入一个值n);printf(5、销毁表n);printf(6、退出系统);printf(n);printf(请选择你需要的操作（16）：);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

16、);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;elseprintf(查找失败，表中无此值，是否继续查找？(y/n):);getchar();q=getchar();if(q=y|q=y)goto

17、 h2;elsesystem(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;els

18、esystem(cls);goto h1; elseprintf(删除失败，表中无此值，请按任意键返回继续.);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;elsesyste