数据结构：线性表（List）小结

AcWing 826.从零开始学数据结构：线性表（中）

AcWing 827. 从零开始学数据结构：线性表（下）

一、绪论

1.线性表的定义

线性表(linear list)简称表，是n(n >= 0)个数据元素的有限序列，线性表中数据元素的个数称为线性表的长度。

其中$a_i$(1 <= i <= n)称为数据元素，下角标i表示该元素在线性表中的位置。$a_1$称为表头元素，$a_n$称为表尾元素，任意一对相邻的数据元素$a_{i - 1}$和$a_i$之间存在序偶关系，且$a_{i - 1}$称为$a_i$的前驱，$a_i$称为$a_{i-1}$的后继。

注意：元素$a_i$无前驱，元素$a_{n}$无后继。其他每一个元素有且只有一个前驱和后继。

2.线性表的抽象数据类型定义

线性表是一个相当灵活的数据结构， 对线性表的数据元素不仅可以进行储存和访问，还可以进行插入和删除等基本操作。其抽象数据类型定义为：

ADT List
    DataModel
    Operation
        InitList
            输入：无
            功能：线性表的初始化
            输出：空的线性表
        CreatList
            输入：n 个数据结构
            功能：建立一个线性表
            输出：具有n 个元素的线性表
        DestoryList
            输入：无
            功能：销毁线性表
            输出：释放线性表的储存空间
        PrintList
            输入：无
            功能：遍历操作，遍历输出整个线性表
            输出：线性表的各个元素
        Length
            输入：无
            功能：返回线性表的长度
            输出：线性表中数据元素的个数
        Locate
            输入：数据元素x
            功能：按值查找，在线性表中查找值为x的数据元素
            输出：如果查找成功，返回x值的序号，否则返回查找失败信息
        Get
            输入：元素的序号i
            功能：按位查找，在线性表中查找下标为i的数据元素
            输出：如果查找成功，返回i下标处的值，否则返回查找失败信息
        Insert
            输入：插入位置i;待查元素x;
            功能：插入操作，在线性表的第一个位置处插入一个新元素x
            输出：如果插入成功，返回新的线性表，否则返回插入失败信息
        Delete
            输入：删除位置i
            功能：删除操作，删除线性表中的第i个元素
            输出：如果删除成功，返回被删元素，否则返回删除错误信息
        Empty
            输入：无
            功能：判空操作，判断线性表是否为空表
            输出：如果是空表，返回1，否则返回0
    endADT

需要强调的是，对于不同的应用，线性表的基本操作不同。对于一些不同的问题，各种操作所需的接口可能和基本操作不大一样，这时需要活学活用。

二、顺序表

1.顺序表的存储结构定义

线性表的顺序结构称为顺序表(sequential list)，其基本思想是用一段地址连续的存储单元依次存储线性表的数据结构。

顺序表中数据结构的存储地址是其序号的线性函数，只要确定了顺序存储的起始地址（即基地址），计算任意一个元素的存储地址的时间是相同的，具有这一特点的顺序存储结构称为随机存取结构。

通常使用一维数组来实现顺序表，需要强调的是C语言中下标是从0开始的，而线性表中元素的序号是从1开始的。也就是说，线性表中第$i$个元素是储存在数组中第$i - 1$的位置。

数组中需要分配固定长度的数组空间，因此就必须确定存放线性表的长度。因为线性表中可以插入元素，所以数组的长度必须大于当前线性表的长度。

2.顺序表的实现

· 顺序表的结构体定义

用MaxSize表示数组的长度，用length表示线性表的长度。

下面给出顺序表的储存结构定义：

//假设顺序表最多储存一百个元素
#define Maxsize 100

//定义线性表的数据类型，这里假设为int型
typedef int DataType;

//顺序表的储存结构定义
typedef struct 
{
    DataType data[Maxsize];
    int length; // 线性表的长度
} SeqList;

· 初始化顺序表

初始化线性表只需要将顺序表长度length初始为 0, 代码如下：

void InitList(SeqList *L)
{
    L -> length = 0;
}

· 创建一个顺序表

创建一个长度为n的顺序表需要将给定元素传入顺序表中，并将传入元素的个数作为顺序表的长度。函数CreatList 的返回值表示建立顺序表的操作是否成功，如果顺序表的储存空间小于给定的元素格式个数，则无法建立顺序表，代码如下:

int CreatList(SeqList* L, DataType a[], int n)
{
    if (n > Maxsize) 
    {
        printf("顺序表的空间不够，无法建立顺序表\n"); 
        return 0;
    }

    for (int i = 0; i < n; i++)
    {
        L->data[i] = a[i];
    }

    L->length = n;

    return 1;
}

· 销毁线性表

顺序表是静态存储分配，在顺序表变量中退出作用域时自动释放该变量所占内存单元，因此，顺序表无需销毁。

· 判空操作

