C语言&数据结构和算法
2021-05-06 11:13:10 0 举报AI智能生成
C语言基础和进阶（面试向），数据结构和算法（面试常问）
作者其他创作
大纲/内容
c++
基础知识
数据/变量
类型
整型
（双）浮点型
字符型
布尔型
作用域
关键字
auto
static
隐藏
存放在静态存储区
保持变量内容的持久
默认初始值为0
C++中的类成员声明
类中静态成员变量必须在类外初始化
const
加在普通变量上
加在指针变量上
加在函数的参数和返回值上
引用和指针
定义
指针是指向变量地址的变量
引用是所引变量的别名，地址相同
在函数中传递方式
相同点和区别
相同：都可以直接修改变量，避免拷贝副本
区别：
结构体
定义方式
使用结构体变量找到其中成员用.，用结构体指针找成员用->
面向对象
封装
类
调用实例类的成员对象用.
类访问修饰符
对应三种继承方式
构造和析构函数
构造函数可以带参数，不能返回值
析构函数不带参数，也没有返回值
拷贝构造函数，输入另一个同类对象，拷贝进行初始化
友元函数
不属于类成员的函数
this指针
是所有成员函数的隐含参数
用->
静态成员/函数
静态成员在类的所有对象中是共享的，但要在类外初始化
静态函数只要使用类名加范围解析运算符 :: 就可以访问
静态成员函数没有 this 指针，只能访问静态成员
静态成员函数没有 this 指针，只能访问静态成员
数据封装和抽象
把数据和函数开，用public和private
抽象类接口
在基类中声明纯虚函数，作为接口
继承
继承细则
多态
重载
函数重载
运算符重载
虚函数
在基类中用vitrual声明并定义，在派生中的子类中重新定义
纯虚函数
当基类中虚函数没有实际操作时，可以只声明函数名，即纯虚函数
虚函数表
只要类内有定义虚函数，就有自己的一张虚函数表
子类的虚函数表中先放所有基类的虚函数指针
子类有虚函数的覆盖，则在基类虚函数指针的位置覆盖
进阶知识
动态内存
new和malloc
new申请堆的空间，并且根据数据类型创建对象并初始化，返回数据
delete删除空间
malloc申请堆上的空间，输入空间长度，强制类型转换，返回空间地址
free释放空间
深拷贝和浅拷贝
浅拷贝只是复制指针地址，同一块内存
深拷贝是重新开辟一块同样的内存空间，再复制数据
内存管理
四种分配方式
堆（动态）
程序员手动分配和释放的，malloc/free,new/delete
栈
由编译器自动分配和释放，用于存放局部变量和参数
全局/静态存储区
存放全局变量和静态变量，在程序编译时分配
文字常量区
存放常量字符串
STL标准模板库
迭代器
指向序号的指针
容器
顺序存储结构
vector
相当于动态分配内存的数组
可调用的方法
list
非连续存储，用双向链表实现
heap
使用
用数组作为存储结构
stack
push/top/pop/empty/size
队列
单端队列queue
push/front/pop/empty/size
双端队列deque
两端都能进行插入删除的操作
优先队列实现大顶/小顶堆
string
相当于字符数组
可调用的方法
关联存储结构
set
基本操作
用红黑树实现，自动去重排序
map
用红黑树实现，内部都是有序的
基本操作
无序的map
unordered_map，用哈希表实现，查找效率更高
面试常见问题
struct和class的区别
继承关系和成员属性上，struct默认是public的，而class是privates的
没有很大区别，C++中的struct仅仅是为了兼容C
类成员函数的重载和覆盖
overload是同样的函数名不同参数
override是虚函数实现多态的过程
vector的resize和reserve区别
capacity是容器最大容量，size是当前容量，capacity动态分配
resize(x)开辟x个元素的空间，并且创建x个元素，初始值为0
reserve(x)开辟x个元素空间，但当前的size还是0
多重继承和虚函数表
每个父类都有自己的虚表
子类的成员函数被放到了第一个父类的表中
子类有覆盖时，子类虚函数表中对应父类被覆盖的函数指针位置，被替换成了子类的函数指针
new和malloc区别
new是在自由存储区申请空间，malloc是在堆上
new会调用对象的构造和析构函数，malloc只面向存储空间地址
new后面直接跟对象类型，malloc需要计算申请内存的空间大小
new没法对已分配内存进行扩充，malloc可以用realloc
数据结构和算法
算法归纳
排序
稳定
冒泡排序
两两比较交换，每一趟得到最大/小值
改进：设置标记，若某趟不交换则break
时间复杂度最好n，最坏n^2，空间1
插入排序
依次遍历无序元素，在有序序列中找到位置插入
时间复杂度最好n，最坏n^2，空间1
改进：希尔排序（不稳定）
将插入排序的增量做递减调整，gap=length/2
时间复杂度始终是nlogn，空间1
归并排序
先使每个子序列有序，再使子序列段间有序
时间复杂度最好n，最差nlogn，空间n
计数排序
用另一个数组记录元素出现次数
改进：桶排序
将计数的间隔升级为桶，再对每个桶排序
用list数组实现，在每个桶中用插入排序
时间最好n+k，最坏n^2，空间n+k
时间n+k，空间k，复杂度取决于待排数据的数值范围
基数排序
低位先排序，然后收集；再按照高位排序，然后再收集，直到最高位
时间nk，空间n+k，复杂度取决于待排数据的最高位数
不稳定
选择排序
每趟选出最小的，和无序序列的第一个值交换
时间复杂度一直是n^2，空间1
快速排序
分治法来把一个序列分为两个子序列
时间复杂度最好nlogn，最坏n^2，空间n
堆排序
构造最值堆，取出堆顶不断调整
时间复杂度nlogn，空间1
查找
有序
二分查找
递归将序列折半，比较中间值
时间复杂度log2n，ASL=
改进：插值查找
根据待查数据选择折半点
时间复杂度log2(log2n)
改进：斐波那契查找
根据斐波那契函数选择折半点
时间复杂度log(2n)
树表查找
二叉查找树BST
中序遍历（左中右）得到有序数列
时间复杂度最好logn，最坏n
2-3查找树
3节点保存两个值，和左中右三个子节点
3节点的中间子节点，是节点两个值区间的值
时间复杂度
红黑树
是2-3树的另一种表现形式，红线处就是3节点两个值的连接
整棵树黑色平衡
时间复杂度logn
B树
分块查找
序列分块，块间有序，块内无序
不要求有序
顺序查找
依次遍历比较
时间复杂度n，ASL=(n+1)/2
哈希查找
将序列通过函数映射成索引，以空间换时间
”直接定址”与”解决冲突”是哈希表的两大特点
时间复杂度1，空间k
递归
动态规划
操作系统
学习资源
哈工大李治军老师公开课
《深入理解计算机系统》
0 条评论
下一页
