资源描述：
《几种数据结构的抽象数据类型定义》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、几种数据结构的抽象数据类型定义1、线性表的抽象数据类型定义ADTList{数据对象：D={ai
2、ai∈ElemSet,i=1,2,…,n,n≧0}数据关系：R1={
3、ai-1,ai∈D,i=1,2,…,n}基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，
4、则返回TRUE，否则返回FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i,&e)初始条件：线性表L已存在，1≦i≦ListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是数据元素判定函数。操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。PriorElem(L,cur_e,&pr
5、e_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。ListInsert(&L,i,e)初始条件：线性表L已存在，1≦i≦ListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDel
6、ete(&L,i,&e)初始条件：线性表L已存在且非空，1≦i≦ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。}ADTList2、栈的抽象数据类型定义ADTStack{数据对象：D={ai
7、ai∈ElemSet,i=1,2,…,n,n≧0}数据关系：R1={
8、ai-1,ai∈D,i=1,2,
9、…,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的数据元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回
10、S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit())初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。}ADTStack3、队列的抽象数据类型定义ADTQueue{数据对象：D={ai
11、ai∈ElemSet,i=1,2,…,n,n≧0}数据关系：R1={12、i-1,ai>
13、ai-1,ai∈D,i=1,2,…,n}约定a1为队列头，an为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：销毁队列Q。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的数据元素个数，即队列的长度。Ge
14、tHead(Q,&e)初始条件：队列Q已存在且非空。操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)初始条件：队列Q已存在且非空。操作结果：删除Q的队头元素，并用e返回其值。QueueTraverse(Q,visit())初始条件：队列Q已存在且非空。操作结