顺序表的判空操作只需要判断长度length是否为0, 代码如下：

int Empty(SeqList* L)
{
    if (L->length == 0) return 1;
    else return 0;
}

· 求顺序表的长度

在顺序表中用结构体成员length表示线性表的长度，因此，求线性表的长度只需要返回成员length的值，代码实现如下：

int length(SeqList* L)
{
    return L->length;
}

· 遍历操作

在顺序表中，遍历操作即按下标输出各个元素。代码实现如下：

void PrintList(SeqList* L)
{
    for (int i = 0; i < L->length; i++)
    {
        printf("%d", L->data[i]);
    }
}

· 按值查找

在顺序表中实现按值查找操作，需要对顺序表中的元素依次进行比较，如果查找成功，返回元素的序号，否则返回查找失败的标志，实现代码如下：

int Locate(SeqList* L, DataType x)
{
    for (int i = 0; i < L->length; i++)
    {
        if (L->data[i] == x) return i + 1; // 返回序号
    }

    return 0; // 没找到返回0
}

按值查找从第一位元素开始，依次向后找，再好的情况是第一个元素就是我们要找的元素，最坏的情况是最后的一个元素是我们要找的元素。平均下来就是顺序表的一半，所以按值查找的时间复杂度为O(n).

· 按位查找

顺序表中第$i$个位置储存在数组下标为$i- 1$的位置，所以容易实现按位查找。按位查找的时间复杂度为O(1)，通过参数ptr返回查找到的值，代码实现如下：

int Get(SeqList* L, int i, DataType* ptr)
{
    if (i < 1 || i > L->length) 
    { 
        printf("查找数据非法，查找失败\n");
        return 0;
    }
    else
    {
        *ptr = L->data[i - 1];
        return 1;
    }
}

· 插入操作

插入操作是在顺序表的第$i$个位置插入一个新元素x，使长度为n的线性表变成长度为n+1的线性表，插入元素后，元素$a_i$和$a_{i-1}$之间的逻辑关系发生了变化并且要反映在储存空间中。

函数Insert的返回值表示插入操作是否成功，如果插入成功，顺序表L中多一个数据元素，代码如下：

int Insert(SeqList* L, int i, DataType x)
{
    if (L->length >= Maxsize)
    {
        printf("上溢错误，插入失败\n");
        return 0;
    }
    if (i < 1 || i > L->length)
    {
        printf("插入位置错误，插入失败\n");
        return 0;
    }
    for (int j = L->length; j >= i; j--)
    {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = x;
    L->length++;
    return 1;
}

· 删除操作

删除操作是把线性表中第i个元素删除，使用长度为n的线性表变成n-1的线性表，删除操作就是从i+1个元素开始向前移，直至最后一个元素前移位置，并且在移动之前需要取出被删元素。

函数Delete的返回值表示删除操作是否成功，如果删除成功，则通过指针参数ptr返回被删元素值。

int Delete(SeqList* L, int i, DataType* ptr)
{
    if (i < 1 || i > L->length)
    {
        printf("删除位置错误，删除失败\n");
        return 0;
    }
    if (L->length == 0)
    {
        printf("下溢错误，删除失败\n");
        return 0;
    }
    *ptr = L->data[i - 1]; //取出位置i的元素

    for (int j = i; j < L->length; j++)
    {
        L->data[j - 1] = L->data[j]; // 数组左移
    }
    L->length--;

    return 1;
}

3.顺序表的使用

在定义了顺序表的储存结构SeqList并实现了基本操作后，程序中就可以使用SeqList类型来定义变量，并可以调用基本操作实现相应的功能。测试代码如下：

#include <stdio.h>

/*上述用到的函数*/  

int main()  
{  
    SeqList L;  
    InitList(&L);  

    int a[5] = { 1, 2, 3, 4, 5 };  
    CreatList(&L, a, 5);  
    PrintList(&L); // 输出：12345  

    if (Empty(&L)) printf("顺序表为空\n"); // 输出：顺序表为空  
    else printf("顺序表不为空\n");  

    printf("顺序表的长度为：%d\n", length(&L)); // 输出：顺序表的长度为：5  

    DataType x = 3;  
    int pos = Locate(&L, x);  
    if (pos) printf("元素%d在顺序表中的位置是：%d\n", x, pos); // 输出：元素3在顺序表中的位置是：3  
    else printf("顺序表中没有找到元素%d\n", x);  

    int i = 3;  
    DataType value;  
    if (Get(&L, i, &value)) printf("元素%d在顺序表中的值为：%d\n", i, value); // 输出：元素3在顺序表中的值为：3  
    else printf("查找数据非法，查找失败\n");  

    Insert(&L, 2, 100);  
    PrintList(&L); // 输出：1002345  

    Delete(&L, 2, &value);  
    printf("删除元素%d后的值为：", value);  
    PrintList(&L); // 输出：删除元素100后的值为：2345  

    return 0;  
}