C++综合实战：数据结构与算法实现及系列总结

本文是 C++ 系列教程的第 30 篇，也是系列终章。本篇实战数据结构与算法：手写动态数组与链表、排序与查找算法、递归与分治，最后回顾全部 30 篇学习路径，覆盖 9 个完整示例代码。

一、手写动态数组

1.1 为什么手写容器

理解容器内部机制是 C++ 进阶的必经之路。手写一个简化版 `vector，体会内存管理、扩容与拷贝语义：

// my_vector.h —— 简化版动态数组#pragmaonce#include<iostream>usingnamespacestd;template<typenameT>classMyVector{private:T*data;// 指向堆内存size_t sz;// 当前元素个数size_t cap;// 容量voidgrow(){// 扩容：翻倍cap=cap==0?4:cap*2;T*newData=newT[cap];for(size_t i=0;i<sz;++i)newData[i]=data[i];delete[]data;data=newData;}public:MyVector():data(nullptr),sz(0),cap(0){}~MyVector(){delete[]data;}voidpush_back(constT&value){if(sz==cap)grow();data[sz++]=value;}voidpop_back(){if(sz>0)sz--;}T&oper ator[](size_t i){returndata[i];}size_tsize()const{returnsz;}boolempty()const{returnsz==0;}};intmain(){MyVector<int>v;for(inti=1;i<=10;++i)v.push_back(i*i);cout<<"size = "<<v.size()<<endl;for(size_t i=0;i<v.size();++i)cout<<v[i]<<" ";// 1 4 9 16 25 36 49 64 81 100cout<<endl;return0;}

grow()在容量不足时翻倍扩容，均摊时间复杂度为 O(1)。注意实现析构函数释放堆内存避免泄漏。

1.2 迭代器与范围 for 支持

给容器加上简单的迭代器支持：

// 在 MyVector 中补充迭代器public:T*begin(){returndata;}T*end(){returndata+sz;}constT*begin()const{returndata;}constT*end()const{returndata+sz;}

有了begin()/end()，容器就能配合范围 for 循环：

MyVector<int>nums;for(inti=0;i<5;++i)nums.push_back(i*3);for(intx:nums){// 范围 for：自动使用 begin/endcout<<x<<" ";// 0 3 6 9 12}cout<<endl;

二、链表实现

2.1 单链表

// linked_list.cpp —— 单链表#include<iostream>usingnamespacestd;structNode{intdata;Node*next;Node(intd):data(d),next(nullptr){}};classLinkedList{private:Node*head;public:LinkedList():head(nullptr){}~LinkedList(){Node*cur=head;while(cur){Node*tmp=cur;cur=cur->next;deletetmp;// 逐个释放，避免泄漏}}// 头插法voidinsertHead(intvalue){Node*n=newNode(value);n->next=head;head=n;}// 尾插法voidinsertTail(intvalue){Node*n=newNode(value);if(!head){head=n;return;}Node*cur=head;while(cur->next)cur=cur->next;cur->next=n;}boolremove(intvalue){if(!head)returnfalse;if(head->data==value){Node*tmp=head;head=head->next;deletetmp;returntrue;}Node*cur=head;while(cur->next&&cur->next->data!=value)cur=cur->next;if(!cur->next)returnfalse;Node*tmp=cur->next;cur->next=tm p=head;head=head->next;deletetmp;returntrue;}Node*cur=head;while(cur->next&&cur->next->data!=value)cur=cur->next;if(!cur->next)returnfalse;Node*tmp=cur->next;cur->next=tmp->next;deletetmp;returntrue;}voidshow()const{Node*cur=head;while(cur){cout<<cur->data<<" -> ";cur=cur->next;}cout<<"nullptr"<<endl;}};intmain(){LinkedList list;list.insertHead(3);list.insertHead(2);list.insertHead(1);// 1 -> 2 -> 3list.insertTail(4);// 1 -> 2 -> 3 -> 4list.show();list.remove(2);// 1 -> 3 -> 4list.show();return0;}

链表插入删除只需修改指针（O(1)），但随机访问需遍历（O(n)）；与数组恰好互补。

2.2 链表 vs 动态数组

三、排序算法

3.1 快速排序

// quick_sort.cpp —— 快速排序#include<iostream>#include<vector>usingnamespacestd;intpartition(vector<int>&arr,intlow,inthigh){intpivot=arr[high];// 取最后一个元素为基准inti=low-1;for(intj=low;j<high;++j){if(arr[j]<pivot){i++;swap(arr[i],arr[j]);}}swap(arr[i+1],arr[high]);returni+1;}voidquickSort(vector<int>&arr,intlow,inthigh){if(low<high){intpi=partition(arr,low,high);quickSort(arr,low,pi-1);// 递归左半quickSort(arr,pi+1,high);// 递归右半}}intmain(){vector<int>arr={10,7,8,9,1,5};quickSort(arr,0,(int)arr.size()-1);for(intx:arr)cout<<x<<" ";cout<<endl;// 1 5 7 8 9 10return0;}

快速排序平均 O(n log n)，通过分治思想每次把基准放到最终位置，两边递归。

3.2 归并排序

// merge_sort.cpp —— 归并排序#include<iostream>#include<vector>usingnamespacestd;voidmerge(vector<int>&arr,intleft,intmid,intright){vector<int>tmp(right-left+1);inti=left,j=mid+1,k=0;while(i<=mid&&j<=right)tmp[k++]=(arr[i]<=arr[j])?arr[i++]:arr[j++];while(i<=mid)tmp[k++]=arr[i++];while(j<=right)tmp[k++]=arr[j++];for(intt=0;t<(int)tmp.size();++t)arr[left+t]=tmp[t];}voidmergeSort(vector<int>&arr,intleft,intright){if(left>=right)return;intmid=(left+right)/2;mergeSort(arr,left,mid);// 分mergeSort(arr,mid+1,right);merge(arr,left,mid,right);// 治：合并两个有序段}intmain(){vector<int>arr={38,27,43,3,9,82,10};mergeSort(arr,0,(int)arr.size()-1);for(intx:arr)cout<<x<<" ";cout<<endl;// 3 9 10 27 38 43 82return0;}

归并排序稳定、O(n log n)，需要额外 O(n) 空间。快速排序空间 O(log n) 但不稳定。

四、查找算法

4.1 二分查找

// binary_search.cpp —— 二分查找（要求数组有序）#include<iostream>#include<vector>usingnamespacestd;intbinarySearch(constvector<int>&arr,inttarget){intleft=0,right=(int)arr.size()-1;while(left<=right){intmid=left+(right-left)/2;// 防止溢出if(arr[mid]==target)returnmid;if(arr[mid]<target)left=mid+1;elseright=mid-1;}return-1;// 未找到}intmain(){vector<int>arr={1,3,5,7,9,11,13};cout<<binarySearch(arr,7)<<endl;// 3（下标）cout<<binarySearch(arr,8)<<endl;// -1（不存在）return0;}

二分查找每次排除一半区间，O(log n)。mid = left + (right - left) / 2避免(left+right)溢出。

五、实战：学生成绩管理系统（综合）

综合运用容器、排序、查找、lambda 与统计的完整案例：

// student_manager.cpp —— 学生成绩管理#include<iostream>#include<vector>#include<string>#include<algorithm>#include<numeric>usingnamespacestd;structStudent{string name;intscore;};voidshowAll(constvector<Student>&students){for(constauto&s:students)cout<<s.name<<" "<<s.score<<endl;}intmain(){vector<Student>students={{"张三",85},{"李四",92},{"王五",78},{"赵六",95}};// 1. 按分数降序排序（lambda 比较）sort(students.begin(),students.end(),[](constStudent&a,constStudent&b){returna.score>b.score;});cout<<"按分数降序:"<<endl;showAll(students);// 2. 计算平均分（accumulate 求和）doubleavg=accumulate(students.begin(),students.end(),0.0,[](doublesum,constStudent&s){returnsum+s.score;})/students.size();cout<<"平均分: "<<avg<<endl;// 3. 查找最高分autobest=max_element(students.begin(),students.end(),[](constStudent&a,constStudent&b){returna.score<b.score;});cout<<"最高分: "<<best->name<<" "<<best->score<<endl;// 4. 统计及格人数（count_if）intpassed=count_if(students.begin(),students.end(),[](constStudent&s){returns.score>=60;});cout<<"及格人数: "<<passed<<endl;return0;}

六、30 篇系列总结

6.1 学习路径回顾

本系列从零到实战覆盖 C++ 全链路：

6.2 学习建议

1. 动手写代码：每篇示例都亲手编译运行，改参数观察行为变化。
2. 逐步进阶：按阶段顺序学习，模板与并发依赖前面基础。
3. 结合工程：用 CMake 组织项目，用 GDB/ASan 排查问题。
4. 阅读源码：理解vector/string等标准库内部实现。
5. 持续练习：LeetCode 算法题、开源项目阅读，把知识用起来。

总结

作为系列终章，本篇实战了动态数组（手写 vector 与扩容）、链表（插入/删除与内存管理）、快速排序与归并排序（分治思想）、二分查找，并用学生成绩管理系统综合运用 STL 算法，最后回顾了 30 篇完整学习路径。从Hello World到网络编程、从模板元编程到并发线程池，你已经系统掌握了 C++ 的核心知识体系。持续编码、持续学习，C++ 的世界还很大，加油！