当前位置：首页 > news >正文

《手搓动态顺序表：从数组到自动扩容的华丽转身》 - 详解

news 2025/9/21 20:28:02

《手搓动态顺序表：从数组到自动扩容的华丽转身》 - 详解

#新星杯·14天创作挑战营·第15期#

个人主页：月夜的风吹雨的主页
作者简介： C++研发方向学习者
学习专栏：《C语言知识点详解》《VS2022编译器的使用》《数据结构》《算法》
人生格言：任何一个伟大的思想，都有一个微不足道的开始。

文章目录

- 欢迎来到《C语言数据结构实战》！
- 一、为什么不用原生数组？
- 二、结构体定义：搭好地基
- 三、写骨架：核心函数声明
- 四、初始化 & 销毁
- - 4.1 初始化：SLInit
  - 4.2 销毁：SLDestroy
- 五、扩容函数
- - SLCheckCapacity
- 六、增删改查：核心四件套
- - 6.1 尾插：SLPushBack
  - 6.2 尾删：SLPopBack
  - 6.3 头插：SLPushFront
  - 6.4 任意位置插入：SLInsert
  - 6.5 查找：SLFind
- 七、SeqList.h、SeqList.c、test.c 全代码
- 八、实战任务

欢迎来到《C语言数据结构实战》！

这里是从“数组恐惧症”到“顺序表自由人”的修炼场，也是你面试前必刷的硬核副本。

专栏特色：

图解+实战：拒绝纯理论，每行代码都配“人话”解析。
从零到一：手把手带你实现动态顺序表。
避坑指南：那些让你熬夜Debug的坑，我提前给你标好雷区。
真实项目衔接：下一篇直接拿它写通讯录，学完就能用！

学习建议：
1️⃣ 先照着敲一遍（搞崩了也没关系，C语言的浪漫就是Segmentation fault）
2️⃣ 对照注释理解每一行
3️⃣ 用文末【实战任务】巩固肌肉记忆

C语言圈内名言：

“顺序表不是背出来的，是在一次次‘数组越界’中调试出来的！”

一、为什么不用原生数组？

问得好！

原生数组就像你家的老式衣柜：

容量固定：买件大衣？没地方放！
插入麻烦：想在第二件衣服前加一件？后面所有衣服都得挪！
删除尴尬：抽走一件，空位还得手动补！

动态顺序表 = 智能衣柜：
✅ 自动扩容
✅ 插入删除一键搞定
✅ size/capacity 自动记账

一句话总结：

会写动态顺序表，是判断你能不能搞定“真实项目”的第一块试金石。

二、结构体定义：搭好地基

先看核心结构：

#define INIT_CAPACITY 4 // 初始容量，你说了算
typedef int SLDataType;
// 存int，想存结构体？直接改这行！
typedef struct SeqList
{
SLDataType* a;
// 指向动态数组的指针
int size;
// 当前有效数据个数
int capacity;
// 当前总容量
} SL;

关键点：

a 是真正在堆上开辟的数组（堆上开辟的动态内存的空间不随函数的销毁而返回操作系统，而是通过free释放）。
size 和 capacity 是两个“记账本”，缺一不可。

这里我们可以看出size刚好在最后一个有效位置之后便于我们以后的插入和修改

三、写骨架：核心函数声明

接下来，我们把所有核心函数的“空壳子”先声明出来。你只需要把这些代码声明到你的 .h 头文件里，然后在 .c 文件中去实现它们的具体逻辑。
在这里插入图片描述
✍️废话不多说，接下来我们来实现SeqList.h头文件的函数声明

// ================= 初始化 & 销毁 =================
// 初始化顺序表
void SLInit(SL* ps);
// 销毁顺序表，释放内存
void SLDestroy(SL* ps);
// 打印所有数据（调试用）
void SLPrint(SL* ps);
// ================= 核心：自动扩容 =================
// 检查容量，如果满了就自动扩容
// 这是顺序表的灵魂！所有插入操作前都要调用它
void SLCheckCapacity(SL* ps);
// ================= 尾部操作 =================
// 在末尾插入数据
void SLPushBack(SL* ps, SLDataType x);
// 删除末尾的数据
void SLPopBack(SL* ps);
// ================= 头部操作 =================
// 在头部插入数据（所有元素后移）
void SLPushFront(SL* ps, SLDataType x);
// 删除头部的数据（所有元素前移）
void SLPopFront(SL* ps);
// ================= 随机位置操作 =================
// 在指定位置 pos 插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
// 删除指定位置 pos 的数据
void SLErase(SL* ps, int pos);
// 查找数据 x，返回其下标，没找到返回 -1
int SLFind(SL* ps, SLDataType x);

