线性表（链式存储结构）

线性表：包含零个或多个数据元素的有限序列。

线性表的链式存储结构，指的是用一段连续的存储单元存储线性表的数据元素。

线性表特性：

• 是一个序列，元素直接是有顺序的。
• 表中元素个数叫表长，元素个数可以有多个，也可以为0。
• 某个元素的上一个元素叫直接前驱元素，下一个元素叫直接后继元素。

链式存储结构特点
使用带数据域和指针域的节点存储单个元素的值，并通过指针将所有元素连接起来。
优点：

• 可以快速插入和删除节点。
• 无需预先分配大量存储空间。

缺点：

• 查找、修改元素需要遍历整个链表。
• 需要为表中的逻辑关系增加额外的存储空间。

时间复杂度

• 读取时的时间复杂度为O(n)。
• 插入、删除时的时间复杂度为O(1)。

线性链表示意图 线性链表插入元素示意图 线性链表删除元素示意图

实现代码如下：

// 线性表（链式存储结构）
#include <stdio.h>
#include <malloc.h>
#include <time.h>

#define OK 1      // 执行成功
#define ERROR 0   // 执行失败
#define TRUE 1    // 返回值为真
#define FALSE 0   // 返回值为假

typedef int Status; // 函数返回结果类型
typedef int ElemType; // 元素类型

// 链表节点
typedef struct Node {
    ElemType data; // 存放链表元素
    struct Node *next; // 指向下一个节点的指针
} Node;

typedef struct Node *LinkList; // 线性表链表结构

/**
 * 初始化线性表
 * @param L 线性表
 * @return 执行状态
 */
Status InitList(LinkList *L) {
    *L = (LinkList) malloc(sizeof(Node)); // 为链表分配存储空间
    // 存储空间分配失败
    if (!(*L)) {
        return ERROR;
    }

    (*L)->next = NULL; // 让头节点指向为空
    return OK;
}

/**
 * 判断线性表是否为空
 * @param L 线性表
 * @return 执行状态
 */
Status ListEmpty(LinkList L) {
    // 链表中含有元素，不为空
    if (L->next) {
        return FALSE;
    } else {
        return TRUE;
    }
}

/**
 * 清空线性表
 * @param L 线性表
 * @return 执行状态
 */
Status ClearList(LinkList *L) {
    LinkList p, q; // p、q用于遍历并删除L中的所有节点

    p = (*L)->next; // p指向L的第一个节点

    // 链表L中如果还有元素
    while (p) {
        q = p->next; // q指向p的下一个节点
        free(p); // 释放p节点
        p = q; // 让p指向q节点（即相对原来位置向后移动一个位置）
    }
    (*L)->next = NULL; // 头节点指针域置空
    return OK;
}

/**
 * 获取线性表长度
 * @param L 线性表
 * @return 线性表长度
 */
int ListLength(LinkList L) {
    int i = 0; // 用于统计元素个数

    LinkList p = L->next; // p指向L的第一个节点

    // 链表L中如果还有元素
    while (p) {
        i++; // 统计数加1
        p = p->next; // 节点向后移动
    }
    return i; // 返回链表中元素个数
}

/**
 * 获取线性表中指定位置的元素值
 * @param L 线性表
 * @param i 获取元素位置下标
 * @param e 获取元素值
 * @return 执行状态
 */
Status GetElem(LinkList L, int i, ElemType *e) {
    int j; // 计数器
    LinkList p; // 用于遍历链表元素
    j = 1; // 初始下标为1
    p = L->next; // p指向L的第一个元素

    // 当链表L中如果还有元素，并且未到达i位置
    while (p && j < i) {
        p = p->next; // p指向下一个节点
        j++; // 计数器加1
    }

    // p无下一个节点或计数器j超过i位置（即第i个元素不存在）
    if (!p || j > i) {
        return ERROR;
    }
    // 将i节点的数据赋值给e元素
    *e = p->data;
    return OK;
}

/**
 * 定位元素e在线性表中的位置
 * 找到的该元素返回元素下标，未找到该元素返回0
 * @param L 线性表
 * @param e 元素
 * @return 元素在线性表中的下标
 */
int LocateElem(LinkList L, ElemType e) {
    int i = 0; // 记录元素的下标
    LinkList p = L->next; // p指向L的第一个元素

    // 链表L中如果还有元素
    while (p->next) {
        i++; // 下标加1
        // p节点元素的值等于e
        if (p->data == e) {
            return i; // 返回e元素对应的下标
        }
        p = p->next; // p指向下一个元素
    }
    return 0;
}

