数据结构与算法基础——第02周-线性表的类型定义(2.3)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 抽象数据类型线性表定义

1
2
3
4
5
6
7
8
ADT List{
	数据对象：D={ai|ai属于Elemeset,（i=1,2,..n,n>=0）}
	数据关系：R={<ai-1,ai>|ai-1,ai属于D,(i=2,3,..,n)}
	基本操作：
	InitList(&L);       DestroyList(&L);
	ListInsert(&L,i,e); ListDelete(&L,i,e);
	...等等
}ADT List

二 抽象数据类型线性表基本操作

2.1 InitList(&L) (Initialization List)

操作结果：构造一个空的线性表L

2.2 DestroyList(&L)

  • 初始条件：线性表L已经存在
  • 操作结果：销毁线性表L

2.3 ClearList(&L)

  • 初始条件：线性表L已经存在
  • 操作结果：将线性表L重置为空表

2.4 ListEmpty(L)

  • 初始条件：线性表L已经存在
  • 操作结果：若线性表L为空表，则返回True，否则返回False

2.5 ListLength(L)

  • 初始条件：线性表L已经存在
  • 操作结果：返回线性表L中的数据元素个数

2.6 GetElem(L,i,&e)

  • 初始条件：线性表L已经存在，1<=i<ListLength(L);
  • 操作结果：用e返回线性表L中第i个数据元素的值

2.7 LocateElem(L,i,compare())

  • 初始条件：线性表L已经存在，compare()是数据元素判定函数
  • 操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0

2.8 PriorElem(L,cur_e,&pre_e)

  • 初始条件：线性表L已经存在
  • 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败；pre_e无意义

2.9 NextElem(L,cur_e,&next_e)

  • 初始条件：线性表L已经存在
  • 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败；next_e无意义

2.10 ListInsert(&L,i,e)

  • 初始条件：线性表L已经存在，1<=i<=ListLength(L)+1
  • 操作结果：在L的第i个位置之前插入新的数据元素e，L的长度加一
1
2
插入元素e之前(长度为n)：(a1,a2,...,ai-1,ai,...an)
插入元素e之后(长度为n+1)：(a1,a2,...,ai-1,e,ai,...an)

2.11 ListDelete(&L,i,e)

  • 初始条件：线性表L已经存在，1<=i<=ListLength(L)
  • 操作结果：删除在L的第i个数据元素，并用e返回其值，L的长度减一
1
2
删除前(长度为n)：(a1,a2,...,ai-1,ai,ai+1...an)
删除后(长度为n-1)：(a1,a2,...,ai-1,ai+1,...an)

2.12 ListTraverse(&L,visited())

  • 初始条件：线性表L已经存在
  • 操作结果：依次对线性表中每个元素调用visited()

三 线性表的类型定义

以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是"做什么"，至于"如何做"等实现细节，只有确定了存储结构之后才考虑