1.线性表

# 何为线性表

线性表，顾名思义，就是表中的数据排列成线性的一种数据结构，是零个或多个数据元素的有限序列。简单举个例子，就是排队。

# 有限序列

什么叫做有限序列？

例如，一个班级的学生按照学号从小到大的顺序排队。这就是实际生活中的一个有限序列。

• 此处，序列中的元素是学生们，排序的依据是他们的学号。在线性表中，元素排序的依据是他们的编号，从 1 开始，直到最后一个元素结束。
• 就像学号是 2 号的同学前面排的是且只能是 1 号同学，后面排的是且只能是 3 号同学一样，线性表中的元素也只能按照一对一的顺序排列。1 号元素后面只能是 2 号元素，2 号元素前面也只能是 1 号元素。线性表中除了头尾两个元素的其他元素，都有且只有一个前驱和一个后继。
• 例中排队的都只是学生，老师是不进来排的。同理，线性表存放数据时，只存放一种数据类型。
• 最后，例中的学生们是有限的。再大的一个班也不可能有无限大。同理，线性表中的元素个数也是有限的。实际上，计算机处理的所有对象都是有限的。无限的数列只在数学概念中存在。

# 抽象数据类型定义

# 抽象数据类型

抽象数据类型（ADT）是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性（逻辑结构），而与其在计算机内部如何表示和实现（存储结构）无关。例如在地图类或绘图等的软件系统中，经常会用到坐标。既然坐标总有三个整型数字在一起出现，我们就定义一个叫做 point 的抽象数据类型，它有 x，y 和 z 三个整型变量。

定义一个抽象数据类型，还需要定义在该模型上的一组操作。例如刚才的 point ，在实际应用中，我们会需要计算一个点与另外一个点的距离，即输入两个点的坐标，输出两点间的距离。这就是基于 point 的一组操作。

# 线性表的抽象数据类型

如上定义，我们可以写出线性表的抽象数据类型：

ADT 线性表(List)
Data
    线性表的数据对象集合为{a1, a2, ..., an}，每个元素的类型均为 DataType。
    其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素。
    除了最后一个元素an外，每一个元素有且只有一个直接后继元素。
    数据元素之间的关系是一对一的关系。
Operation
    InitList(*L):   初始化，建立一个空的线性表L。
    DestroyList(*L)：   销毁线性表，释放线性表L占用的空间。
    ListLength(L)：求线性表的长度，返回L中元素的个数。
    ListEmpty(L)：  若线性表为空，返回true；否则返回false。
    ClearList(*L)： 将线性表清空。
    GetElem(L, i, *e)： 将线性表L中的第i个位置的元素返回给e。
    LocateElem(L, e)：  在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功。
    ListInsert(*L, i, e)：  在线性表L中的第i个元素前插入与给定值e相等的元素。
    ListDelete(*L, i, e):   找到线性表中的第i个元素，将之存入e中，并从表中删除。
    DispList(L)：   输出整个表。

# 线性表存储结构

# 线性表的顺序存储结构

# 顺序储存结构

顺序储存结构，顾名思义，是以事物的逻辑结构为存储结构来进行储存。比如上面那个按学号排队的例子。每个同学都有一个学号，按照学号从小到大排队，我们就可以轻松的通过某位同学在队伍中的位置获知这位同学是谁。

如下表：

# 顺序存储结构的线性表

在实际使用中，我们定义顺序存储结构的线性表 (下称 “顺序表”) 如：

typedef struct{

    ElemType data[MAX_SIZE];    //MAX_SIZE 是预先定义好的 const（使用宏定义）

    int length;                 // 用于存储线性表长度

}SqList;

数组（int a [n]）的存储实现方式如下表：

是不是正好符合顺序表的需要？
所以，我们可以在此使用数组。

另外，我们还可以使用 malloc () 函数和 realloc () 函数，对顺序表的存储空间进行动态分配。
如此，顺序表定义如：

typedef struct{

    ElemType* data;

    int length;

}SqList;

因为在 C 和 C++ 中，声明一个数组 a 后，实际上变量 a 的值是数组的起始地址。也就是说，其实 a 是一个 const int*。可知，我们对指针类型变量操作，如：

int* data;

int i;

printf(%d,data[0]); // 输出起始地址为 data 的 int 的值

printf(%d,data[i]); // 输出起始地址为 data+i*sizeof (int) 的 int 的值

也可以像操作数组一样操作对应位置的数据。

所以，以上两种定义方式的存储结构是一样的，都和上面的表格一样。唯一的区别是使用数组则顺序表长度有最大限制，为 MAX_SIZE；而使用指针并使用 malloc () 和 realloc () 则顺序表长度没有最大限制（限制为堆大小？）。

顺序表的基本操作如上 ADT，可以根据实际需要进行删减或添加。

# 顺序表的应用实例

# 例 1

假设一个线性表采用顺序存储结构，设计一个算法，删除其中所有值等于 x 的元素，要求算法的时间复杂度为 O(n) ，空间复杂度为 O(1) 。

