第1章 线性表之顺序表：从零开始构建你的第一个数据结构

大家好，我是你们的老朋友。今天咱们来聊聊线性表里最基础、也最常用的一种实现——顺序表。

说实话，我刚开始学数据结构那会儿，觉得顺序表不就是个数组嘛，有啥好学的？后来在项目中吃过亏才明白——数组是语言提供的，顺序表是自己设计的。这两者之间，差着工程思维的距离。

1.1 什么是顺序表？

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

你想想看，这跟数组有什么区别？

嗯，区别在于：数组是静态的，顺序表是动态的。数组的长度一旦定义就不能变了，而顺序表可以动态扩容。这就是为什么我们在工程中更倾向于用顺序表——你永远不知道用户会塞多少数据进来。

核心特征：

  • 元素在内存中连续存储
  • 支持随机访问（O(1)时间复杂度）
  • 插入和删除需要移动元素（O(n)时间复杂度）
  • 可以动态扩容

1.2 顺序表的定义与初始化

先来看看怎么定义一个顺序表。我个人习惯用结构体来封装，这样数据和方法都在一起，清晰明了。

#define INIT_CAPACITY 10  // 初始容量

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

这里要注意：data是一个指针，它指向堆上分配的内存。length是实际存了多少个元素，capacity是当前能存多少个。

初始化函数怎么写？

// 初始化顺序表
int initList(SeqList *list) {
    list->data = (int *)malloc(INIT_CAPACITY * sizeof(int));
    if (list->data == NULL) {
        return -1;  // 内存分配失败
    }
    list->length = 0;
    list->capacity = INIT_CAPACITY;
    return 0;
}

小提示：初始化时一定要检查malloc的返回值。我曾经在一个项目中忘了检查，结果线上环境内存不足时直接段错误，排查了半天才发现是这里的问题。

1.3 插入操作

插入操作是顺序表的核心操作之一。它的逻辑是：在指定位置插入一个新元素，该位置之后的元素全部后移一位。

// 在位置pos插入元素value（pos从0开始）
int insertList(SeqList *list, int pos, int value) {
    // 检查位置合法性
    if (pos < 0 || pos > list->length) {
        return -1;  // 位置不合法
    }
    
    // 检查是否需要扩容
    if (list->length >= list->capacity) {
        if (expandList(list) != 0) {
            return -2;  // 扩容失败
        }
    }
    
    // 从后往前移动元素
    for (int i = list->length; i > pos; i--) {
        list->data[i] = list->data[i - 1];
    }
    
    // 插入新元素
    list->data[pos] = value;
    list->length++;
    
    return 0;
}

为什么从后往前移动？你想想看，如果从前往后移，前面的元素会把后面的覆盖掉，数据就丢了。这个细节，我当年面试的时候就答错过。

注意：插入位置pos的范围是[0, length]。如果pos等于length，相当于在末尾追加，不需要移动元素。如果pos大于length，那就是非法操作了。

1.4 删除操作

删除操作和插入相反：把指定位置的元素删掉，后面的元素全部前移一位。

// 删除位置pos的元素，通过value返回被删除的值
int deleteList(SeqList *list, int pos, int *value) {
    // 检查位置合法性
    if (pos < 0 || pos >= list->length) {
        return -1;
    }
    
    // 取出被删除的元素
    *value = list->data[pos];
    
    // 从前往后移动元素
    for (int i = pos; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    
    list->length--;
    return 0;
}

这里有个小细节：删除后我们并没有释放内存，只是把length减1了。为什么？因为后面可能还要插入新元素，留着空间可以避免频繁扩容。这是一种空间换时间的策略。

1.5 查找操作

查找操作分两种：按值查找和按位置查找。

按位置查找很简单，直接通过下标访问就行，时间复杂度O(1)。

// 按位置查找
int getElement(SeqList *list, int pos, int *value) {
    if (pos < 0 || pos >= list->length) {
        return -1;
    }
    *value = list->data[pos];
    return 0;
}

按值查找需要遍历整个表，时间复杂度O(n)。

// 按值查找，返回第一个匹配的位置
int findElement(SeqList *list, int value) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == value) {
            return i;
        }
    }
    return -1;  // 没找到
}

1.6 动态扩容策略

这是顺序表最精彩的部分。当表满了怎么办？我们需要申请一块更大的内存，把旧数据搬过去。

