数据结构及算法

1.存储结构

数组：具有相同类型的若干变量按有序的形式组织起来，因此占用的空间是连续的。数组可分为数值数组、字符数组、指针数组、结构数组等。

bool a[x] 数组占字节数：1xy

char/unsigned (short) a[x] [y]数组占字节数：2xy

int/unsigned long/float a[x] [y]数组占字节数：4xy

(unsigned) long long/double a[x] [y]数组占字节数：8xy

链表：物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。相比于线性表顺序结构，链表比较方便插入和删除。（NOIP2015提高组）

单链表：每个节点只有一个存储直接后继结点地址的链域。

双向链表：既有存储直接后继结点地址的链域，称为右链域。又有存储直接前驱节点地址的链域，称为左链域。（NOIP2015提高组T13：插入结点；NOIP2010T9：删除结点）

2.数据结构

散列表：又称哈希表，通过关键码映射到表中一个位置来访问记录，以加快查找的速度。

栈：后进先出，栈顶允许进行插入和删除操作，栈底固定。（NOIP2015提高组）

队列：先进先出，队头进行删除操作，队尾进行插入操作。

3.树

树上每个元素称为节点，有一个特定的节点称为根节点。树是递归定义的，因此树的操作和应用大都是采用递归思想来解决的。

节点的度：一个节点的子树个数。度为0的节点称为叶节点（or 树叶），度不为0的节点称为分支节点，根节点以外的分支节点称为内部节点。树中各节点的度的最大值称为这棵树的（宽）度。

深度：节点的层次等于其父节点的层次数加1，树中各点的层次的最大值称为这棵树的深度。

森林：m（m≥0）棵互不相交的树的集合。

性质：①树上任意两个节点之间有且只有一条路径

②一个拥有N个节点的树，必然存在N-1条边（NOIP2015、2017提高组）

③树中任意一条边的删除都会导致不连通

前序遍历：根左右 中序遍历：左根右 后序遍历：左右根 （NOIP2015提高组）

二叉树的性质：①在二叉树的第i层上至多有 个节点（i≥1）。

（NOIP2018）②深度为k的二叉树至多有 个节点（k≥1）。特别地，一棵深度为k且有 个节点的二叉树称为满二叉树。（根的深度为1）

③若叶节点数为 度为2的节点数为 ，则一定满足 。

完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。

完全二叉树的性质：①叶节点只可能出现在最下面两层。

②对任一节点，若其右子树深度为m，则其左子树的深度必为m或m+1.

③具有n个节点的完全二叉树的深度为 （根的深度为1）。

（NOIP2015提高组，深度=高度）

④一棵n个节点的完全二叉树，对于任一编号为i节点，有：

i.如果i=1，则节点i为根，无父节点；否则，其父节点的编号为

ii.如果2i>n，则节点i为叶节点，否则左孩子编号为2i。

iii.如果2i+1>n，则节点i无右孩子，否则右孩子编号为2i+1。

堆：完全二叉树，节点的值大于它两个儿子的值时称为大根堆，节点的值小于它两个儿子的值时称为小根堆。堆可以在log n的时间内完成插入节点的功能。

4.图

有向图：若有n个顶点，则最多有n(n-1)条弧，此时称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。任意两点之间有双向路径的有向图称为强连通图，否则，将其中的极大连通子图称为强连通分量。

无向图：若有n个顶点，则最多有n(n-1)/2条边，此时称作无向完全图。与顶点v相关的边的条数称作顶点v的度。任意两点之间都连通的无向图称为连通图，否则，将其中的极大连通图称为连通分量。

定理：①图G中所有顶点的度数之和等于边数的两倍。

②任意一个图一定有偶数个奇点。

路径长度：路径上边或弧的数目。若路径上顶点没有重复出现，则称这条路径为简单路径。

生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。

哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。运用了贪心思想。