C语言数据结构基础：线性表详解

线性表是数据结构中最基础、最常用的形式，就像一列整齐排队的游客：每个元素有固定位置（前驱和后继），长度可动态变化。在C语言中，它主要通过顺序表（数组实现）和链表（指针实现）两种方式构建。理解线性表是掌握栈、队列等高级结构的基石。本文将深入解析两者的实现、优缺点及实际应用场景，帮助读者打下扎实的数据结构基础。

---

一、顺序表：像火车车厢一样紧密排列

顺序表使用连续内存空间存储元素，类似火车车厢——知道第一节车厢位置，就能快速定位所有车厢。

• 核心特点：地址连续、依次存放、支持随机存取、所有元素类型相同。
• 代码实现：使用数组和长度变量管理。

#include <stdio.h>
#define MAX_SIZE 100  // 最大容量typedef struct {int data[MAX_SIZE];  // 存储数据的数组int length;          // 当前元素数量
} SeqList;// 初始化顺序表
void InitList(SeqList *L) {L->length = 0;  // 初始长度为0
}// 插入元素（在位置i插入e）
int Insert(SeqList *L, int i, int e) {if (i < 1 || i > L->length + 1) return 0;  // 位置不合法if (L->length >= MAX_SIZE) return 0;        // 空间已满// 将i之后的元素后移（从最后一个元素开始移动）for (int j = L->length; j >= i; j--) {L->data[j] = L->data[j-1];}L->data[i-1] = e;  // 插入新元素（索引从0开始）L->length++;       // 长度增加return 1;
}

• 案例演示：假设顺序表存储学生成绩 [85, 92, 78]，在位置2插入新成绩90：
  1. 位置2及之后的元素后移：[85, _, 92, 78]（空出位置）。
  2. 插入新元素：[85, 90, 92, 78]。
• 优缺点分析：
  • ✅ 随机访问快：通过下标直接定位元素，时间复杂度 $O(1)$。
  • ❌ 插入/删除慢：需移动大量元素，时间复杂度 $O(n)$。

---

二、链表：像寻宝游戏一样按线索连接

链表元素分散存储，通过指针连接，类似寻宝地图——每个地点标注下一个地点的位置。

• 核心特点：元素不连续、通过指针链接、支持动态扩展。
• 代码实现：使用节点结构体管理。

#include <stdlib.h>
typedef struct Node {int data;           // 数据域struct Node *next;  // 指针域（指向下一个节点）
} Node, *LinkList;// 创建新节点
Node* CreateNode(int e) {Node *n = (Node*)malloc(sizeof(Node));n->data = e;n->next = NULL;return n;
}// 在链表头部插入元素
void InsertAtHead(LinkList *L, int e) {Node *newNode = CreateNode(e);newNode->next = *L;  // 新节点指向原头节点*L = newNode;        // 更新链表头指针
}// 遍历链表
void PrintList(LinkList L) {Node *p = L;while (p != NULL) {printf("%d -> ", p->data);p = p->next;  // 移动到下一个节点}printf("NULL\n");
}

• 案例演示：链表存储任务清单：
  • 初始状态：买菜 -> 做饭 -> NULL。
  • 头部插入“取快递”：取快递 -> 买菜 -> 做饭 -> NULL。
• 优缺点分析：
  • ✅ 插入/删除快：只需修改指针，时间复杂度 $O(1)$。
  • ❌ 访问元素慢：需从头遍历，时间复杂度 $O(n)$。

---

三、顺序表与链表的对比与应用场景

下表总结关键差异，帮助选择合适结构：

特性	顺序表	链表
内存占用	连续紧凑，无额外开销	分散存储，有指针开销
访问速度	极快（随机访问）$O(1)$	慢（顺序访问）$O(n)$
增删效率	慢（需移动元素）$O(n)$	快（仅改指针）$O(1)$
典型应用	数组计算、矩阵运算	文件系统、浏览器历史记录

选择建议：

• 需要频繁访问元素（如数据查询） ➜ 顺序表。
• 需要频繁插入/删除（如动态列表管理） ➜ 链表。

---

总结

通过本文，你已掌握线性表的核心：顺序表和链表各有优势，是数据结构大厦的基石。实际开发中，结合场景选择：顺序表适合快速访问，链表适合动态操作。后续的栈、队列等结构均基于此衍生。动手实践代码案例，加深理解——数据结构的学习，从线性表开始，步步为营！