C语言设计线性表：从零掌握顺序存储与链式存储的核心实现与操作技巧

引言：线性表的基础概念

线性表（Linear List）是计算机科学中最基本、最常用的数据结构之一。它由零个或多个数据元素组成的有限序列，具有相同的数据类型，且元素之间存在一对一的前驱后继关系。在C语言中，设计线性表通常涉及两种主要的存储方式：顺序存储结构（通常使用数组实现）和链式存储结构（通常使用指针实现）。

理解这两种存储方式的区别与联系，是掌握数据结构设计的关键。顺序存储适合频繁访问元素但插入删除较慢的场景，而链式存储则适合频繁插入删除但访问较慢的场景。本文将从零开始，详细讲解如何在C语言中设计和实现这两种线性表，并提供完整的代码示例和操作技巧。

我们将按照以下结构展开：

顺序存储线性表的定义与实现。
顺序存储的核心操作（插入、删除、查找等）。
链式存储线性表的定义与实现（单链表）。
链式存储的核心操作（插入、删除、链表反转等）。
两种存储方式的比较与应用场景。
完整代码示例与测试。

通过本文，你将能够独立编写高效的线性表代码，并理解其背后的内存管理技巧。

1. 顺序存储线性表：数组实现

顺序存储线性表（Sequential List）是用一段地址连续的存储单元依次存储线性表的数据元素。通常使用数组来实现，这种结构支持随机访问，时间复杂度为O(1)，但在插入和删除元素时可能需要移动大量元素，时间复杂度为O(n)。

1.1 定义与结构设计

在C语言中，我们需要定义一个结构体来表示顺序表。结构体应包含：

一个数组用于存储数据。
一个整型变量表示当前元素个数（长度）。
一个整型变量表示数组的最大容量（避免溢出）。

为了灵活性，我们可以使用动态内存分配（malloc）来创建数组，而不是固定大小的数组。这样可以根据需要调整容量。

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define INIT_SIZE 10 // 初始容量 // 顺序表结构体 typedef struct { int *data; // 指向数据数组的指针 int length; // 当前长度 int capacity; // 数组总容量 } SeqList; // 初始化顺序表 bool initSeqList(SeqList *list) { list->data = (int *)malloc(INIT_SIZE * sizeof(int)); if (!list->data) { return false; // 内存分配失败 } list->length = 0; list->capacity = INIT_SIZE; return true; }

解释：

data 是动态数组的指针，使用 malloc 分配内存。
length 记录当前元素个数，初始为0。
capacity 记录数组总大小，初始为 INIT_SIZE。
initSeqList 函数负责初始化，如果内存不足返回 false。

1.2 核心操作：插入元素

插入元素时，需要检查位置是否合法（1 <= pos <= length+1）。如果当前长度等于容量，需要扩容（例如翻倍）。插入后，将pos及之后的元素后移一位。

// 扩容函数（内部使用） bool resize(SeqList *list) { int new_capacity = list->capacity * 2; int *new_data = (int *)realloc(list->data, new_capacity * sizeof(int)); if (!new_data) { return false; } list->data = new_data; list->capacity = new_capacity; return true; } // 在指定位置插入元素 bool insertSeqList(SeqList *list, int pos, int value) { if (pos < 1 || pos > list->length + 1) { printf("插入位置无效！n"); return false; } if (list->length >= list->capacity) { if (!resize(list)) { printf("扩容失败！n"); return false; } } // 后移元素 for (int i = list->length; i >= pos - 1; i--) { list->data[i + 1] = list->data[i]; } list->data[pos - 1] = value; // 插入位置从0开始 list->length++; return true; }

详细说明：

位置检查：pos从1开始计数（用户友好），实际数组下标从0开始。
扩容：使用 realloc 扩展内存，翻倍容量以减少频繁分配。
移动元素：从末尾开始后移，避免覆盖。
示例：假设列表为 [10, 20]，在位置2插入30，结果为 [10, 30, 20]。

1.3 核心操作：删除元素