// 扩容：每次扩容为原来的2倍
int expandList(SeqList *list) {
    int newCapacity = list->capacity * 2;
    int *newData = (int *)realloc(list->data, newCapacity * sizeof(int));
    
    if (newData == NULL) {
        return -1;  // 扩容失败
    }
    
    list->data = newData;
    list->capacity = newCapacity;
    return 0;
}

为什么扩容倍数是2？不是1.5？不是3？

这里面有讲究：

  • 如果扩容倍数太小（比如1.1），会频繁触发扩容，性能差
  • 如果扩容倍数太大（比如3），会浪费大量内存
  • 2倍是一个折中方案，时间效率和空间效率都比较均衡

我的经验：在嵌入式系统中，内存比较金贵，我一般用1.5倍扩容。在服务器端，内存充裕，用2倍扩容更省时间。没有银弹，要根据场景选。

知识体系总览

下面这张图把顺序表的核心知识点串起来了，你可以对照着复习：

顺序表 定义与初始化 插入操作 删除操作 查找操作 动态扩容 销毁与清理 位置检查 元素后移 2倍扩容 realloc 时间复杂度：随机访问O(1) | 插入删除O(n) | 查找O(n)

完整代码示例

最后，我把所有操作整合成一个完整的示例，方便你直接运行测试：

#include <stdio.h>
#include <stdlib.h>

#define INIT_CAPACITY 10

typedef struct {
    int *data;
    int length;
    int capacity;
} SeqList;

// 初始化
int initList(SeqList *list) {
    list->data = (int *)malloc(INIT_CAPACITY * sizeof(int));
    if (list->data == NULL) return -1;
    list->length = 0;
    list->capacity = INIT_CAPACITY;
    return 0;
}

// 扩容
int expandList(SeqList *list) {
    int newCapacity = list->capacity * 2;
    int *newData = (int *)realloc(list->data, newCapacity * sizeof(int));
    if (newData == NULL) return -1;
    list->data = newData;
    list->capacity = newCapacity;
    return 0;
}

// 插入
int insertList(SeqList *list, int pos, int value) {
    if (pos < 0 || pos > list->length) return -1;
    if (list->length >= list->capacity) {
        if (expandList(list) != 0) return -2;
    }
    for (int i = list->length; i > pos; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[pos] = value;
    list->length++;
    return 0;
}

// 删除
int deleteList(SeqList *list, int pos, int *value) {
    if (pos < 0 || pos >= list->length) return -1;
    *value = list->data[pos];
    for (int i = pos; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;
    return 0;
}

// 按位置查找
int getElement(SeqList *list, int pos, int *value) {
    if (pos < 0 || pos >= list->length) return -1;
    *value = list->data[pos];
    return 0;
}

// 按值查找
int findElement(SeqList *list, int value) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == value) return i;
    }
    return -1;
}

// 打印
void printList(SeqList *list) {
    printf("[");
    for (int i = 0; i < list->length; i++) {
        printf("%d", list->data[i]);
        if (i < list->length - 1) printf(", ");
    }
    printf("]\n");
}

// 销毁
void destroyList(SeqList *list) {
    free(list->data);
    list->data = NULL;
    list->length = 0;
    list->capacity = 0;
}

int main() {
    SeqList list;
    initList(&list);
    
    // 插入测试
    insertList(&list, 0, 10);
    insertList(&list, 1, 20);
    insertList(&list, 2, 30);
    insertList(&list, 1, 15);  // 在中间插入
    printList(&list);  // [10, 15, 20, 30]
    
    // 删除测试
    int val;
    deleteList(&list, 2, &val);
    printf("删除的元素: %d\n", val);  // 20
    printList(&list);  // [10, 15, 30]
    
    // 查找测试
    int pos = findElement(&list, 15);
    printf("15的位置: %d\n", pos);  // 1
    
    destroyList(&list);
    return 0;
}

避坑指南：我曾经在项目中忘记调用destroyList释放内存，导致内存泄漏。虽然程序退出时系统会回收，但如果是长期运行的服务，内存会越占越多。记住：malloc和free要成对出现。

好了，顺序表的内容就讲到这里。代码不多，但每个细节都值得你亲手敲一遍。下一章咱们聊聊链表，那又是另一番天地了。

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

← 上一章 📖 返回目录 下一章 →