一、线性表：从生活到代码

大家好，我是你们的讲师。今天咱们聊聊线性表——数据结构里最基础、最常用的结构之一。

什么叫线性表？说白了，就是一组数据排成一队。你想想看，生活中的排队买票、通讯录里的联系人、播放列表里的歌曲，都是线性表。它们有一个共同特点：每个元素都有前一个和后一个（除了头和尾）。

我个人习惯把线性表理解成「一串珠子」。每颗珠子是一个数据元素，线把它们串起来。你可以从第一颗摸到最后一颗，也可以从中间抽出一颗再塞回去。嗯，这个比喻很形象，对吧？

1.1 线性表的抽象数据类型

抽象数据类型，简称ADT。别被这个词吓到，它其实就是定义「能干什么」，不管「怎么干」。就像你点外卖，你只关心能不能送到、多少钱，不关心骑手走哪条路。

线性表的ADT包括：

• 数据对象：一组同类型的数据元素
• 数据关系：元素之间是一对一的线性关系
• 基本操作：初始化、插入、删除、查找、获取长度、判空等

我在项目中遇到过很多新手，一上来就写代码，结果写到一半发现「哎呀，这个操作我忘了定义」。所以我的建议是：先想清楚你要哪些操作，再动手写代码。

二、顺序表：用数组实现线性表

顺序表，就是用数组来存储线性表。逻辑上相邻的元素，在物理内存里也相邻。说白了，就是一块连续的内存空间，一个挨一个地放数据。

顺序表有两种实现方式：

• 静态数组：大小固定，比如 int arr[100]。缺点很明显——用少了浪费，用多了不够。
• 动态数组：运行时动态分配内存，不够了可以扩容。这才是实战中常用的方式。

我个人强烈推荐用动态数组。为什么？因为静态数组的容量是写死的，你永远不知道用户会塞多少数据。我曾经接手过一个项目，原代码用静态数组存传感器数据，结果某天数据量突然超标，程序直接崩溃……从那以后，我再也不敢用固定大小的数组了。

2.1 动态数组的实现

咱们来看看动态数组的结构体定义：

typedef struct {
    int *data;      // 指向动态分配的内存
    int length;     // 当前元素个数
    int capacity;   // 当前最大容量
} SeqList;

这里要注意：length是实际存了多少个元素，capacity是能存多少个。两者不一样。当 length == capacity 时，就需要扩容了。

初始化函数：

void initList(SeqList *list, int initCapacity) {
    list->data = (int*)malloc(initCapacity * sizeof(int));
    if (list->data == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    list->length = 0;
    list->capacity = initCapacity;
}

扩容函数：

void expandList(SeqList *list) {
    int newCapacity = list->capacity * 2;  // 每次翻倍
    int *newData = (int*)realloc(list->data, newCapacity * sizeof(int));
    if (newData == NULL) {
        printf("扩容失败\n");
        exit(1);
    }
    list->data = newData;
    list->capacity = newCapacity;
}

三、插入与删除操作

插入和删除是顺序表最核心的操作，也是面试最爱考的点。咱们一个一个来看。

3.1 插入操作

在位置i插入一个元素，需要把i及之后的所有元素往后挪一位。注意：位置i从0开始。

void insertList(SeqList *list, int pos, int value) {
    // 检查位置合法性
    if (pos < 0 || pos > list->length) {
        printf("插入位置不合法\n");
        return;
    }
    
    // 检查是否需要扩容
    if (list->length >= list->capacity) {
        expandList(list);
    }
    
    // 从后往前挪元素
    for (int i = list->length; i > pos; i--) {
        list->data[i] = list->data[i - 1];
    }
    
    // 插入新元素
    list->data[pos] = value;
    list->length++;
}

这里有个细节：为什么从后往前挪？因为如果从前往后挪，后面的元素会被覆盖掉。嗯，这个坑我踩过，当时调试了半天才发现是顺序搞反了。

3.2 删除操作

删除位置i的元素，需要把i之后的所有元素往前挪一位。

void deleteList(SeqList *list, int pos) {
    // 检查位置合法性
    if (pos < 0 || pos >= list->length) {
        printf("删除位置不合法\n");
        return;
    }
    
    // 从前往后挪元素
    for (int i = pos; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    
    list->length--;
}

删除操作的时间复杂度是O(n)，因为最坏情况下要挪动n-1个元素。插入也一样，最坏情况是O(n)。

四、顺序表的优缺点

没有完美的数据结构，只有适合的场景。顺序表也不例外。

优点	缺点
随机访问快：O(1)时间就能访问任意位置	插入和删除慢：平均需要移动一半元素，O(n)
内存连续，CPU缓存友好	需要连续的大块内存，可能造成碎片
实现简单，代码量少	扩容操作有开销，且可能浪费空间
存储密度高（不需要额外指针）	长度变化不灵活，不适合频繁增删

什么时候用顺序表？我个人经验是：

• 数据量相对固定，或者你知道大概范围
• 主要操作是读取，很少插入删除
• 对访问速度要求高

什么时候别用？频繁在中间插入删除的场景，比如文本编辑器、任务调度队列。这时候链表更合适——咱们下一章会讲。

五、知识体系总览

为了让大家对本章内容有个整体认识，我画了一张图：

这张图把本章的知识点串起来了。从线性表的定义出发，到ADT，再到两种实现方式。咱们这节课重点讲顺序表，它的三个核心操作——插入、删除、查找——时间复杂度分别是O(n)、O(n)、O(1)。记住这个，面试时能省不少事。

六、总结

好了，这节课的内容就到这里。咱们回顾一下：

• 线性表是n个数据元素的有限序列，元素之间是一对一关系
• 顺序表用连续内存存储，支持随机访问
• 动态数组比静态数组更灵活，实战中优先使用
• 插入和删除需要移动元素，时间复杂度O(n)
• 顺序表适合读多写少的场景

最后说一句：数据结构没有银弹。顺序表简单高效，但也不是万能的。理解它的优缺点，才能在合适的场景用合适的工具。这是咱们做嵌入式开发的基本功。

---

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