抽象数据类型实现动态查找表.doc

抽象数据类型动态查找表的定义如下：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(&T, key); 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值； 操作结果：若DT中存在其关键字等于key的数据元素，则删除之。 TraverseDSTable(DT, Visit(); 初始条件：动态查找表DT存在，Visit是对结点操作的应用函数； 操作结果：按某种次序对DT的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。 ADT DynamicSearchTable一、顺序储蓄：1、 顺序存储结构定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define IBFEASIBLE -1#define OVERFLOW -2 #define TABLE_INIT_SIZE 100typedef int KeyType;typedef int Status;typedef structKeyType key; ElemType; typedef structElemType *elem;数据元素存储基址 int length;/有的长度 DSTable;2、 算法设计/构建一个空的动态查找表void InitDSTable(DSTable &T) T.elem=(ElemType *)malloc(TABLE_INIT_SIZE*sizeof(ElemType); if(!T.elem)exit(OVERFLOW); 如果分配失败，返回ERROR T.length=0;/Ends InitDSTable/销毁动态查找表void DestroyDSTable(DSTable &T) free(T.elem);释放元素存储的空间 /Ends DestroyDSTable/动态查找表查找元素Status SearchDSTable(DSTable T,KeyType key) int n;while(!T.elem) return ERROR; /表为空,返回ERRORfor(n=0;n=0) for(j=i;j0) int n; for(n=0;nT.length;n+) visit(T,n); printf(n);/Ends TraveseDSTable3、测试及调试测试调用的函数void NewFile(DSTable &T)int i,j,k,a20; printf(n要输入的元素的个数为:); scanf(%d,&i); printf(n这些元素是(元素以空格键分开):n); for(j=0;ji;j+) scanf(%d,&aj); InitDSTable(T); for(k=0;k7) printf(操作代号为1-7，请重新输入操作代号 ); switch(SOC) case 1:NewFile(T);break; case 2:LookUp(T,a);break; case 3:DeleteContant(T,b);break; case 4:DeleteTable(T);break; case 5:charu(T);break; case 6:TraveseDSTable(T);break; case 7:exit(0); s=SOC;运行程序后，屏幕显示：主界面选择命令1按下ENTER进入下一个界面 然后输入7个数据.它们分别为1 2 3 4 5 6 7;以空格键分开.输完后按下ENTER.进入下一个界面:选择数据3然后按下ENTER键,显示3所在的位置.如下图:查找不存在的数字如下：进入下一个界面: 选择你要删除的元素.选择2然后按下ENTER.显示如下图:选择5进入下一个界面: 输入元素8,然后元素8插入到表末.如下图所示.选择6对动态表进行遍历.如下图表中的元素显示到界面,如下图然后我选择了4,选择4后动态查找表会被销毁.全都元素也将消失,如下图最后选择7退出程序.4、测试数据:选择1然后输入7然后再分别输入1 2 3 4 5 6 7流个数据;按下ENTER.输出:1 2 3 4 5 6 7选择2进入下一个界面:选择数据3然后按下ENTER键输出:2 (以0为基址作为数据的第一个存储位置)选择3进入下一个界面: 选择你要删除的元素.这里我选了元素2然后按下ENTER.输出:1 3 4 5 6 7选择5进入下一个界面: 输入元素8,按下ENTER键.输出:1 3 4 5 6 7 8 选择6按下ENTER键,对动态表进行遍历输出: 1 3 4 5 6 7 8选择了4,选择4后动态查找表会被销毁.全都元素也将消失.选择7退出程序.二、链表储蓄：1、二叉排序树存储结构：#include #include#define TRUE 1#define FALSE 0#define OK 1#define N 10 /数据元素的个数typedef int 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; /* 空指针赋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); else return SearchBST(T-rchild,key); /* 在右子树中继续查找 */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); /* 在左子树中继续查找 */ 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,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); 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); /* 最后中序遍历右子树 */ 3、测试及调试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; ElemType r10=45,1,12,2,53,3,3,4,37,5,24,6,100,7,61,8,90,9,78,10; /* 测试数据*/ InitDSTable(&dt); /* 构造空表 */ for(i=0;idata.key,p-data.others); /getchar(); getchar(); printf(n是否继续查找？(Y/N):); q=getchar(); getchar(); if(q=Y|q=y) goto H3; 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)