数据结构：线性表的顺序与链式存储实现

C 的初始动态分配语句为：

L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);

2.3 顺序表的优缺

• 优点：可以随机访问，存储密度高。
• 缺点：不方便变动，不够灵活。

2.4 核心功能实战

顺序表的初始化

静态分配

void InitList(SqList *L) {
    L->length = 0; // 顺序表初始长度为 0
}

动态分配

void InitList(SeqList *L) {
    L->data = (ElemType*)malloc(sizeof(ElemType) * InitSize); // 分配动态存储空间
    L->length = 0;                                           // 顺序表初始长度为 0
    L->MaxSize = InitSize;                                   // 初始存储容量
}

插入操作

这里要注意位序和数组下标的转换。我们通常用 1-based 的位序来描述，但代码里要用 0-based 的下标。

// 在指定位置插入元素
bool ListInsert(SqList *L, int i, ElemType e) {
    // 判断位序 i 是否合法
    if (i < 1 || i > L->length + 1) 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 个位置插入元素
    L->data[i - 1] = e;
    L->length++;
    return true;
}

顺序表插入元素的平均时间复杂度是 O(n)。

删除操作

// 删除指定位置的元素
bool ListDelete(SqList *L, int i, ElemType *e) {
    // 判断位序 i 是否合法
    if (i < 1 || i > L->length) return false;
    // 保存被删除的元素
    *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(n)。

按位查找

// 按位查找
bool GetElem(SqList L, int i, ElemType *e) {
    // 判断位序 i 是否合法
    if (i < 1 || i > L.length) return false;
    *e = L.data[i - 1];
    return true;
}

顺序表按位查找的平均时间复杂度是 O(1)。

按值查找（顺序查找）

// 按值查找
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) return i + 1;
    }
    return 0;
}

顺序表按值查找的平均时间复杂度是 O(n)。

以上是基于 C 语言的代码实现，以下是 Java 的代码实现，逻辑类似，但利用了 Java 的数组特性。

public class SequentialList {
    // 定义常量和数据类型
    private static final int MAX_SIZE = 100;
    private int[] data;
    private int length;

    // 构造函数：初始化顺序表
    public SequentialList() {
        data = new int[MAX_SIZE];
        length = 0;
    }

    // 在指定位置插入元素
    public boolean insert(int index, int element) {
        // 判断索引是否合法（1~length+1）
        if (index < 1 || index > length + 1) return false;
        // 判断顺序表是否已满
        if (length >= MAX_SIZE) return false;
        // 将第 index 个位置及之后的元素后移
        for (int j = length; j >= index; j--) {
            data[j] = data[j - 1];
        }
        data[index - 1] = element; // 在第 index 个位置插入元素
        length++;                  // 顺序表长度加 1
        return true;
    }

    // 删除指定位置的元素
    public boolean delete(int index, int[] element) {
        // 判断索引是否合法（1~length）
        if (index < 1 || index > length) return false;
        element[0] = data[index - 1]; // 保存被删除的元素
        // 将第 index+1 个位置及之后的元素前移
        for (int j = index; j < length; j++) {
            data[j - 1] = data[j];
        }
        length--; // 顺序表长度减 1
        return true;
    }

    // 按位查找：获取顺序表中第 index 个位置的元素
    public boolean getElement(int index, int[] element) {
        // 判断索引是否合法（1~length）
        if (index < 1 || index > length) return false;
        element[0] = data[index - 1]; // 将第 index 个位置的元素赋值给 element
        return true;
    }

    // 打印顺序表中的所有元素
    public void printList() {
        System.out.print("顺序表中的元素： ");
        for (int i = 0; i < length; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println("\n顺序表长度：" + length);
    }
}

三、线性表的链式表示

3.1 单链表

3.1.1 定义

单链表是一种链式存储结构，通过节点（Node）连接而成。每个节点包含：

• 数据域：存储数据元素的值
• 指针域：存储下一个节点的地址（null 表示无后继节点）

逻辑结构： head -> Node1 -> Node2 -> ... -> Node(n) -> null （head 为头指针，指向链表第一个节点；最后一个节点的指针域为 null）

3.1.2 节点定义

typedef int ElemType;
// 单链表节点结构体
typedef struct LNode {
    ElemType data;      // 数据域
    struct LNode* next; // 指针域，指向下一个节点
} LNode, *LinkList;     // LinkList 为指向结构体的指针类型

3.1.3 核心操作实现

（1）初始化空链表

带头节点能简化很多边界情况处理，比如插入第一个元素不需要特殊判断头指针。

// 初始化空链表（带头节点）
bool InitList(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode)); // 分配头节点
    if (*L == NULL) return false;        // 内存分配失败
    (*L)->next = NULL;                   // 头节点指针域置空
    return true;
}

