资源描述:
《几种数据结构的抽象数据类型定义》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
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已存在且非空。操作结