软件工程师必备CC常用知识点总结

引言

对于立志于从事C/C++软件开发的工作人员来说，无论是面试也好，工作中的使用也罢，有些基本知识是没法逃掉的，其中的类、结构、指针、成员函数等，都是C/C++开发者常见的内容，本文将简单的对其中的部分知识做介绍！

C++的多态与重载

多态性分为编译时多态性和运行时多态性，

编译时多态性通过静态编联完成，例如函数重载，运算符重载；

运行时多态性则是动态编联完成，主要通过虚函数来实现；

函数重载不需要是成员函数，在内外声明或定义的函数同样可以对其进行重载

重载的调用主要根据参数个数，参数类型，参数顺序来确定，函数重载是忽略返回值的

类的成员函数调用

父类指针指向子类实例对象，调用普通重写方法时，会调用父类中的方法。而调用被子类重写的虚函数时，会调用子类中的方法。

再次说明了，子类中被重写的虚函数的运行方式是动态绑定的，与当前指向类实例的父类指针类型无关，仅和类实例对象本身有关。

程序运行状态改变

程序的运行状态、就绪状态以及阻塞状态之间的相互转化关系如下：

适应算法小结

在可变式分区分配方案中，将空白区在空白区表中按地址递增次序排列是最先适应的算法

最佳适应:空闲区按容量大小递增；最差适应:空闲区按容量大小递减；最先适应:空闲区按地址大小递增。

MYSQL中处理插入过程主键或唯一重复值的解决办法

MYSQL中处理插入过程主键或唯一重复值的解决办法：

1.IGNORE:有则忽略，无则插入

2.REPLACE：有则删除再插入，无则插入

3.ONDUPLIACATEKEYUPDATE:有则更新，无则插入

内联函数以及宏的调用和编译

编译器把内联函数展开，inline关键字的声明要与函数定义放在一个文件上才起作用。而且声明为inline的函数编译器也不一定将其展开。预编译器就是预处理器，进行宏观展开。

缓存调用问题

当主机A与主机B已建立TCP连接，A的cwnd（拥塞窗口）大小初始值为1KB，ssthresh(阈值)为16KB，B的rwnd(接收缓存窗口)初始值为8KB，一个最大报文段为1KB，假设数据传输过程中未出现超时，经过3个RTT（3轮传输）后，且B尚未从缓存中取出任何数据时候，主机A的发送窗口大小为

解析：在计算机操作系统中信号量可以用来保证两个或多个关键代码段不被并发调用，而在进入一个关键代码段之前，线程必须获取到一个信号量，现假设有4个进程共享同一程序段，而且每次最多允许3个进程进入该程序段，则信号量的变化范围是多少。

允许3个进程同时进入程序段，因此信号量S设为3。这里的信号量P操作应该是等待时，将其挂到信号量等待队列中，因此可以为负数。先对信号量执行减1操作，如果为负数，将进程添加到信号量等待队列，并挂起进程。

本题中，当3个线程进入程序段后，S=0；第4个进程再想进入时，S=-1，因此取值范围是[3,-1]（整数）。

二叉树遍历

二叉树的遍历主要有三种：

（1）先(根)序遍历（根左右）

（2）中(根)序遍历（左根右）

（3）后(根)序遍历（左右根）

举个例子：

先(根)序遍历（根左右）：ABDHEICFJKG

中(根)序遍历（左根右）:DHBEIAJFKCG

后(根)序遍历（左右根）:HDIEBJKFGCA

以后(根)序遍历为例，每次都是先遍历树的左子树，然后再遍历树的右子树，最后再遍历根节点，以此类推，直至遍历完整个树。

此外，还有一个命题：给定了二叉树的任何一种遍历序列，都无法唯一确定相应的二叉树。但是如果知道了二叉树的中序遍历序列和任意的另一种遍历序列，就可以唯一地确定二叉树。常见的二叉树开发思路分为递归法、迭代法以及Morris法。下面代码是从引用网上的相关内容进行讲解：

