数据结构复习整理

概论

逻辑结构

线性

非线性

线性表

逻辑结构

前驱、后继

存储结构

顺序：顺序表

链式：链表

链表

不带头结点

带头结点

栈与队列

栈

后进先出

应用实例：括号匹配，表达式求值

表达式求值

中缀表达式，用运算符优先级表

中缀表达式转后缀表达式：遇到数字直接输出，遇到运算符，先与栈顶运算符比较

若比栈顶运算符优先级高，则入栈，若优先级低，则栈顶运算符出栈

中缀表达式运算：遇到数字直接进数字栈，遇到运算符，先与运算符栈顶运算符比较

若比栈顶运算符优先级高，则入运算符栈，若优先级低，则运算符栈顶运算符出栈，并从数字运算符栈拿出相应数字计算

然后把新数压数字栈

后缀表达式求值：不管优先级，遇到运算符就拿出对应的数运算，然后再把新数压栈

栈和递归

应用：深度优先搜索

递归工作栈

将递归转化为非递归

队列

先进先出

假溢出问题：引入循环队列

循环队列

进队

1
2
3
4
if(队满)
    return false;
data[rear]=x;
rear=(rear+1)%maxSize;

出队

1
2
3
4
if(队空)
    return false;
x=data[front];
front=(front+1)%maxSize;

造成浪费一个空间，故判断队满

1
2
3
bool SeqQueue::IsFull(){ 
     return (rear+1) % maxSize == front;
};

循环队列用于解决假溢出问题

循环队列少用一个存储空间为了解决队列判满问题

队列应用

广度优先搜索：迷宫最短路径

数组，串和广义表

特殊矩阵

特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵

特殊矩阵的压缩

存储主要是针对阶数很高的特殊矩阵

为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储

对称矩阵的压缩

为节约存储，只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素

前者称为上三角矩阵，后者称为下三角矩阵

把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式

数组 B 共有 \(n+(n-1)+ \cdots +1 = n \cdot (n+1)/2\) 个元素

三对角矩阵的压缩

稀疏矩阵

概念

设矩阵 A 中有 s 个非零元素，若 s 远远小于矩阵元素的总数（即 \(s \ll m\cdot n\)），则称 A 为稀疏矩阵

稀疏矩阵的存储

稀疏矩阵的转置

广义表

广义表是 \(n ( n \ge 0 )\) 个表元素组成的有限序列，记作 \[ LS(a_1,a_2,a_3,\cdots,a_n) \] LS 是表名，\(a_i\) 是表元素，可以是表（称为子表），可以是数据元素（称为原子）

n为表的长度，\(n = 0\) 的广义表为空表

\(n > 0\)时，表的第一个表元素称为广义表的表头（head），除此之外，其它表元素组成的表称为广义表的表尾（tail）

树与二叉树

树基本概念

结点的度：结点拥有的子树棵数

树的度：各个节点度的最大值

分支节点（非终端节点）：除叶结点以外的节点

兄弟节点：同一父节点的子女

祖先节点：从根节点到该节点所经的所有节点

节点层次：根节点到该节点的层数

树的深度：距离根节点最远的节点的层数

树的高度：叶节点高度为1，非叶节点高度等于子女+1

森林：树的集合

二叉树

二叉树特点

每个结点最多有两个子女，分别称为该结点的左孩子和右孩子

二叉树中不存在度大于2的结点，并且二叉树的子树有左右子分，其子树的次序不能颠倒

二叉树性质

1、若二叉树结点的层次从 1 开始, 则在二叉树的第 i 层最多有 $ 2^{i-1} $ 个结点。( i≥1)

2、深度为 k 的二叉树最少有 k 个结点，最多有$ 2^{k-1} $个结点。( k≥1 )

3、对任何一棵二叉树，如果其叶结点有 \(n_0\) 个, 度为 2 的非叶结点有 \(n_2\) 个, 则有 \(n_0＝n_2+1\)

性质3证明：设总结点数为 \(n\) \[ \begin{align*} 树的边数 &= 节点数-1 \\ 2 \times n_2 &= n_0 + n_2 - 1 \\ n_0 &= n_2 + 1 \end{align*} \]

满二叉树

每层节点都是最大个数

设深度为k，共 \(2^{k}-1\)个节点，除叶子结点以外度都为2

完全二叉树

除最底层外，其它层都是满二叉树