✨接下来就是这些核心函数的实现了。

四、初始化 & 销毁

4.1 初始化：SLInit

void SLInit(SL* ps)
{
assert(ps);
// 防御式编程第一步
ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
if (ps->a == NULL) {
perror("malloc failed");
exit(-1);
}
ps->size = 0;
ps->capacity = INIT_CAPACITY;
}

❗ 注意事项：

assert(ps)：防止传入空指针，程序秒崩。
malloc 必须检查返回值，一但开辟失败你不进行检查所有数据将会丢失。
size 和 capacity 必须初始化，不然就是随机值。
INIT_CAPACITY是在头文件进行宏定义，代表初始化开辟的空间

4.2 销毁：SLDestroy

void SLDestroy(SL* ps)
{
assert(ps);
free(ps->a);
// 释放堆内存
ps->a = NULL;
// 防野指针
ps->size = 0;
ps->capacity = 0;
}

❗ 注意事项：

free 之后必须 = NULL，否则你的ps->a变为野指针。
即使 ps->a 是 NULL，free(NULL) 也是安全的，但置空操作不能省。

五、扩容函数

SLCheckCapacity

void SLCheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity) {
// 扩容为原来的2倍
int newCapacity = ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newCapacity);
if (tmp == NULL) {
perror("realloc failed");
exit(-1);
}
ps->a = tmp;
// 更新指针
ps->capacity = newCapacity;
// 更新容量
}
}

❗ 注意事项：

所有插入函数第一行必须调用它！
必须用临时指针 tmp，防止 realloc 失败导致原指针丢失，内存泄漏。
扩容策略：通常选“倍增”（一般扩容2~3倍），时间与空间的完美平衡。

六、增删改查：核心四件套

6.1 尾插：SLPushBack

void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
// 第一步！永远的第一步！
ps->a[ps->size] = x;
ps->size++;
}

❗ 注意事项：

顺序不能错：先扩容，再赋值，最后 size++。

6.2 尾删：SLPopBack

void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size >
0);
// 防止对空表删除
ps->size--;
// 逻辑删除，物理上数据还在，但被“隐藏”了
}

❗ 注意事项：

不需要移动任何数据，效率 O(1)，最安全的删除方式。
- 因为有效数据只会读到size下标的前一个

6.3 头插：SLPushFront

void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
// 从最后一个元素开始，逐个后移
for (int i = ps->size; i >
0; i--) {
ps->a[i] = ps->a[i - 1];
}
ps->a[0] = x;
ps->size++;
}

❗ 注意事项：

移动数据必须从后往前，避免数据覆盖。
时间复杂度 O(n)，数据量大时慎用。

6.4 任意位置插入：SLInsert

void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);// pos合法性检查SLCheckCapacity(ps);// 从最后一个元素开始，逐个后移for (int i = ps->size; i > pos; i--) {ps->a[i] = ps->a[i - 1];}ps->a[pos] = x;ps->size++;}

❗ 注意事项：

pos 的合法范围是 [0, size]。pos == size 等价于尾插。
同样，移动数据要从后往前。

在这里插入图片描述

6.5 查找：SLFind

