3.线性表

友人大约 8 分钟

3.线性表

线性表定义和操作

线性表

线性表是具有相同数据类型的n个数据元素的有限集序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，其一般表示为：L = ( a₁ ,a₂ ,...,a_i ,a_i+1 ,...,a_n )

线性表的基本操作：

InitList(&L):初始化表，构造一个空的线性表。
Length(L):求表长，返回线性表L的长度，即L中元素的个数。
LocateElem(L,e):按值查找操作，在表L中查找具有给定关键字值的元素。
GetElem(L,i):按位查找操作。获取表L中第i个位置的数据元素的值。
ListInsert(&L,i,e):插入操作，在表L中的第i个位置上插入指定的元素e.
ListDelete(&L,i,&e):删除操作，删除表L中的第i个位置的元素，并用e返回删除元素的值。
PrintList(L):输出操作，按前后顺序输出线性表L的所有元素值。
Empty(L):判空操作，若L表为空，则返回True，否则返回false。
DestroyList(&L):销毁操作，销毁线性表，并释放线性表L所占用的内存空间。

顺序表

线性表的顺序结构又称为顺序表，他是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理上也相邻。

线性表的顺序存储类型描述：

ElemType 是线性表的元素类型

#define MaxSize 50  // 定义线性表的最大容量
typedef struct{
    ElemType data[MaxSize]; // 顺序表的元素
    int length; // 顺序表当前的长度
}SqList;    // 顺序表的类型定义

顺序表的特点

顺序表中元素的逻辑顺序和实际的物理顺序相同，所以插入和删除操作需要移动大量元素。
顺序表中第一个元素存储在线性表的起始位置，第 i 个元素的存储位置后面紧接着存储的是第 i + 1 个元素，称 i 为元素 ai 在线性表中的位序。
顺序表最重要的特点是支持随机访问，即通过首地址和元素需要可在 O(1) 时间内找到指定的元素。
通常情况下使用数组来表述线性表的顺序存储结构。
顺序表的存储密度高，每个结点只存储数据元素。

注意

线性表中元素的位序是从 1 开始的，而数组中元素的下标是从 0 开始的。

顺序表上基本操作的实现：

说明

这里实现了顺序表的插入、删除、按值查询、按序号查询操作的算法。

插入操作

在顺序表 L 的第 i 个位置插入新元素 e 。若 i 的位置不合法，则返回 fasle，表示插入失败。否则将第 i 个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素 e，顺序表长度增加 1 ，插入成功，返回 true。

bool ListInsert(SqList &L, int i, ElemType e){
    // 判断 i 的范围是否合法
    if (i < 1 || i >= L.length){
        return false;
    }

    // 当存储空间已满时，则无法插入
    if (L.length >= MaxSize){
        return false;
    }

    // 将第 i 个元素及之后的元素后移
    for (int j = L.length; j >= i; j--){
        L.data[j] = L.data[j - 1];
    }

    // 在位置 i 处放入 e
    L.data[i - 1] = e;

    // 线性表长度加 1
    L.length ++;

    return true;
}

最好情况：在表头插入（即 i = n + 1），元素后移语句将不执行，时间复杂度为 O(1)

最坏情况：在表头插入（即 i = 1），元素后移语句将执行 n 次，时间复杂度为 O(n)

平均情况：假设 $p_i$ 是在第 i 个位置上插入的一个结点的概率，则在长度为 n 的线性表中插入一个结点时，所需要移动结点的平均次数为 $\sum\limits _{i=1}^{n+1} p_i (n-i+1) = \sum\limits _{i = 1} ^{n+1} \frac {1} {n + 1} * (n - i + 1) = \frac {1} {n + 1} \sum\limits _{i = 1} ^{n+1} (n - i + 1) = \frac {1} {n + 1} \frac {n(n + 1)} {2} = \frac {n} {2}$ ，则平均时间复杂度为 O(n)

删除操作

删除顺序表 L 中第 i 个位置的元素，用引用变量 e 返回。

bool ListDelete(SqList &L, int i, ElemType &e){
    // 判断 i 的位置是否合法
    if (i < 1 || i >= L.length){
        return false;
    }

    // 将被删除的元素赋值给 e
    e = L.data[i - 1];

    // 将第 i 个位置后的元素前移
    for (int j = i; j < L.length; j ++){
        L.data[j - 1] = L.data[j];
    }

    // 线性表长度 减1
    L.length --;

    return true;
}

