第5章线性表

课程目录第5章线性表

5. 线性表：从数组到链表，存储的智慧

大家好，我是你们的老朋友。今天我们来聊聊线性表。

说实话，线性表这个概念，在数据结构里属于「入门级」的。但你别小看它。我见过不少工作两三年的工程师，写起链表来照样 bug 一堆。为什么？因为基础不牢。

线性表，说白了就是一组数据排成一条线。每个元素有且只有一个前驱和一个后继（除了头尾）。你想想看，排队打饭、书架上的书、通讯录里的联系人——这些都是线性表。

5.1 线性表的定义

线性表（Linear List）是由 n（n ≥ 0）个相同类型的数据元素构成的有限序列。

当 n = 0 时，称为空表
n > 0 时，除了第一个和最后一个元素，每个元素都有唯一的前驱和后继
元素之间是一对一的线性关系

举个例子：L = (a1, a2, a3, ..., an)。a1 是第一个元素，an 是最后一个。a2 的前驱是 a1，后继是 a3。很直观，对吧？

  核心要点：线性表强调的是「逻辑结构」——元素之间是线性关系。至于物理上怎么存，那是另一回事。

5.2 线性表的抽象数据类型

抽象数据类型（ADT）是什么？我习惯把它理解成「接口定义」。你不需要知道内部怎么实现，只要知道它能干什么。

线性表的 ADT 大概长这样：

ADT 线性表 (List)
Data
  线性表的数据对象集合为 {a1, a2, ..., an}
  每个元素类型均为 DataType
Operation
  InitList(&L):    初始化空表
  DestroyList(&L): 销毁表
  ListEmpty(L):    判断是否为空
  ListLength(L):   返回表长度
  GetElem(L, i):   获取第 i 个元素
  LocateElem(L, e):查找元素 e 的位置
  ListInsert(&L, i, e):在第 i 个位置插入 e
  ListDelete(&L, i):   删除第 i 个元素
  PrintList(L):    遍历输出
endADT

嗯，这里要注意：不同的教材可能操作名不一样，但核心功能就这些。增删改查，一个都不能少。

5.3 顺序存储结构（数组实现）

顺序存储，就是用一块连续的存储空间来存放线性表。说白了就是数组。

优点很明显：

随机存取：O(1) 时间就能拿到第 i 个元素
存储密度高：只存数据，不存指针

缺点也很致命：

插入和删除需要移动大量元素，平均时间复杂度 O(n)
需要预先分配空间，扩容麻烦

我在项目中遇到过一个问题：一个日志系统，需要频繁在中间插入记录。一开始用的数组，结果数据量一上来，插入操作慢得离谱。后来果断换成了链表。

来看代码：

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];  // 数组存储数据
    int length;         // 当前长度
} SqList;

// 插入操作
int ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) return 0;  // 位置不合法
    if (L->length >= MAXSIZE) return 0;         // 表已满

    for (int k = L->length; k >= i; k--) {
        L->data[k] = L->data[k-1];  // 后移
    }
    L->data[i-1] = e;
    L->length++;
    return 1;
}

// 删除操作
int ListDelete(SqList *L, int i, int *e) {
    if (i < 1 || i > L->length) return 0;

    *e = L->data[i-1];
    for (int k = i; k < L->length; k++) {
        L->data[k-1] = L->data[k];  // 前移
    }
    L->length--;
    return 1;
}

避坑指南：我曾经在删除操作里忘了更新 length，结果遍历时多读了一个脏数据。排查了半天才发现。记住：增删操作后一定要同步更新长度！

5.4 链式存储结构（单链表）

链式存储，每个节点除了存数据，还要存一个指向下一个节点的指针。这样就不需要连续的内存了。

你想想看，这就像寻宝游戏——你拿到一张纸条，上面写着下一个线索的位置。顺着找下去，就能走完整条路。

单链表的结构定义：

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node, *LinkList;

核心操作：

// 头插法创建链表
LinkList CreateList_Head(int n) {
    LinkList L = (LinkList)malloc(sizeof(Node));
    L->next = NULL;

    for (int i = 0; i < n; i++) {
        Node *p = (Node *)malloc(sizeof(Node));
        scanf("%d", &p->data);
        p->next = L->next;
        L->next = p;
    }
    return L;
}

// 按位查找
Node *GetElem(LinkList L, int i) {
    if (i < 1) return NULL;

    Node *p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;  // 如果 i 超出范围，返回 NULL
}

// 插入操作
int ListInsert(LinkList L, int i, int e) {
    Node *prev = GetElem(L, i-1);  // 找到前驱节点
    if (!prev) return 0;

    Node *p = (Node *)malloc(sizeof(Node));
    p->data = e;
    p->next = prev->next;
    prev->next = p;
    return 1;
}

// 删除操作
int ListDelete(LinkList L, int i, int *e) {
    Node *prev = GetElem(L, i-1);
    if (!prev || !prev->next) return 0;

    Node *p = prev->next;
    *e = p->data;
    prev->next = p->next;
    free(p);
    return 1;
}

个人经验：写链表操作时，我习惯先画图。把指针的指向画清楚，代码自然就写对了。尤其是插入和删除，顺序搞反了就会丢节点。

5.5 顺序表 vs 链表：怎么选？

对比维度	顺序表（数组）	单链表
存储空间	连续，预分配	离散，动态分配
随机存取	O(1)	O(n)
插入/删除	O(n)（需移动元素）	O(1)（已知位置）
存储密度	高（只存数据）	低（存数据+指针）
适用场景	频繁查找，少增删	频繁增删，少查找

怎么选？我个人的经验是：

如果数据量固定，且主要操作是读取——用顺序表
如果数据量不确定，或者频繁插入删除——用链表
如果两者都需要——考虑用双链表或静态链表

5.6 知识体系总览

下面这张图，是我梳理的本章知识结构。你看一眼就能明白线性表的核心脉络：

这张图把线性表的三大块——定义、顺序存储、链式存储——串在了一起。你顺着看下来，会发现其实逻辑很清晰：先搞清楚「是什么」，再搞清楚「怎么存」，最后搞清楚「怎么选」。

好了，线性表的内容就到这里。记住：数组和链表是数据结构的基石，后面学栈、队列、树，都离不开它们。把今天的内容吃透，后面的路就好走了。

公众号：蓝海资料掘金营，微信 deep3321

📚 课程目录

5. 线性表：从数组到链表，存储的智慧

5.1 线性表的定义

5.2 线性表的抽象数据类型

5.3 顺序存储结构（数组实现）

5.4 链式存储结构（单链表）

5.5 顺序表 vs 链表：怎么选？

5.6 知识体系总览