基础数据类型
char(1字节),bool(1字节),short(2字节),int(4字节),float(4字节),double(8字节),

一般指针为4字节,结构体(struct)里面所占的空间为各成员所占内存之和，一个联合体(union)所占的空间为是最大成员的大小

一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构(元素存在一对一的相互关系)、树形结构(元素存在一对多的相互关系)和图形结构(元素存在多对多的相互关系)。

线性结构
线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。常用的线性结构有：一维数组，链表，栈，队列等。

1.链表
定义：链表和数组都可用于存储数据，其中链表通过指针来连接元素，而数组则是把所有元素按次序依次存储。

链式存储结构(链表)由一系列结点组成，每个结点包含两个部分：存储元素本身的数据域和存储下一个结点地址的指针域。用一组非连续的存储单元来存储结点数据 ，且链表的长度不是固定的。

优点1：存储空间是动态分配的，只要计算机内存空间还有空闲，就不会发生溢出。

优点2：插入或者删除元素方便，时间复杂度为O(1)。

缺点：查找元素不方便，时间复杂度为O(n)。链表不可以随机访问任意数据！

2.栈
栈

定义：有一叠碗，每一次取的时候取最上面的出来，放的时候放到最上面，先进来的后出去，后进来的先出去，具有先进后出(FILO,first in last out)的特性。 进行删除和插入的一端称为栈顶(top)，另一端称为栈底，插入一般称为进栈(push)，删除则称为退栈或出栈(pop)。

3.队列
队列(queue)和栈一样，是一种操作受限制的特殊线性表。它只允许在表的队头(head)进行出队操作，而在队尾(tail)进行入队操作。具有先进先出(FIFO,first in fist out)的特性。

队首/队头：队列的第一项。

队尾：队列的最后一项。

13333.png

4.树形结构
a.jpg

树形结构指的是数据元素之间存在着“一对多”的关系的数据结构。特点：根节点除外的每个结点有一个或多个后驱(child)，一前驱(parent)。如图就是一棵树，我们看到它是若干结点(A、B、C等都是结点)的集合，是由惟一的根(结点A)和若干棵互不相交的子树(如B、E、F、K、L这5个结点组成的树就是一棵子树)组成的。其中每一棵子树又是一棵树，也是由惟一的根结点和若干棵互不相交的子树组成。

结点：A、B、C等都是结点，注意结点不仅包含数据元素，而且也含指向子树的分支。如A结点不仅包含数据元素A,而且包舍三个指向子树的指针。

根结点：一棵树至少有一个结点，这个结点就是根结点

叶子结点：又叫做终端结点，指度为0的结点，如F、G、I、J、K、L、M结点，都是叶子结点。

非终端结点：又叫分支结点，指度不为0的结点，如A、B、C、D、E、H结点，都是非终端结点。除了根结点之外的非终端结点，也叫做内部结点，如B、C、D、E、H结点.都是内部结点。

父结点：称上端结点为下端结点的父结点，如B是E和F的父节点

孩子结点：称下端结点为上端结点的子结点，如E是B的子节点

兄弟结点：称同一个父结点的多个子结点为兄弟结点，如E和F为兄弟结点

祖先结点：又称从根结点到某个子结点所经过的所有结点称为这个结点的祖先，如L的祖先有E,B,A

子孙结点：称以某个结点为根的子树中的任一结点都是改结点的子孙，如结点B,E,K都是结点A的子孙。

结点的度：结点拥有的子树个数或者分支的个数。如A结点有三棵子树、所以A结点的度为3。

树的度：树中各结点度的最大值。如图中结点度最大为3(A、D结点)，最小为0(F、G、I、J、K、L、M结点)，所以树的度为3。

树的深度(或高度)：树中结点的最大层次。如例子中的树共4层，所以深度为4

5.二叉树
将一般的树加上如下这两个限制条件就得到二叉树。

(1)每个结点最多只有两棵子树，即二叉树中结点的度只能为
0
,
1
,
2
0,1,2.

(2)子树有左右之分，不能颠倒。

根据二叉树的定义，可以知道二义树有
5
5种基本的形态，如下图

二叉树的5种基本形态为:

13333.png

(a)空二叉树。

(b)只有根结点。

(c)只有左子树，右子树为空。

(d)只有右子树，左子树为空。

(e)既有左子树，又有右子树。

