数据结构研究什么.doc

数据结构研究什么
数据处理中数据之间的逻辑关系、数据在计算机中的存储方式和在这种“结构”上能进行的操作(运算)。
如何表示数据，如何存储数据，如何对数据进行处理
3种逻辑结构
线性结构树形结构(图结构
线性结构的性质和概念
: 性质：
< 全序性：线性结构的全部结点两两都可以比较前后关系。
< 单索性：除头结点外，每个结点有唯一的直接前驱结点；除尾结点外，每个结点有唯一的直接后继结点。
: 概念：
< 直接前驱、直接后继结点：前后相邻的结点；
< 前驱、后继结点：前面、后面的结点。
< 在不混淆的前提下，直接前驱和直接后继可简称为前驱和后继。
树结构的性质和概念
: 性质和概念：
< 根结点：“树的根”，一棵树只有唯一的一个根结点。
< 叶子结点：“树的叶子”，一棵树有很多叶子。
< 除根结点外，每个结点有唯一的父结点；除叶子结点外，每个结点允许有多个子结点。
< 父亲结点，子女结点，兄弟结点，祖先结点，子孙结点。
< 树结构是一棵“倒立的树”。
4种存储结构

顺序结构的优缺点
用一块连续的、无间隙的存储空间按顺序存储各结点。
< 各结点地址计算方法(问题1)：
结点i的地址 = 起始地址 + i×每个结点所占存储空间大小
< 各结点之间逻辑关系表示(问题2)：地址相邻关系就表达了结点之间的逻辑关系。
顺序存储结构是在内存中开辟一个连续的空间用来存储数据,因此对于内存的需求和苛刻,必须是连续的空间.在数据查找(特别是不按照规律排列的数据),时间复杂度教少.效率高.
链式结构的优缺点
链式存储结构是采取连表指针来指示数据的存储位置,这就可以是在内存中随意的存储,没有必须连续储存空间的要求,对于内存的要求相对教容易.但是要是是从小到大顺序排列的数据,链式存储结构的时间复杂度教小,效率高.但是要是不规则排布的数据一般时间复杂度较高,效率更低
算法渐进复杂度的表示方法
: 算法时间复杂度的渐进分析：在时间复杂度t(n)中，剔除不会从实质上改变函数数量级的项，经过这样处理得到的函数是t(n)的近似效率值，但这个近似值与原函数已经足够接近，当问题规模很大时尤其如此。这种效率的度量就称为算法的渐进复杂度。(在不引起混淆的情况下，也可简称时间复杂度)
算法的最好、最坏和平均时间复杂度
: 算法的复杂度往往取决于输入数据，例如一个排序算法的时间复杂度往往取决于输入数据的原始有序程度。因此分析算法复杂度时往往要区分最好情况、最坏情况和平均情况。
: 例如，在一个包含n个元素的数组中查找某个数据(假定该数据是数组元素)：
< 最好情况：该数据就是第0个元素，只需比较1次就可以结束了，其复杂度为O(1)。
< 最坏情况：该数据是数组最后一个元素，则需要比较n次，其复杂度为O(n) 。
< 评均情况：假设需要查找的数据是第0个元素、第1个元素、…、最后一个元素的概率相等，则平均需要查找的次数为：1×1/n + 2×1/n + … + n×1/n = (n+1)/2。其复杂度为O(n)。
基本的算法复杂度类型

线性表、顺序表、链表、栈和队列的基本概念
: 线性表是一类线性（区别于树型结构和图结构）数据结构，它有多种存储结构和应用方法，从而可以细分为顺序表、链表、队列、栈等。
: “线性表”是从逻辑结构的角度来描述数据结构的，它主要有两种存储结构：顺序存储结构和链式存储结构。
: 顺序表(sequential list)又称为向量(vector)，它采用定长的一维数组存储结构。
: 向量的主要特性：
: 元素的类型相同。
: 元素顺序地存储在一块有连续地址的存储空间中，每一个元素按其顺序有唯一的索引值，又称下标值，用它可以方便地访问元素内容。
: STL提供了3种通用实体：容器、迭代器和算法。
: 链表(linked list)的特点是动态申请内存空间，并通过指针来链接结点，按照线性表的前驱/后继关系把一个个结点链接起来。
: 几种用于线性表的链式存储结构：
: 单链表；
: 双链表；
: 循环单链表；
: 循环双链表。
: 链表存储是最常用的存储方式之一，它不仅可以用来表示线性表，而且也可以用于其他非线性的数据结构中，如树结构和图结构。
: 栈(stack)是一种限制访问端口的线性表，常称为后进先出表(LIFO－Last In, First Out)。
: 栈的一端称为“栈顶”，表元素的插入和删除均限制在栈顶；表的另一端成为“栈底”。
: 表元素的插入，成为压栈(push)。
: 表元素的删除，称为出栈(pop)。
: 队列(queue)也属于限制访问端口的线性表。数据进入/取出的方式为先进先出表(FIFO－First In, First Out)，因此队列也称为先进先出表。
: 只允许从队列尾(rear)进入数据。
: 只允许从队列头(front)取出数据。

顺序表的抽象数据类型：插入元素
//插入一个元素，使之成为第index个元素
template <class ELEM>
void Vector<ELEM>::insert( const ELEM& item, int index )
{
assert( Size<Length ); assert( index>=0 && index<=Size );
for( int i=Size; i>index; i-- ) //移动元素
elmlist[i] = elmlist[i-1];
elmlist[index] = item;
Size++;
}

顺序表的抽象数据类型：删除元素
template <class ELEM>
void Vector<ELEM>::remove( int index ) //删除第index个元素
{
assert( index>=0 && index<Size );
for( int i=index; i<Size-1; i++ ) //移动元素
elmlist[i] = elmlist[i+1];
Size--;
}

顺序表的优缺点
优点：
1) 直接存储元素，每个元素不需要存储指针等其他信息。
2) 直接访问元素，访问第k个元素的时间为O(1)，与n无关。
缺点：
1) 插入新元素需要移动大量的元素，复杂度为O(n)。
2) 删除元素也需要移动大量的元素，复杂度为O(n)。
顺序表的缺点之一：插入新元素时需要移动大量的元素。
设顺序表的长度为n，在各个位置插入的概率相等，则插入算法平均需要移动n/2个元素。其复杂度为O(n)。
顺序表的缺点之二：删除元素时需要移动大量的元素。
删除算法的复杂度也为O(n) 。

