线性表（静态链表）

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

线性链表：指的是使用数组代替指针，来描述单链表；每个数据项含有data和cur属性，data是数据的值，cur相当于指向下一个节点的指针。

线性表特性：

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

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

优点：

• 拥有单链表类似的特性。
• 插入和删除元素的时候，只需要修改游标。
• 改进了顺序存储结构中插入和删除操作需要大量移动元素的缺点。

缺点：

• 没有解决连续存储分配带来的表长难以确定的问题。
• 失去了顺序存储结构随机存取的特性。

时间复杂度

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

数据项示意图 空静态链表示意图 静态链表插入元素示意图 静态链表删除元素示意图

实现代码如下：

// 线性表（静态链表）
#include <stdio.h>
#include <malloc.h>
#include <time.h>

#define OK 1      // 执行成功
#define ERROR 0   // 执行失败

#define MAXSIZE 100 // 初始分配存储空间

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

/**
 * 静态链表结构
 * 1. 数组最后一个元素的cur用来存放第一个插入元素的下标，
 *    相当于头节点，指向0时表示链表为空
 * 2. 数组0下标元素的cur用来存放下一个可用存储位置的下标，
 *    即下一个插入节点的位置
 */
typedef struct {
    ElemType data; // 存放元素值
    int cur; // 指向下一个节点的下标，为0表示无指向，即到达链表末尾
} Component, StaticLinkList[MAXSIZE];

/**
 * 初始化静态链表
 * 将一维数组L的分量链接成一个备用链表，L[0].cur为头指针，0表示空指针
 * @param L 静态链表
 * @return 执行状态
 */
Status InitList(StaticLinkList L) {
    int i; // 用于遍历表元素

    for (i = 0; i < MAXSIZE - 1; i++) {
        L[i].cur = i + 1; // 设置每个位置的指针指向下一个元素的位置
    }
    // 链表中最后一个元素指向0（表示当前第一个插入的节点下标为0，此时链表为空）
    L[MAXSIZE - 1].cur = 0;
    return OK;
}

/**
 * 获取下一个可用存储位置的下标
 * @param L 静态链表
 * @return 下一个可用存储位置的下标，无可用存储位置时返回0
 */
int Malloc_SSL(StaticLinkList L) {
    int i = L[0].cur; // L中0位置cur存的值就是下一个可用存储位置的下标

    // 当前静态链表未满
    if (L[0].cur) {
        L[0].cur = L[i].cur; // 获取下一个可用存储位置的下标
    }
    return i; // 返回下一个可用存储位置的下标
}

/**
 * 释放下标为k的元素到备用链表
 * 即让下标为k的元素成为下一个可插入节点
 * @param L 静态链表
 * @param k 元素下标
 */
void Free_SSL(StaticLinkList L, int k) {
    L[k].cur = L[0].cur; // 让k下标元素的下一个元素指向原本的下一个可插入节点
    L[0].cur = k; // 让k下标的元素成为下一个可插入节点
}

/**
 * 获取线性链表长度
 * @param L 线性链表
 * @return 线性链表长度
 */
int ListLength(StaticLinkList L) {
    int j = 0; // 用于统计元素个数
    int i = L[MAXSIZE - 1].cur; // 获取第一个元素的下标

    // 遍历链表元素
    while (i) {
        i = L[i].cur; // 获取下一个元素的下标
        j++; //统计个数加1
    }
    return j; // 返回链表长度
}

/**
 * 在线性链表中指定位置插入新元素
 * @param L 线性链表
 * @param i 插入位置
 * @param e 插入的值
 * @return 执行状态
 */
Status ListInsert(StaticLinkList L, int i, ElemType e) {
    int j, t; // j是下一个可插入位置的下标，t用于遍历for循环

    int k = MAXSIZE - 1; // 最后一个元素的下标

    // 插入位置下标越界，插入失败
    if (i < 1 || i > ListLength(L) + 1) {
        return ERROR;
    }

    j = Malloc_SSL(L); // 获取下一个可插入位置的下标

    // 线性链表未满（j不为0）
    if (j) {
        L[j].data = e; // 将e赋值给下一个可插入节点的值（j下标的元素表示新节点）

        // 遍历线性链表，找到插入位置的上一个节点
        for (t = 1; t <= i - 1; t++) {
            k = L[k].cur; // 获取下一个元素的坐标
        }

        L[j].cur = L[k].cur; // 新节点的指向插入位置前一个元素的下一个元素（即原本i位置的节点）
        L[k].cur = j; // 插入位置的上一个节点指向新节点
        return OK;
    }
    return ERROR;
}

/**
 * 删除线链性表中指定位置的元素
 * @param L 线性链表
 * @param i 删除位置的下标
 * @return 执行状态
 */
Status ListDelete(StaticLinkList L, int i) {
    int j; // 用于遍历元素

    int k = MAXSIZE - 1; // 最后一个元素的下标

    // 插入位置下标越界，插入失败
    if (i < 1 || i > ListLength(L) + 1) {
        return ERROR;
    }

    // 遍历线性链表，找到删除位置的上一个节点
    for (j = 1; j <= i - 1; j++) {
        k = L[k].cur; // 获取下一个元素的下标
    }

    j = L[k].cur; // 获取被删除元素的下标
    L[k].cur = L[j].cur; // 【被删除节点的上一个节点】指向【被删除节点的下一个节点】（即跳过被删除节点）
    Free_SSL(L, j); // 释放被删除节点
    return OK;
}

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

/**
 * 遍历输出线性链表中所有元素
 * @param L 线性链表
 * @return 执行状态
 */
Status ListTravel(StaticLinkList L) {
    int i = L[MAXSIZE - 1].cur; // 获取链表第一个元素的下标

    printf("[ ");
    // 遍历链表中所有元素
    while (i) {
        visit(L[i].data); // 打印单个节点的值
        i = L[i].cur; // 获取下一个节点的下标
    }
    printf("]\n");
    return OK;
}

int main() {
    StaticLinkList L; // 线性链表
    Status status; // 执行状态

    status = InitList(L); // 初始化线性链表

    printf("初始化后，L的长度为：%d\n", ListLength(L));

    status = ListInsert(L, 1, 'F');
    status = ListInsert(L, 1, 'E');
    status = ListInsert(L, 1, 'D');
    status = ListInsert(L, 1, 'B');
    status = ListInsert(L, 1, 'A');

    printf("在L的表头分别插入五个元素后，L中的值为：");
    ListTravel(L); // 遍历链表元素
    printf("L的长度为：%d\n", ListLength(L));

    status = ListInsert(L, 3, 'C'); // 在第三个位置插入C元素
    printf("在第三个位置插入一个元素C后，L中的值为：");
    ListTravel(L); // 遍历链表元素
    printf("L的长度为：%d\n", ListLength(L));

    status = ListDelete(L, 4); // 删除第四个位置的元素
    printf("删除第四个位置的元素D后，链表L中的值为：");
    ListTravel(L); // 遍历链表元素
    printf("L的长度为：%d\n", ListLength(L));

    return 0;
}

运行结果