① 满二叉树

13333.png

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。深度为
k
k且含有
2
k
−
1
2 
k
 −1个结点。

② 完全二叉树

叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。(树中所含的
n
n个结点和满二叉树中编号为1至
n
n的结点一一对应。)

二叉树性质：
性质1：二叉树的第
i
i层上最多有
2
i
−
1
2 
i−1
 个结点(i>=1)
结点最多的情况即为满二叉树的情况。

性质2：高度(或深度)为
k
k的二叉树最多有
2
k
2 
k
 -1个结点
(
k
>
=
1
)
(k>=1)
性质3：
n
n个节点的完全二叉树深度为
l
o
g
2
n
+
1
log 
2
n
​
 +1
性质4：对任意一棵二叉树，如果其叶结点数为
n
0
n 
0
​
 ，度为2的结点数为
n
2
n 
2
​
 ，则一定满足：
n
0
=
n
2
+
1
n 
0
​
 =n 
2
​
 +1.
二叉树的遍历
a.jpg

(一)先序遍历：

如果二叉树是空树，则什么都不做；

否则：

访问根结点；

先序遍历左子树；

先序遍历右子树。

先序遍历右图二叉树的结果为：124753689

(二)中序遍历：

中序遍历操作过程：

如果二叉树是空树，则什么都不做；

否则：

中序遍历左子树；

访问根结点；

中序遍历右子树。

中序遍历右图二叉树的结果为：742513869

(三)后序遍历：

后序遍历操作过程：

如果二叉树是空树，则什么都不做；

否则：

后序遍历左子树；

后序遍历右子树。

访问根结点；

后序遍历右图二叉树的结果为：745289631

6.字符串
定义：字符串指一串字符组成的串。

子串：子串被定义为字符串中任意个连续的字符组成的子序列，子串个数=
n
∗
(
n
+
1
)
2
+
1
2
n∗(n+1)
​
 +1，非空子串的个数=
n
∗
(
n
+
1
)
2
2
n∗(n+1)
​
 

注意：前提是字符串中的各个字符互不相同。

7.前/中/后缀表达式：
① 前缀表达式

又称波兰式；一种没有括号的表达式，与后缀表达式不同的是，将运算符写在前面，

操作数写在后面。如：前缀表达式 -1+2 3 的中缀形式为1−(2+3)。

② 中缀表达式

就是我们平时最常用的表达式；

③ 后缀表达式

又称逆波兰式；与前缀表达式相反，将操作数写在前面，运算符写在后面。如：后缀

表达式 1 2 3 + − 的中缀形式为 1-(2+3)。

④ 表达式互换

（1）前/后缀表达式转中缀表达式：

1.画出表达式树：表达式树是一种特殊的树，叶节点是操作数，其他节点为运算符 2.将表达式树前序遍历，可得前缀表达式；中序遍历可得中缀表达式；后序遍历可得后缀表达式。

（2）中缀表达式转前/后缀表达式

1.给中缀表达式加上括号：

1-2+3 →((1−2)+3)

2.把运算符移到括号前/后面（移到前面为前缀表达式，反之亦然）：

((1-2)+3)→((12)−3)+

3.删去括号，剩下的即为最终解：

((12)−3)+ → 12−3+

也可以用上文的“表达式树”做，比较复杂，推荐以上加括号的方法。

图
图的定义：图是由结点的有穷集合
V
V和边的集合
E
E组成。

其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点/节点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。（边（Edge）：节点之间的连线）

有向图和无向图：如图中一个是有向图(a)，即每条边都有方向，另一个是无向图(b),即每条边都没有方向。

13333.png 完全图：任意两点都有边相连。

简单路径：两点之间通过不重复的边相连。

连通图：任意两点都可以直接/间接到达，注意区别于完全图，完全图属于连通图，

连通图不一定属于完全图。

有向完全图：若有向图中有
n
n个顶点，则最多有
n
(
n
−
1
)
n(n−1)条边(即图中任意两个顶点都有两条边相连) ，我们又将具有
n
(
n
−
1
)
n(n−1)条边的有向图称作有向完全图。

无向完全图：若无向图中有
n
n个顶点，则最多有
n
(
n
−
1
)
/
2
n(n−1)/2条边(即任意两个顶点之间都有一条边)，