单链表的理解
: 在单链表中，每个结点由两部分组成：
< 存放结点数据的data域；
< 存放指向后继结点的next指针域。
: 因为每个结点中只有指向后继结点的指针，因此由这种结点链接而成的链表，称为单链表。
: 表首指针first：指向单链表中第0个结点(结点序号从0开始计起)。

单链表的抽象数据类型：释放所有结点
单链表的抽象数据类型：插入结点
单链表的抽象数据类型：删除结点
单链表的优缺点
双链表的理解
双链表的抽象数据类型：插入结点(简单情形)
双链表的抽象数据类型：删除结点(简单情形)
栈的理解
STL中的栈
栈的应用1：十进制整数转换成二进制
栈的应用2：括号匹配
顺序栈的理解
顺序栈的抽象数据类型：压栈
顺序栈的抽象数据类型：出栈
顺序栈的抽象数据类型：取出栈顶结点
顺序栈的抽象数据类型：判空
链式栈的理解
链式栈的抽象数据类型：释放所有结点
链式栈的抽象数据类型：压栈
链式栈的抽象数据类型：出栈
链式栈的抽象数据类型：取出栈顶结点
链式栈的抽象数据类型：判空
顺序栈和链式栈的比较
计算表达式的值：中缀表达式→后缀表达式
(不要求记忆算法执行过程)
计算表达式的值：计算后缀表达式的值
队列的理解
STL中的队列
队列的应用：BFS的实现
顺序队列的理解
顺序队列的抽象数据类型：入队列
顺序队列的抽象数据类型：出队列
顺序队列的抽象数据类型：取出队列头结点
链式队列的理解
链式队列的抽象数据类型：入队列
链式队列的抽象数据类型：出队列
链式队列的抽象数据类型：取出队列头结点
顺序队列和链式队列的比较
第3章 字符串
编号 知识点 类型 掌握程度 代码要求
3_01 字符串的模式匹配 概念 理解
: 字符串的模式匹配：给定目标字符串T(Target)和一个模板P(Pattern)，也是字符串，在目标字符串T中查找与模板完全相同的子串，返回T中和P匹配的第一个子串(简称为配串)的首字符位置。