设深度为k，除第k层外，其它层节点数都最大

完全二叉树性质

设深度为k，节点数为n，则 \(2^{k-1}-1<n\le 2^k-1\)

具有n个节点的完全二叉树 \((n\ge0)\) 深度为 \(\lceil{\log_2{(n+1)}\rceil}\) (向上取整)

若给完全二叉树编号，从根节点开始标1，依次往下：

\[ \begin{gather*} i=1, 则节点无双亲 \\ i>1, i的双亲为\lfloor i\div2 \rfloor \\ i的左子女为i\times2 \\ i的右子女为i\times2+1 \\ i为奇数，且i\ne1,左兄弟为i-1 \\ i为偶数，且i\ne{n},右兄弟为i+1 \\ \end{gather*} \]

二叉树的存储表示

数组存储

极端情况，仅有右子树的二叉树，浪费空间

链表存储

二叉链表

三叉链表

多一个指向双亲的指针

二叉树链表示例

二叉树遍历

递归遍历

设访问根结点记作 V

遍历根的左子树记作 L

遍历根的右子树记作 R

前序 （VLR）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PreOrder(int subroot)	//数组存储写法
    {
        int temp = subroot;

        if (subroot > this->num - 1)	
        {
            return;
        }
        if (this->lst[subroot] == 0)	//0没存值跳过
        {
            return;
        }
        cout << this->lst[subroot] << " ";

        subroot = temp * 2 + 1;		//左孩子
        PreOrder(subroot);

        subroot = temp * 2 + 2;		//右孩子
        PreOrder(subroot);

    }

中序 （LVR）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void InOrder(int subroot)	//数组存储写法
    {
        int temp = subroot;

        if (subroot > this->num - 1)
        {
            return;
        }

        subroot = temp * 2 + 1;
        InOrder(subroot);

        subroot = temp;
        if (this->lst[subroot] == 0)
        {
            return;
        }
        cout << this->lst[subroot] << " ";

        subroot = temp * 2 + 2;
        InOrder(subroot);

    }

后序（LRV）

1
2
3
4
5
6
7
8
9
10
void PostOrder(TreeNode* subroot)		//链表存储写法
    {
        if (subroot == NULL)
        {
            return;
        }
        PostOrder(subroot->lchild);
        PostOrder(subroot->rchild);
        cout << subroot->data << " ";
    }

层次遍历

利用队列，循环条件是队列非空，依次将出队元素的左右孩子节点加入队中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void LevelOrder()
    {
        lst.EnQueue(*this->Root);
        while (!lst.IsEmpty())
        {
            TreeNode temp;
            lst.DeQueue(temp);
            if (temp.lchild != NULL)
            {
                lst.EnQueue(*temp.lchild);
            }
            if (temp.rchild != NULL)
            {
                lst.EnQueue(*temp.rchild);
            }
        }
        lst.PrintData();
    }

非递归遍历

把前序中序后序改成非递归，自建一个栈存储信息

二叉树重建

前序：1, 2, 5, 3, 6, 7

中序：2, 5, 1, 6, 3, 7

后序：5, 2, 6, 7, 3, 1

层次：1, 2, 3, 5, 6, 7


先序遍历第一个是根节点，后序遍历最后一个是根节点

层次遍历第一个是根节点

中序遍历，根节点左边的在左子树上，右边的在右子树上


根据中序遍历和其他任意一种遍历可以重建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Build(int data, TreeNode*& subroot)    //建树一定要对原来指针进行修改，即传递指针的引用 ********
    {
        if (subroot == NULL)		//插入节点
        {
            TreeNode* newNode = new TreeNode(data);
            subroot = newNode;
        }
        if (FindNum(data) < FindNum(subroot->data))	
        {
            Build(data, subroot->lchild);
        }
        if (FindNum(data) > FindNum(subroot->data))
        {
            Build(data, subroot->rchild);
        }
    }
void BuildTree()
    {
        for (int i = 1; i < n; i++)
        {
            Build(PreOrder[i], this->Root);
        }
    }

线索二叉树

此树中序遍历：B, D, A, E, C

此树中有5个结点，10个链域（其中4个是非空，6个为空）

利用N+1个空的链域存放结点直接前驱和直接后继的信息

线索二叉树核心思想

如果结点中leftChild指向空，则令leftChild指向当前结点的直接前驱；