删除元素时，同样检查位置合法性，然后将后续元素前移。

// 删除指定位置元素 bool deleteSeqList(SeqList *list, int pos, int *value) { if (pos < 1 || pos > list->length) { printf("删除位置无效！n"); return false; } *value = list->data[pos - 1]; // 保存删除的值 // 前移元素 for (int i = pos - 1; i < list->length - 1; i++) { list->data[i] = list->data[i + 1]; } list->length--; return true; }

说明：

value 参数用于返回删除的元素值。
前移操作覆盖了被删除元素。
示例：删除 [10, 20, 30] 的位置2，结果 [10, 30]，返回20。

1.4 其他操作：查找与打印

查找按值返回位置（从1开始），打印遍历数组。

// 按值查找位置 int locateSeqList(SeqList *list, int value) { for (int i = 0; i < list->length; i++) { if (list->data[i] == value) { return i + 1; // 位置从1开始 } } return -1; // 未找到 } // 打印顺序表 void printSeqList(SeqList *list) { printf("顺序表 (长度: %d, 容量: %d): ", list->length, list->capacity); for (int i = 0; i < list->length; i++) { printf("%d ", list->data[i]); } printf("n"); } // 销毁顺序表（释放内存） void destroySeqList(SeqList *list) { free(list->data); list->data = NULL; list->length = 0; list->capacity = 0; }

技巧：始终检查内存分配失败，并在程序结束时释放内存，避免泄漏。

1.5 顺序表的优缺点

优点：随机访问快（O(1)），存储密度高（无指针开销）。
缺点：插入删除慢（O(n)），需要预分配空间或动态扩容。
应用场景：数据量固定或访问频繁，如数组排序、静态数据存储。

2. 链式存储线性表：单链表实现

链式存储使用指针链接元素，每个元素（节点）包含数据和指向下一个节点的指针。单链表是最简单的形式，支持高效的插入删除（O(1) 如果已知位置），但访问需要O(n)。

2.1 定义与结构设计

节点结构体包含数据域和指针域。链表结构体包含头指针和长度（可选）。

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // 链表节点结构 typedef struct Node { int data; struct Node *next; } Node; // 链表结构（可选，包含头指针和长度） typedef struct { Node *head; int length; } LinkedList; // 初始化链表（带头节点，简化操作） bool initLinkedList(LinkedList *list) { list->head = (Node *)malloc(sizeof(Node)); if (!list->head) { return false; } list->head->next = NULL; // 头节点的next为空 list->length = 0; return true; }

解释：

带头节点：头节点不存储数据，仅用于指向第一个实际节点。这样插入删除第一个节点时无需特殊处理。
length 可选，用于快速获取长度，但会增加维护成本。

2.2 核心操作：插入元素

插入时，找到位置的前驱节点，调整指针。

// 在指定位置插入元素（pos从1开始） bool insertLinkedList(LinkedList *list, int pos, int value) { if (pos < 1 || pos > list->length + 1) { printf("插入位置无效！n"); return false; } Node *new_node = (Node *)malloc(sizeof(Node)); if (!new_node) { return false; } new_node->data = value; // 找到前驱节点 Node *pre = list->head; for (int i = 1; i < pos; i++) { pre = pre->next; } // 插入 new_node->next = pre->next; pre->next = new_node; list->length++; return true; }

详细说明：

寻找前驱：从头节点开始，移动pos-1步。
指针调整：先让新节点指向原位置节点，再让前驱指向新节点。顺序不能反！
示例：链表 10 -> 20，在位置2插入30，结果 10 -> 30 -> 20。
技巧：如果pos=1，pre是头节点，插入在头后。

2.3 核心操作：删除元素

类似插入，找到前驱，调整指针并释放节点。

// 删除指定位置元素 bool deleteLinkedList(LinkedList *list, int pos, int *value) { if (pos < 1 || pos > list->length) { printf("删除位置无效！n"); return false; } Node *pre = list->head; for (int i = 1; i < pos; i++) { pre = pre->next; } Node *temp = pre->next; *value = temp->data; pre->next = temp->next; free(temp); list->length--; return true; }