3_02 朴素的模式匹配算法 算法 掌握原理 代码段
第0趟开始比较。在第0趟，将模板P的第0个字符对准T的第0
个字符，将两字符串对应位置上的字符一一比较，如果匹配成
功则结束，否则(即匹配失败)将P右移一个位置进入第1趟比较，
…。第s趟比较是从T的第s个字符和P的第0个字符开始比较。
反复进行每一趟的比较，直到出现以下情况：
(1) 执行到某一趟，模板所有字符与目标串中对应的字符都相等，匹配成功。
(2) 模式移动到最后可能与T比较的位置，但还不能匹配，则匹配失败。

3_03 KMP算法：模式串前缀函数值的人工求解 算法 掌握原理

3_04 KMP算法：模式串前缀函数值的推导 算法 掌握原理

3_05 KMP算法：模式串前缀函数值的求解 算法 掌握原理 代码段

3_06 KMP算法：实现 算法 掌握原理 代码段

第4章 二叉树
编号 知识点 类型 掌握程度 代码要求
4_01 树与子树 概念 理解
4_02 二叉树的定义 概念 理解
4_03 二叉树的基本概念 概念 理解
4_04 满二叉树 概念 理解
4_05 完全二叉树 概念 理解
4_06 扩充二叉树 概念 理解
4_07 扩充二叉树的外部路径长度和内部路径长度 计算 掌握方法
4_08 扩充二叉树的性质 性质 理解
4_09 二叉树性质1(满二叉树定理) 性质 理解
4_10 二叉树性质2(满二叉树定理推论) 性质 理解
4_11 二叉树性质3 性质 理解
4_12 二叉树性质4 性质 理解
4_13 二叉树性质5 性质 理解
4_14 二叉树性质6 性质 理解
4_15 二叉树的二叉链表实现 原理 掌握
4_16 二叉树的二叉链表实现：从二叉树根结点出发，查找指定结点的父结点 算法 掌握原理 代码段
4_17 二叉树的二叉链表实现：返回指定结点左兄弟 算法 掌握原理 代码段
4_18 二叉树的二叉链表实现：返回指定结点右兄弟 算法 掌握原理 代码段
4_19 二叉树的二叉链表实现：删除二叉树的递归算法 算法 掌握原理 代码段
4_20 二叉树的遍历 概念 理解
4_21 二叉树的前序(中序、后序)遍历 算法 掌握原理
4_22 前序(中序、后序)遍历的递归实现 算法 掌握原理 代码段
4_23 前序遍历的非递归实现 算法 掌握原理 代码段
4_24 三叉链表 原理 掌握
4_25 完全二叉树的数组实现 性质 理解
4_26 二叉链表及线索二叉链表性质 性质 理解
4_27 前序(中序或后序)线索二叉树 原理 掌握原理
4_28 二叉搜索树：定义 概念 理解
4_29 给定关键码序列，构造二叉搜索树 算法 掌握原理
4_30 二叉搜索树：插入结点 算法 掌握原理 代码段
4_31 二叉搜索树：删除结点 算法 掌握原理 代码段
4_32 二叉搜索树：查找结点 算法 掌握原理 代码段
4_33 STL优先级队列 应用 掌握方法 完整程序
4_34 最小(大)堆定义 概念 理解
4_35 堆的创建－筛选法 算法 掌握原理
4_36 堆的操作：插入结点 算法 掌握原理
4_37 堆的操作：删除结点 算法 掌握原理
4_38 前缀编码 概念 理解
4_39 加权平均编码长度 概念 理解
4_40 Huffman树加权外部路径长度 概念 理解
4_41 构造Huffman树 算法 掌握原理

