抽象数据类型实现动态查找表.doc_第1页
抽象数据类型实现动态查找表.doc_第2页
抽象数据类型实现动态查找表.doc_第3页
抽象数据类型实现动态查找表.doc_第4页
抽象数据类型实现动态查找表.doc_第5页
免费预览已结束,剩余13页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

抽象数据类型动态查找表的定义如下: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)

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论