说明：

保存要删除的节点指针，释放内存。
示例：删除 10 -> 30 -> 20 的位置2，结果 10 -> 20，返回30。

2.4 其他操作：查找、打印与反转

查找遍历链表，打印同理。反转链表是常见技巧，使用迭代法。

// 按值查找（返回节点指针，或NULL） Node* locateLinkedList(LinkedList *list, int value) { Node *p = list->head->next; while (p) { if (p->data == value) { return p; } p = p->next; } return NULL; } // 打印链表 void printLinkedList(LinkedList *list) { printf("链表 (长度: %d): ", list->length); Node *p = list->head->next; while (p) { printf("%d -> ", p->data); p = p->next; } printf("NULLn"); } // 反转链表（迭代法） void reverseLinkedList(LinkedList *list) { Node *prev = NULL; Node *curr = list->head->next; Node *next = NULL; while (curr) { next = curr->next; // 保存下一个 curr->next = prev; // 反转指针 prev = curr; // 移动prev curr = next; // 移动curr } list->head->next = prev; // 头节点指向新头 } // 销毁链表 void destroyLinkedList(LinkedList *list) { Node *p = list->head; while (p) { Node *temp = p; p = p->next; free(temp); } list->head = NULL; list->length = 0; }

反转技巧详解：

使用三个指针：prev（前一个）、curr（当前）、next（下一个）。
循环中，先保存next，然后反转curr的next指向prev，最后移动prev和curr。
示例：10 -> 20 -> 30 反转为 30 -> 20 -> 10。
注意：反转后长度不变，但顺序改变。适用于需要逆序访问的场景。

2.5 链表的优缺点

优点：插入删除高效（O(1) 如果已知位置），无需预分配内存，动态增长。
缺点：访问慢（O(n)），额外指针开销（存储密度低），可能内存泄漏。
应用场景：数据量不确定、频繁插入删除，如浏览器历史、任务队列。

3. 两种存储方式的比较与操作技巧

3.1 时间与空间复杂度比较

操作	顺序表（数组）	链表（单链表）
访问元素	O(1)	O(n)
插入/删除	O(n)	O(1)（已知位置）
空间开销	低（仅数据）	高（指针）
内存管理	需要扩容	动态分配

技巧1：顺序表适合读多写少；链表适合写多读少。
技巧2：链表中，使用双向链表可以O(1)删除任意节点（包括自身），但增加一个指针开销。
技巧3：在C语言中，链表操作要注意空指针检查，例如 if (p == NULL) 避免段错误。
技巧4：顺序表扩容时，考虑负载因子（length/capacity），超过阈值（如0.75）再扩容，提高效率。
技巧5：链表可以实现循环链表，用于循环队列等场景。

3.2 高级操作技巧

顺序表合并：如果两个顺序表有序，可以归并排序合并，时间O(n+m)。
链表合并：类似，调整指针即可，无需移动元素。
内存池：对于链表，频繁malloc/free可能碎片化，使用内存池预分配节点。
递归实现：链表操作如反转、查找可以用递归，但注意栈溢出风险。

4. 完整代码示例与测试