编号 知识点
5_01 森林的概念
: 森林(forest)：由零棵或多棵不相交的树组成的集合。
: 注意：自然界中的树和森林是不同的概念。而数据结构中的树和森领只有微小的差别，删去根结点，则树就变成森林；加上一个结点作为根，则森林就变成树。
: 在树或森林与二叉树之间存在一个自然的、一一对应的关系。任何树或森林都唯一地对应到一棵二叉树；反过来，任何二叉树也都唯一地对应到一棵树或一个森林。

5_02 一般树转换成二叉树
把一般树转换成二叉树，可分为3个步骤：
(1) 连线：在所有兄相邻的弟结点之间加一条连线。
(2) 切线：对树中的每个结点，只保留他与第一个子女结点之间的连线，删除它与其它子女结点之间的连线。
(3) 旋转：以树及子树的根结点为轴心，将所有水平方向的连线顺时针旋转一定角度，使之结构层次分明。(也就是所有水平方向连线中右边的结点作为左边结点的右子女结点)

5_03 森林转换成二叉树
把森林转换成二叉树，可分为3个步骤：
(1) 连线：在每棵树的所有兄弟结点之间加一条连线，并将每棵树的根结点用水平线连接(与将一般树转换成二叉树相比，这是唯一增加的操作)。
(2) 切线：对树中的每个结点，只保留他与第一个子女结点之间的连线，删除它与其它子女结点之间的连线。
(3) 旋转：以树及子树的根结点为轴心，将所有水平方向的连线顺时针旋转一定角度，使之结构层次分明。(也就是所有水平方向连线中右边的结点作为左边结点的右子女结点)

5_04 二叉树还原为一般树
把二叉树还原成一般树，可分为3个步骤：
(1) 连线：如果某结点N是其父结点的左子女结点，则将该结点的右子女及沿着其右指针不断搜索到的右子孙，都分别与结点N的父结点用虚线连接。
(2) 切线：去掉原二叉树中每个结点与其右子女结点之间的连线，仅保留与左子女结点之间的连线。
(3) 整理：把虚线改为实线，按层次整理好。

5_05 二叉树还原为森林
把二叉树还原成森林，可分为2个步骤：
(1) 切线：先从根结点出发沿着其右指针不断遍历到的所有右子孙，将每个右子孙结点N与N的父结点的连线去掉，得到分离的二叉树。
(2) 还原：把分离后的每棵二叉树还原为一般树。所有的这些一般树就组成了森林。

5_06 树的动态“左子结点/右兄弟结点”二叉链表表示

5_07 树的先根、后根次序遍历
: 与二叉树的深度优先遍历有3种次序不同的是：树的深度优先遍历只有先根次序和后根次序，不方便按照中序法定义中根次序，因为一个根结点有多于两个子结点时无法明确给出根结点和这些子结点的次序。
先根次序遍历的递归定义为：
访问根结点；
按先根次序遍历第一棵子树；
按先根次序遍历其他子树。
后根次序遍历的递归定义为：
按先根次序遍历第一棵子树；
访问根结点；
按先根次序遍历其他子树。
(注意理解“后根”)
: 按先根次序遍历树，等价于按先序遍历对应的二叉树；按后根次序遍历树，等价于按中序遍历对应的二叉树。即：
< 树的先根次序遍历ó对应二叉树的先序遍历(ó表等价)
< 树的后根次序遍历ó对应二叉树的中序遍历