如果结点中rightChild指向空，则令rightChild指向当前结点的直接后继

中序线索二叉树例

B左孩子空，没有直接前驱，指空

D左孩子空，指向B

D右孩子空，指向A

E左孩子空，指向A

E右孩子空，指向C

C右孩子空，没有直接后继，指空


表示线索二叉树

增加两个tag

ltag (或rtag) = 0，表示相应指针指示左子女（或右子女结点）

ltag (或rtag) = 1， 表示相应指针为前驱（或后继）线索

中序线索二叉树遍历

中序序列中第一个结点为二叉树最左边，左孩子为空的结点

查找第一个节点：从根结点开始，如果结点中ltag为0，移动到当前结点左孩子；此过程一直持续，直到结点的ltag为1

中序序列中最后一个结点为二叉树最右边，右孩子为空的结点

查最后一个节点：从根结点开始，如果结点中rtag为0，移动到当前结点右孩子；此过程一直持续，直到结点的rtag为1

树的存储表示

广义表表示

A(B(E, F), C, D(G))

父指针表示

子女链表表示

子女兄弟表示（树的二叉树表示）

节点构造

例

广义表转子女兄弟表示：

森林

森林和二叉树的转换

先将所有树用子女兄弟表示法化成二叉树

再将树连一起

树与森林的遍历

树的遍历

深度优先

先根遍历

树的先根遍历结果与其对应二叉树表示的前序遍历结果相同

可借助二叉树表示的前序遍历实现

后根遍历

树的后根遍历结果与其对应二叉树表示的中序遍历结果相同

可借助二叉树表示的中序遍历实现

广度优先

借助队列

森林的遍历

先根遍历、后根遍历、层次遍历

堆

堆基本概念

最小堆

\[ \begin{gather*} K_i\le K_{2i+1} \\ K_i\le K_{2i+2} \end{gather*} \]

最大堆

\[ \begin{gather*} K_i\ge K_{2i+1}\\ K_i\ge K_{2i+2} \end{gather*} \]

堆的创建

堆的特点

树形结构

局部有序，堆不唯一

哈夫曼树

路径

从树中一个结点到另一个结点之间的分支构成该两结点之间的路径

路径长度

路径上的分支条数

树的路径长度

从树的根结点到每一个结点的路径长度之和

最小路径长度

完全二叉树和理想平衡二叉树满足要求

扩充二叉树

叶子结点带权的树

带权叶节点叫外结点，其余叫内节点

外结点的带权路径长度为T的根到该结点的路径长度与该结点上权值的乘积

WPL: 带权路径长度 \[ \begin{gather*} WPL = \sum_{i=1}^{n}w_i\cdot l_i\\ w_i: 外结点i带的权值\\ l_i: 外结点i到根节点的路径长度 \end{gather*} \] WPL最小的扩充二叉树为最优二叉树

Huffman树

带权路径长度最小的二叉树即是Huffman树，Huffman树中权值大的外结点离根结点最近

Huffman树的构造

重复以下步骤, 直到 F 中仅剩一棵树为止：

在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树

置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和

在 F 中删去这两棵二叉树

把新的二叉树加入 F

Huffman树的应用：Huffman编码

等长编码

所有编码都等长，表示 n 个不同的字符需要 \(\log_2n\)位

字符的使用频率相等

ASCII码

不等长编码

经常出现的字符的编码较短，不常出现的字符编码较长

前缀编码

任何一个字符的编码都不是另外一个字符编码的前缀

这种前缀特性保证了代码串被反编码时，不会有多种可能

如图是一种前缀编码，对于 “000110”，可以翻译出唯一的字符串“EEEL”

Huffman编码过程

首先，按照“权”(例如频率)将字符排为一列

接着，拿走前两个字符(“权”最小的两个字符)

再将它们标记为Huffman树的树叶，将这两个树叶标为一个分支结点的两个孩子，而该结点的权即为两树叶的权之和

将所得“权”放回序列，使“权”的顺序保持

重复上述步骤直至序列处理完毕

哈希表

概念

冲突：不同关键字，用同一个哈希函数得到相同哈希地址

同义词：发生冲突的关键字

哈希函数构造方法

  1. 直接定址法

  2. 除留余数法

  3. 数字分析法

  4. 平方取中法

  5. 折叠法

  6. 随机数法

冲突处理

