基础数据类型

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)的特性。

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

队尾：队列的最后一项。

4.树形结构

树形结构指的是数据元素之间存在着“一对多”的关系的数据结构。特点：根节点除外的每个结点有一个或多个后驱(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$.

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

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

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

(a)空二叉树。

(b)只有根结点。

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

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

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

① 满二叉树

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

② 完全二叉树

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

二叉树性质：

• 性质1：二叉树的第$i$层上最多有$2 ^{i-1}$个结点(i>=1)

结点最多的情况即为满二叉树的情况。

• 性质2：高度(或深度)为$k$的二叉树最多有$2^k$-1个结点$(k>=1)$
• 性质3：$n$个节点的完全二叉树深度为$log_2^n+1$
• 性质4：对任意一棵二叉树，如果其叶结点数为$n_0$，度为2的结点数为$n_2$，则一定满足：$n_0=n_2+1$.

二叉树的遍历

(一)先序遍历：

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

否则：

访问根结点；

先序遍历左子树；

先序遍历右子树。

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

(二)中序遍历：

中序遍历操作过程：

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

否则：

中序遍历左子树；

访问根结点；

中序遍历右子树。

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

(三)后序遍历：

后序遍历操作过程：

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

否则：

后序遍历左子树；

后序遍历右子树。

访问根结点；

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

6.字符串

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

子串：子串被定义为字符串中任意个连续的字符组成的子序列，子串个数=$\frac {n*(n+1)} 2+1$，非空子串的个数=$\frac {n*(n+1)} 2$

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

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$和边的集合$E$组成。

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

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

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

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

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

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

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

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

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

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

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

图的遍历

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

深度优先搜索序列是:ADECB

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

广搜序列为：ABCDEFGHI

排列组合

1.加法原理(分类计数原理)：

完成一件事，有$n$类办法，如果在第1类办法中有$m_1$种不同的方法，在第2类办法中有$m_2$种不同的方法，…，在第$n$类办法中有$m_n$种不同的方法，那么完成这件事共有：$N＝m_1,+m_2...m_n$种不同的方法。

2.乘法原理(分步计数原理)：

完成一件事，需要分成$n$个步骤，如果做第1步$m_1$有种不同的方法，做第2步有$m_2$种不同的方法，……，做第n步有$m_n$种不同的方法，那么完成这件事共有：N＝$m_1 \times m_2 .... m_n$种不同的方法。

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

3.排列

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

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

排列数公式：$A_n^m=n(n-1)(n-1)...(n-m+1)=\frac {n!} {(n-m)!}$

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

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

规定：$0!＝1$。

4.组合

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

2.公式 $C_n^m=\frac {A_n^m} {m!} = \frac {m!} {m!(n-m)!}$

3.组合数的性质

• $C_n^m=C_n^{n-m}$,规定$C_m^0=1$
• $C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}$

5.排列组合解题技巧

• 先选后排：先将元素选出来，再进行排列，非常有效的降低问题的复杂度。
• 特殊优先：特殊元素，优先处理；特殊位置，优先考虑。
• 分排用直排：$n$个元素，从中选出$m$个，将这$m$个元素排成若干排。分排问题的排列可以看做一排，避免考虑了复杂的前后排列，简化了问题。
• 分类法：当计算符合条件的数目比计算不符合条件数目简单时，将问题分成若干类，逐个求解，与“排除法”相对。
• 排除法：当计算符合条件的数目比计算不符合条件数目复杂时，简称正难则反。排除不符合要求的，剩下的就是符合题目要求的。与“分类法”相对。
• 捆绑法：$n$个不同元素排成一列，要求$m$个元素必须相邻。可以特殊优先，把$m$个元素捆绑在一块单独处理。 $S=A_{n-m+1}^{n-m+1}\times A_m^m$
• 插空法：$n$个不同元素排成一列，要求$m$个元素不能相邻。先把不用特殊处理的元素进行排列，再把甲乙进行插空。 $S=A_{n-m}^{n-m} \times C_{n-m+1}^m$
• 隔板法/插板法：将$n$个相同元素分成$m$组，每组至少有一个元素。相当于把$m-1$个隔板插到$n$个元素形成的$n-1$个空隙里。 $S=C_{n-1}^{m-1}$
• 定序： $n$个元素的全排列中有 $m$个元素必须定序排列，这$m$个元素相邻或不相邻不受限制。 $S= \frac {A_n^n} {A_m^m}$

  复杂度

一个问题有很多种不同的算法，如何评价一个算法的好坏呢？这就需要时间复杂度和空间复杂度来衡量了。

定义

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

例如，一个程序的语句执行次数为 $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$次，所以时间复杂度为O$(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$次，cin >> b[i][j] 也执行了$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$ 次，cin >> b[i][j] 执行了 $n^3$次，取最高次项，时间复杂度是O$(n ^3)$。

非递归程序的时间复杂度的计算

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

递归程序

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

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