#新星杯·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;
}
✅ 代码全在这儿了,一个字符都不差。
⌨️ 别光看,打开你的编译器,照着——敲——一——遍!
知道你心里在想:
“复制粘贴多快啊,何必自己敲?”
但——信我一次!
✋ 亲手敲代码 和 Ctrl+C
/ Ctrl+V
,
是两种完全不同的世界!
你会在敲的过程中:
发现括号没配对
发现分号漏了
发现变量名拼错了
甚至手滑把 ==
敲成 =
……
这些看似“浪费时间”的 Debug
过程,
恰恰是你肌肉记忆形成的关键!
是你真正内化知识的必经之路!
✨ 敲完、编译、运行、跑通的那一刻——
那种从指尖传到心里的成就感,
比刷十篇教程、看一百个视频都爽!
八、实战任务
任务1: 把上面所有代码整合到一个项目里,实现一个能存100个整数的顺序表。
任务2: 在 main 函数里,测试所有操作:初始化、尾插10个数、头插一个数、中间插入一个数、查找、删除、打印、销毁。
任务3(进阶): 把 SLDataType
改成 struct Student
,实现一个学生信息管理系统! (储存学生姓名就行了)
把这个顺序表吃透,它就是你C语言进阶路上的第一块基石。
觉得有用的大佬,点个赞支持一下!
关注我 @月夜的风吹雨,下一篇我们用这个顺序表,手把手撸一个【通讯录系统】!