（1）开放定址法（开地址法）：线性探测、二次探测、伪随机探测

（2）链地址法（拉链法）

（3）再哈希法（双哈希函数法）

（4）建立一个公共溢出区

哈希表查找分析

哈希查找的速度是否为真正的O(1) ？

不是

由于冲突的产生，使得哈希表的查找过程仍然要进行比较，用平均查找长度ASL和装填因子α来衡量

装填因子α = 表中填入的记录数 / 哈希表的长度

α 越小，发生冲突的可能性越小

反之，发生冲突的可能性越大

搜索结构

搜索的概念

通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成

在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象，称为关键码。

使用基于关键码的搜索，搜索结果应是唯一的。

静态搜索结构

静态搜索表

顺序搜索

二分搜索

二叉搜索树（二叉排序树，二叉查找树）

性质

每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同

左子树（如果非空）上所有结点的关键码都小于根结点的关键码

右子树（如果非空）上所有结点的关键码都大于根结点的关键码

左子树和右子树也是二叉搜索树

如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树

插入

插入元素前要先检查元素在树中是否存在

删除

删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可

被删结点右子树为空，可以拿它的左子女结点顶替它的位置，再释放它

被删结点左子树为空，可以拿它的右子女结点顶替它的位置，再释放它

被删结点左、右子树都不为空，可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中

AVL树

性质

一棵 AVL 树或者是空树，或者是具有下列性质的二叉搜索树

它的左子树和右子树都是 AVL 树，且左子树和右子树的高度之差的绝对值不超过1

h为深度，求树最少有多少结点，可以写为递归式

\(N_h=N_{h-1}+N_{h-2}+1\)

高度为h的平衡二叉树，节点个数为高度为h-1的平衡二叉树节点个数+高度为h-2的平衡二叉树节点个数+1

平衡因子

每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差，这个数字即为结点的平衡因子bf

AVL树任一结点平衡因子只能取 -1, 0, 1

如果一个结点的平衡因子的绝对值大于1，则这棵二叉搜索树就失去了平衡，不再是AVL树

如果一棵有 n 个结点的二叉搜索树是高度平衡的，其高度可保持在\(O(\log_2n)\)，平均搜索长度也可保持在\(O(\log_2n)\)

平衡化旋转

书上讲太复杂了，有个视频可以很好理解 平衡二叉树的调整

注意要顺着插入的新节点路径往上找，找与不平衡节点最近的三个节点，调整即可

LL

RR

RL

LR

元素删除

注意树的调整

图

概念

有向图

\(Path (x, y)\)表示从 x 到 y 的一条单向通路, 它是有方向的

\(Graph＝( V, E )\)

其中\(V = \{ x | x \in 某个数据对象\}\) 是顶点的有穷非空集合

\(E = \{<x, y> | x, y \in V \&\& Path (x, y) \}\)是顶点之间关系的有穷集合，也叫做边(edge)集合

无向图

\(Graph＝( V, E )\)

其中\(V = \{ x | x \in 某个数据对象\}\) 是顶点的有穷非空集合

\(E = \{<x, y> | x, y \in V \}\)是顶点之间关系的有穷集合，也叫做边(edge)集合

完全图

有 \(n\) 个顶点的无向图有 $n(n-1)/2 $条边, 则此图为完全无向图

有 \(n\) 个顶点的有向图有$n(n-1) $条边, 则此图为完全有向图

完全图中边数达到最大

带权图

边带权

子图

顶点的度

一个顶点v的度是与它相关联的边的条数。记作TD(v)

在有向图中, 顶点的度等于该顶点的入度与出度之和

其中，顶点v的入度是以v为终点的有向边的条数，记作indeg(v)

顶点v的出度是以v为始点的有向边的条数, 记作outdeg(v)

路径

在图 \(G＝(V, E)\) 中, 若从顶点 \(v_i\) 出发, 沿一些边经过一些顶点 \(v_{p1}, v_{p2}, …, v_{pm}\)，到达顶点\(v_j\)，则称顶点序列 $ (v_i，v_{p1}，v_{p2} …v_{pm}， v_j) $ 为从顶点\(v_i\) 到顶点 \(v_j\) 的路径。它经过的边\((v_i, v_{p1})、(v_{p1}, v_{p2})、...、(v_{pm}, v_j)\) 应是属于\(E\)的边。

简单路径

