【数据结构初阶】顺序表从0到1：增删查改代码实现详解

一.顺序表的概念概念顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构⼀般情况下采⽤数组存储顺序表和数组的区别顺序表的底层结构是数组对数组的封装实现了常⽤的增删改查等接二.顺序表的分类2.1静态顺序表概念使⽤定⻓数组存储元素大小在编译时就确定了。代码如下#define N 10 typedef int SLDataType; typedef struct SeqList { SLDataType array[N]; // 定长数组 size_t size; // 有效数据个数 } SeqList;这里的N是 10最多就只能存 10 个数据。缺点挺明显的把 N 开大了数据少的时候浪费空间把 N 开小了数据多的时候又不够用。只适合那种事先确切知道数据量的场景平时写项目基本用不上。2.2动态顺序表动态顺序表用malloc或realloc动态申请空间数据多了就扩容。typedef int SLDataType; typedef struct SeqList { SLDataType* a; // 指向动态开辟的数组 size_t size; // 有效数据个数 size_t capacity; // 容量大小 } SeqList;这里的a指向一块堆空间size记录当前存了多少个数据capacity记录总共能存多少个。当size达到capacity时就调用realloc扩容。SLDataType是int的别名这样做的好处是如果后面想把 int 改成 char 或者其他类型只需要在这一行改就行了不用到处找。size_t是无符号整数类型专门用来表示长度和大小。2.3 动态顺序表接口的实现1.创建三个文件2.头文件SeqList.h代码如下// 文件名SeqList.h // 功能动态顺序表动态数组头文件 #pragma once // 头文件包含 #include assert.h // assert() 断言 #include stdlib.h // realloc(), free() 等内存管理函数 #includestdio.h // 类型定义 // 顺序表存储的数据类型便于后续修改 typedef int SLDataType; // 动态顺序表结构体 typedef struct SeqList { SLDataType* a; // 指向动态开辟的数组存储数据 size_t size; // 有效数据个数当前已存储的元素数量 size_t capacity; // 容量空间大小当前最多能存储的元素数量 } SeqList; // 基本增删查改接口 // 初始化和销毁 void SeqListInit(SeqList* ps); // 顺序表初始化 void SeqListDestroy(SeqList* ps); // 顺序表销毁释放内存 // 容量管理 void CheckCapacity(SeqList* ps); // 检查空间如果满了则进行增容 // 尾部操作 void SeqListPushBack(SeqList* ps, SLDataType x); // 尾插 void SeqListPopBack(SeqList* ps); // 尾删 // 头部操作 void SeqListPushFront(SeqList* ps, SLDataType x); // 头插 void SeqListPopFront(SeqList* ps); // 头删 // 指定位置操作 void SeqListInsert(SeqList* ps, size_t pos, SLDataType x); // 在 pos 位置插入 x void SeqListErase(SeqList* ps, size_t pos); // 删除 pos 位置的值 // 查找与访问 int SeqListFind(SeqList* ps, SLDataType x); // 查找数据返回下标-1表示未找到 void SeqListAt(SeqList* ps, size_t pos, SLDataType x); // 修改指定下标位置的数据 // 工具函数 void SeqListPrint(SeqList* ps); // 打印顺序表所有元素 size_t SeqListSize(const SeqList* ps); // 查看有效数据个数只读3.在SeqList.c实现各个接口函数1.初始化顺序表//初始化顺序表 void SeqListInit(SeqList* ps); { assert(ps); // 断言 -- 防止传进来的指针为空 ps-a NULL; // 初始化顺序表为空 ps-size 0; // 初始数据个数为0 ps-capacity 0; // 初始空间容量为0 }2. 销毁顺序表void SeqListDestroy(SeqList* ps) { assert(ps); // 断言 -- 防止传进来的指针为空 free(ps-a); // 释放动态开辟的空间 ps-a NULL; // 置空 ps-size 0; // 数据个数置为0 ps-capacity 0; // 空间容量大小置为0 }3. 容量管理 检查空间如果满了进行增容//检查容量满了则增容 // 扩容策略容量为0时扩容到4否则扩容为原来的2倍 // 为什么是2倍—— 避免频繁扩容代价高同时避免空间浪费3倍/4倍浪费太多 void SLCheckCapacity(SeqList* ps) { assert(ps); // 防御性检查 if (ps-size ps-capacity) // 空间已满需要增容 { // 计算新容量原来为0则给4否则翻倍 size_t newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity; // 使用 realloc 扩容 SLDataType* tmp (SLDataType*)realloc(ps-a, sizeof(SLDataType) * newCapacity); // 检查 realloc 是否成功 if (tmp NULL) { perror(SLCheckCapacity::realloc failed); return; } ps-a tmp; // 更新指针 ps-capacity newCapacity; // 更新容量 } }realloc 的三种情况情况realloc行为示例传入 NULL等价于malloc(size)开辟新空间realloc(NULL, 40)→ 开辟 40 字节传入有效指针且空间足够原地扩容返回原地址realloc(ptr, 80)→ 在原地址后追加空间传入有效指针但空间不足找新地址拷贝数据释放旧空间返回新地址realloc(ptr, 200)→ 迁移到新地址4. 顺序表尾插// 顺序表尾插 void SeqListPushBack(SeqList* ps, SLDateType x) { // 方法一直接尾插 /* CheckCapacity(ps); // 检查容量不够则扩容 ps-a[ps-size] x; // 在末尾位置插入数据 ps-size; // 有效数据个数1 */ // 方法二复用 SeqListInsert在 size 位置插入 SeqListInsert(ps, ps-size, x); }作用在顺序表末尾插入一个元素。方法一先检查容量CheckCapacity不足则扩容然后在ps-size位置赋值最后size。方法二复用SeqListInsert函数在ps-size位置插入也就是末尾插入代码更简洁。时间复杂度O(1)不考虑扩容的情况。5. 顺序表尾删// 顺序表尾删 void SeqListPopBack(SeqList* ps) { assert(ps); // 断言指针不为空 // 方法一暴力检查推荐 /* assert(ps-size 0); // 顺序表不能为空 ps-size--; // 有效数据个数-1逻辑上删除最后一个元素 */ // 方法二复用 SeqListErase删除最后一个元素 SeqListErase(ps, ps-size - 1); }作用删除顺序表最后一个元素。核心思想只需将size减 1最后一个元素在逻辑上就不存在了。注意不需要把最后一个元素置为 0因为数据类型不确定可能是结构体、浮点数等即使置 0 也没意义浪费性能错误检查方式温柔检查if (ps-size 0) { ps-size--; }不推荐错误被掩盖暴力检查推荐assert(ps-size 0);出错直接报错方便调试时间复杂度O(1)。温柔检查不推荐void SeqListPopBack(SeqList* ps) { assert(ps); if (ps-size 0) { // 有数据才删 ps-size--; } }问题顺序表为空时什么都不做就返回了调用者不知道删除失败bug被隐藏。暴力检查推荐void SeqListPopBack(SeqList* ps) { assert(ps); assert(ps-size 0); // 为空直接报错终止 ps-size--; }优点出错立即报错并显示位置方便调试。6. 顺序表头插// 顺序表头插 第一种 void SeqListPushFront(SeqList* ps, SLDateType x) { assert(ps); // 断言指针不为空 CheckCapacity(ps); // 检查容量不够则扩容 // 将现有元素从后往前依次向后移动一位 for (int i ps-size; i 0; i--) { ps-a[i] ps-a[i - 1]; } ps-a[0] x; // 在头部插入新元素 ps-size; // 有效数据个数1 } 第二种 void SeqListPushFront(SeqList* ps, SLDateType x) { SeqListInsert(ps, 0, x); // 在下标0插入 }作用在顺序表头部插入一个元素。实现步骤检查容量是否充足将所有已有元素从后往前向后移动一位腾出第一个位置在a[0]位置插入新元素size为什么从后往前移动如果从前往后移动后面的数据会被覆盖。时间复杂度O(n)因为需要移动所有元素。7.顺序表头删// 顺序表头删 void SeqListPopFront(SeqList* 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--; // 有效数据个数-1 // 方法二 SeqListErase(ps, 0); }作用删除顺序表第一个元素。实现步骤检查顺序表是否为空将后续元素从前往后依次前移一位覆盖第一个元素size--时间复杂度O(n)。8.打印顺序表void SeqListPrint(SeqList* ps) { assert(ps); // 防止传空指针进来 for (int i 0; i ps-size; i) { printf(%d , ps-a[i]); // 一个一个打印出来 } printf(\n); // 打印完换行 }就是遍历数组把每个元素打印出来。ps-size记录着有几个有效数据所以循环到size就行。最后加个换行好看一点。9.查找指定值int SeqListFind(SeqList* ps, SLDateType x) { assert(ps); for (int i 0; i ps-size; i) { if (ps-a[i] x) { return i; // 找到了返回下标 } } return -1; // 找遍了都没有返回-1 }从头到尾遍历找到了就直接返回下标。如果循环结束了还没找到说明没有这个值返回 -1因为下标从0开始-1肯定不可能是合法位置。外面调用的时候判断一下返回值是不是 -1 就知道找没找到了。10.在 pos 位置插入 xvoid SeqListInsert(SeqList* ps, size_t pos, SLDateType x) { assert(ps); // 防止传空指针 assert(pos 0 pos ps-size); // 检查位置合不合法 CheckCapacity(ps); // 空间不够就扩容 //第一种写法while 循环 size_t end ps-size; while (end pos) { ps-a[end] ps-a[end - 1]; // 从后往前依次往后挪 end--; // 继续挪下一个 } // 第二种写法for 循环 for (size_t i ps-size; i pos; i--) { ps-a[i] ps-a[i - 1]; // 从后往前依次往后挪 } ps-a[pos] x; // 把新数据放进去 ps-size; // 有效数据1 }插入的核心就是挪数据。比如要在下标2的位置插入那原来的2、3、4...都要往后挪给新元素腾地方。注意pos可以是size就是在末尾插入相当于尾插挪的时候必须从后往前挪如果从前往后挪会把后面的数据覆盖掉举个例子 [1,2,3,4]在 pos1 插入 99 从后往前挪4--3位置3--2位置2--1位置 然后 a[1]99 结果[1,99,2,3,4]在这里我踩过一些坑一开始我是这么写的//错误写法 for (int i ps-size - 1; i pos; i--) { ps-a[i 1] ps-a[i]; }看着好像没问题但是当pos 0的时候i会一直减到-1然后i 0这个条件-1 0应该是假的循环就该停了。但是如果i是int类型pos是size_t无符号比较的时候i会被转成无符号数-1就变成了一个超级大的数肯定大于等于pos循环就停不下来了直接越界访问崩溃。那应该怎么改呢// 正确写法 for (size_t i ps-size; i pos; i--) { ps-a[i] ps-a[i - 1]; }i从size开始不是size-1;循环条件是i pos当i减到0时如果pos 0条件0 0是假的循环结束;永远不会出现i -1的情况.11. 删除 pos 位置的值// 顺序表删除pos位置的值 void SeqListErase(SeqList* psl, size_t pos) { assert(psl); // 断言 assert(psl-size 0); // 顺序表不能为空 assert(pos 0 pos psl-size); // 检查pos下标的合法性 // 第一种写法 /* size_t start pos; while (start psl-size-1) { psl-a[start] psl-a[start 1]; start; } */ //第二种写法 size_t i 0; for (i pos 1; i psl-size; i) // 将pos位置后面的数据依次向前挪动一位 { psl-a[i - 1] psl-a[i]; } psl-size--; // 有效数据个数-1 }两种写法其实一样一个用while一个用for做的事情完全相同while版本先定义end size每次挪完end--直到end不大于posfor版本i从size开始每次i--直到i不大于pos我一般用for写起来短一点看起来也舒服。12.查看有效数据个数// 查看顺序表中有多少个有效数据 size_t SeqListSize(const SeqList* ps) { assert(ps); return ps-size; }13.修改指定位置的数// 修改指定下标位置的数据 void SeqListAt(SeqList* ps, size_t pos, SLDateType x) { assert(ps); assert(ps-size 0); // 表不能是空的 assert(pos 0 pos ps-size);// 位置要在范围内 ps-a[pos] x; // 直接改掉 }那为啥不直接访问刚学的时候我也纳闷明明sl.size直接就能拿到为啥非要写个函数去取原因如下1. 安全万一哪天改代码把size这个变量名换了或者结构体变了所有直接访问的地方都得改麻烦死了。用函数的话只改这一个地方就行。2. 好加检查比如修改数据的时候直接在函数里加上assert判断位置对不对你要是直接访问数组赋值位置错了可能都不知道。3. 规范不让外面随便动内部数据都通过函数接口来操作不容易出乱子。补充关于数组越界数组越界不是每次都会报错越界读printf(%d, ps-a[ps-size]); // 多读了一个这种一般不会崩因为只是看看没改什么东西系统不太管你。但读出来的是垃圾数据可能会影响程序逻辑。越界写ps-a[ps-size] 10; // 在size位置写数据没扩容这个就比较危险了相当于在别人的地盘乱写东西。如果改到了系统用来标记内存边界的数据程序可能直接就崩了。重点系统检查越界有点像抽查不是每次都管所以不能指望系统帮你发现错误自己写代码的时候要小心。三.代码整合SeqList.h头文件#pragma once #include stdio.h #include assert.h #include stdlib.h // 类型定义 typedef int SLDateType; // 顺序表结构体 typedef struct SeqList { SLDateType* a; // 指向动态数组 int size; // 有效数据个数 int capacity; // 容量大小 } SeqList; // 函数声明 // 1. 初始化 void SeqListInit(SeqList* ps); // 2. 销毁 void SeqListDestroy(SeqList* ps); // 3. 检查容量 void CheckCapacity(SeqList* ps); // 4. 打印 void SeqListPrint(SeqList* ps); // 5. 尾插 void SeqListPushBack(SeqList* ps, SLDateType x); // 6. 尾删 void SeqListPopBack(SeqList* ps); // 7. 头插 void SeqListPushFront(SeqList* ps, SLDateType x); // 8. 头删 void SeqListPopFront(SeqList* ps); // 9. 查找 int SeqListFind(SeqList* ps, SLDateType x); // 10. 指定位置插入 void SeqListInsert(SeqList* ps, size_t pos, SLDateType x); // 11. 指定位置删除 void SeqListErase(SeqList* ps, size_t pos); // 12. 获取有效数据个数 size_t SeqListSize(const SeqList* ps); // 13. 修改指定位置的数据 void SeqListAt(SeqList* ps, size_t pos, SLDateType x);SeqList.c具体实现#include SeqList.h //1. 初始化 void SeqListInit(SeqList* ps) { assert(ps); ps-a NULL; ps-size 0; ps-capacity 0; } // 2. 销毁 void SeqListDestroy(SeqList* ps) { assert(ps); free(ps-a); ps-a NULL; ps-size 0; ps-capacity 0; } // 3. 检查容量 void CheckCapacity(SeqList* ps) { assert(ps); if (ps-size ps-capacity) { int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2; SLDateType* tmp (SLDateType*)realloc(ps-a, newCapacity * sizeof(SLDateType)); if (tmp NULL) { printf(扩容失败\n); exit(-1); } ps-a tmp; ps-capacity newCapacity; } } // 4. 打印 void SeqListPrint(SeqList* ps) { assert(ps); for (int i 0; i ps-size; i) { printf(%d , ps-a[i]); } printf(\n); } // 5. 尾插 void SeqListPushBack(SeqList* ps, SLDateType x) { SeqListInsert(ps, ps-size, x); // 在size位置插入就是尾插 } // 6. 尾删 void SeqListPopBack(SeqList* ps) { assert(ps); assert(ps-size 0); // 不能删空的 SeqListErase(ps, ps-size - 1); // 删最后一个 } // 7. 头插 void SeqListPushFront(SeqList* ps, SLDateType x) { SeqListInsert(ps, 0, x); // 在0位置插入就是头插 } // 8. 头删 void SeqListPopFront(SeqList* ps) { assert(ps); assert(ps-size 0); SeqListErase(ps, 0); // 删第0个 } // 9. 查找 int SeqListFind(SeqList* ps, SLDateType x) { assert(ps); for (int i 0; i ps-size; i) { if (ps-a[i] x) { return i; // 找到了返回下标 } } return -1; // 没找到返回-1 } // 10. 指定位置插入 void SeqListInsert(SeqList* ps, size_t pos, SLDateType x) { assert(ps); assert(pos 0 pos ps-size); // pos要在0到size之间 CheckCapacity(ps); // 空间不够就扩容 // 从后往前挪给新元素腾位置 for (size_t i ps-size; i pos; i--) { ps-a[i] ps-a[i - 1]; } ps-a[pos] x; ps-size; } // 11. 指定位置删除 void SeqListErase(SeqList* ps, size_t pos) { assert(ps); assert(pos 0 pos ps-size); // pos要在0到size-1之间 // 从前往后挪覆盖掉要删的那个 for (size_t i pos; i ps-size - 1; i) { ps-a[i] ps-a[i 1]; } ps-size--; } // 12. 获取有效数据个数 size_t SeqListSize(const SeqList* ps) { assert(ps); return ps-size; } // 13. 修改指定位置的数据 void SeqListAt(SeqList* ps, size_t pos, SLDateType x) { assert(ps); assert(ps-size 0); // 表不能是空的 assert(pos 0 pos ps-size);// 位置要在范围内 ps-a[pos] x; }test.c(测试文件#include SeqList.h // 测试1初始化 void TestSeqList1() { printf(测试初始化\n); SeqList sl; SeqListInit(sl); printf(size %d, capacity %d\n, sl.size, sl.capacity); SeqListDestroy(sl); } // 测试2销毁 void TestSeqList2() { printf(测试销毁\n); SeqList sl; SeqListInit(sl); SeqListPushBack(sl, 1); SeqListPushBack(sl, 2); printf(销毁前 size %d\n, sl.size); SeqListDestroy(sl); printf(销毁后 size %d\n, sl.size); } // 测试3打印 void TestSeqList3() { printf(测试打印\n); SeqList sl; SeqListInit(sl); SeqListPushBack(sl, 1); SeqListPushBack(sl, 2); SeqListPushBack(sl, 3); printf(打印数据); SeqListPrint(sl); SeqListDestroy(sl); } // 测试4头插头删 void TestSeqList4() { SeqList sl; SeqListInit(sl); SeqListPushFront(sl, 1); SeqListPushFront(sl, 2); SeqListPushFront(sl, 3); SeqListPrint(sl); SeqListPopFront(sl); SeqListPrint(sl); SeqListDestroy(sl); } // 测试5尾插尾删 void TestSeqList5() { SeqList sl; SeqListInit(sl); SeqListPushBack(sl, 1); SeqListPushBack(sl, 2); SeqListPushBack(sl, 3); SeqListPrint(sl); SeqListPopBack(sl); SeqListPrint(sl); SeqListDestroy(sl); } // 测试6混着来 void TestSeqList6() { SeqList sl; SeqListInit(sl); SeqListPushBack(sl, 1); SeqListPushBack(sl, 2); SeqListPushFront(sl, 0); SeqListPushBack(sl, 3); SeqListPrint(sl); SeqListPopFront(sl); SeqListPopBack(sl); SeqListPrint(sl); SeqListDestroy(sl); } // 测试7指定位置插入 void TestSeqList7() { SeqList sl; SeqListInit(sl); SeqListPushBack(sl, 1); SeqListPushBack(sl, 2); SeqListPushBack(sl, 4); SeqListPushBack(sl, 5); SeqListPrint(sl); SeqListInsert(sl, 2, 3); SeqListPrint(sl); SeqListDestroy(sl); } // 测试8指定位置删除 void TestSeqList8() { SeqList sl; SeqListInit(sl); for (int i 1; i 5; i) { SeqListPushBack(sl, i); } SeqListPrint(sl); SeqListErase(sl, 2); SeqListPrint(sl); SeqListDestroy(sl); } // 测试9查找 void TestSeqList9() { SeqList sl; SeqListInit(sl); SeqListPushBack(sl, 10); SeqListPushBack(sl, 20); SeqListPushBack(sl, 30); int idx SeqListFind(sl, 20); printf(20的位置%d\n, idx); idx SeqListFind(sl, 100); printf(100的位置%d\n, idx); SeqListDestroy(sl); } // 测试10修改数据 void TestSeqList10() { SeqList sl; SeqListInit(sl); SeqListPushBack(sl, 1); SeqListPushBack(sl, 2); SeqListPushBack(sl, 3); SeqListPrint(sl); SeqListAt(sl, 1, 99); SeqListPrint(sl); SeqListDestroy(sl); } // 测试11有效数据个数 void TestSeqList11() { SeqList sl; SeqListInit(sl); printf(空表大小%d\n, SeqListSize(sl)); SeqListPushBack(sl, 1); SeqListPushBack(sl, 2); printf(插了两个后%d\n, SeqListSize(sl)); SeqListPopBack(sl); printf(删了一个后%d\n, SeqListSize(sl)); SeqListDestroy(sl); } int main() { TestSeqList1(); TestSeqList2(); TestSeqList3(); TestSeqList4(); TestSeqList5(); TestSeqList6(); TestSeqList7(); TestSeqList8(); TestSeqList9(); TestSeqList10(); TestSeqList11(); return 0; }