1、递归法

这是思路最简单的方法，容易想到并且容易实现。递归的终止条件是当前节点是否为空。首先递归调用遍历左子树，然后访问当前节点，最后递归调用右子树。代码如下：

//recursive

classSolution1{

public:

vectorintinorderTraversal(TreeNode*root){

vectorintret;

if(root==NULL)returnret;

inorderHelper(ret,root);

returnret;

}

private:

voidinorderHelper(vectorintret,TreeNode*root)

{

if(root==NULL)return;

inorderHelper(ret,root-left);

ret.push_back(root-val);

inorderHelper(ret,root-right);

};

2、迭代法

在迭代方法中，从根节点开始找二叉树的最左节点，将走过的节点保存在一个栈中，找到最左节点后访问，对于每个节点来说，它都是以自己为根的子树的根节点，访问完之后就可以转到右儿子上了。代码如下：

//iterate,usingastack

classSolution2{

TreeNode*curr=root;

stackTreeNode*st;

while(!st.empty()

curr!=NULL)

while(curr!=NULL)

st.push(curr);

curr=curr-left;

curr=st.top();

st.pop();

ret.push_back(curr-val);

curr=curr-right;

这种方法时间复杂度是O(n)，空间复杂度也是O(n)。

3、Morris法

这种方法是Morris发明的，看完之后感觉精妙无比。这种方法不使用递归，不使用栈，O(1)的空间复杂度完成二叉树的遍历。这种方法的基本思路就是将所有右儿子为NULL的节点的右儿子指向后继节点（对于右儿子不为空的节点，右儿子就是接下来要访问的节点）。这样，对于任意一个节点，当访问完它后，它的右儿子已经指向了下一个该访问的节点。对于最右节点，不需要进行这样的操作。注意，这样的操作是在遍历的时候完成的，完成访问节点后会把树还原。整个循环的判断条件为当前节点是否为空。例如上面的二叉树，遍历过程如下（根据当前节点c的位置）：

（1）当前节点为10，因为左儿子非空，不能访问，找到c的左子树的最右节点p：

结果：[]

（2）找节点c的左子树的最右节点有两种终止条件，一种右儿子为空，一种右儿子指向当前节点。下面是右儿子为空的情况，这种情况先要构造，将节点p的右儿子指向后继节点c，然后c下移：

（3）当前节点c的左儿子为空，进行访问。访问后将c指向右儿子（即后继节点）：

结果：[5]

（4）继续寻找左子树的最右节点，这次的终止条件是最右节点为当前节点。这说明当前节点的左子树遍历完毕，访问当前节点后，还原二叉树，将当前节点指向后继节点：

结果：[5,10]

（5）重复上述过程，直到c指向整棵二叉树的最右节点：

左儿子为空，进行访问，c转到右儿子。右儿子为空，不满足判断条件，循环结束，遍历完成。结果如下：

[5,10,6,15,2]

这就是Morris方法，时间复杂度为O(n)，空间复杂度是O(1)。代码如下：

//Morristraversal,withoutastack

classSolution3{

TreeNode*pre;

while(curr)

if(curr-left==NULL)

else

pre=curr-left;

while(pre-rightpre-right!=curr)

pre=pre-right;

if(pre-right==NULL)

pre-right=curr;

pre-right=NULL;

大小顶堆问题

如果每个节点的值都大于等于左右孩子节点的值，这样的堆叫大顶堆；

如果每个节点的值都小于等于左右孩子节点的值，这样的堆叫小顶堆。

堆是一个完全二叉树：将序列按照从上到下，从左至右构建二叉树：第一层（3）；第二层（45）；第三层（）.可以看出是小顶堆

写在最后

本次就为大家分享到这里，希望对大家有所帮助。送人玫瑰，手有余香，期待您的点赞

转载请注明：http://www.aierlanlan.com/tzrz/2454.html