路径上各顶点不重复

回路

起点与终点重合

连通图和连通分量

在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的

如果图中任意一对顶点都是连通的, 则称此图是连通图

非连通图的极大连通子图叫做连通分量

强连通图和强连通分量

在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图

非强连通图的极大强连通子图叫做强连通分量

生成树

一个连通图的生成树是其极小连通子图，在 n 个顶点的情形下，有 n-1 条边

图的存储结构

邻接矩阵

设图$ A = (V, E) $是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 \(A.edge[n][n]\)

无向图的邻接矩阵是对称的

有向图的邻接矩阵可能是不对称的

在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度

在无向图中, 统计第 i 行 (列) 1 的个数可得顶点 i 的度

邻接表

无向图

统计某顶点对应边链表中结点个数，可得该顶点的度

某条边\((v_i, v_j)\)在邻接表中有两个边结点，分别在第 i 个顶点和第 j 个顶点对应的边链表中

有向图

带权图

邻接矩阵和邻接表

图的遍历

为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]

深度优先搜索

广度优先搜索

最短路

边上权值非负情形的单源最短路径问题

​ — Dijkstra算法

边上权值为任意值的单源最短路径问题

​ — Bellman和Ford算法（了解即可）

所有顶点之间的最短路径

​ — Floyd算法（了解即可）

Dijkstra算法：优先队列（也可排序），根节点到各节点最短路径数组（每次更新），标记数组

从根节点出发，更新根节点到各点最短路径数组

选取路径数组中最短的路径，以及节点O，通过节点O更新最短路径数组（新的最短路径为节点O到对应节点的路径+根节点到节点O的路径），跟原最短路径数组对比，若更小，则更新

循环重复该过程，直到队列空

最小生成树

图 G 的生成树是一棵包含 G 的所有顶点的树，树上所有权值总和表示代价

那么在 G 的所有的生成树中代价最小的生成树称为图 G 的 最小生成树(简称 MST)

最小生成树算法

Prime算法

从起点出发，选择与起点距离最短的点（权最小）加入生成树顶点集合U中

每次找最短路：条件是起点在U中，终点不在U中（Debug的终点）

直到所有点加入U中为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
void Prim()
		{
			cout << "Prim:" << endl;
			int** mat = new int*[n];
			for (int i = 0; i < n; i++)
			{
				mat[i] = new int[n];
			}
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					mat[i][j] = 0;
				}
			}								//初始化二维数组
		
			int num = 0;
			int MinEdge = defaultsize;
			int MinStart = 0;
			int MinFinal = 0;
			MyQueue que;
			EdgeNode tmp(0, 0, 0);
			flag[0] = 1;

			while (num != n)
			{
				PrintMap(mat);
				cout << endl;
				for (int i = 0; i < n; i++)				//在出队节点的终点里寻找边，最开始为0
				{
					if (Matrix[MinFinal][i] == 0)		//边长为0跳过
					{
						continue;
					}
					if (flag[i] == 1)
					{
						continue;
					}
					EdgeNode temp(Matrix[MinFinal][i], MinFinal, i);
					que.EnQueue(temp);					//边长不为0入队
				}
				que.Sort();							    //给队列排序，充当优先队列作用
				//que.Print();
				while (num != n)						//↓↓↓↓↓↓↓↓↓极其重要↓↓↓↓↓↓↓↓↓↓↓↓
				{
					que.DeQueue(tmp);					//出队，此时要保证终点不在集合里，即flag为0，debug的终点
					if (que.isEmpty())					//队空退出
					{
						break;
					}
					if (flag[tmp.final] == 1)
					{
						continue;
					}

					break;
				}
				MinFinal = tmp.final;
				MinStart = tmp.start;
				MinEdge = tmp.length;
				mat[MinStart][MinFinal] = MinEdge;
				mat[MinFinal][MinStart] = MinEdge;		//无向图存2次
				flag[MinFinal] = 1;						//更新flag
				num++;
			}

		}

Kruskal算法

现将所有边按从小到大排序，依次选择最小的构成树，条件是属于不同连通分量，直至所有边全加入树