int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++) {if (ps->a[i] == x) {return i;// 找到，返回下标}}return -1;// 未找到}

❗ 注意事项：

别忘了 return -1！因为我们需要返回找不到的情况。
时间复杂度 O(n)，大数据量考虑哈希表优化。

七、SeqList.h、SeqList.c、test.c 全代码

SeqList.h

#pragma once
#define INIT_CAPACITY 4
#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <string.h>// 1. 定义你要存的数据类型// 比如存整数，就用 int；存通讯录联系人，可以改成 struct Contacttypedef int SLDataType;// 2. 定义顺序表结构体typedef struct SeqList{SLDataType* a;// 指向动态数组的指针（这就是我们的“盒子”本体）int size;// 当前盒子里有多少个有效数据int capacity;// 当前盒子总共能装多少个数据（容量）} SL;// 起个短点的别名，后面用着方便// ================= 初始化 & 销毁 =================// 初始化顺序表void SLInit(SL* ps);// 销毁顺序表，释放内存void SLDestroy(SL* ps);// 打印所有数据（调试用）void SLPrint(SL* ps);// ================= 核心：自动扩容 =================// 检查容量，如果满了就自动扩容// 这是顺序表的灵魂！所有插入操作前都要调用它void SLCheckCapacity(SL* ps);// ================= 尾部操作 =================// 在末尾插入数据void SLPushBack(SL* ps, SLDataType x);// 删除末尾的数据void SLPopBack(SL* ps);// ================= 头部操作 =================// 在头部插入数据（所有元素后移）void SLPushFront(SL* ps, SLDataType x);// 删除头部的数据（所有元素前移）void SLPopFront(SL* ps);// ================= 随机位置操作 =================// 在指定位置 pos 插入数据void SLInsert(SL* ps, int pos, SLDataType x);// 删除指定位置 pos 的数据void SLErase(SL* ps, int pos);// 查找数据 x，返回其下标，没找到返回 -1int SLFind(SL* ps, SLDataType x);

SeqList.c

// ============= 动态顺序表实现 =============
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
// 初始化
void SLInit(SL* ps)
{
assert(ps);
ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
if (ps->a == NULL)
{
perror("malloc failed");
exit(-1);
}
ps->size = 0;
ps->capacity = INIT_CAPACITY;
}
// 销毁
void SLDestroy(SL* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
// 打印
void SLPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");}// 检查容量并扩容void SLCheckCapacity(SL* ps){assert(ps);if (ps->size == ps->capacity){int newCapacity = ps->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newCapacity);if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}}// 尾部插入void SLPushBack(SL* ps, SLDataType x){assert(ps);SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;}// 尾部删除void SLPopBack(SL* ps){assert(ps);assert(ps->size >0);ps->size--;}// 头部插入void SLPushFront(SL* ps, SLDataType x){assert(ps);SLCheckCapacity(ps);// 从后往前挪动数据for (int i = ps->size; i >0; i--){ps->a[i] = ps->a[i - 1];}ps->a[0] = x;ps->size++;}// 头部删除void SLPopFront(SL* ps){assert(ps);assert(ps->size >0);// 从前往后挪动数据for (int i = 0; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;}// 在指定位置插入void SLInsert(SL* ps, int pos, SLDataType x){assert(ps);assert(pos >= 0 && pos <= ps->size);// pos == size 是尾插SLCheckCapacity(ps);// 从最后一个元素开始，逐个后移for (int i = ps->size; i > pos; i--){ps->a[i] = ps->a[i - 1];}ps->a[pos] = x;ps->size++;}// 删除指定位置的元素void SLErase(SL* ps, int pos){assert(ps);assert(pos >= 0 && pos < ps->size);// pos 必须小于 size// 从 pos 位置开始，逐个前移for (int i = pos; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;}// 查找元素，返回下标，未找到返回 -1int SLFind(SL* ps, SLDataType x){assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
// ============= 测试代码 =============
void TestSeqList()
{
SL sl;
SLInit(&sl);
// 测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPrint(&sl);
// 预期输出: 1 2 3
// 测试头插
SLPushFront(&sl, 0);
SLPrint(&sl);
// 预期输出: 0 1 2 3
// 测试任意位置插入
SLInsert(&sl, 2, 99);
SLPrint(&sl);
// 预期输出: 0 1 99 2 3
// 测试查找
int pos = SLFind(&sl, 99);
printf("99 is at position: %d\n", pos);
// 预期输出: 2
// 测试删除
SLErase(&sl, 2);
SLPrint(&sl);
// 预期输出: 0 1 2 3
// 测试头删和尾删
SLPopFront(&sl);
SLPopBack(&sl);
SLPrint(&sl);
// 预期输出: 1 2
SLDestroy(&sl);
}
int main()
{
TestSeqList();
return 0;
}