/**
 * 在线性表中指定位置插入新元素
 * @param L 线性表
 * @param i 插入位置
 * @param e 插入的值
 * @return 执行状态
 */
Status ListInsert(LinkList *L, int i, ElemType e) {
    int j; // 下标计数器
    LinkList p, s; // p用来遍历L的节点，s用来生成新节点

    j = 1; // 计数器起始值为1
    p = *L; // p指向链表头节点

    // 链表L中如果还有元素，并且下标未移动到i位置
    while (p && j < i) {
        p = p->next; // p向后移动
        j++; // 下标计数器加1
    }

    // p节点未空，或下标计数器超出范围（即第i个元素不存在，插入失败）
    if (!p || j > i) {
        return ERROR;
    }

    s = (LinkList) malloc(sizeof(Node)); // 生成新节点
    s->data = e; // 给新节点赋值为e的值
    s->next = p->next; // 新节点s的指针指向插入位置的下一个节点
    p->next = s; // 插入位置的下一个节点指向新节点s
    return OK;
}

/**
 * 删除线性表中指定位置的元素
 * 删除位置的值，将存到元素e中
 * @param L 线性表
 * @param i 删除位置的下标
 * @param e 删除位置的值
 * @return 执行状态
 */
Status ListDelete(LinkList *L, int i, ElemType *e) {
    int j; // 下标计数器
    LinkList p, q; // p用来遍历L的节点，s用来指向将删除的节点

    j = 1; // 计数器起始值为1
    p = *L; // p指向链表头节点

    // 链表L中如果还有元素，并且下标未移动到i位置
    while (p->next && j < i) {
        p = p->next; // p向后移动
        j++; // 下标计数器加1
    }

    // p节点未空，或下标计数器超出范围（即第i个元素不存在，删除失败）
    if (!(p->next) || j > i) {
        return ERROR;
    }

    q = p->next; // q指向被删除节点
    p->next = q->next; // p指向被删除节点的后一个节点
    *e = q->data; // 将被删除节点的值赋值给e元素
    free(q); // 释放被删除节点的空间
    return OK;
}

/**
 * 打印单个元素
 * @param e 元素值
 * @return 执行状态
 */
Status visit(ElemType e) {
    printf("%d ", e);
    return OK;
}

/**
 * 遍历输出线性表中所有元素
 * @param L 线性表
 * @return 执行状态
 */
Status ListTravel(LinkList L) {
    LinkList p = L->next; // p指向L的第一个节点

    printf("[ ");
    // 链表L中如果还有元素
    while (p) {
        visit(p->data); // 打印单个元素
        p = p->next; // p向后移动
    }
    printf("]\n");
    return OK;
}

/**
 * 随机产生n个元素，创建带表头结点的单链线性表（头插法）
 * @param L 线性表
 * @param n 插入元素个数
 */
void CreateListHead(LinkList *L, int n) {
    LinkList p; // 用来创建新节点
    int i; // 用于遍历下标

    srand(time(0)); // 设置随机数种子
    *L = (LinkList) malloc(sizeof(Node)); // 创建带表头节点的单链表
    (*L)->next = NULL; // 将链表指针置空

            // 给线性表L插入n个100以内的随机数
    for (i = 0; i < n; i++) {
        p = (LinkList) malloc(sizeof(Node)); // 生成新节点
        p->data = rand() % 100 + 1; // 生成100以内的随机数，赋值给新节点
        p->next = (*L)->next; // 新元素指向头节点的下一个元素
        (*L)->next = p; // 头节点指向新元素
    }
}

/**
 * 随机产生n个元素，创建带表头结点的单链线性表（尾插法）
 * @param L 线性表
 * @param n 插入元素个数
 */
void CreateListTail(LinkList *L, int n) {
    LinkList p, r; // p用来创建新节点，r用来指向L的表尾
    int i; // 用于遍历下标

    srand(time(0)); // 设置随机数种子
    *L = (LinkList) malloc(sizeof(Node)); // 创建带表头节点的单链表
    r = *L; // r指向L的表尾

    // 给线性表L插入n个100以内的随机数
    for (i = 0; i < n; i++) {
        p = (LinkList) malloc(sizeof(Node)); // 生成新节点
        p->data = rand() % 100 + 1; // 生成100以内的随机数，赋值给新节点
        r->next = p; // 表尾指向新节点
        r = p; // 新节点成为表尾
    }
    r->next = NULL; // 设置表尾指向置空
}