用并查集判断同一条边关联的两个顶点是否属于同一连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
bool isConnected(int x, int y)		//并查集判断是否属于同一连通分量
		{
			int i = x;
			while (flag[i] != i)	//查出i号的Boss是谁
			{
				i = flag[i];
			}
			int j = y;
			while (flag[j] != j)	//查出j号的Boss是谁
			{
				j = flag[j];
			}
			return i == j;			//i的Boss == j的Boss，则同一连通分量
		}

		int getBoss(int x)		//与上面相同的函数
		{
			while (flag[x] != x)
			{
				x = flag[x];
			}
			return x;
		}

		void Kruskal()
		{
			cout << "Kruskal:" << endl;
			int** mat = new int* [n];
			for (int i = 0; i < n; i++)
			{
				mat[i] = new int[n];
			}
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					mat[i][j] = 0;
				}
			}								//初始化二维数组

			for (int i = 0; i < n; i++)
			{
				flag[i] = i;				//用于并查集的数组
			}

			EdgeNode lst[defaultsize];
			int Iterator = 0;
			for (int i = 0; i < n; i++)
			{
				for (int j = i; j < n; j++)	//只考虑其中一个边
				{
					if (Matrix[i][j] == 0)
					{
						continue;
					}
					EdgeNode temp(Matrix[i][j], i, j);
					lst[Iterator] = temp;
					Iterator++;

				}
			}								//生成lst

			for (int i = 0; i < Iterator-1; i++)
			{
				for (int j = 0; j < Iterator-i-1; j++)
				{
					if (lst[j].length > lst[j + 1].length)
					{
						EdgeNode temp = lst[j];
						lst[j] = lst[j + 1];
						lst[j + 1] = temp;
 					}
				}
			}								//lst排序

			int num = 0;
			int it = 0;
			while (num != n)
			{
				PrintMap(mat);							//打印矩阵
				cout << endl;
				num++;
				
				while (num != n)
				{
					int len = lst[it].length;
					int start = lst[it].start;
					int final = lst[it].final;
					if (!isConnected(start, final))		//如果lst中最小边起点终点不相连
					{
						mat[start][final] = len;
						mat[final][start] = len;		//输出矩阵更新
						flag[getBoss(final)] = start;	//更新flag，终点的顶点改为起点
						it++;
						break;
					}
					else								//如果lst中最小边起点终点相连，跳过
					{
						it++;
						continue;
					}
				}	
			}
		}

用边表示活动的网络（AOV网络）

AOV网络概念

可以用有向图表示一个工程

用顶点表示活动，用有向边<Vi, Vj>表示活动Vi 必须先于活动Vj 进行

这种有向图叫做顶点表示活动的AOV网络 (Activity On Vertices)

在AOV网络中不能出现有向回路, 即有向环

如果出现了有向环，则意味着某项活动应以自己作为先决条件

对给定的AOV网络，必须先判断它是否存在有向环

检测有向环：拓扑排序

如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中, 则该网络中必定不会出现有向环

拓扑序列不唯一

拓扑排序实现

在AOV网络中选一个没有直接前驱的顶点（单独一个节点也算没有前驱，如下图C3）, 并输出

从图中删去该顶点, 同时删去所有它发出的有向边

重复以上步骤，直至全部顶点均已输出，拓扑有序序列形成，拓扑排序完成

或图中还有未输出的顶点, 但已跳出处理循环，说明图中还剩下一些顶点, 它们都有直接前驱，这时网络中必存在有向环

用顶点表示活动的网络（AOE网络）

AOE网络概念

在无有向环的带权有向图中

用有向边表示一个工程中的活动 (Activity)

用边上权值表示活动持续时间 (Duration)

用顶点表示事件 (Event)

则这样的有向图叫做用边表示活动的网络, 简称 AOE ( Activity On Edges ) 网络

完成整个工程所需的时间取决于从源点到汇点的最长路径长度, 即在这条路径上所有活动的持续时间之和

这条路径长度最长的路径就叫做关键路径(Critical Path)

要找出关键路径，必须找出关键活动, 即不按期完成就会影响整个工程完成的活动

关键路径上的所有活动都是关键活动，因此, 只要找到了关键活动, 就可以找到关键路径

与关键活动有关的量

分清楚活动 $ a_k $ 和事件 \(V_i\)

活动 $a_k $ 是箭头，事件 \(V_i\) 是节点

事件 \(V_i\) 的最早可能开始时间 \(V_e(i)\) ，即从源点 \(V_0\) 到顶点 \(V_i\) 的最长路径长度

