软件评测师笔记（6）数据结构与算法
1. 线性结构
每个元素最多只有一个出度和一个入度，表现为一条线状。线性表按存储方式分为顺序表和链表
- 顺序存储：用一组地址连续的存储单元一次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻
- 链式存储：存储个数据元素的节点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。
当需要对元素进行破坏性操作（插入、删除）时，链表效率更高，因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他节点位置都需要变动。
当需要对元素进行不改变结构操作时（读取、查找），顺序表效率更高，因为其物理地址是连续的，如同数组一般，只需按索引号就可快速定位，而链表需要从头节点开始，一个个的查找下去。
2. 栈和队列
队列、栈结构如下图
队列是先进先出，分队头和队尾；
栈是先进后出，只有栈顶能进出。
- 循环队列
设循环队列Q的容量为MAXSIZE,初始时队列为空，且Q.rear和Q.front都等于0.元素入队时修改队尾指针，即令Q.rear=(Q.rear+1)%MAXSIZE。元素出队时修改队头指针，即令Q.fronts=(Q.front+-1)%MAXSIZE。根据队列操作的定义，当出队操作导致队列变为空时，有Q.rear==Q.front;若入队操作导致队列满，Q.rear=Q.front。
3. 广义表
广义表是线性表的推广，是由0个或多个单元素或自表组成的有限序列
表头：广义表的第一个表元素就是表头
表尾：广义表中，除了第一个元素之外的其他所有元素构成的表称之为表尾
广义表和线性表的区别：线性表的元素都是结构上不可分的单元素，而广义表的元素既可以是单元素也可以是有结构的表
4. 数组
数组存储地址的计算，特别是二维数组，要注意理解，假设每个数组元素占用存储长度为len,起始地址为a,存储地址计算如下（默认从0开始编号）：
| 数组类型 | 存储地址计算 |
|---|---|
| 一维数组a[n] | a[i的存储地址为：a+i*len |
| 二维数组a[m][n] | a[i]的存储地址(按行存储)为：a+(i *n+j) *len a[i]的存储地址(按列存储)为：a+(j *m+i) *len |
5. 二叉树
是n个节点的有限集合，它或者是空树，或者是由一个跟节点及两个互不相交且分别称为左、右子树的二叉树所组成。与树的区别在于每个节点最多只有两个字节点。
- 满二叉树：每层都是满节点的
- 完全二叉树：k-1层全是满节点，第k层从左到右是满的
- 最优二叉树(哈夫曼树)：是一类带权，路径长度最短的树
路径：树中一个节点到另一个节点之间的通路
节点的路径长度：两节点路径上的分支数目
树的路径长度：根节点到达每一个叶子节点之间的路径长度之和
权：节点代表的值
节点的带权路径长度：该节点到跟节点之间的路径长度乘以该节点的权
树的带权路径长度(树的代价)：树的所有叶子节点的带权路径长度之和
- 查找二叉树：查找二叉树上每一个节点都存储一个值，且每个节点的所有左孩子节点值都小于父节点值，而有右孩子节点值都大于父节点值
- 平衡二叉树又称为AVL树，它或者是一棵空树，或者是具有下列性质的二叉树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。若将二叉树结点的平衡因子(Balance Factor,BF)定义为该结点左子树的高度减去其右子树的高度，则平衡二叉树上所有结点的平衡因子只可能是1、0和1。只要树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
以根节点顺序遍历二叉树有三种方式
- 先序：根左右
- 中序：左根右
- 后续：左右根
示例：前序：12457836；中序：42785136；后序：48752631
5.1 哈夫曼树的求法
给出一组权值，将其中两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而后删除这两个叶子节点权值，并将父节点的值添加到该组权值中。重复进行上述步骤，直至所有权值都被使用完。
5.2 哈夫曼编码
若需要构造哈夫曼编码（要保证左节点值小于右节点的值，才是标准的哈夫曼树)，将标准哈夫曼树的左分支设为0，右分支设为1，写出每个叶节点的编码，会发现，哈夫曼编码前缀不同，因此不会混淆，同时也是最优编码。
6. 图
6.1 图的基本概念
无向图：图的结点之间连线是没有箭头的，不分方向
有向图：图的结点之间连线是箭头，区分A到B，和B到A是两条线
完全图：无向完全图中，节点两两之间都有连线，有向完全图中两两节点之间都有互通的两个箭头
6.2 图的存储
邻接矩阵：假设一个图中有n个节点，则使用n阶矩阵来存储这个图中各节点的关系，规则是若节点i到节点j有连线，则矩阵Rij=1否则为0
邻接链表：用到了两个数据结构，先用一个一维数组将图中所有结点存储起来，而后对此一维数组的每个结点元素使用链表挂上和其有连接关系的结点的编号和权值
6.3 图的遍历
深度优先：从任一节点出发，遍历到底，直至返回，再选取任一其他节点出发，重复这个过程直至遍历完整个图
广度优先：先访问完一个顶点的所有邻接点，而后再依次访问其邻接点的所有邻接点
6.4 最小生成树
假设有n个结点，那么这个图的最小生成树有n-1条边
- 克鲁斯卡尔算法：这个算法是从边出发，因为本质是选取权值最小的n-1条边，因此就将边按权值大小排序，依次选取权值最小的边，直至囊阔所有结点，注意选边时不能形成环路
针对上图使用克鲁斯卡尔算法生成最小生成树步骤如下
- 一共9个节点，因此我们最小生成树共8条边
- 选择权值最小的边V4-V7，没有形成环路，添加入树
- 选择权值最小的边V2-V8，没有形成环路，添加入树
- 选择权值最小的边V0-V1，没有形成环路，添加入树
- 选择权值最小的边V0-V5，没有形成环路，添加入树
- 选择权值最小的边V1-V6，没有形成环路，添加入树
- 选择权值最小的边V1-V6，没有形成环路，添加入树
- 选择权值最小的边V3-V7，没有形成环路，添加入树
- 选择权值最小的边V5-V6，形成环路，舍弃
- 选择权值最小的边V1-V2，形成环路，舍弃
- 选择权值最小的边V6-V7，没有形成环路，添加入树
- 到此我们已经有了8条边（n-1=9-1=8），最小生成树已经完成
6.5 拓扑序列
若图中一个节点入度为0，则应该最先执行此活动，而后删除掉此节点和其关联的有向边，再去找图中其他没有入度的结点，执行活动，依次进行，示例如下(有点类似于进程的前趋图原理)
7. 排序算法
排序的分类：稳定排序与不稳定排序：依据是两个的值在一个待排序序列中的顺序在排序前后是不是相对不变的，若相对不变则为稳定排序，反之则为不稳定排序。
内排序和外排序：依据排序是在内存中进行的还是在外部进行的
排序的算法有很多，大致可以分为以下几类
- 插入类排序：直接插入排序、shell排序
选择类排序
- 简单选择排序：假设待排序的元素有n个，在第一趟排序过程中，从n个元素序列中选择最小的元素，并将其放在元素序列的最前面，即第一个位置。在第二趟排序过程中，从剩余的n-1个元素中，选择最小的元素，将其放在第二位置。以此类推，直到没有待比较的元素，简单选择排序算法结束。
- 堆排序：将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆。将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端。重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤直到整个序列有序
交换类排序
- 冒泡排序：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
- 快速排序：采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。
- 归并排序：归并是将两个或两个以上的有序表组合成一个新的有序表，假设初始序列含有n个记录，则可看成是n个子序列，每个子序列的长度为1，然后两两归并，得到[ n/2 ]个长度为2或为1的有序的子序列；再将子序列两两归并。如此重复，直到得到一个长度为n的有序序列为止
- 基数排序
