抽象数据类型实现_动态查找表.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 100 typedef int KeyType; typedef int Status; typedef struct{KeyType key; }ElemType; typedef struct{ ElemType *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; //表为空,返回ERROR for(n=0;nT.length;n++) {while(T.elem[n].key==key) return n+1;} //返回查找结果 return ERROR; //查找失败,返回ERROR }//Ends SearchDSTable //插入新元素到动态查找表中 void InsertDSTable(DSTable T,KeyType e) { T.elem[T.length].key=e; //插入元素 T.length++;//增加表长 }//Ends InsertDSTable //删除动态查找表中元素e void DeleteDSTable(DSTable T,KeyType e) {int i,j; i=SearchDSTable(T,e)-1; //查找删除元素所在位置 if(i=0) {for(j=i;jT.length-1;j++) {T.el