事件\(V_i\) 的最迟允许开始时间 \(V_l(i)\) 是在保证汇点 \(V_{n-1}\) 在 \(V_e(n-1)\) 时刻完成的前提下，事件\(V_i\) 允许的最迟开始时间

活动 \(a_k\) 的最早可能开始时间 \(e[k]\)，设活动\(a_k\) 在边\(<V_i, V_j>\)上，\(e[k] = V_e(i)\)

活动 \(a_k\) 的最迟允许开始时间 \(l[k]\) 是在不会引起时间延误的前提下, 该活动允许的最迟开始时间，\(l[k] = V_l(j)-dur(<i, j>)\)

时间余量 \(l[k]-e[k]\) 表示活动\(a_k\)的松弛时间，\(l[k] = e[k]\)表示活动 \(a_k\) 是没有时间余量的关键活动

为找出关键活动, 需要求各个活动的 \(e[k]\) 与 \(l[k]\)，以判别是否 \(l[k] == e[k]\)

计算

这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行

\(e[k] = V_e(i)\)（\(a_k\)在边\(<V_i, V_j>\)上）

\(l[k] = V_l(j)-dur(<i, j>)\)（\(a_k\)在边\(<V_i, V_j>\)上，即指向节点的\(V_l - a_k\)）

这个例子不明显，看看书上的例子

如上图

\[ \begin{align*} l(6)&=V_l(5)-a_6\\ &=10-2\\ &=8 \end{align*} \]

排序

概念

排序算法稳定性

如果在元素序列中有两个元素r[i]和r[j], 它们的排序码 k[i] == k[j] , 且在排序之前, 元素r[i]排在r[j]前面

如果在排序之后, 元素r[i]仍在元素r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的

内排序与外排序

内排序是指在排序期间数据元素全部存放在内存的排序

外排序是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序

插入排序

基本思想

每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上, 直到元素全部插入为止

直接插入排序

折半插入排序

希尔排序

空间复杂度为\(O(1)\)

交换排序

基本思想

两两比较待排序元素的排序码，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之，直到所有元素都排好序为止

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BubbleSort(int a[],int n)
{
	int i,j;
	for(i=0;i<n-1;i++)
	{
		for(j=0;j<n-i-1;j++)
		{
			if(a[j]>a[j+1])
			{
				Swap(&a[j],&a[j+1]);
			}
		}
	}
}

快速排序

快排是递归的

选择排序

基本思想

每一趟 (例如第 i 趟, i = 0, 1, …, n-2) 在后面 n-i 个待排序元素中选出排序码最小的元素，作为有序元素序列的第 i 个元素

待到第 n-2 趟完，待排序元素只剩下1个, 就不用再选了

直接选择排序

堆排序

归并排序

基本思想

将两个或两个以上的有序表合并成一个新的有序表

基数排序

基本思想

基数排序是采用“分配”与“收集”的办法，用对多排序码进行排序的思想，实现对单排序码进行排序的方法

最高位优先(MSD)

先根据最高位排序码 \(K^1\)排序, 得到若干元素组, 元素组中各元素都有相同排序码 \(K^1\)

再分别对每组中元素根据排序码 \(K^2\) 进行排序, 按 \(K^2\) 值的不同, 再分成若干个更小的子组, 每个子组中的元素具有相同的 \(K^1\)和 \(K^2\)值

依此重复, 直到对排序码 \(K^d\)完成排序为止

最后, 把所有子组中的元素依次连接起来，就得到一个有序的元素序列

最低位优先(LSD)

首先依据最低位排序码 \(K^d\)对所有元素进行一趟排序

再依据次低位排序码 \(K^{d-1}\)对上一趟排序的结果再排序

依次重复，直到依据排序码 \(K^1\)最后一趟排序完成，就可以得到一个有序的序列

使用这种排序方法对每一个排序码进行排序时，不需要再分组，而是整个元素组都参加排序

排序对比

考后总结

哈希表竟然出大题了，这下嘻哈了

编程题出的是链表和二叉搜索树，还是比较容易实现的

填空题更是重量级，考高中的排列组合就不说了，竟然考手算递归，阿克曼函数归(3,3)，问题是还有人归出来了，太哈人了

不过考Ackermann(3,3)应该就是看你能不能即时放弃吧，毕竟这玩意归个(4,3)能把计算机递归瘸了




参考资料

数据结构课程PPT

AVL树调整