下面是一个完整的C程序，包含上述所有函数，并提供main函数测试。

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // 顺序表部分（省略重复代码，直接整合） #define INIT_SIZE 10 typedef struct { int *data; int length; int capacity; } SeqList; bool initSeqList(SeqList *list) { list->data = (int *)malloc(INIT_SIZE * sizeof(int)); if (!list->data) return false; list->length = 0; list->capacity = INIT_SIZE; return true; } bool resize(SeqList *list) { int new_capacity = list->capacity * 2; int *new_data = (int *)realloc(list->data, new_capacity * sizeof(int)); if (!new_data) return false; list->data = new_data; list->capacity = new_capacity; return true; } bool insertSeqList(SeqList *list, int pos, int value) { if (pos < 1 || pos > list->length + 1) return false; if (list->length >= list->capacity && !resize(list)) return false; for (int i = list->length; i >= pos - 1; i--) { list->data[i + 1] = list->data[i]; } list->data[pos - 1] = value; list->length++; return true; } bool deleteSeqList(SeqList *list, int pos, int *value) { if (pos < 1 || pos > list->length) return false; *value = list->data[pos - 1]; for (int i = pos - 1; i < list->length - 1; i++) { list->data[i] = list->data[i + 1]; } list->length--; return true; } int locateSeqList(SeqList *list, int value) { for (int i = 0; i < list->length; i++) { if (list->data[i] == value) return i + 1; } return -1; } void printSeqList(SeqList *list) { printf("SeqList: "); for (int i = 0; i < list->length; i++) printf("%d ", list->data[i]); printf("n"); } void destroySeqList(SeqList *list) { free(list->data); list->data = NULL; list->length = 0; list->capacity = 0; } // 链表部分 typedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *head; int length; } LinkedList; bool initLinkedList(LinkedList *list) { list->head = (Node *)malloc(sizeof(Node)); if (!list->head) return false; list->head->next = NULL; list->length = 0; return true; } bool insertLinkedList(LinkedList *list, int pos, int value) { if (pos < 1 || pos > list->length + 1) return false; Node *new_node = (Node *)malloc(sizeof(Node)); if (!new_node) return false; new_node->data = value; Node *pre = list->head; for (int i = 1; i < pos; i++) pre = pre->next; new_node->next = pre->next; pre->next = new_node; list->length++; return true; } bool deleteLinkedList(LinkedList *list, int pos, int *value) { if (pos < 1 || pos > list->length) return false; Node *pre = list->head; for (int i = 1; i < pos; i++) pre = pre->next; Node *temp = pre->next; *value = temp->data; pre->next = temp->next; free(temp); list->length--; return true; } Node* locateLinkedList(LinkedList *list, int value) { Node *p = list->head->next; while (p) { if (p->data == value) return p; p = p->next; } return NULL; } void printLinkedList(LinkedList *list) { printf("LinkedList: "); Node *p = list->head->next; while (p) { printf("%d -> ", p->data); p = p->next; } printf("NULLn"); } void reverseLinkedList(LinkedList *list) { Node *prev = NULL; Node *curr = list->head->next; Node *next = NULL; while (curr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } list->head->next = prev; } void destroyLinkedList(LinkedList *list) { Node *p = list->head; while (p) { Node *temp = p; p = p->next; free(temp); } list->head = NULL; list->length = 0; } // 测试主函数 int main() { // 测试顺序表 printf("=== 测试顺序表 ===n"); SeqList seq; if (!initSeqList(&seq)) { printf("初始化失败n"); return 1; } insertSeqList(&seq, 1, 10); insertSeqList(&seq, 2, 20); insertSeqList(&seq, 2, 15); // 插入中间 printSeqList(&seq); // 输出: 10 15 20 int del_val; deleteSeqList(&seq, 2, &del_val); printf("删除的值: %dn", del_val); // 15 printSeqList(&seq); // 输出: 10 20 printf("查找20的位置: %dn", locateSeqList(&seq, 20)); // 2 destroySeqList(&seq); // 测试链表 printf("n=== 测试链表 ===n"); LinkedList list; if (!initLinkedList(&list)) { printf("初始化失败n"); return 1; } insertLinkedList(&list, 1, 10); insertLinkedList(&list, 2, 20); insertLinkedList(&list, 2, 15); printLinkedList(&list); // 输出: 10 -> 15 -> 20 -> NULL deleteLinkedList(&list, 2, &del_val); printf("删除的值: %dn", del_val); // 15 printLinkedList(&list); // 输出: 10 -> 20 -> NULL reverseLinkedList(&list); printLinkedList(&list); // 输出: 20 -> 10 -> NULL printf("查找10的节点: %pn", locateLinkedList(&list, 10)); // 地址 destroyLinkedList(&list); return 0; }

编译与运行：