void delnode1(SqList* &L, ElemType x)

{

    int k = 0,i;

    for(i = 0;i<L->length;i++)

        if(L->data[i] != x)

        {

            L->data[k] = L->data[i];

            k++;

        }

    L->length = k;

}

void delnode2(SqList* &L, ElemType x)

{

    int k = 0;i = 0;

    while(i<L->length)

    {

        if(L->data[i] == x)

            k++;

        else

            L->data[i-k] = L->data[i];

    }

    L->length -= k;

}

有时候，我们可能会更容易想到如下两种解法：
(1) 每次删除一个等于 x 的元素时都进行元素移动。该算法时间复杂度为 O(n^2) ，空间复杂度为 O(1)
(2) 在算法中临时新建一个顺序表用于存放不等于 x 的元素，通过扫描原来的顺序表得到新的顺序表。该算法时间复杂度为 O(n) ，空间复杂度为 O(n) 。

# 例 2

有一个顺序表 L ，假设元素类型 ElemType 为 int ，设计一个尽可能高效的算法，以第一个元素为分界线（基准），将所有小于等于它的元素移到该基准的前面，将所有大于它的元素移到该基准的后面。

解决思路是使用一个变量（如 pivot ）存储该基准，然后用 i 从前向后扫描大于基准的元素，用 j 从后向前扫描小于基准的元素。交换每对 i 和 j , 直到全部找完。

void partition1(SqList *&L)

{

    int i=0,j=L->length-1;

    ElemType pivot=L->data[0];

    while(i<j)

    {

        while(i<j && L->data[j]>pivot)

            j--;

        while(i<j && L->data[i]<=pivot)

            i++;

        if(i<j)

            swap(L->data[i],L->data[j]);

    }

    swap(L->data[0],L->data[i])

}

void partition2(SqList *&L)

{

    int i=0,j=L->length-1;

    ElemType pivot=L->data[0];

    while(i<j)

    {

        while(i<j && L->data[j]>pivot)

            j--;

        L->data[i]=L->data[j];

        while(i<j && L->data[i]<=pivot)

            i++;

        L->data[j]=L-data[i]

    }

    L->data[i]=pivot;

}

两种解法的时间复杂度均为 O(n) ，空间复杂度均为 O(1) 。
但相对来讲，第二个算法中移动元素的次数更少，所以算法更优（swap 一次等于移动三次）。

本例实际上是快速排序的划分过程。

# 例 3

有一个顺序表 L ，假设元素类型 ElemType 为 int ，设计一个尽可能高效的算法，将所有奇数移动到偶数的前面。

void move1(SqList *&L)

{

    int i=0,j=L->length-1;

    while(i<j)

    {

        while(i<j && L->data[j]%2==0)

            j--;

        while(i<j && L->data[i]%2==1)

            i++;

        if(i<j)

            swap(L->data[i],L->data[j]);

    }

}

void move2(SqList *&L)

{

    int i=-1,j;

    for(j=0;j<=L->length-1;j++)

    {

        if(L->data[j]%2==1)

        {

            i++;

            if(i!=j)

                swap(L->data[i],L->data[j])

        }

    }

}

两种解法的时间复杂度均为 O(n) ，空间复杂度均为 O(1) 。

# 线性表的链式存储结构

# 链式存储结构

啥叫链式？顺序表的特点是逻辑结构就是它的存储结构，也就是说一个跟着一个。链式存储结构的线性表（链表）的特点就是一个连着一个，这就叫链式。

这连着和跟着有啥区别呢？区别在于，链表的每一个元素，都只知道它的后一个元素在哪里。换言之，你现在已知链表中间的某个元素，你想要找它前面的元素，那是确实有点难办的；要想找它后面的元素，那也不是不行，只不过也比顺序表麻烦而已。下面看个实际生活中的例子：

• 李刚出去游泳。带的东西有点多了，一个储物格放不下。他见没有连续的空位了，便决定挑两个分开的柜子放自己的东西。放完东西准备出去了，他发现拿两把钥匙太麻烦了，怎么办？

显然，最好想的办法是把其中一把钥匙放到另外一把钥匙对应的柜子里，然后带走另外一把钥匙。这样，只用拿一把钥匙，很方便。这就是链表的基本结构：存储一个结点的地址（通常是头结点），每个结点中存储着指向下一个结点的指针（最后一个结点的指针指向 NULL，类比一下就是最后一个柜子里没有下一个柜子的钥匙）。这种一个结点指向下一个结点的顺序表，就叫做链表。

# 链式存储结构的线性表

结点结构体定义如下：

typedef struct LNode

{

    ElemType data;

    LNode* next;

}LinkNode

其中， data 存储该结点的数据， next 指针指向下一个结点。
因为一个结点只存储一个数据，链表不需要考虑超限的问题：它本来就是一种动态的存储结构。

# 参考资料

1. 清华大学出版社 - 数据结构教程（第五版）