C数据结构（顺序表）进阶（遗忘复习跟进C++）：C++17标准-北京尧图网络

第一次写这么多内容可否支持一下。单链表目录前言流程规划初始编码1. 第一个问题explicit 是什么2. std::size_t 是什么意思3. 为什么不把 4 直接写在 capacity_ 之后4. data_ std::make_uniqueint[](capacity_); 是什么意思4.1 没有写 new怎么开辟内存初始状态接口1.noexcept什么意思const访问元素函数允许修改1.int at引用问题2.超出异常out_of_range只允许读取动态数组扩容1.data_[i]难道不是unique_ptr吗为什么可以for循环复制2.data_ std::move(new_data);什么意思尾部插入与自动扩容为什么new_capacity capacity_ * 2;插入删除查找1.插入循环应该从 size_ 开始而不是 capacity_删除查找完整代码呈现前言有没有像我一样在学完 C 语言后就学习数据结构的同学之前我一直以为我的数据结构已经可以了但现在学完了 C 和很多知识后不少内容都有些疏漏和遗忘但又不想重新学习一遍数据结构。那么我们不妨大胆一点直接跟进 C 和操作系统等知识以一个未来工作的视角去看待数据结构的编写。因此这篇博客中数据结构的很多基础内容讲的比较少这篇文章或许会很长但它会一步一步地把所有顺序表以及新增的 C 内容全部讲清楚。这可是我一步一步追着 AI 刨根问底的结果。或许各位大佬都比我厉害不少知识可能赘述过多还请谅解毕竟这也是对我自己的一次自测。本篇内容多以代码实现及个人理解为主理论知识只会偶尔涉及。流程规划我们都清楚顺序表的主要形式是写代码之前首先明确我们顺序表的整体结构、接口数量等且创建一个cpp文件。接口功能push_back尾部插入insert指定位置插入erase删除指定位置元素find查找元素at访问指定位置的元素size返回当前元素数量capacity返回当前容量reserve扩大容量减少重复分配依据这个表格我们一步一步进行编码。初始编码简单过一下代码即可暂时不用全部理解。#includeiostream#includecstddef#includememoryclassSeqList{private:// 当前元素数量std::size_t size_;// 当前数组容量std::size_t capacity_;// 管理动态数组std::unique_ptrint[]data_;public:// 构造函数创建一个指定初始容量的顺序表explicitSeqList(std::size_t initial_capacity4):size_(0),capacity_(initial_capacity){if(capacity_0){data_std::make_uniqueint[](capacity_);}}};1. 第一个问题explicit是什么这在基础课程中几乎不涉及。这是一个 C 关键字主要用来禁止编译器擅自进行隐式类型转换。为方便理解我们先以一个简单代码举例。在如下代码中我们设计了一个Student类其中Student(int age)是一个构造函数。调用它时需要给age一个值。见main函数可知Student s 18;把Student类型的变量s当成普通整数去赋值了。这其实不是标准写法但编译器明白你想干什么于是用隐式转换的方式在系统内部转换为Student s Student(18);于是成功运行。#includeiostreamclassStudent{public:Student(intage){std::cout年龄agestd::endl;}};intmain(){Student s18;}而如果我们加上explicitStudent s 18;就不允许了因为它禁止隐式转换。#includeiostreamclassStudent{public:explicitStudent(intage){std::cout年龄agestd::endl;}};intmain(){// Student s 18; // 编译错误Students(18);// 正确Student t{18};// 正确}2.std::size_t是什么意思std::size_t在这里提一嘴此类型包含在#include cstddef里面通常表示非负整数。后面的initial_capacity是一个变量名表示初始容量。3. 为什么不把 4 直接写在capacity_之后// 写法一explicitSeqList(std::size_t initial_capacity4):size_(0),capacity_(initial_capacity)// 写法二explicitSeqList():size_(0),capacity_(4)完全可以而且如果你只希望顺序表的默认容量固定为 4这种写法反而更直观。但是这两种写法也有区别创建方式写法一写法二SeqList list;容量为 4容量为 4SeqList list(10);容量为 10编译错误SeqList list(100);容量为 100编译错误因此为了灵活更改我们一般不要把容量写死。4.data_ std::make_uniqueint[](capacity_);是什么意思需要#include memory。std::make_unique出现于 C17。动态申请一块能够存放capacity_个int元素的数组并让智能指针data_管理这块内存。4.1 没有写new怎么开辟内存这是现代 C 与所学基础 C 的区别。int*datanewint[4];这种写法大家肯定熟悉。而我们今天不这么写了。data_std::make_uniqueint[](4);虽然没有直接写new但std::make_unique在内部负责完成动态内存分配并把分配得到的资源交给智能指针管理。而且还有一个好处make_unique出来的数组元素会被初始化为 0而new一般不会。初始状态接口// 获取当前元素数量std::size_tsize()constnoexcept{returnsize_;}// 获取当前容量std::size_tcapacity()constnoexcept{returncapacity_;}// 判断顺序表是否为空boolempty()constnoexcept{returnsize_0;}此段代码主要实现获取元素数量获取容量判断是否为空。元素数量与容量并不相同可以向上翻看图片内容1.noexcept什么意思noexcept是一个来自C11的关键字一般放在函数声明之后。作用是阻止异常从函数里抛出去。这里与throw的作用做一个对比。关键字作用通俗理解throw抛出异常把问题交出去noexcept声明函数不会让异常跑出去保证问题不会以异常的形式传出去为了更好理解这里给出一个例子在讲noexcept之前我们先弄清楚throwintdivide(inta,intb){if(b0){throw1;}returna/b;}该实例是一个除法问题其中除数不能为0因此当输入参数b为0时明显有异常throw把异常抛出函数throw 1 会让程序跳过 divide() 中剩下的代码去寻找能够处理这个异常的 catch。如果找到就进入对应的 catch如果没有找到最终会调用std::terminate()一般会终止。try//尝试执行代码并在指定位置接住异常、处理问题{intresultdivide(10,0);std::coutresult;}catch(inte){std::cout除数不能为 0;}程序不必因此整体退出还可以继续执行后面的代码。所以抛出异常不是为了让程序报错退出而是为了把无法正常处理的问题交给其他代码处理。这样我们清楚了抛出异常的过程接下来就可以看看noexcept了回到我们原本的代码std::size_tsize()constnoexcept{returnsize_;}它的作用只是返回顺序表当前有多少个元素。没有必要抛出异常于是你可以写 noexcept明确告诉 C这个函数保证不会让异常跑到函数外面。对于 size() 这样的简单查询函数我们可以保证其执行过程中不会抛出异常。调用者因此可以依赖这一异常保证编译器也可能利用 noexcept 信息进行优化。但如果你写了noexcept又让异常跑了出来C 就会调用std::terminate()通常直接使程序终止const为什么这里要加const这是为了告诉C此段函数不会对顺序表做出修改只读取顺序表数据。这算是一道防线如果没有const。std::size_tsize()noexcept{size_0;// 编译器允许returnsize_;}因此加上const限制防止意外修改。访问元素函数允许修改#includestdexcept//添加头文件//使用 std::out_of_range 需要包含头文件// 访问元素只允许读取constintat(std::size_t index)const{if(indexsize_){throwstd::out_of_range(index out of range);}returndata_[index];}1.int at引用问题以引用的方式传入顺序表数据不需要复制原件直接对顺序表本身做修改。2.超出异常out_of_rangestd::out_of_range是C标准库提供的一种异常类型用来表示访问的数据超出了允许的范围。至于为什么要用out_of_range正常情况下throw1;// 抛出一个整数别人不知道1是什么因此有局限性。而throwstd::out_of_range(Index out of range);一眼就可以知道是什么异常更重要的是调用者可以专门捕获这种异常。try{intvaluelist.get(5);}catch(conststd::out_of_rangee){std::coute.what();//e.what()获取异常附带的错误描述。}const std::out_of_range e用引用接收这个异常对象。只允许读取// 访问元素只允许读取constintat(std::size_t index)const{if(indexsize_){throwstd::out_of_range(index out of range);}returndata_[index];}此段函数与上面的相似不再做细致解析动态数组扩容#includeutility// 扩大容量voidreserve(std::size_t new_capacity){if(new_capacitycapacity_){return;}autonew_datastd::make_uniqueint[](new_capacity);for(std::size_t i0;isize_;i){new_data[i]data_[i];}data_std::move(new_data);// move需要添加 #include utilitycapacity_new_capacity;}扩容结构用户传进来一个新容量判断如果该容量小于原容量直接撤掉。如果大于原容量就建立一个新的new_data并为其开辟空间方法在初始编码中有涉及。然后通过for遍历容器并将原本data里面的数据调整到new_data里面1.data_[i]难道不是unique_ptr吗为什么可以for循环复制data_是管理整个数组的智能指针而 data_[i] 是数组中第 i1 个元素。它们不是同一个东西写法含义类型data_管理数组的智能指针std::unique_ptrint[]data_[0]第一个元素intdata_[1]第二个元素int正因此可以通过for循环去复制元素。2.data_ std::move(new_data);什么意思让new_data接管data的内存。std::unique_ptrint[]data_;它负责管理顺序表当前使用的数组。现在可以把它们理解成data_ 原来的数组管理者。new_data 新数组的管理者。通过move转接管理权。而由于data_和new_data都是unique_ptr因此不可复制即data_new_data;// 错误试图复制data_std::move(new_data);// 正确转移管理权尾部插入与自动扩容// 在末尾添加元素voidpush_back(intvalue){if(size_capacity_){std::size_t new_capacity1;if(capacity_0){new_capacitycapacity_*2;}reserve(new_capacity);}data_[size_]value;size_;}这段代码逻辑比较简单主要就是检查容量扩展容量更新元素size_ 表示当前元素数量capacity_ 表示当前容量。当两者相等时说明数组已经装满不能直接添加新元素需要先扩容。为什么new_capacity capacity_ * 2;这里先把新容量设为 1。如果当前容量大于 0就把容量扩大为原来的两倍。例如当前容量为 0新容量设为 1。当前容量为 4新容量变为 8。当前容量为 8新容量变为 16。这样做可以避免每添加一个元素就重新申请数组减少频繁扩容带来的开销。插入删除查找1.插入voidinsert(std::size_t index,intvalue){if(indexsize_){throwstd::out_of_range(index out of range);}if(size_capacity_){std::size_t new_capacity1;if(capacity_0){new_capacitycapacity_*2;}reserve(new_capacity);}for(std::size_t isize_;iindex;i--){data_[i]data_[i-1];}data_[index]value;size_;}有关插入涉及更多的是数据结构基础与函数调用。我们设计两个传入参数分别是插入位置和插入元素值。函数的最开始是要检查输入是否异常如果index大于size_直接抛出越界异常即可。如果size_等于capacity_我们需要扩大容量方法与push_back函数类似不再重复。把异常情况排除之后我们就可以考虑真正的插入操作了。从后往前遍历直到插入位置这期间的元素都要向后移动一位腾出插入位置。循环应该从 size_ 开始而不是 capacity_有没有过这种想法如果容量为10大小为4那么如果我要在位置7插入数据的话难道就不对吗这里恰好涉及顺序表的一个核心概念容量 capacity_ 和元素数量 size_ 是两个不同的东西但合法插入位置由 size_ 决定而不是由 capacity_ 决定。capacity_ 10size_ 4下标 0 1 2 3. 4 5 6 7 8 9数据 10 20 30 40 · · · · · ·└──── 有效元素 ────┘合法位置为012344为末位因此也是合法的如果想在7位置插入数据呢。顺序表的规则是在已有的序列中插入数据而隔位插入是非法的如果你确实想让下标 7 存储那是另一种接口设计需要明确规定中间空位如何处理。删除voiderase(std::size_t index){if(indexsize_){throwstd::out_of_range(index out of range);}for(std::size_t iindex1;isize_;i){data_[i-1]data_[i];}size_--;}你的底层数组由std::unique_ptrint[]管理。这里的data_[index]是一个 int 元素不是通过 new 单独创建的对象。因此既不符合删除单个元素的方式也无法实现需要的效果。顺序表删除元素本质上是移动元素并减少 size_不需要手动释放单个元素的内存。查找intfind(intvalue)constnoexcept{for(std::size_t i0;isize_;i){if(data_[i]value){returni;}}return-1;}完整代码呈现#includeutility#includecstddef#includeiostream#includememory#includestdexceptclassSeqList{private:// 当前元素数量std::size_t size_;// 当前数组容量std::size_t capacity_;// 管理动态数组std::unique_ptrint[]data_;public:// 构造函数explicitSeqList(std::size_t initial_capacity4):size_(0),capacity_(initial_capacity){if(capacity_0){data_std::make_uniqueint[](capacity_);}}// 获取当前元素数量std::size_tsize()constnoexcept{returnsize_;}// 获取当前容量std::size_tcapacity()constnoexcept{returncapacity_;}// 判断顺序表是否为空boolempty()constnoexcept{returnsize_0;}// 访问元素允许修改intat(std::size_t index){if(indexsize_){throwstd::out_of_range(index out of range);}returndata_[index];}// 访问元素只允许读取constintat(std::size_t index)const{if(indexsize_){throwstd::out_of_range(index out of range);}returndata_[index];}// 扩大容量voidreserve(std::size_t new_capacity){if(new_capacitycapacity_){return;}autonew_datastd::make_uniqueint[](new_capacity);for(std::size_t i0;isize_;i){new_data[i]data_[i];}data_std::move(new_data);capacity_new_capacity;}// 在末尾添加元素voidpush_back(intvalue){if(size_capacity_){std::size_t new_capacity1;if(capacity_0){new_capacitycapacity_*2;}reserve(new_capacity);}data_[size_]value;size_;}// 在指定位置插入元素voidinsert(std::size_t index,intvalue){if(indexsize_){throwstd::out_of_range(index out of range);}if(size_capacity_){std::size_t new_capacity1;if(capacity_0){new_capacitycapacity_*2;}reserve(new_capacity);}for(std::size_t isize_;iindex;i--){data_[i]data_[i-1];}data_[index]value;size_;}// 删除指定位置的元素voiderase(std::size_t index){if(indexsize_){throwstd::out_of_range(index out of range);}for(std::size_t iindex1;isize_;i){data_[i-1]data_[i];}size_--;}// 查找元素返回下标不存在时返回 -1intfind(intvalue)constnoexcept{for(std::size_t i0;isize_;i){if(data_[i]value){returni;}}return-1;}// 遍历输出顺序表voidprint()const{for(std::size_t i0;isize_;i){std::coutdata_[i] ;}std::cout\n;}};intmain(){SeqList list;list.push_back(10);list.push_back(20);list.push_back(30);list.print();list.insert(2,88);list.print();list.erase(3);list.print();list.find(10);//测试自动扩容list.push_back(10);list.push_back(20);list.push_back(30);// 修改元素list.at(1)25;list.print();// 测试越界访问boolexception_caughtfalse;// 测试越界访问try{list.at(list.size());std::coutError: expected an exception\n;}catch(conststd::out_of_range){std::coutOut-of-range test passed\n;}list.print();std::coutBasic tests passed.\n;}如果这篇内容对你有帮助欢迎点赞支持一下。

C数据结构（顺序表）进阶（遗忘复习跟进C++）：C++17标准

相关推荐

高并发框架选型：别只看Star数，压测数据才是硬道理

电动汽车集群并网调度的分布式鲁棒优化模型及Matlab实现

OpenMontage深度解析：5.4万Star的开源视频神器，是革命还是半成品？

更多资讯

顺序表增删查改详解：从内存布局到动态数组实现

Retrofit原理与实战：从动态代理到网络层优雅设计

Linux虚拟机ens33网卡获取不到IP？三步排查搞定无地址故障

反爬对抗实战：从请求头到浏览器自动化的完整破解链路

软件咨询公司面试全流程复盘：从HomeWork到结对编程的实战指南

Windows上部署Diffy：差分测试工具实现接口回归对比

今日更新

声子晶体仿真：三角晶格与六角晶格的能带计算实战

度假村安保定岗定编：岗位梳理、编制测算与排班设计

COMSOL等离子体模块实战：氩气双层DBD仿真建模全解析

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？