5_08 树的广度优先遍历
: 广度优先遍历也称为宽度优先遍历，或层次遍历。
: 广度优先遍历过程为：首先依次访问层次为0的结点；然后依次访问层次为1的结点，等等。

5_09 树的子结点表表示法
: 子结点(链)表表示法包含以下两部分：
< 用数组存储每个结点，每个结点包含3个域：结点值、父结点编号、子结点链表表头指针－顺序存储方式。
< 将每个结点的子结点按从左到右的顺序连接成一个单链表，并用它的表头指针域指向这个链表－链式存储方式。
: 优点：访问每个结点的所有子结点很方便。
: 缺点：访问每个结点的兄弟结点很难实现。
: 其他操作讨论：插入结点、删除结点、创建树、删除树、按各种方式遍历、合并两棵树等等。

5_10 树的父指针表示法
: 实现树的最简单方法是对每个结点只保存一个指针域parent，指向其父结点，这种实现方法称为父指针表示法。
: 父指针表示法在实现树的操作方面没有任何优势，但是它可以实现一种特殊的数据结构－并查集。

5_11 等价关系及等价类
: “同班同学”、“同属于一个集合”、“森林中两个顶点属于同一棵树”都是等价关系。
: 等价关系(equivalent relation)的三个条件(或称为性质)：
< 自反性：如X≡X，则X≡X；(假设用“X≡Y”表示“X与Y等价”)
< 对称性：如X≡Y，则Y≡X；
< 传递性：如X≡Y，且Y≡Z，则X≡Z。
: 如果X≡Y，则称X与Y是一个等价对(equivalence)。

5_12 并查集的概念及作用
< 判定两个顶点是否属于同一个等价类(或集合，或同一棵树)。
< 将两个等价类(或两个集合，或两棵树)合并。

: 一个等价关系R将集合A划分成为若干个子集合，这些子集合互不相交，且这些子集合的并集就是A。

5_13 并查集的三个重要运算
1) 查找(Find)：查找一个元素属于哪个集合。
2) 判断：判断两个元素是否属于同一个集合。往往包含在合并运算中。
3) 合并(Union)：合并两个集合。

5_14 用父指针表示法实现并查集的思路和方法
: 要判别每个结点属于哪棵树，只需要记录每个结点的父结点编号(不需要记录每个结点的其他信息，比如左子女、右兄弟等)。对于每棵树的根结点，由于它没有父结点，则可以用它所在的树中结点数目代替它的父结点编号(并取负值，假定结点的编号没有负值)。
: 定义parent[n]数组，parent[i]中存放的就是结点i所在的树中结点i父亲结点的序号。例如，如果parent[4] = 5，就是说4号结点的父亲是5号结点。
: 约定：如果结点i的父结点(即parent[i])是负数的话，表示结点i就是它所在树的根结点；并且用负的绝对值作为这棵树中所含结点个数。例如，如果parent[7] = -4，说明7号结点就是它所在树的根结点，这棵树有4个结点。
: 初始时，所有结点的parent[ ]值为-1，说明每个结点自成一棵树，且都是根结点。
: 对读入的每个等价对X≡Y，先判定结点X和Y是否属于同一个集合，如果是，则不管；如果不是，则合并结点X和结点Y所在的集合。(并查集的3种运算的实现在例3中讨论)
5_15 并查集：查找运算及优化方案的实现
5_16 并查集：合并运算及优化方案的实现
5_17 并查集应用

