下载掌阅APP，畅读海量书库
立即打开
线性表是由 n ( n ≥0)个相同类型的数据元素组成的有限序列，其元素可以是一个数、一个符号，也可以是由多个数据项组成的复合形式。其中数据元素的个数 n 定义为线性表的长度。当 n =0时线性表为空表，记为（ ）或Φ。
常常将非空的线性表（ n >0）记作( a 1 , a 2 ,…, a n )，这里的数据元素 a i （1≤ i ≤ n ）只是一个抽象的符号，其具体含义在不同的情况下可以不同。
例如，由26个英文字母组成的字母表
(A, B, C, … , Z)
就是一个线性表，表中的每个数据元素均是一个大写字母。
再如，软件2001班、软件2002班、软件2003班、……、软件2010班的班级人数
(44, 45, 46,...,45)
也是一个线性表，表中的每个数据元素均是正整数。这两个线性表都是包含简单数据元素的例子。
设序列中第 i （ i 表示逻辑位序）个元素为 a i （1≤ i ≤ n ），则线性表的一般表示为
( a 1 , a 2 ,…, a i , a i +1 ,..., a n )
其中， a 1 为第一个元素，又称作表头元素； a 2 为第二个元素； a n 为最后一个元素，又称作表尾元素。
一个线性表可以用一个标识符来命名，如用 L 命名上面的线性表，则
L = ( a 1 , a 2 ,…, a i , a i +1 ,..., a n )
线性表中的元素在位置上是有序的，即第 i 个元素 a i 处在第 i −1个元素 a i −1 的后面和第 i +1个元素 a i +1 的前面，这种位置上的有序性就是一种线性关系，所以线性表是一个线性结构，用二元组表示为
L = ( D , R )
其中，
D = { a i |1≤ i ≤ n , n ≥0, a i 为ElemType类型}，ElemType是自定义的类型标识符。
R = { r }， r = {< a i , a i +1 >|1≤ i ≤ n −1}。
线性表是一种相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，也可以进行插入和删除操作等。
抽象数据类型线性表的定义如下：
ADT List{
数据对象：D={ai|1≤i≤n,n≥0, ai为ElemType类型}
数据关系：R={<ai, ai+1>| ai,ai+1∈D,i=1,…,n−1}
基本操作：
//初始化线性表，构造一个空的线性表L
InitList(&L)
//销毁一个已存在的线性表，释放线性表L占用的内存空间
DestroyList(&L)
//判断线性表是否为空，若L为空表，则返回真值，否则返回false
ListEmpty(L)
//求线性表长度，返回线性表中元素的个数
ListLength(L)
//输出线性表，当线性表L不为空时，依次输出线性表中各元素
DispList(L)
//获取线性表中某位置元素，获取线性表L中位置i的元素，用e返回该元素
GetElem(L,i,&e)
//按元素查找，返回线性表中第一个等于e的元素的位置，不存在则返回0
LocateElem(L,e)
//插入元素，在线性表L位置i处插入一个元素，该元素值等于e
ListInsert(&L,i,e)
//删除元素，将线性表L位置i处的元素删除，并用e将该元素返回
ListDelete(&L,i,&e)
}
对于上面定义的抽象数据类型线性表，还可以进行一些更复杂的操作，例如，将两个或两个以上的线性表合并成一个线性表，把一个线性表分拆成两个或两个以上的线性表等。
一个线性表 L =('a', 'f ', 'e', 'd')，求ListLength(L)、ListEmpty(L)、GetElem(L,2,e)、LocateElem(L,'a')、ListInsert(L,4,'e')和ListDelete(L,3)等基本运算的执行结果。
各种基本运算结果如下：
ListLength(L) = 4；
ListEmpty(L); //返回false（0）
GetElem(L,2,e),e = 'f'；
LocateElem(L,'a') = 1；
ListInsert(L,4,'e'); //执行后线性表L = ('a', 'b', 'f', 'e', 'e', 'd')
ListDelete(L,3); //执行后线性表L = ('a', 'f', 'e', 'd')