数据结构-线性表第一篇

前言最近二刷了数据结构顺序表的视频课程第一遍学的时候C语言结构体、动态内存分配、指针这些基础掌握得并不扎实只是跟着敲了一遍代码似懂非懂。这次特意从头重学课件作为核心思路参考所有代码全程自己手写、调试、改错、优化把动态顺序表从基础实现到一步步排错再到封装通用打印函数的完整过程走了一遍。这是我的数据结构学习系列第一篇先从最基础的头尾增删开始后续会陆续更新指定位置插入/删除、按值查找、按位置修改等进阶操作最终会基于顺序表实现完整的通讯录项目把学到的知识真正落地。另外我的C语言基础专栏也快要更新收尾了打好C语言地基再循序渐进啃数据结构才是最稳妥的学习节奏。一、学习心得为什么要二刷顺序表顺序表是数据结构第一个线性结构底层完全依赖C语言基础如果结构体、指针、动态内存没学牢根本学不透第一遍只追求“跑起来就行”忽略了代码规范、边界校验、内存泄漏、函数封装这些细节这次重学坚持自己手写每一行代码出Bug自己排查真正理解每一步扩容、插入、删除的逻辑刻意做了代码优化把打印函数改成通用可适配类型后续改顺序表存储类型不用改打印逻辑。二、动态顺序表核心原理结合代码讲解2.1 什么是顺序表顺序表是线性表的一种它的特点是逻辑上连续物理存储上也连续底层本质就是一个数组。我们对数组进行了一层封装加上了“有效数据个数”和“容量”的管理就变成了顺序表。和原生数组相比顺序表的优势是自动管理容量满了自动扩容统一的增删改查接口不用自己手动计算下标自带边界校验减少非法访问2.2 动态顺序表结构体定义这是我自己定义的动态顺序表结构体核心三个成员分工明确// 顺序表存储类型后续改类型只改这里 typedef int SLType; // 动态顺序表结构体 typedef struct SeqList { SLType* a; // 指向动态数组的指针真正存储数据 int size; // 当前有效数据个数 int capacity; // 当前数组总容量满了就自动扩容 }SL;SLType* a用指针指向堆上开辟的动态数组这样才能实现按需扩容int size永远记录当前顺序表里有多少个有效数据所有增删操作都要更新它int capacity记录当前数组最多能存多少个数据当size capacity时触发扩容2.3 核心操作总览本篇先实现顺序表最基础的7个核心操作对应7个函数函数名功能时间复杂度SLInit初始化空顺序表O(1)Destroy销毁顺序表释放内存O(1)SLExp检测并自动扩容O (n)扩容时需要拷贝数据PushBack尾部插入O (1)均摊PushFront头部插入O(n)SLDeleteBack头部删除O(n)SLDeleteBehind尾部删除O(1)Print遍历打印顺序表O(n)后续更新预告下一篇会补充实现SLInsert指定位置插入、SLErase指定位置删除、SLFind按值查找、SLModify按位置修改4个进阶接口让顺序表功能更完整。三、我的代码迭代 排错优化过程全程手写踩坑记录这部分是我这次学习收获最大的地方每一个错误都是自己实际写代码时踩过的坑不是凭空想象的。3.1 初期手写遇到的5个硬性BugBug1头删函数数组越界崩溃错误代码// 错误写法 void SLDeleteBack(SL* ps) { assert(ps); assert(ps-size); // 错误循环条件写成了 i ps-size for (int i 0; i ps-size; i) { ps-a[i] ps-a[i 1]; } ps-size--; }错误原因当i ps-size - 1时i 1 ps-size访问了数组下标为size的元素这是非法内存直接导致程序崩溃。正确代码// 正确写法 void SLDeleteBack(SL* ps) { assert(ps); assert(ps-size); // 正确循环到 size-2 即可最后一个元素不用移动 for (int i 0; i ps-size - 1; i) { ps-a[i] ps-a[i 1]; } ps-size--; }Bug2删除函数多余参数错误代码// 错误写法多了无用参数x void SLDeleteBack(SL* ps, SLType x) void SLDeleteBehind(SL* ps, SLType x)错误原因删除操作只需要知道要删除哪个位置的元素不需要传入数据值。这个多余的参数会导致调用时必须传一个没用的数否则编译报错。正确代码// 正确写法删掉参数x void SLDeleteBack(SL* ps) void SLDeleteBehind(SL* ps)Bug3缺少指针防护断言错误代码// 错误写法没有加 assert(ps) void SLInit(SL* ps) { ps-a NULL; ps-capacity 0; ps-size 0; }错误原因如果不小心传入了NULL指针会直接野指针访问程序崩溃。正确代码// 正确写法第一行加断言校验 void SLInit(SL* ps) { assert(ps); ps-a NULL; ps-capacity 0; ps-size 0; }Bug4扩容逻辑写错错误代码// 错误写法用 size 计算新容量 int Newspace ps-capacity 0 ? 4 : 2 * ps-size;错误原因size是当前有效数据个数capacity才是数组的总容量。虽然在满容时size capacity数值上巧合相等但逻辑上必须用capacity计算。正确代码// 正确写法用 capacity 计算新容量 int Newspace ps-capacity 0 ? 4 : 2 * ps-capacity;Bug5打印函数初始版本漏洞错误代码// 错误写法 void Print(SL* ps) { assert(ps); assert(ps-size); // 错误1空表不能打印 // 错误2少打印最后一个元素 for (int i 0; i ps-size - 1; i) { printf(%d , ps-a[i]); // 错误3格式符写死 } }错误原因空表也应该能打印直接输出空行即可不能断言崩溃循环条件i ps-size - 1会少打印最后一个元素格式符写死为%d改SLType类型就要改打印代码3.2 关键优化通用打印函数实现为了解决“改SLType类型就要改printf格式符”的问题我用宏定义做了一层封装实现了真正通用的打印函数。第一步头文件添加打印格式宏// 通用打印格式宏切换类型只改这里 #define SLTYPE_PRINT_FMT %d // 顺序表存储类型 typedef int SLType;第二步通用打印函数// 通用打印函数适配任意SLType类型 void Print(SL* ps) { assert(ps); for (int i 0; i ps-size; i) { // 直接引用宏自动匹配对应格式 printf(SLTYPE_PRINT_FMT , ps-a[i]); } printf(\n); }切换类型示例如果想改成存储float类型只需要改头文件两行#define SLTYPE_PRINT_FMT %f typedef float SLType;其他所有代码包括打印函数完全不用动直接编译运行即可。3.3 工程化优化多文件拆分我严格按照C语言工程规范把代码拆分成了三个独立文件SeqList.h头文件存放结构体定义、类型别名、宏定义、函数声明SeqList.c源文件存放所有功能函数的具体实现test.c测试文件单独存放主函数专门用来测试所有接口这样拆分的好处是代码结构清晰便于维护接口和实现分离后续修改实现不影响接口测试代码和业务代码解耦不会互相干扰四、完整最终代码本人手写版4.1 SeqList.h 头文件#pragma once #includestdio.h #includestdlib.h #includeassert.h // 通用打印格式宏切换类型只改这里 #define SLTYPE_PRINT_FMT %d // 顺序表存储类型 typedef int SLType; // 动态顺序表结构体 typedef struct SeqList { SLType* a; int size; // 有效数据个数 int capacity; // 储存空间总容量 }SL; // 初始化和销毁 void SLInit(SL* ps); void Destroy(SL* ps); void Print(SL* ps); // 扩容检测 void SLExp(SL* ps); // 头部操作 void PushFront(SL* ps, SLType x); // 头部插入 void SLDeleteBack(SL* ps); // 头部删除 // 尾部操作 void PushBack(SL* ps, SLType x); // 尾部插入 void SLDeleteBehind(SL* ps); // 尾部删除4.2 SeqList.c 功能实现文件#includeSeqList.h // 初始化顺序表 void SLInit(SL* ps) { assert(ps); ps-a NULL; ps-capacity 0; ps-size 0; } // 销毁顺序表释放动态内存 void Destroy(SL* ps) { assert(ps); if (ps-a) { free(ps-a); ps-a NULL; ps-capacity 0; ps-size 0; } } // 检测并自动扩容 void SLExp(SL* ps) { assert(ps); if (ps-capacity ps-size) { int Newspace ps-capacity 0 ? 4 : 2 * ps-capacity; SLType* Newps (SLType*)realloc(ps-a, Newspace * sizeof(SLType)); if (Newps NULL) { perror(Failed to apply for space); exit(1); } ps-a Newps; ps-capacity Newspace; } } // 尾部插入 void PushBack(SL* ps, SLType x) { assert(ps); SLExp(ps); ps-a[ps-size] x; } // 头部插入 void PushFront(SL* ps, SLType x) { assert(ps); SLExp(ps); // 元素后移从最后一个元素开始往前移 for (int i ps-size; i 0; i--) { ps-a[i] ps-a[i - 1]; } ps-a[0] x; ps-size; } // 头部删除 void SLDeleteBack(SL* ps) { assert(ps); assert(ps-size); // 元素前移覆盖第一个元素 for (int i 0; i ps-size - 1; i) { ps-a[i] ps-a[i 1]; } ps-size--; } // 尾部删除 void SLDeleteBehind(SL* ps) { assert(ps); assert(ps-size); // 逻辑删除只需要把有效数据个数减1 ps-size--; } // 通用打印函数适配任意SLType类型 void Print(SL* ps) { assert(ps); for (int i 0; i ps-size; i) { printf(SLTYPE_PRINT_FMT , ps-a[i]); } printf(\n); }4.3 test.c独立测试文件#include SeqList.h int main() { // 定义顺序表变量 SL sl; // 初始化 SLInit(sl); printf( 顺序表初始化完成 \n\n); // 测试尾插 printf(----- 测试尾插 -----\n); PushBack(sl, 10); PushBack(sl, 20); PushBack(sl, 30); PushBack(sl, 40); printf(尾插 10 20 30 40 后); Print(sl); printf(\n); // 测试头插 printf(----- 测试头插 -----\n); PushFront(sl, 5); PushFront(sl, 1); printf(头插 5 1 后); Print(sl); printf(\n); // 测试尾删 printf(----- 测试尾删 -----\n); SLDeleteBehind(sl); SLDeleteBehind(sl); printf(尾删2次后); Print(sl); printf(\n); // 测试头删 printf(----- 测试头删 -----\n); SLDeleteBack(sl); printf(头删1次后); Print(sl); printf(\n); // 释放内存 printf( 顺序表销毁完成 \n); Destroy(sl); return 0; }五、编译运行输出结果5.1编译命令gcc test.c SeqList.c -o SeqList5.2运行输出 顺序表初始化完成 ----- 测试尾插 ----- 尾插 10 20 30 40 后10 20 30 40 ----- 测试头插 ----- 头插 5 1 后1 5 10 20 30 40 ----- 测试尾删 ----- 尾删2次后1 5 10 20 ----- 测试头删 ----- 头删1次后5 10 20 顺序表销毁完成 六、学习总结与后续更新计划基础是重中之重顺序表卡壳本质是C语言结构体、指针、动态内存没学牢。二刷补完短板后写代码顺畅很多也能理解为什么要这么写。拒绝复制粘贴课件只看思路代码自己手写、自己排错印象远比抄代码深刻。每一个 Bug都是一次宝贵的学习机会。注重代码质量不只是实现功能还要考虑健壮性assert断言、可扩展性通用打印宏、工程规范多文件拆分。后续更新计划下一篇实现顺序表进阶接口——SLInsert指定位置插入、SLErase指定位置删除、SLFind按值查找、SLModify按位置修改再下一篇基于完整的顺序表接口实现一个可增删改查的通讯录项目长期规划继续学习链表、栈、队列、二叉树等数据结构坚持每一个知识点都手写实现踩坑记录的形式沉淀扎实的基础初学数据结构不要追求进度慢一点、写一遍、改一遍、优化一遍远比快速刷完视频有用得多。