第6章 图结构
编号 知识点 类型 掌握程度 代码要求
6_01 图的基本概念 概念 理解
图是由顶点集合和顶点间关系集合(即边的集合或弧的集合)组成的数据结构，通常可以用G(V,E)来表示，其顶点集合和边的集合分别用V(G)和E(G)表示。V(G)中的元素称为顶点，用u、v等符号表示；顶点个数称为图的阶，通常用n表示。E(G)中的元素称为边，用e等符号表示；边的个数称为图的边数，通常用m表示。
顶点的度(degree)：一个顶点的度是与它相关联的边的条数，记作deg(u) 在有向图中，顶点的度等于该顶点的出度与入度之和。其中，顶点u的出度是以u为起始顶点的有向边(即从顶点u出发的有向边)的数目，记作od(u)；顶点u的入度是以u为终点的有向边(即进入到顶点u的有向边)的数目，记作id(u)。顶点u的度数：
deg(u) = od(u) + id(u)。
即在无向图和有向图中，所有顶点的度的总和，等于边的数目的两倍。这是因为，不管是有向图还是无向图，在统计所有顶点的度的总和时，每条边都统计了两次。
生成树：一个无向连通图的生成树是它的包含所有顶点的极小连通子图，这里所谓的极小就是边的数目极小。如果图中有n个顶点，则生成树有n-1条边。
在图G(V, E)中，若从顶点vi出发，沿着一些边经过一些顶点vp1, vp2, …, vpm，到达顶点vj，则称顶点序列(vi, vp1, vp2,…, vpm, vj)为从顶点vi到顶点vj的一条路径，其中(vi, vp1), (vp1, vp2), …, (vpm, vj)为图G中的边。如果G是有向图，则<vi, vp1>, <vp1, vp2>, …, <vpm, vj>为图中的有向边。
路径的长度：路径中边的数目通常称为路径的长度。
: 权值：某些图的边具有与它相关的数，称为权值。这些权值可以表示从一个顶点到另一个顶点的距离、花费的代价、所需的时间等。如果一个图，其所有边都具有权值，则称为网络。
: 根据网络中的边是否具有方向性，又可以分为有向网和无向网。网络可以用G(V, E)表示，其中边的集合E中每个元素包含3个分量：边的两个顶点和权值。

6_02 图的邻接矩阵 概念 理解
: 在邻接矩阵中，除了一个记录各个顶点信息的顶点数组外，还有一个表示各顶点之间关系的矩阵，称为邻接矩阵。

6_03 图的邻接表实现 算法 掌握原理 代码段
: 邻接表：把同一个顶点发出的边链接在同一个称为边链表的单链表中。(这种邻接表也称为出边表)
: 逆邻接表：也称为入边表，顶点i的边链表中链接的是所有进入该顶点的边。适合求顶点的入度。
以有向图为例介绍邻接表的实现方法。为了方便求解顶点的出度和入度，在实现时，把出边表和入边表同时包含在表示顶点的结构体中。

6_04 图的遍历 概念 理解
图的遍历(Graph Traversal)的含义：从已给图中的某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次(注意理解)。

6_05 图的深度优先搜索 算法 掌握原理
深度优先搜索(Depth First Search)：是一个递归过程，有回退过程，它的思想在很多题目当中要用到对图6.4.1(a)所示的无向连通图，采用DFS思想搜索的过程为：
(在图(a)中，箭头旁的数字跟下面的序号对应)
(1) 从顶点A出发，访问顶点序号最小的邻接顶点，即顶点B；
(2) 然后访问顶点B的一个未访问过的邻接顶点，即顶点C；
(3) 接着访问顶点C的一个未访问过的邻接顶点，即顶点G；
(4) 此时顶点G已经没有未访问过的邻接顶点了，所以回退到顶点C；
(5) 回退到顶点C后，顶点C也没有未访问过的邻接顶点了，所以继续回退到顶点B；
。6) 顶点B还有一个未访问过的邻接顶点，即顶点E，所以访问顶点E；
(7) 然后访问顶点E的一个未访问过的邻接顶点，即顶点F；
(8) 顶点F有两个未访问过的邻接顶点，选择顶点序号最小的，即顶点D，所以访问D；
(9) 此时顶点D已经没有未访问过的邻接顶点了，所以回退到顶点F；
(10) 顶点F还有一个未访问过的邻接顶点，即顶点H，所以访问顶点H；
(11) 然后访问顶点H的一个未访问过的邻接顶点，即顶点I；
(12) 此时顶点I已经没有未访问过的邻接顶点了，所以回退到顶点H；
(13) 回退到顶点H后，顶点H也没有未访问过的邻接顶点了，所以继续回退到顶点F；
(14) 回退到顶点F后，顶点F也没有未访问过的邻接顶点了，所以继续回退到顶点E；
(15) 回退到顶点E后，顶点E也没有未访问过的邻接顶点了，所以继续回退到顶点B；
(16) 回退到顶点B后，顶点B也没有未访问过的邻接顶点了，所以继续回退到顶点A；

