线性表的定义与特点及抽象数据类型定义

系统管理员 2023-07-08 09:26 17阅读 0赞

## 一、线性表的定义 ##

由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表。  
线性表中元素的个数n(n>=0)定义为线性表的长度，n=0时线性表称为空表。

## 二、非空线性表及线性结构的特点 ##

1、存在唯一的一个被称为“第一个”的数据元素；  
2、存在唯一的一个被称为“最后一个”的数据元素；  
3、除第一个结点外，剩余的每个数据元素都只有一个前驱；  
4、除最后一个结点外，剩余的每个数据元素都只有一个后继；

## 三、线性表的抽象数据类型定义 ##

**ADT List\{**   
数据对象： D=\{ai I aiEElemSet, i=l, 2, …， n, n;;,Q\}  
数据关系：R=(<a 七 1,ai>I a 仁 1,aiED, i=2, …, n\}  
基本操作：  
**Ini tList (&L)**  
操作结果：构造一个空的线性表L。  
**DestroyList(&L)**  
初始条件：线性表L已存在。  
操作结果：销毁线性表L。  
**ClearList (&L)**  
初始条件：线性表L已存在。  
操作结果：将L重置为空表。  
**ListEmpty(L)**  
初始条件：线性表L已存在。  
操作结果：若L为空表，则返回true, 否则返回false。  
**ListLength(L)**  
初始条件：线性表L已存在。  
操作结果：返回L中数据元素个数。  
**GetElem(L,i,&e)**  
初始条件：线性表L巳存在，且1:,s;i:os;ListLength(L)。  
操作结果：用e返回L中第1个数据元素的值。  
**LocateElem(L,e)**  
初始条件：线性表L已存在。  
操作结果：返回L中第1个 值与e相同的元素在 L中的位置 。若这样的数据元素不存在 ，则返回值为0。  
**PriorElem(r,cur\_e,&pre\_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:,s;i:os;ListLength (L) +l。  
操作结果：在 L中第1个位置之前插入新的数据元素 e, L的长度加1。  
**ListDelete(&L,i)**  
初始条件：线性表L已存在且非空，且l:os;i:os;ListLength(L)。  
操作结果：删除L的第1个数据元素，L的长度减1。  
**TraverseList(L)**  
初始条件：线性表L已存在。  
操作结果：对线性表L进行遍历，在遍历过程中对 L的每个结点访问一次。  
**\} ADT List**