数据结构实验报告动态查找表.doc

数据结构实验报告 题目：动态查找表 学 院 计算机学院 专 业 计算机科学与技术 年级班别 2010级计科4 班 学 号 3110006015 学生姓名 张法光 指导教师 张巍 成 绩 _2012年6月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 DynamicSearchTable2. 存储结构定义：公用头文件DS0.h和宏定义:#include #include#define TRUE 1 /* TRUE函数值为1*/#define FALSE 0 #define N 10 /* 数据元素个数 */typedef int Status; /* Status为函数类型*/typedef int KeyType; /* 关键字域为整型 */#define EQ(a,b) (a)=(b) /*定义等于*/#define LT(a,b) (a)lchild) DestroyDSTable(&(*DT)-lchild); /* 销毁左孩子子树 */ if(*DT)-rchild) DestroyDSTable(&(*DT)-rchild); /* 销毁右孩子子树 */ free(*DT); *DT=NULL; /* 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素， */ /* 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。*/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); /* 在右子树中继续查找 */* 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找 */ /* 成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上 */ /* 访问的最后一个结点并返回FALSE,指针f指向T的双亲，其初始调用值为NULL */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); /* 递归调用-继续在右子树查找 */* 当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE， */* 否则返回FALSE。*/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; /* 被插结点*s为新的根结点 */ else if LT(e.key,p-data.key) p-lchild=s; /* 被插结点*s为左孩子 */ else p-rchild=s; /* 被插结点*s为右孩子 */ return TRUE; else return 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的右子树 */ else q-lchild=s-lchild; /* 重接*q的左子树 */ free(s); /* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点， */ /* 并返回TRUE；否则返回FALSE。*/Status DeleteBST(BiTree *T,KeyType 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); else DeleteBST(&(*T)-rchild,key); return TRUE; /* 初始条件: 动态查找表DT存在，Visit是对结点操作的应用函数 */ /* 操作结果: 按关键字的顺序对DT的每个结点调用函数Visit()一次且至多一次 */void TraverseDSTable(BiTree DT,void(*Visit)(ElemType) if(DT) TraverseDSTable(DT-lchild,Visit); /* 先中序遍历左子树 */ Visit(DT-data); /* 再访问根结点 */ TraverseDSTable(DT-rchild,Visit); /* 最后中序遍历右子树 */ 4. 测试void print(ElemType c) /*以下主函数调用*/ printf(%d,%d) ,c.key,c.others);void main() /*二叉排序树的查找*/ char q; BiTree dt,p; int i,num; KeyType j; ElemType k; ElemType r10=2,22,3,33,4,44,5,55,6,66,7,77,8,88,9,99,1,11,10,110; /* 测试数据*/ InitDSTable(&dt); /* 构造空表 */ for(i=0;i10;i+) InsertBST(&dt,ri); /* 依次插入数据元素 */ H1: printf( ); printf(n); printf(1、遍历原表n); printf(2、查找元素n); printf(3、删除元素n); printf(4、插入元素n); printf(5、销毁表n); printf(6、退出); printf(n); printf(请选择你需要的操作步：); scanf(%d,&num); switch(num) /*遍历所有元素*/ H2: case 1:printf(原有的表遍历如下：n); TraverseDSTable(dt,print); printf(n); printf(按任意键返回.); getchar(); getchar(); 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) goto H3; else goto H1; else printf(查找失败，表中无此值，是否继续查找？(Y/N):); getchar(); q=getchar(); if(q=Y|q=y) goto H2; else 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 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 goto H1; else printf(插入失败，表中已存在此值，请返回）; getchar(); getchar(); goto H5; /*销毁表*/ case 5: DestroyDSTable(&dt); printf(销毁成功.); goto H2; /*退出系统*/ case 6: printf(nnn 任务完成，再见); printf(nnn ); system(pause); 5.代码分析和测试结果 1.主程序模块与各子程序模块间的调用关系: int main() H（） switch() InitDSTable(DT) InsertDSTable(DT,e) TraverseDSTable(dt,print) 构造空表 插入元素 遍历原表 SearchBST(T,key) DeleteBST(&dt,j) DestroyDSTable(&dt) 查找元素 删除元素 销毁表 其中H