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

1、抽象数据类型动态查找表的定义如下：ADT DynamicSearchTable 数据对象 D：D 是具有相同特性的数据元素的集合。每个数据元素含有类型，相同的关键字，可唯一标识数据元素。数据关系R:数据元素同属一个集合。基本操作 P：InitDSTable(&DT);操作结果:构造一个空的动态查找表 DT。DestroyDSTable(&DT);初始条件：动态查找表DT存在；操作结果:销毁动态查找表 DT。SearchDSTable(DT, key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值； 操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该 元素的值或在

2、表中的位置，否则为“空” 。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() 失败

3、，则操作失败。 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;/ 有的长度D

4、STable;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 SearchDSTabl

5、e(DSTable T,KeyType key)int n;while(!T.elem) return ERROR; / 表为空 , 返回 ERROR for(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;

6、ji;j+) scanf(%d,&aj); InitDSTable(T);for(k=0;k7)printf( 操作代号为 1-7, 请重新输入操作代号)；switeh(SOC)ease 1:NewFile(T);break;ease 2:LookUp(T,a);break;ease 3:DeleteC ontan t(T,b);break;ease 4:DeleteTable(T);break;ease 5:eharu(T);break;ease 6:TraveseDSTable(T);break;ease 7:exit(0);s=SOC;运行程序后，屏幕显示：主界面2 4 fi中 表表表査

7、杳香一 态态态 动动动 查餐选择命令1按下ENTER进入下一个界面主菜单晴输入操作代号（1-7） :1要输入的元素的个数为汐这些元素是C元素以空格键分开:儿 建除入岀 B 13 5 7t然后输入7个数据.它们分别为1 2 3 4 5 6 7;以空格键分开.输完后按下ENTER.进入下一个界面：选择数据3然后按下ENTERS,显示3所在的位置.如下图：13 5?杳香一太笑心素兀建除入岀.81容 内素 入元 表表动动动 贅历 查销遍中羹表查查查桑心态请输入操作号码（1-7）=2查找不存在的数字如下:素丄屮表表表 杳一查查 盏-心 动动动 醫历 查矍 * V * 2 4 6Z3- 菜 主7,兀秦请输

8、入操作代号（1-7）=2进入下一个界面：选择你要删除的元素选择2然后按下ENTER显示如下图：素丄屮 耒表表S3查查查态态态查齧 _ 2 4 6单菜容 內素 入元 S i 查查 盔态素 a-祈元 建除入出 新9 13 5 7请输入操作号码(I?) =3 扮想删墜的躯字是吃剩下的内容有：1 3 4 5 & ?输入元素8,然后元素8插入到表末.如下图所示.选择5进入下一个界面素元丄屮表表表8 查查查 态态态 杳销遍 ! 2 4 6单菜内素 入元 表表 查查 态态素 訪-元 建除入岀13 5?悴输入操作号码(1-7)=5青输入要插入的元素汕扁入后的动态查找表为：1345678选择6对动态表进行遍历.

9、如下图表中的元素显示到界面，如下图素元屯表表裘 查查查 桑态 a-动动 普历 查餐 2 4 6单菜熏素 元 建除入出 flBlfi 13 5 7请输入操作号码17)話134567 H然后我选择了 4,选择4后动态查找表会被销毁.全都元素也将消失，如下图请输入操作号码(1-?)=4gWAQ容木表的兀素元1屮表表表香香S-态态态醫历S89*2 4 6最后选择 7 退出程序 .4、测试数据 :选择1然后输入 7然后再分别输入 1 2 3 4 5 6 7 流个数据;按下 ENTER. 输出:1 2 3 4 5 6 7选择2进入下一个界面：选择数据3然后按下ENTERS输出:2 （ 以 0为基址作为数据

10、的第一个存储位置 ）选择 3 进入下一个界面 ： 选择你要删除的元素 . 这里我选了元素 2 然后按下 ENTER.输出：1 3 4 5 6 7选择5进入下一个界面：输入元素8,按下ENTERS.输出：1 3 4 5 6 7 8选择 6 按下 ENTERS, 对动态表进行遍历输出： 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 / 数据元

11、素的个数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 的数

12、据元素， */ /* 若查找成功，则返回指向该数据元素结点的指针 ,否则返回空指针。 */ 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); /* 在右子树中继续查找 */void SearchBST1(BiTree *T,KeyType1 key,BiTree

13、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 的数据元素时，插入

14、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 为

15、左孩子 */ elsep-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(

16、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 的数据元素时，则删除该数据元素结 点， */*并返回T

17、RUE ;否则返回FALSE。*/Status DeleteBST(BiTree *T,KeyType1 key) if(!*T) /* 不存在关键字等于 key 的数据元素 */ return FALSE;elseif 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 是对结

18、点操作的应用函数 */* 操作结果 : 按关键字的顺序对 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

19、,%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();

20、getchar();if(q=Y|q=y)goto H3;elsesystem(cls);goto H1;elseprintf( 查找失败，表中无此值，是否继续查找？ (Y/N):);getchar();q=getchar();if(q=Y|q=y)goto H2;elsesystem(cls);goto H1;H4: case 3:pri ntf(原有的表遍历如下：n);TraverseDSTable(dt,print);printf(n);printf(n 请输入你要删除的值： ); scanf(%d,&j);/getchar();/q=getchar();p=SearchBST(dt,j

21、);if(p)printf( 删除此值后： n);DeleteBST(&dt,j);TraverseDSTable(dt,print);printf(n 是否继续删除？ (Y/N):); getchar();q=getchar();if(q=Y|q=y)goto H4;elsesystem(cls);goto H1;elseprintf( 删除失败，表中无此值，请按任 意键返回继续 );printf(n);getchar();getchar();goto H4;H5: case 4:pri ntf(原有的表遍历如下：n);TraverseDSTable(dt,print);printf(n);

22、 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( 插入失败，表中已存在此值， 请 按任意键返回继

23、续 );getchar()；getchar();goto H5;case 5:DestroyDSTable(&dt);printf( 销毁成功 );goto H2;case 6:system(cls);printf(nnnnnnnnn= 谢谢使用！ =);printf(nnn);system(pause);4、在主函数已经构建了二叉排序树。按课本227页45,1,12,2,53,3,3,4,37,5,24,6,100,7,61,8,90,9,78,10FD:c + -F_placeDynmicSearchTable2DebugDyrnannicSearchTable2.乍 -亠川-. H 鮒

24、有內內个统腰 肇表一表系儒选择了 1之后中序遍历后结果得到D:c + +_p I a ceDyn a m i eSea rchTa ble2Deb u g Dyn a m i eSea rch T a ble2. exe选择2之后查找“ 12”这个元素匸 |回 45. 78,10 90,22是否继续宜找? ：(90,D:c+ + _placeDynainicSearchTabk2DebLigDyni3tnicSfarchT3ble2.exe查有爲个：一耳房SASsisf 、人W人J冃氣-要缪 量表一表系儒搜选有”选择了 3之后，删除“ 12”D:c + + _placeDyin a m i cSea rchTab I e2 DebuqVn a mi cSea rc hTa bl e2. eKel匸I动态查找表演示系统III删瞅裘内但 蒲人二个德 鱷统 進敷畫要购操作(厂): 3 有的裘遍历如下:,4 90,9) 请幫血維删除的血12 53,3) 曰否继续删除？ /N =pi