2.1 线性表的逻辑结构

2.1.1 线性表的概念

线性表是由 n ( n ≥0)个相同类型的数据元素组成的有限序列，其元素可以是一个数、一个符号，也可以是由多个数据项组成的复合形式。其中数据元素的个数 n 定义为线性表的长度。当 n =0时线性表为空表，记为（　　）或Φ。

常常将非空的线性表（ n >0）记作( a ₁ , a ₂ ,…, 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 ₁ , a ₂ ,…, a _i , a _{i +1} ,..., a _n )

其中， a ₁ 为第一个元素，又称作表头元素； a ₂ 为第二个元素； a _n 为最后一个元素，又称作表尾元素。

一个线性表可以用一个标识符来命名，如用 L 命名上面的线性表，则

L = ( a ₁ , a ₂ ,…, 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}。

2.1.2 线性表的基本操作

线性表是一种相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，也可以进行插入和删除操作等。

抽象数据类型线性表的定义如下：

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)等基本运算的执行结果。

各种基本运算结果如下： 1+9FYpGXuYNM9b8aNTI8ooE9U3YlenSyqWVhMQoYfLWE69/b/q1tY5tylR7Jxt6V

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')