int main() {
    LinkList L; // 线性表

    Status status; // 执行状态
    ElemType e; // 线性表元素
    int result; // 运行结果
    int j, k; // 用于遍历元素的下标

    status = InitList(&L); // 初始化线性表
    printf("初始化线性表L后，L的长度为：%d\n", ListLength(L));

    result = ListEmpty(L); // 获取线性表是否为空
    printf("L是否为空：%s\n", result == TRUE ? "是" : "否");

    /*** 给L的表头插入5个元素 ***/
    for (j = 1; j <= 5; j++) {
        status = ListInsert(&L, 1, j); // 向线性表表头插入值
    }
    printf("在L表头依次插入1~5后，L中的值为：");
    ListTravel(L); // 遍历线性表

    printf("插入5个元素后，L的长度为：%d\n", ListLength(L));

    result = ListEmpty(L); // 获取线性表是否为空
    printf("L是否为空：%s\n", result == TRUE ? "是" : "否");

    /*** 清空L中的元素 ***/
    status = ClearList(&L); // 清空线性表
    printf("清空线性表L后，L的长度为：%d\n", ListLength(L));

    result = ListEmpty(L); // 获取线性表是否为空
    printf("L是否为空：%s\n", result == TRUE ? "是" : "否");

    /*** 给L的表尾插入10个元素 ***/
    for (j = 1; j <= 10; j++) {
        ListInsert(&L, j, j); // 向线性表表尾插入值
    }
    printf("在L表尾依次插入1~10后，L中的值为：");
    ListTravel(L); // 遍历线性表

    printf("插入10个元素后，L的长度为：%d\n", ListLength(L));

    /*** 给L的表头插入一个元素 ***/
    ListInsert(&L, 1, 33); // 向线性表表头插入元素33

    printf("在L表头插入元素33后，L中的值为：");
    ListTravel(L); // 遍历线性表

    printf("插入元素33后，L的长度为：%d\n", ListLength(L));

    /*** 获取第5个元素的值 ***/
    GetElem(L, 5, &e); // 获取L中下标为5的元素到e中
    printf("L中第5个元素的值为：%d\n", e);

    /*** 获取下标为3、4元素的值 ***/
    for (j = 3; j <= 4; j++) {
        k = LocateElem(L, j); // 获取L中下标为j的元素的值
        if (k) {
            printf("第%d个元素的值为：%d\n", k, j);
        } else {
            printf("没有值为%d的元素\n", j);
        }
    }

    /*** 删除表中多个元素 ***/
    k = ListLength(L); // k为表长
    for (j = k + 1; j >= k; j--) {
        status = ListDelete(&L, j, &e); // 删除L中第j个元素，并把删除元素的值赋值给e
        if (status == ERROR) {
            printf("删除第%d个元素失败\n", j);
        } else {
            printf("删除第%d个元素的值为：%d\n", j, e);
        }
    }
    printf("删除表中元素后，L中的值为：");
    ListTravel(L); // 遍历线性表

    /*** 删除L中第5个元素 ***/
    j = 5;
    ListDelete(&L, j, &e); // 删除L中第j个元素，并把删除元素的值赋值给e
    printf("删除第%d个元素的值为：%d\n", j, e);

    printf("删除第%d个元素后，L中的值为：",j);
    ListTravel(L); // 遍历线性表

    /*** 清空L中元素,并使用头插法插入20个元素 ***/
    status = ClearList(&L); // 清空表中元素
    printf("清空L中元素后，L的长度为：%d\n", ListLength(L));

    CreateListHead(&L, 20); // 使用头插法插入20个随机元素
    printf("使用头插法插入20个随机元素后，L中的值为：");
    ListTravel(L); // 遍历线性表

    /*** 清空L中元素,并使用尾插法插入20个元素 ***/
    status = ClearList(&L); // 清空表中元素
    printf("清空L中元素后，L的长度为：%d\n", ListLength(L));

    CreateListTail(&L, 20); // 使用尾插法插入20个随机元素
    printf("使用尾插法插入20个随机元素后，L中的值为：");
    ListTravel(L); // 遍历线性表

    return 0;
}

线性链表运行结果