最好情况：删除表尾元素，则无需移动元素，时复杂度为 O(1)

最坏情况：删除表头元素，则需要移动除表头元素以外的所有元素，时间复杂度为 O(n)

平均情况：假设 $p_i$ 是删除第 i 个位置结点的概率，则在长度为 n 的线性表中删除一个结点时，所需要移动结点的平均次数为 $\sum\limits _{i=1}^{n} p_i (n-i) = \sum\limits _{i = 1} ^{n} \frac {1} {n} * (n - i) = \frac {1} {n} \sum\limits _{i = 1} ^{n} (n - i) = \frac {1} {n} \frac {n(n - 1)} {2} = \frac {n - 1} {2}$ ，则平均时间复杂度为 O(n)

按值查询

在顺序表 L 中查找第一个元素值等于 e 的元素，返回其位序。如果没有找到，则返回 0。

需要注意的是，位序是从 1 开始的，而索引是从 0 开始的。

int LocateElem(SqList &L, ElemeType e){
    int i;

    for (i = 0; i < L.length; i ++){
        if (L.data[i] == e){
            return i + 1;
        }
    }
    return 0;
}

最好情况：查找的元素就在第一个，则只需要比较一次，时间复杂度为 O(1)

最坏情况：查找的元素在最后一个，需要将所有的元素都进行对比，时间复杂度为 O(n)

平均情况：假设 $p_i$ 是在第 i 个位置上插入的一个结点的概率，则在长度为 n 的线性表中查找值为 e 的元素需要比较的平均次数为 $\sum\limits _{i=1}^n p_i * i = \sum\limits _{i = 1} ^n \frac {1} {n} * i = \frac {1} {n} \frac {n(n + 1)} {2} = \frac {n + 1} {2}$ ，则平均时间复杂度为 O(n)

按序号查询

在顺序表 L 中查找位序为 i 个元素的值。

需要注意的是，位序是从 1 开始的，而索引是从 0 开始的。

int getByIndex(SqList &L,int i){
    if (i <= 0 || i > L.length){
        return -1;
    }

    return L.data[i - 1];
}

因为顺序表支持随机访问，所以这里通过位序或者索引进行查找的最好、最坏和平均复杂度都是 O(1) 。

单链表

线性表的链式存储成为单链表，他是通过一组任意的存储单元来存储线性表中的数据元素。通过节点中存储后续节点的指针来进行连接。

单链表中节点类型的描述

typedef struct LNode{   // 定义单链表节点类型
    ElemeType data;     // 数据域
    struct LNode *next; // 指针域
}LNode, *LinkList;

单链表的特点

可以存储大量数据，解决了顺序表需要大量连续存储单元的缺点
存储数据域，还存储指针域，浪费了存储空间
单链表元素离散的分布在存储空间中，是非随机存取的存储结构
通常头指针来标示一个单链表，为了方便操作，在第一个实际节点之间附加一个头结点

单链表上基本操作的实现

头插法建立单链表

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头，即头结点之后。

LinkList List_HeadInsert(LinkList &L){  // 逆向建立单链表
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));// 创建头结点
    L->next = NULL;     // 初始化为空链表
    scanf("%d",&x);     // 输入结点的值
    while (x != 9999) { // 输入 9999 表示结束
        s = (LNode*)malloc(sizeof(LNode)); // 创建新节点
        s->data = x;    // 赋值
        s->next = L->next;      // 赋指针
        L->next = s;    // 将新节点插入表中，L为头指针
        scanf("%d",&x); // 读取下一个值
    }
    return L;
}

每个结点插入的时间为 O(1) ，则当单链表长为 n 时，总时间复杂度为 O(n)

尾插法建立单链表
按序号查找结点值
按值查找表节点
插入结点操作
对某一节点进行前插操作
删除节点操作
求表长操作

int *GetListLen(LinkList L){
    int length = 0;
    for (Node i = L; i = L.next ; i != null){
        length ++;
    }
    return length;
}

双链表

双链表

循环链表

循环链表

静态链表

静态链表