我们又将具有
n
(
n
−
1
)
/
2
n(n−1)/2条边的无向图称作无向完全图。

顶点的度：与顶点
v
v相关的边的条数称作顶点
v
v的度。图(b)中，顶点D的度为2。

顶点的入度和出度：在有向图中指向顶点
v
v的边的条数称作顶点
v
v的入度，由顶点
v
v发出的边的条数称作顶点
v
v的出度。如图(a),顶点C的入度为0出度为2，顶点D的入度为1出度为1。

图的遍历
图的深度优先搜索遍历：它的基本思想是首先访问出发点
v
v,并将其标记为己访问过;然后选取与
v
v邻接的未被访问的任意一个顶点
w
w，访问之；再选取与
w
w邻接的未被访问的任一顶点访问之，重复进行如上步骤。 当一个顶点所有的邻接顶点都被访问过时，则依次退回到最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取一个重复上述的访问过程，直至图中所顶点都被访问过为止。

13333.png

深度优先搜索序列是:ADECB

图的广度优先搜索遍历： 它的基本思想是首先访问起始顶点v,然后选取与
v
v邻接的全部顶点
w
1
.
.
.
.
.
.
w
n
w 
1
​
 ......w 
n
​
 进行访问，再依次访问
w
1
…
…
w
n
w 
1
​
 ……w 
n
​
 邻接的全部顶点(己经访问过的除外)，依次类推，直到所顶点都被访问过为止。例如下图为一个图的广度优先搜索遍历过程。

13333.png

广搜序列为：ABCDEFGHI

排列组合
1.加法原理(分类计数原理)：
完成一件事，有
n
n类办法，如果在第1类办法中有
m
1
m 
1
​
 种不同的方法，在第2类办法中有
m
2
m 
2
​
 种不同的方法，…，在第
n
n类办法中有
m
n
m 
n
​
 种不同的方法，那么完成这件事共有：
N
＝
m
1
,
+
m
2
.
.
.
m
n
N＝m 
1
​
 ,+m 
2
​
 ...m 
n
​
 种不同的方法。

2.乘法原理(分步计数原理)：
完成一件事，需要分成
n
n个步骤，如果做第1步
m
1
m 
1
​
 有种不同的方法，做第2步有
m
2
m 
2
​
 种不同的方法，……，做第n步有
m
n
m 
n
​
 种不同的方法，那么完成这件事共有：N＝
m
1
×
m
2
.
.
.
.
m
n
m 
1
​
 ×m 
2
​
 ....m 
n
​
 种不同的方法。

两个原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”。

3.排列
(1)排列：从
n
n个不同的元素中取出
m
(
m
≤
n
)
m(m≤n)个元素，按照一定的顺序排成一列，叫做从
n
n个不同的元素中取出
m
m个元素的一个排列。相同的排列是指元素相同且顺序相同。

(2)排列数：从
n
n个不同的元素中取出
m
(
m
≤
n
)
m(m≤n)个元素的所有排列的个数，叫做从
n
n个不同的元素中取出
m
m个元素的排列数，用符号
A
n
m
A 
n
m
​
 表示。

排列数公式：
A
n
m
=
n
(
n
−
1
)
(
n
−
1
)
.
.
.
(
n
−
m
+
1
)
=
n
!
(
n
−
m
)
!
A 
n
m
​
 =n(n−1)(n−1)...(n−m+1)= 
(n−m)!
n!
​
 

(3)全排列：把
n
n个不同的元素全部取出(从
n
n个不同的元素中取出
n
n个元素)，按照一定的顺序排成一列，叫做
n
n个不同的元素的一个全排列，全排列的个数叫做
n
n个元素的全排列数，用符号
A
n
n
A 
n
n
​
 表示。此时，
A
n
n
=
n
(
n
−
1
)
(
n
−
2
)
…
…
3
⋅
2
⋅
1
=
n
！
A 
n
n
​
 =n(n−1)(n−2)……3⋅2⋅1=n！

n
!
n!表示正整数
1
1到
n
n的连乘，叫做
n
n的阶乘。

规定：
0
!
＝
1
0!＝1。

4.组合
1.组合：从
n
n个不同的元素中取出
m
(
m
≤
n
)
m(m≤n)个元素并成一组，叫做从
n
n个不同的元素中取出
m
m个元素的一个组合。即不关心被选元素的顺序。记为
C
n
m
C 
n
m
​
 

