面向对象

1. 调用用户定义的类成员函数或具体对象（一个库类面向具体数据的过程）
2. 常见语言：Java、Python、C++
3. class 或 struct

面向过程

1. 定义：需要程序员自己考虑程序运行的每个细节和函数功能的实现
2. 常见语言：C

指针

1. 定义 *p，存储地址的变量类型
2. 可以访问其他变量的地址
3. 加 * 代表值，不加 * 表示地址

#include<cstdio>
#include<iostream>
using namespace std;

int main(void){
	int a=6,b=20,*p;
	p=&a;
	cout<<p<<" "<<*p<<endl;
	a=10;
	cout<<p<<" "<<*p<<endl;
	p=&b;
	cout<<p<<" "<<*p<<endl;
	b=a;//将 a 的值赋给 b，将 p 指向 a 的地址
	cout<<p<<" "<<*p<<endl;
	return 0;
}

output：

0x6ffe04 6
0x6ffe04 10
0x6ffe00 20
0x6ffe00 10

链表和数组的区别

1. 数组和链表都可以排序
2. 链表和数组储存的信息差不多，但是链表调整所用的时间比数组少
3. 数组大小固定，链表大小可动态调整

表达式

1. 前缀表达式 +ab
2. 中缀表达式 a+b
3. 后缀表达式 ab+
4. 转换方法： （1）按照数学运算顺序增添括号 （2）将运算符号按法则调整顺序

例

对表达式 a+(b-c)*d 的前缀表达式为（ ），其中 +、-、* 是运算符。

答案 +a*-bcd

a+(b-c)*d
a+[(b-c)*d]
a+(-bc*d)
a+*-bcd
+a*-bcd

哈夫曼编码

1. 特点：左小右大，左0右1
2. 转化：将哈夫曼树转为哈夫曼编码
3. 本质上是一种贪心的策略。

例

假设字母表{a,b,c,d,e}在字符串出现的频率分别为10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，求字母d的编码长度（）位。

答案：2

a:110
b:111
c:01
d:10
e:00

二叉树

1. 完全二叉树：允许最后一层的节点排列不满，但上层的节点必须排满（不能构成完整三角形）
2. 满二叉树：每个节点没有子节点或有两个子节点（可以构成完整三角形）

排序

1. 稳定排序：插入排序、冒泡排序、归并排序、基数排序
2. 不稳定排序：选择排序、快速排序、希尔排序、堆排序

稳定：相同元素相对位置不变

枚举算法

1. 定义：枚举所有可能。从所有候选答案中去搜索正确的解。
2. 使用条件：

• 可预先确定候选答案的数量
• 候选答案的范围在求解之前必须有一个确定的集合

贪心算法

1. 定义：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解

递归算法

1. 定义：自调用函数
2. 条件：不允许使用多组参数调用函数
3. 规则：先递进，后回归

#include<cstdio>
#include<iostream>
using namespace std;

int getNum(int x){
	if(x==1) return 1;
	else return x+getNum(x-1);
} 
int main(void){
	cout<<getNum(5);
	return 0;
}

递进

getNum(5); 
5+getNum(4);
5+4+getNum(3);
5+4+3+getNum(2);
5+4+3+2+getNum(1);

回归

5+4+3+2+1;
5+4+3+3;
5+4+6;
5+10;
15;

三大逻辑运算

与(and)

1. 编程符号：&
2. 运算符号：^
3. 运算规则：两个同时为真结果真

0&0=0;
0&1=0;
1&0=0;
1&1=1;

按位与

原理

注：负数按补码形式参加按位与运算

或(or)

1. 编程符号：|
2. 运算符号：∨
3. 运算规则：一真则真

0|0=0;
0|1=1;
1|0=1;
1|1=1;

非(not)

1. 运算符号：!
2. 运算规则：反操作，原为真，结果为假，反之亦然

!1 = 0;
!0 =1;