6_06 图的广度优先搜索 算法 掌握原理
: 广度优先搜索(Breadth First Search) ：是一个分层的搜索过程，没有回退的情况，是非递归的。

6_07 图的最小生成树 概念 理解
: 生成树：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。
: 用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。
: 生成树是连通图的最小连通子图。所谓最小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。
: 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。
: 最小生成树：生成树各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。
: 构造最小生成树的准则：
: 必须只使用该网络中的边来构造最小生成树；
: 必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点；
: 不能使用产生回路的边。
: 构造最小生成树的方法：克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法。都得遵守以上准则。

6_08 Kruskal算法 算法 掌握原理 完整程序
Kruskal算法执行过程：
1) 将m条边存储在edges数组中，并按权值从小到大排序。
2) 依次检查每条边，如果该边的两个顶点不属于同一个集合，则选用该边、并将这两个集合合并；否则弃用这条边。

6_09 最短路径问题 概念 理解
: 最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。
: 求解算法：
< 权值为非负的单源最短路径问题(固定源点)－Dijkstra算法(迪克斯特拉算法,1959)；
< 权值为任意值的单源最短路径问题(固定源点) －Bellman-Ford算法(贝尔曼－福特算法)；
< Bellman-Ford算法的改进 － SPFA算法；
< 所有顶点之间的最短路径问题－Floyd-Warshall算法(弗洛伊德算法)；

6_10 Dijkstra算法 算法 掌握原理 完整程序
ü 为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。

第7章 内排序
编号 知识点 类型 掌握程度 代码要求
7_01 排序问题的基本概念 概念 理解
: 在计算机应用软件中经常需要对所管理的各种数据进行处理，排序往往是这些数据处理中需要用到的核心运算。
: 内排序：如果待排序的记录个数较少，整个排序过程中所有的记录都可以直接存放在内存中，这样的排序叫做内排序(internal sorting)。
: 外排序：如果待排序的记录数量太大，内存无法容纳所有的记录，因此排序过程中还需要访问外存，这样的排序叫做外排序(external sorting)。
: 由于讨论的是内排序，在大部分情况下本章都是考虑基于顺序存储的排序，即待排序的数据是存储在数组中。
: 记录(record)：参与排序的元素称为记录，记录是进行排序的基本单位。
: 序列(sequence)：所有待排序记录的集合称为序列。所谓排序就是将序列中的记录按照特定的顺序排列起来。

7_02 用系统函数实现排序 应用 掌握方法 完整程序
: 在实际编程时，可能不需要自己实现排序算法，直接调用系统函数实现排序即可。但这并不意味着本章介绍的排序算法原理、程序实现不需要掌握。
: 实现排序的系统函数主要有：qsort、sort函数
: qsort函数：
< 采用快速排序算法(7.4.1节)实现。
: sort函数：
< STL提供的算法，常常结合STL中的容器和迭代器使用。

7_03 插入法排序 算法 掌握原理 完整程序
: 逐个处理待排序的记录，每个新记录都要与前面那些已排好序的记录进行比较，然后插入到适当的位置。

7_04 冒泡法排序 算法 掌握原理 完整程序
5
4
2
0
4
5
2
0
4
2
5
0
4
2
0
5
4
2
0
2
4
0
2
0
4
2
0
0
2

