第1页 / 共76页
第2页 / 共76页
第3页 / 共76页
第4页 / 共76页
第5页 / 共76页
第6页 / 共76页
第7页 / 共76页
第8页 / 共76页
C++进阶拔高与计算机网络.pdf
C++进阶拔高与计算机网络
Laotan
重庆邮电大学
2018 年 7 月
作者：
学校：
时间：
摘要
该复习文档是本人根据和 CSDN 博客上的众多文章总结而成的。感谢博客上各位大佬
的总结，使我在复习课本的同时补充了很多其他方面的关键知识，如 C++内存管理，STL 库
等内容。本文章适合 C++初学者的快速复习和应届生的笔试面试准备，书中给出了面试中
常见的 C++拔高的部分知识。对于初学者来说，也可以加强对 C++的认识。
文档主要分为 C++数据结构具体实现代码，C++的 STL 库，C++与数据库，C++内存管
理，C++智能指针和基于 C++的网络爬虫（暂定）。这一些知识一般在课上被老师直接跳过，
笔者在看了众多大佬的面经中，感觉这几个部分是被问的最多的，因此笔者挑出了这几个部
分进行总结。
最后部分对谢希仁的《计算机网络》进行了回顾，重点是链路层，网络层，运输层和
应用层部分的 DNS。
笔者的话
笔者作为一个普通一本的屌丝研究生，和在看这篇文档的各位比起来没有一丝丝不同。
回顾本科和研究生已经度过的 2 年，感慨颇多。笔者的专业不是计算机相关专业的，但是彷
徨了 6 年发现其实毕业生可以选择的出路并不多，想有高收入，又没啥技术，唉，现实总是
很骨感。网申简历各种被拒，当初很难受，现在其实也就看淡了。经过前一段时间找实习各
种悲剧，笔者决定痛定思痛，好好补一下技术。想想自己曾经学过什么，好像也只有 C++可
以拿得出手，其实对于通信专业的同学来说，找 IT 类的工作难度还是很大的，毕竟只掌握
一门语言并没有什么优势，可以说现在毕业的大学生几乎都会 C++。和计算机专业的同学
比起来，我们没学过算法导论，没学过 Linux 操作系统，甚至连数据库都不太会用。所以仅
看本文档的话是明显不够的，各位读者还是需要加强基础知识的学习。
天行健君子以自强不息，师父领进门修行在个人，想要有个好出路还是要看个人的修行，
除非你后台坚挺，否则没有什么人可以帮助你。好在从现在开始还不算太晚，抓紧时间学习
吧，达瓦里氏！
注意
本文所总结的内容均来自于笔者所写的 CSDN 博客，https://blog.csdn.net/Lao_tan 为
笔者的博客链接，转载请声明来源和作者。此外，未经本人授权，本文档总结不得用于任
何商业活动，笔者拥有对文档的绝对解释权。违反者将被依法追究法律责任。
目 录
第一章 C++数据结构的具体实现 ............................................................................................................... 1
1.1 向量 Vector 的具体实现 ................................................................................................................. 1
1.2 列表 List 的具体实现 ........................................................................................................................ 7
1.3 栈 Stack 的具体实现 ...................................................................................................................... 14
1.4 队列 Queue 的具体实现 ............................................................................................................... 15
第二章 C++STL ................................................................................................................................................ 15
2.1 C++ STL 简介 .................................................................................................................................... 15
2.2 STL 迭代器 .......................................................................................................................................... 16
2.3 utility ..................................................................................................................................................... 18
2.4 iterator ................................................................................................................................................. 20
2.5 STL 算法 .............................................................................................................................................. 22
2.6 algorithm ............................................................................................................................................. 23
2.7 容器 ..................................................................................................................................................... 26
2.8 参考文献 ............................................................................................................................................ 27
第三章 C++与 Mysql 数据库....................................................................................................................... 27
3.1 数据库的概念和基本操作 ............................................................................................................ 27
3.2 MYSQL 数据库编程与 API ............................................................................................................. 32
第四章 C++内存管理..................................................................................................................................... 36
4.1 内存管理 ............................................................................................................................................ 37
4.2 智能指针 ............................................................................................................................................ 41
4.3 内存泄漏 ............................................................................................................................................ 44
第五章 STL 容器的具体用法 ...................................................................................................................... 45
5.1 vector 用法总结 ................................................................................................................................ 45
5.2 list 用法总结 ....................................................................................................................................... 46
5.3 stack 用法总结 .................................................................................................................................. 47
5.4 queue 用法总结 ................................................................................................................................ 48
第六章 计算机网络 ......................................................................................................................................... 49
6.1 计算机网络概述 .............................................................................................................................. 49
6.2 数据链路层 ........................................................................................................................................ 51
6.3 网络层 ................................................................................................................................................. 56
6.4 运输层 ................................................................................................................................................. 64
6.5 应用层 ................................................................................................................................................. 71
第一章 C++数据结构的具体实现
本章节的所有代码均是博主前面几篇博客的参考，C++及数据结构复习笔记（十一~十
二）的参考，可以说是前面所讲数据结构时，对所有模板类以及 ADT 接口的一个整合。可
以辅助大家对于数据结构具体实现的理解。其中有很大一部分是我在前面的博客中没有讲到
的，读者可以根据自己的情况决定是否精进。
1.1 向量 Vector 的具体实现
#ifndef VECTOR_H
#define VECTOR_H
#include "Fib.h"
typedef int Rank;//秩
#define DEFAULT_CAPACITY 3 //默认的初始容量
template class Vector{ //向量模板类
protected:
Rank _size; int _capacity; T* _elem;//规模、容量、数据区
void copyFrom(T const *A, Rank lo, Rank hi);//复制数组区间 A[lo,hi)
void expand();//空间不足时扩容
void shrink();//装填因子过小时压缩
Rank bubble(Rank lo, Rank hi);//扫描交换
void bubbleSort(Rank lo, Rank hi);//起泡排序算法
Rank max(Rank lo, Rank hi);//选取最大元素
void selectionSort(Rank lo, Rank hi);//选择排序算法
void merge(Rank lo, Rank mi, Rank hi);//归并算法
void mergeSort(Rank lo, Rank hi);//归并排序算法
Rank partition(Rank lo, Rank hi);//轴点构造算法
void quickSort(Rank lo, Rank hi);//快速排序算法
void heapSort(Rank lo, Rank hi);//堆排序
public:
//构造函数
Vector(int c = DEFAULT_CAPACITY,int s = 0 ,T v = 0){ //容量为 c，规模为 s，所有元素
初始化 v
_elem = new T[_capacity = c];
for (_size = 0; _size < s; _elem[_size++] = v);//s<=c
}
Vector(T const *A, Rank n){//数组整体复制
copyFrom(A, 0, n);
}
Vector(T const *A, Rank lo, Rank hi){//数组区间
copyFrom(A, lo, hi);
1
}
Vector(Vector const& V, Rank lo, Rank hi){//向量区间
copyFrom(V._elem, lo, hi);
}
Vector(Vector const& V){//向量整体复制
copyFrom(V._elem, 0, v._size);
}
//析构函数
~Vector(){
delete[] _elem;//释放空间
}
//只读访问接口
Rank size() const{ return _size; }//规模
bool empty() const{ return !_size; }//判空
int disordered() const;//判断向量是否已排序
Rank find(T const& e) const { return find(e, 0, _size); }//无序向量整体查找
Rank find(T const &e, Rank lo, Rank hi) const;//无序向量区间查找
Rank search(T const& e) const{//有序向量整体查找
return(0 >= _size) ? -1 : search(e, 0, _size);
}
Rank search(T const& e, Rank lo, Rank hi) const;//有序向量区间查找
//可写访问接口
T& operator[] (Rank r) const;//重载下标操作符
Vector & operator= (Vector const&); //重载赋值操作符以便于克隆向量
T remove(Rank r);//删除秩为 r 的元素
int remove(Rank lo, Rank hi);//删除秩在区间[lo,hi)之内的元素
Rank insert(Rank r, T const& e);//插入元素
Rank insert(T const& e){ return insert(_size, e); }//默认作为末元素插入
void sort(Rank lo, Rank hi);//对[lo,hi)排序
void sort(){ sort(0, _size); }//整体排序
void unsort(Rank lo, Rank hi);//对[lo,hi)置乱
void unsort(){ unsort(0, _size); }//整体置乱
int deduplicate();//无序去重
int uniquify();//有序去重
//遍历
void traverse(void(*visit)(T&));//遍历（使用函数指针，只读或者局部性修改）
template void traverse(VST&);//遍历（使用函数对象，可全局性修
改）
};
//函数定义
template
void Vector::copyFrom(T const *A, Rank lo, Rank hi){
_elem = new T[_capacity = 2 * (hi - lo)];//分配空间
2
_size = 0;//规模清零
while (lo < hi)//[lo,hi)内的元素逐一
_elem[_size++] = A[lo++];//复制到_elem[0,hi-lo)
}
template
void Vector::expand(){
if (_size < _capacity) return;//尚未满员，不必扩容
if (_capacity < DEFAULT_CAPACITY)_capacity = DEFAULT_CAPACITY;//不低于最小容量
T* oldElem = _elem;
_elem = new T[_capacity <<= 1];//容量倍增
for (int i = 0; i < _size; i++)
_elem[i] = oldElem[i];//T 为基本类型，或者已经重载复制操作符"="
delete[] oldElem;//释放原空间
}
template
Rank Vector::insert(Rank r, T const& e){//插入操作
expand();//若有必要扩容
for (int i = _size; i > r; i--)//自后向前
_elem[i] = _elem[i - 1];
_elem[r] = e; _size++; return r;//置入新元素，更新容量，返回秩
}
template
void Vector::traverse(void(*visit)(T &)){//利用函数指针机制，只读或者局部性修改
for (int i = 0; i < _size; i++)
visit(_elem[i]);//遍历向量
}
template template
void Vector::traverse(VST& visit){//借助函数对象机制
for (int i = 0; i < _size; i++)
visit(_elem[i]);//遍历向量
}
template
int Vector::disordered() const{
int n = 0;
for (int i = 1; i < _size; i++)
n += (_elem[i - 1]>_elem[i]);//逆序则计数
return n;//向量有序当且仅当 n=0
}
template
T& Vector::operator[](Rank r) const{//重载下标操作符
return _elem[r]; //0 <= r < _size
}
template
int Vector::remove(Rank lo, Rank hi){//区间删除[lo,hi)
3
if (lo == hi) return 0;//单独处理退化情况
while (hi < _size) _elem[lo++] = _elem[hi++];//[hi, _size)顺次前移
_size = lo; shrink();//更新规模，若有必要则缩容
return hi - lo;//返回被删除元素的数目
}
template
T Vector::remove(Rank r){//单元素删除，可作为区间删除的特例
T e = _elem[r];//备份删除的元素
remove(r, r + 1);//调用区间删除算法
return e;//返回被删除的元素
}
template
void Vector::shrink(){
if (_capacity < DEFAULT_CAPACITY << 1)return;//不至于收缩到 DEFAULT_CAPACITY 以
下
if (_size << 2>_capacity)return;//已 25%为界
T* oldElem = _elem; _elem = new T[_capacity >>= 1];//容量减半
for (int i = 0; i < _size; i++) _elem[i] = oldElem[i];//复制原内容
delete[] oldElem;//释放原空间
}
template
Rank Vector::find(T const & e, Rank lo, Rank hi) const{//无序向量的顺序查找：返回最后
一个元素 e 的位置；失败时，返回 lo-1
while ((lo < hi--) && (e != _elem[hi]));//从后顺序查找
return hi;//若 hi
int Vector::deduplicate(){//无序向量去重操作
int oldSize = _size;//记录原规模
Rank i = 1;
while (i < _size)
(find(_elem[i], 0, i) < 0) ?
i++ ://若无雷同则继续向后考察
remove(i);//否则删除重复元素
return oldSize - _size;//返回规模变化量 即被删除元素的个数
}
template
int Vector::uniquify(){//有序向量重复去重算法（高效版）
Rank i = 0, j = 0;//各对互异元素的秩
while (++j<_size)
if (_elem[i] != _elem[j])
_elem[++i] = _elem[j];//发现不同时向前移动至前者的紧邻右侧
_size = ++i; shrink();//直接劫除尾部多余元素
return j - i;//向量规模变化量，即被删除元素的个数
4
}
template
void Vector::sort(Rank lo, Rank hi){//向量区间[lo,hi)排序
switch (rand()%5){//随机选取排序算法。可根据具体问题的特点灵活选取或者扩充
case 1:bubbleSort(lo, hi); break;//起泡排序
case 2:selectionSort(lo, hi); break;//选择排序
case 3:mergeSort(lo, hi); break;//归并排序
case 4:heapSort(lo, hi); break;//堆排序
default:quickSort(lo, hi);//快速排序
}
}
template
Rank Vector::search(T const& e, Rank lo, Rank hi) const{//在有序向量的区间[lo,hi)内，
确定不大于 e 的最后一个节点的秩
return(rand() % 2) ? binSearch(_elem, e, lo, hi) : fibSearch(_elem, e, lo, hi);//各按照 50%随
机使用二分查找和 fibonacci 查找
}
template
void Vector::bubbleSort(Rank lo, Rank hi){//向量的起泡排序
while (lo < (hi = bubble(lo, hi)));//逐趟做扫描交换直至全序
}
template
Rank Vector::bubble(Rank lo, Rank hi){//一趟扫描交换
Rank last = lo;//最右侧的逆序对初始化为[lo-1,lo]
while (++lo_elem[lo]){
last = lo;//更新最右侧逆序对位置记录，并
swap(_elem[lo - 1], _elem[lo]);//通过交换使局部有序
}
return last;//返回最右侧的逆序对位置
}
/*
template
void swap(T const& A, T const& B){//交换两个 T 类型元素
T C = B;
B = A; A = C;
}
*/
template
void Vector::mergeSort(Rank lo, Rank hi){
if (hi - lo < 2) return;//单元素区间自然有序，否则。。。
int mi = (lo + hi) / 2;//以中点为界
mergeSort(lo, mi);//分别排序
mergeSort(mi, hi);
5
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