（2）按位序插入节点

// 在第 i 个位置插入元素 e（带头节点）
bool ListInsert(LinkList L, int i, ElemType e) {
    if (i < 1) return false; // 位序 i 不能小于 1
    LNode *p = L;            // p 指向头节点，从第 0 个位置开始遍历
    int j = 0;               // 当前位置 j=0（头节点位置）
    // 找到第 i-1 个节点
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return false; // i 超过链表长度 +1
    // 创建新节点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next; // 新节点指向 p 的后继节点
    p->next = s;       // p 的后继节点改为新节点
    return true;
}

（3）按位序删除节点

// 删除第 i 个位置的元素，并用 e 返回值（带头节点）
bool ListDelete(LinkList L, int i, ElemType *e) {
    if (i < 1) return false;
    LNode *p = L;
    int j = 0; // 找到第 i-1 个节点
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL || p->next == NULL) return false; // i 不合法或链表为空
    LNode *q = p->next; // q 指向待删除节点
    *e = q->data;       // 保存删除元素的值
    p->next = q->next;  // 跳过待删除节点
    free(q);            // 释放内存
    return true;
}

（4）按位序查找节点

// 按位序 i 查找节点（返回节点指针）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) return NULL; // i=0 时返回头节点
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p; // 找到返回节点，否则返回 NULL
}

3.1.4 特点

• 优点：动态分配内存，无需预先确定长度；插入/删除操作无需移动大量元素，时间复杂度为 O(1)（找到前驱节点后）。
• 缺点：无法随机访问元素，按位查找需遍历链表（时间复杂度 O(n)）；存储密度低（每个节点需额外存储指针域）。

3.2 双链表

3.2.1 定义

双链表的节点包含两个指针域：

• prior：指向前驱节点
• next：指向后继节点

逻辑结构：head <-> Node1 <-> Node2 <-> ... <-> Node(n)（头节点的 prior 为 null，尾节点的 next 为 null）

3.2.2 节点定义

typedef struct DNode {
    ElemType data;
    struct DNode* prior; // 前驱指针
    struct DNode* next;  // 后继指针
} DNode, *DLinkList;

3.2.3 核心操作实现（插入与删除）

（1）插入节点（在 p 节点后插入 s 节点）

void InsertAfter(DNode *p, DNode *s) {
    s->next = p->next; // s 的后继指向 p 的后继
    if (p->next != NULL) { // 若 p 不是尾节点，更新后继的前驱
        p->next->prior = s;
    }
    p->next = s;   // p 的后继指向 s
    s->prior = p;  // s 的前驱指向 p
}

（2）删除节点（删除 p 节点的后继节点 q）

bool DeleteNext(DNode *p) {
    if (p == NULL || p->next == NULL) return false;
    DNode *q = p->next; // q 为 p 的后继节点
    p->next = q->next;  // p 的后继改为 q 的后继
    if (q->next != NULL) { // 若 q 不是尾节点，更新后继的前驱
        q->next->prior = p;
    }
    free(q); // 释放内存
    return true;
}

3.2.4 特点

• 优点：支持双向遍历，可快速找到前驱节点；插入/删除操作更安全（避免单向链表的'断链'风险）。
• 缺点：结构更复杂，占用内存更多；操作需同时维护两个指针域。

3.3 循环链表

3.3.1 定义

循环链表是首尾相连的链表，分为单循环链表和双循环链表：

• 单循环链表：尾节点的 next 指向头节点
• 双循环链表：头节点的 prior 指向尾节点，尾节点的 next 指向头节点

逻辑结构（单循环链表）：head -> Node1 -> Node2 -> ... -> Node(n) -> head

3.3.2 核心特点

• 判空条件：头节点的 next 是否指向自身（单循环链表）
• 遍历终止条件：是否回到头节点
• 合并操作：可通过修改首尾节点的指针实现 O(1) 时间复杂度合并

3.3.3 单循环链表初始化

// 初始化单循环链表（带头节点）
bool InitCircList(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode));
    if (*L == NULL) return false;
    (*L)->next = *L; // 头节点指针指向自身
    return true;
}

3.3.4 遍历操作（单循环链表）

void TraverseCircList(LinkList L) {
    LNode *p = L->next; // p 指向第一个节点
    while (p != L) {    // 未回到头节点时继续遍历
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

四、顺序表 vs 链表 对比

总结：

• 若需要高效查询，选顺序表；
• 若需要灵活增删，选链表；
• 循环链表适合环形结构场景（如约瑟夫环问题）；
• 双链表适合双向遍历需求（如文件历史记录）。