冒泡法是不是一定要比较n-1趟？
不一定！比如前面的例2中，n=8，但实际上只需要进行5趟比较，后面2趟没有进行交换。也就是说，如果在某一趟比较过程中，没有发现 前一个数比后一个数大的情况，即没有进行交换数据，那么后面就不需要再进行比较了。
极端的情况，假设n个数已经是按从小到大的顺序排好了，那么实际上只需要进行一趟比较就可以得出结论了。

7_05 选择法排序 算法 掌握原理 完整程序
直接选择排序法也需要用一个二重循环来实现，同样可以带着以
下3个类似问题来理解其思想(有n个数，要求按照从小到大的顺序
排序)：
1) 要进行多少趟选择？—— 要进行n-1趟选择(第0趟，第1趟，…，第n-2趟)。因此外循环的循环变量i的取值是从0到n-1 (不取等号！)。
2) 在第i趟里怎么选？—— 第i趟要从a[i], a[i+1], ..., a[n-1]中选择最小的数，记为a[k]，i=0，1，2，...，n-2。首先假设a[i]就是最小的，然后对a[i+1], ..., a[n-1]每个数都判断一下是否比当前的最小值还要小。因此内循环的循环变量j的取值是从i+1到n-1。
3) 在第i趟里怎么交换？—— 每趟选择最终交换的是a[i]和a[k]。
4) 这3种排序算法虽然简单，但时间复杂度都比较大，虽然做了很多改进，但仍然没有太大成效(这些改进没有从本质上降低算法时间复杂度)，在平均和最坏情况下的时间复杂度均为O(n2)。
1) 说明：单纯地看算法复杂度O(n2)，其实复杂度并不高，很多有效算法的时间复杂度都是O(n2)；但排序问题不同，它的规模可以达到很大，比如10000个数，这时复杂度为O(n2)的算法的时间劣势就很明显了。
5) 直接插入和冒泡算法都有一个共同的缺点：只对相邻的两个记录进行比较和交换，因此一个记录只能一步步地向它应在的位置移动，效率低下。
6) 选择排序虽然不是比较和交换相邻记录，但是在选择第i小的记录时也是在剩下的记录中逐个地进行线性比较，它虽然比冒泡法在交换次数上有很大的改进，但比较次数仍没有降低，因此总体效率依旧很低。。

7_06 Shell排序法 算法 掌握原理 完整程序
< 先将序列转化为若干小序列，在这些小序列内进行插入排序；
< 逐渐扩大小序列的规模(即扩大小序列中记录的个数)，而减少小序列个数，使得待排序序列逐渐处于更有序的状态，有利于插入排序操作；
< 最后，所有序列都合并在原来的大序列中，这个大序列基本有序了(整个序列比较接近于正序状态)，然后再对整个序列进行扫尾直接插入排序，从而完成排序。
< 然后减少记录间的间距，从而将原始序列分成更少的子序列，分别进行插入排序；
……
< 重复下去，直到最后间距减少为1，然后对整个序列进行插入排序。
: 由于Shell排序按照不断缩小的增量来将原始序列分成若干个子序列，因此有时也称为缩小增量排序算法。

7_07 快速排序法 算法 掌握原理 完整程序
(1) 从待排序序列中选择一个记录k作为轴值(pivot)。
(2) 将剩余的记录分割成两个子序列L和R，L中包含所有小于或等于轴值k的记录，R中包含所有大于轴值k的记录。
(3) 将L中的所有记录放在k的左边，R中的所有记录放在k的右边；此时k左边的记录都小于或等于k，k右边的记录都大于它，因此k正好位于正确位置。
(4) 对子序列L和R进行快速排序，直到子序列中只含有0或1个记录。
具体实现时，(2)、(3)可同时实现，即在分割的过程就将所有
小于或等于轴值k的记录放到k左边，将大于它的记录放到右
边。分割是快速排序算法的关键。

7_08 归并排序法 算法 掌握原理 完整程序