2.公式 
C
n
m
=
A
n
m
m
!
=
m
!
m
!
(
n
−
m
)
!
C 
n
m
​
 = 
m!
A 
n
m
​
 
​
 = 
m!(n−m)!
m!
​
 

3.组合数的性质

C
n
m
=
C
n
n
−
m
C 
n
m
​
 =C 
n
n−m
​
 ,规定
C
m
0
=
1
C 
m
0
​
 =1
C
n
m
=
C
n
−
1
m
−
1
+
C
n
−
1
m
C 
n
m
​
 =C 
n−1
m−1
​
 +C 
n−1
m
​
 
5.排列组合解题技巧

先选后排：先将元素选出来，再进行排列，非常有效的降低问题的复杂度。
特殊优先：特殊元素，优先处理；特殊位置，优先考虑。
分排用直排：
n
n个元素，从中选出
m
m个，将这
m
m个元素排成若干排。分排问题的排列可以看做一排，避免考虑了复杂的前后排列，简化了问题。
分类法：当计算符合条件的数目比计算不符合条件数目简单时，将问题分成若干类，逐个求解，与“排除法”相对。
排除法：当计算符合条件的数目比计算不符合条件数目复杂时，简称正难则反。排除不符合要求的，剩下的就是符合题目要求的。与“分类法”相对。
捆绑法：
n
n个不同元素排成一列，要求
m
m个元素必须相邻。可以特殊优先，把
m
m个元素捆绑在一块单独处理。 
S
=
A
n
−
m
+
1
n
−
m
+
1
×
A
m
m
S=A 
n−m+1
n−m+1
​
 ×A 
m
m
​
 
插空法：
n
n个不同元素排成一列，要求
m
m个元素不能相邻。先把不用特殊处理的元素进行排列，再把甲乙进行插空。 
S
=
A
n
−
m
n
−
m
×
C
n
−
m
+
1
m
S=A 
n−m
n−m
​
 ×C 
n−m+1
m
​
 
隔板法/插板法：将
n
n个相同元素分成
m
m组，每组至少有一个元素。相当于把
m
−
1
m−1个隔板插到
n
n个元素形成的
n
−
1
n−1个空隙里。 
S
=
C
n
−
1
m
−
1
S=C 
n−1
m−1
​
 
定序： 
n
n个元素的全排列中有 
m
m个元素必须定序排列，这
m
m个元素相邻或不相邻不受限制。 
S
=
A
n
n
A
m
m
S= 
A 
m
m
​
 
A 
n
n
​
 
​
 
复杂度
一个问题有很多种不同的算法，如何评价一个算法的好坏呢？这就需要时间复杂度和空间复杂度来衡量了。

定义
渐进时间复杂度，用符号O表示。一个算法里语句的执行次数可以用一个式子表示，取这个式子的最高次项且忽略系数表示该算法的时间复杂度。

例如，一个程序的语句执行次数为 
2
n
+
3
n
2
+
9
+
8
n
2n+3n 
2
 +9+8n，则该算法的时间复杂度为O(n^2)。

示例
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        cin >> a[i][j];
本代码中，cin >> a[i][j] 执行了
n
2
n 
2
 次，所以时间复杂度为O
(
n
2
)
(n 
2
 )。

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        cin >> a[i][j];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        cin >> b[i][j];
本代码中，cin >> a[i][j] 执行了 
n
2
n 
2
 次，cin >> b[i][j] 也执行了
n
2
n 
2
  次，忽略系数，时间复杂度还是 
n
2
n 
2
 。

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        cin >> a[i][j];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        for(int k = 1; k <= n; k++)
            cin >> b[i][j];
本代码中，cin >> a[i][j] 执行了 
n
2
n 
2
  次，cin >> b[i][j] 执行了 
n
3
n 
3
 次，取最高次项，时间复杂度是O
(
n
3
)
(n 
3
 )。

非递归程序的时间复杂度的计算
非递归程序的时间复杂度计算一般都比较简单，直接数循环。大多数算法都适用于此，但是也有例外，例如二分等，需要特别留心。

递归程序
假设某算法的计算时间表示为递归式：

对于 T(n) = T(n-1) + T(n-2) + 1，其时间复杂度是O
(
2
n
)
(2 
n
 )