顺序表

矩阵的压缩存储，对称矩阵，三对角，上下三角矩阵

对称矩阵位置

A[i][j]

• i(i-1)/2 + j - 1 (i>=j 下三角区)
• j(j-1)/2 + i - 1 (i<j 上三角区)
• max(i,j) * (max(i,j) + 1)/2 + min(i,j) (行列通用)

  上下三角位置

  A[i][j]

• 下三角
  • i(i-1)/2 + j - 1 (i>=j)
  • n(1+n)/2 (i<j)
• 上三角
  • (2n-i+2)(i-1)/2 + (j-i) (i>=j)
  • n(1+n)/2 (i<j)

三对角

• i = (k+2)/3 (向下取整) 或 (k+1)/3+1 (向上取整)
• j = k - 2i + 3 (若i从0开始, k - 2i + 2)
• k = 2i + j - 3 (若i从0开始, 2i + j - 2)

链表

常用C库函数

• isdigit 是否为数字
• isalpha 是否为字母

队列、栈

循环队列

• 判空: Q.front == Q.rear
• 判断: Q.front == (Q.rear + 1) % MaxSize
• 队列元素个数: (Q.rear - Q.front + MaxSize) % MaxSize)
• 队首指针: rear = (rear + 1) % MaxSize
• 队头指针: front = (front + 1) % MaxSize

栈的计算公式

• 出栈序列方式数量：n个元素进栈，共有C(2n,n)/(n+1)种方式

前、中、后缀表达式

• 前缀

求前缀表达式：- * + 3 4 5 6的值：
  1. 从右至左扫描，将6、5、4、3压入堆栈；
  2. 遇到 + 运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算 3+4 的值，得7，再将7入栈；
  3. 接下来是 * 运算符，因此弹出7和5，计算 7*5=35 ，将35入栈。
  4. 最后是 - 运算符，计算 35-6 的值，即29，得最终结果29.

• 中缀（正常表达）
• 后缀

  举例： 求 (3+4)*5-6 的后缀表达式 （3 4 + 5 * 6 -）
  1. 从左至右扫描，将3和4入栈；
  2. 遇到运算符 + ，因此弹出4和3，计算 3+4 的值，再将7入栈；
  3. 将5入栈；
  4. 接下来是 * 运算符，因此弹出5和7，计算出 7*5=35，将35入栈；
  5. 将6入栈；
  6. 最后是 - 运算符，计算 35-6 (value = top->link - top) 的值，即29，由此得出最终结果。

  中缀表达式转后缀表达式

  1. 初始化两个栈：运算符栈s1和储存中间结果栈s2；
  2. 从左至右扫描中缀表达式；
  3. 遇到操作数时，将其压入s2；
  4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
  （1）如果s1为空，或栈顶运算符为左括号“（” ,则直接将此运算符入栈；
  （2）否则，若优先级比栈顶运算符高，也将运算符压入是s1；
  （3）否则，将s1栈顶的运算符弹出并压入到s2中，再次转到4.1步骤与s1中新的栈顶运算符相比较；
  5. 遇到括号时：
  （1）如果时左括号“（” ，则直接压入s1；
  （2）如果是右括号“）” ，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃;
  6. 重复步骤2至5，直到表达式的最右边；
  7. 将s1中剩余元素依次弹出并压入s2;
  8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。

  广义表

  注意广义表中的head、tail两个概念，以及深度、长度的概念；

  对于L = (x0,x1,…,xn), head(L) = x0，tail(L) = (x1,x2,…,xn)

区分广义表中的纯表、再入表、循环表（深度为∞）等概念

• 纯表：任何元素（原子/子表）只能出现1次（类似正常的树结构）
• 再入表：表中元素可以重复出现（类似树结构中兄弟结点可以连线）
• 循环表：表中有回路，深度为无穷大

线性表 <= 纯表（树）<= 再入表（兄弟结点之间有连线） <= 图

广义表的画法

• 有序树形: 点 -> 点
• 链式存储:
  • 原子节点 [ 0, 节点值, hp指针 ]
  • 连接节点 [ 2, hp指针(当前表的原子或子表), tp指针(下一个原子或子表) ]
  • 子表节点 [ 1, 节点值, ^ ]

串

BF算法

• 匹配失败：
  • i = i - j + 2 （回溯）
  • j = 1 （从头开始）
• Index(S, T, pos)
  • 将主串的第pos个字符和模式串的第一个字符比较
  • 若相等，继续逐个比较后续字符
  • 若不等，从主串的下一字符起，重新与模式串的第一个字符比
• 若n为主串长度，m为子串长度，最坏情况是
  • 总比较次数为：(n - m) * m + m
  • 若 M << n，则算法复杂度 O(n * m)

KMP算法

• next[j] =
  • max{k | 1 < k < j, 且 "P1...Pk-1"(从头开始的k-1个元素) = "Pj-k+1 ... Pj-1"(j前面k-1个元素)}
• 主串S的指针i不必回溯，算法复杂度O(n + m)`。

树、二叉树

基本形态（五种）

• 空二叉树
• 只有一个根结点的二叉树
• 只有左子树
• 只有右子树
• 完全二叉树

性质求结点数

1. 树的节点数 = 所有节点的度数 + 1
   • 度数之和 = 分支数
   • 分支数 = n-1
   • n = 度数之和 + 1
   • n = n0 + n1 + n2 + ...
   • n = 1 + Σ (i * ni)
2. 度为m的树中第i层上至多有m^(i - 1)个结点(i >= 1)
3. 高度为h的m叉树至多有(m^h - 1)/(m - 1)个结点
4. 具有n个结点的m叉树的最小高度为logm(n(m-1) + 1) 向上取整
5. 非空二叉树上叶子节点等于双分支节点数 + 1
6. n个节点可以构造C(2*n-2,n-1)/(n)颗不同形状的树，C(2*n,n)/(n+1)颗不同形状的二叉树（如n=6,C(12,6)/7 = (121110987)/(654321) * 7 = 132)
7. 对于一棵具有n个结点的树,该树中所有结点的度数之和n-1

二叉树重点性质

1. 二叉树的结点个数
   • n = n0 + n1 + n2
   • n = 1 + n1 1 + n2 2
   • n0 = n2 + 1
2. 完全二叉树中 度为1的节点个数最多为1个，即n1 = 1

树转二叉树

左子女-右兄弟

1. 在兄弟节点之间加一条线
2. 对每个节点，只保留它与第一个还在的连线，而与其他孩子的连线全部抹掉
3. 以树根为轴心，顺时针旋转45度

堆

• 顺序存储中，一个元素的下标为i，则它的左子女元素的下标为2i + 1，右子女的下标为2i + 2

哈夫曼树

WPL 带权路径长度

WPL = Σ(各个节点) 层数 * 结点值

HT数组

• HT 初态

• HT 终态

注意问题

删除操作

delete x;
x = NULL;

查找

ASL 平均搜索长度

• 概率不相同情况：ASL = ∑ C(i) * P(i) (C为依次同有关元素比较的总次数,P为搜索第i元素的概率)

• 概率相同情况下：ASL = (∑ i) / n = (n + 1) / 2

  折半查找

• 对于长度为n的有序顺序表，采用折半搜索，则对所有元素的搜索长度中最大的为log2(n+1)[向上取整] 或 log2n + 1[向下取整]。

  AVL树

  平衡因子

  左子树和右子树的高度之差绝对值不超过1

• -1 ： 表示右子树比左子树高

• 1 : 表示左子树比右子树高

• 0 ： 表示左子树和右子树等高

• 若平衡二叉树的高度为n，且所有非叶节点的平衡因子均为1，则该平衡二叉树的节点总数

  • F(n) = 1 + F(n - 1) + F(n - 2)

平衡旋转

• 左旋[只有左孩子才能右上旋] (f 是爹，p 为左孩子，gf为f他爹)

  f->lchild = p->rchild;
  p->rchild = f;
  gf->lchild/rchild = p;

• 右旋[只有右孩子才能左上旋] (f 是爹，p 为右孩子，gf为f他爹)

  f->rchild = p->lchild;
  p->lchild = f;
  gf->lchild/rchild = p;

调整规律

• LL
  • 调整：A的左孩子结点右上旋
• RR
  • 调整：A的右孩子结点左上旋
• LR
  • 调整：A的左孩子的右孩子 先左上旋再右上旋
• RL
  • 调整：A的右孩子的左孩子 先右上旋再左上旋

二叉排序树

删除

• 直接后继（教材方法）：找到右子树的最小（左）结点替换当前删除元素
• 直接前继：找到左子树的最大（右）结点替换当前删除元素

B树

B树 - m阶查找树 性质

• B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称B树的阶，通常用m表示。
• 策略：
  • 树中每个节点至多有m棵子树，即至多含有m-1个关键字
  • 若根节点不是终端节点，则至少有两棵子树
  • m叉查找树中，规定除了根节点外，任何结点至少有(m/2)[向上取整]个分叉，即至少含有(m/2)[向上取整] - 1个关键字
  • m叉查找树中，规定对任何一个结点，其所有子树的高度都要相同。
• 核心特性：
  1. 根节点的子树数∈[2 , m]，关键字数∈[1 , m-1]。其他结点数的子树数∈[[m/2], m]; 关键字数∈[[m/2]-1, m-1] （尽可能“满”）
  2. 对任一结点，其所有子树高度都相同 （尽可能“平衡”）
  3. 关键字的值：子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < ... (类比二叉查找树 左 < 中 < 右)

含n个关键字的m阶B树，最大、最小高度：

• 最小高度：让每个节点尽可能的满，有m-1个关键字，m个分叉，则有n<=(m-1)(1+m+m^2+m^3+...+m^h-1) = m^h - 1，因此h>=logm(n+1)
• 最大高度：让各层的分叉尽可能的少，即根节点只有2个分叉，其他结点只有(m/2)[向上取整]个分叉，各层结点至少有：第一层 1、第二层 2、第三层 2(m/2)[向上取整] ... 第h层 2(m/2)^(h-2)[向上取整]
  • 第h+1层共有叶子节点(失败结点) 2(m/2)^(h-1)[向上取整]
  • n个关键字的B树必有n+1个叶子结点，则 n + 1 >= 2((m/2)^(h-1))[向上取整]，即h <= log[m/2](((n+1)/2)+1)

含n个关键字的m叉B树，最大、最小高度：

• 最大高度：让每个结点包含的关键字、分叉尽可能的少。记k=(m/2)[向上取整]

h层的m阶B树至少包含关键字总数 1+2(k-1)(k^0+k^1+k^2+...+k^h-2) = 1+2(k^(h-1) - 1)

若关键字总数少于这个值，则高度一定小于h，因此 n >= 1+2(k^(h-1) - 1)

得 h <= logk((n+1)/2) +1 = log[m/2]((n+1)/2) + 1

B树的插入

• 核心要求
  • 除根节点外，结点关键字个数(m/2)[向上取整] - 1 <= n <= m - 1
  • 子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < ...
• 新元素一定是插入到最底层“终端节点”，用“查找”来确定插入位置
• 在插入key后，若导致原结点关键字数超过上限，则从中间位置((m/2)[向上取整])将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置((m/2)[向上取整])的结点插入原结点的父结点
• 若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根节点为止，进而导致B树高度增1。

B树的删除

非终端节点的删除

• 对非终端节点关键字的删除，必然可以转化为对终端节点的删除操作

  • 直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
  • 直接后继：当前关键字右侧指针所指子树中“最左下”的元素

    终端节点的删除

• 若被删除关键字在终端节点，则直接删除该关键字（要注意节点关键字个数是否低于下限(m/2)[向上取整] -1）

• 若被删除关键字所在节点删除前的关键字个数低于下限

  • 兄弟够借，且与节点右（或左）兄弟节点的关键字个数还很宽裕，则需要调整该节点、右（或左）兄弟节点及其双亲结点（父子换位法）
  • 当右兄弟很宽裕时，用当前节点的后继、后继的后继来填补空缺
  • 当左兄弟很宽裕时，用当前节点的前驱、前驱的前驱来填补空缺
  • 兄弟不够借，且此时与该节点相邻的左、右兄弟结点的关键字个数均=(m/2)[向上取整] - 1，则将关键字删除后与左（或右）兄弟节点及双亲结点中的关键字进行合并
  • 在合并过程中，双亲结点中的关键字个数会减1。
    • 若双亲结点是根节点且，关键字个数减 少至0（根节点关键字个数1时，有2棵子树），则直接将根节点删除，合并后的新节点成为根；
    • 若双亲结点不是根结点，且关键字个数减少到(m/2)[向上取整] - 2，则又要与它自己的兄弟节点进行调整或合并操作，并重复上述步骤，直至符合B树的要求

各别性质问题

• 高度为h的m阶B树，至少(满二叉树)有2^h-1个结点，最多结点数(即满树)为(m^h - 1)/(m-1)个结点
• 含有n个非叶节点的m阶B树中至少包含(n-1)([m/2]-1) + 1
• 含有n个关键点的m阶B树，B树的最大高度log2(n)，最小高度logm(n)

B+树

性质

1. 每个分支节点最多m棵子树（孩子节点）
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有(m/2)[向上取整]棵子树
3. 结点的子树个数与关键字个数相等
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（支持顺序查找）
5. 所有分支节点中仅包含它的各个子节点中关键字的最大值及指向其子结点的指针

B+树中，无论查找成功与否，最终一定都要走到最下面一层

B+树 VS B树

• m阶B树：

  1. 节点中n个关键字对应n+1棵子树
  2. 根节点的关键字数n∈[1 , m-1]。关键字数n∈[[m/2]-1, m-1]
  3. 各节点中包含的关键字是不重复的
  4. 所有结点中都包含了关键字对应的记录的存储地址

• m阶B+树：

  1. 节点中n个关键字对应n棵子树
  2. 根节点的关键字数n∈[1 , m]。关键字数n∈[[m/2], m]
  3. 在B+树中，叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中
  4. 叶结点包含信息，所有非叶节点仅起索引作用，非叶节点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址

在B+树中，非叶节点不含有该关键字对应记录的存储地址。可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，树高更矮，读磁盘次数更少，查找更快

散列表（哈希表）

拉链法

• 拉链法（又称链接发，链地址法），处理“冲突”：把所有“同义词”存储在一个链表中

删除方式

• 直接物理删除

查找长度

• 在查找运算中，需要对比关键字的次数称为查找长度
• 平均查找长度ASL：
  • ASL成功：(Σ (各层高度 * 各层的元素个数)) / 元素总数
  • ASL失败（装填因子）：Σ (各个地址的元素个数) / 地址总数
  • 装填因子a = 表中记录数 / 散列表长度 （装填因子会直接影响散列表的查找效率）装填因子越大意味着发生散列冲突的概率越大,而散列冲突对散列表的效率有影响
• 对包含n个元素的散列表进行查询，平均查找长度O(n)，不直接依赖于n

除留余数法

• H(key) = key % p
• 散列表表长为m，取一个不大于 m 但最接近或等于 m 的质数p (除了1和此整数自身外，不能被其他自然数整除的数)

直接定址法

• H(key) = key 或 H(key) = a*key + b
• 其中，a和b是常数。适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费

数字分析法

• 选取数码分布较为均匀的若干位作为散列地址
• 设挂念子是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方式适合于已知的关键字集合，若更换了关键字，则需要重新构造新得散列函数。

平方取中法

• 取关键字的平方值的中间几位作为散列地址
• 这种方法得到的散列地址与关键字的每位都有关系。适用于关键字的每位取值都不够均匀或均小于散列地址所需的位置

处理冲突的方法 —— 开放定址法

由于散列函数的选取，仍然有可能产生地址冲突，冲突是不能绝对避免的

• 所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为：

Hi = (H(key) + di) % m (i = 0,1,2,...,k (k <= m - 1), m表示散列表表长; di为增量序列; i可以理解为“第i次发生冲突”)

线性探测法

di = 0,1,2,3,...,m-1; 即发生冲突时，每次往后探测相邻的下一个单元是否为空

H(key) = 1 % 13 = 1

H0 = (1+d0) % 16 = 1

删除结点不能简单地将被删结点地空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个“删除标记”，进行逻辑删除

• ASL成功 = Σ(各个元素的查找对比次数) / 模的值

线性探测法很容易造成同义词，非同义词的“聚集（堆积）”现象，严重影响查找效率

产生原因 -- 冲突后再探测一定是放在某个连续的位置

平方探测法

当di = 0^2, 1^2, -1^2, 2^2, -2^2, ..., k^2, -k^2时，称为平方探测法，又称二次探测法其中 k <= m/2

• 小坑：散列表长度m必须是一个可以表示成 4j+3 的素数，才能探测到所有位置

伪随机序列法

di 是一个伪随机序列，如di = 0, 5, 24, 11,...

删除方法

只能做标记。该地址可能是该记录地同义词查找路径上的地址，物理地删除就中断了查找路径，因为查找时碰到空地址就会认为是查找失败

处理冲突的方法 —— 再散列法

再散列法（再哈希法）：除了原始的散列函数 H(key) 之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止：

Hi = RHi(Key) i = 1,2,3,...,k

图

重连通图

• 关节点：删除该节点后，原来的图被分割为两个及以上的连通分量
• 重连通图：判断一个图是否是重连通图，也可以转变为：判断图中是否有关节点，如果没有关节点，证明此图为重连通图；反之则不是。

邻接表to邻接矩阵、邻接矩阵to邻接表

1. 邻接矩阵的定义

   #define INFINITY INT_MAX //INT_MAX 为最大整数，表示∞
   const int MaxVertices = 20;
   template <class Type>struct AdjMatrix{
   Type * NodeTable; //顶点表定义
   float arr[MaxVertices][MaxVertices] //邻接矩阵定义
   int NumVertices;  // 当前顶点个数
   int NumEdges; // 当前边数个数
   };

2. 邻接表定义

   struct Edge{  //邻接表中边节点的定义
   int dest; // 邻接的结点
   float cost; //边的权值
   Edge *link;  //下一条边的指针
   }
   template <class Type> struct Vertex{  // 邻接表中顶点的定义
   Type data;  // 顶点的值
   Edge *adj;  // 顶点的指针（指向下一条边）
   }
   template <class Type> struct AdjTable{  //邻接表
   Vertex<Type> *NodeTable;  // 顶点表
   int NumVertices;  // 当前顶点个数
   int NumEdges; // 当前边数  
   }

• 邻接矩阵to邻接表

  AdjTable<Type> * convertM(){
  AdjTable<Type>* A; Edge *e;
  A->NodeTable = new Vertex<Type>[NumVertices];
  A->NumEdges = NumEdges;
  A->NumVertices = NumVertices;
  for(int i = 0;i< NumVertices;i++){
  A->NodeTable[i].data = NodeTable[i];
  A->NodeTable[i].adj = NULL;
  for(int j = 0;j< NumVertices;j++){
    // 若值不等于∞或为空，则有边
    if(arr[i][j] != NULL && arr[i][j] != INFINITY)
    {
      e = new Edge;
      e->dest = j;
      // 链接到该顶点邻接表的边上
      e->link = A->NodeTable[i].adj;
      // 顶点的指针链接到该边（类似于栈）
      NodeTable[i].adj = e;
    }
  }
  }
  return A;
  }

• 邻接表to邻接矩阵

  AdjTable<Type> * convertAL(){
  AdjMatrix<Type>* A; Edge *e;
  int i,j;
  A->NodeTable = new Vertex<Type>[NumVertices];
  A->arr = new float[MaxVertices][MaxVertices];
  A->NumEdges = NumEdges;
  A->NumVertices = NumVertices;
  for(i = 0;i < NumVertices; i++){
  // 初始化邻接矩阵
  for(j = 0;j < NumVertices; j++) A->arr[i][j] = INFINITY;
  A->NodeTable[i] = NodeTable[i].data; //给每一个顶点赋值
  }
  for(i = 0;i < NumVertices; i++){
  p = NodeTable[i].adj;
  while(p != NULL){
    // 遍历该结点的边的顶点
    A->arr[i][p->dest] = p->cost;
    p = p->link;
  }
  }
  return A;
  }

邻接表to逆邻接表

邻接表：该节点的出度链接；逆邻接表：该节点的入度链接

• 邻接表、逆邻接表结构

  struct Edge{  // 结点定义
  int dest; //邻接结点
  float cost; //边的权值
  Edge *link;  // 下一个结点的指针
  };
  template<class Type> struct Vertex{  //顶点定义
  Type data;  // 顶点的值
  Edge *adj;  // 顶点的指针（指向下一个结点）
  }
  template<class Type> struct Graph{  // 邻接表与逆邻接表定义
  Vertex<Type>* NodeTable;  // 邻接表顶点表
  Vertex<Type>* OppositNodeTable; //逆邻接表顶点表
  int NumVertices;  //当前顶点个数
  int NumEdges; // 当前边数
  }

• 邻接表to逆邻接表

  void convertM(){
  int i; Edge *p, *q;
  OppositNodeTable = new Vertex<Type>[NumVertices];
  for(i = 0;i < NumVertices;i++){
  // 初始化各个顶点的值与指针
  OppositNodeTable[i].data = NodeTable[i].data;
  OppositNodeTable[i].adj = NULL;
  }
  for(i = 0;i< NumVertices;i++){
  p = NodeTable[i].adj;
  while(p != NULL){
    q = new Edge;
    q->dest = i;
    q->cost = p->cost;
    // 链接到顶点的邻接结点的指针
    q->link = OppositNodeTable[p->dest].adj;
    OppositNodeTable[p->dest].adj = q;
    p = p->link;
  }
  }
  }

  DFS、BFS

• 邻接表结构

  
  #define MaXV <最大顶点个数>
  typedef struct ANode
  {
  int adjvex; // 该边的终点编号
  struct ANode* nextarc;  // 指向下一条边的指针
  InfoType info;  // 该边的相关信息
  }ArcNode; // 改表节点类型

typedef struct Vnode{ Vertex data; // 顶点信息 ArcNode* firstarc; // 指向第一条边 }VNode; typedef VNode AdjList[MaXV]; // AdjList是邻接表类型

typedef struct{ AdjList adjlist; // 邻接表 int n,e; // 图中顶点数n和边数e }ALGraph; // 完整的图邻接表类型

### DFS
```C++
bool visited[MAX_VERTEX NUM]; //访问标记数组
void DFSTraverse(Graph G) // 对图 G进行深度优先遍历
{
  // 初始化已访问标记数据
  for(v = 0;v < G.vexnum; ++v)
    visited[v]=false;
  // 从v=0开始遍历
  for(v = 0;v < G.vexnum; ++v)
    if(!visited[v])
      DFS(G, v);
}
void DFS(ALGraph *G, int v)
{
  visit(v);
  visited[v] = true;  // 已访问
  for(w = FirstNeighbor(G, v);w>=0;w->NextNeighor(G, v, w))
  {
    // 访问该结点的所有邻接点（NextNeighbor(G,v,w)返回除w之外顶点v的下一个邻接点的顶点号）
    if (!visited[w]){ // w 为u的尚未访问的邻接顶点
      DFS(G, w);  // 深度访问，直至都访问完毕
    } 
  }
}

BFS

bool visited[MAX_VERTEX NUM]; //访问标记数组
void BFSTraverse(Graph G) // 对图 G进行广度优先遍历
{
  // 初始化已访问标记数据
  for(v = 0;v < G.vexnum; ++v)
    visited[v]=false;
  InitQueue(Q); // 初始化辅助队列Q
  for(v = 0;v < G.vexnum; ++v)
    if(!visited[v])
      BFS(G, v);
}
void BFS(ALGraph *G, int v)
{
  visit(v);
  visited[v] = true;  // 已访问
  Enqueue(Q, v); // 将顶点v入队列Q
  while(!isEmpty(Q)){
    DeQueue(Q, v);  // 将顶点v出列
    for(w = FirstNeighbor(G, v); w>=0;w=NextNeighbor(G,v,w)){
      //检测v所有的邻接点（NextNeighbor(G,v,w)返回除w之外顶点v的下一个邻接点的顶点号）
      if(!visited[w]){
        visit(w);
        visited[w] = true;
        EnQueue(Q, w); //将w入队
      }
    }
  }  
}

* 最小生成树

* Prim

#define INF 32767 //INF表示∞
void Prim(MGraph g, int v)
{
  int lowcost[MAXV];
  int min;
  int closest[MAXV], i, j, k;
  for(i=0;i<g.n;i++) //给lowcost[]和closest[]置初值
  {
    lowcost[i] = g.edges[v][i];
    closest[i] = v;
  }
  for(i=1;i<g.n;i++)  //找出(n-1)个顶点
  {
    min = INF;
    for(j=0;j<g.n;j++) //在(V-U)中找出离U最近的顶点k
    {
      if(lowcost[j]!=0 && lowcost[j]<min)
      {
        min = lowcost[j];
        k = j;  //k 记录最近顶点的编号
      }
    }
    printf(" 边(%d, %d)权为:%d\n", closest[k], k, min);
    lowcost[k] = 0; //标志k已经加入U
    for(j=0;j<g.n;j++)  //修改数组lowcost和closes
    {
      if(g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j])
      {
        lowcost[j] = g.edges[k][j];
        closest[j] = k;
      }
    }
  }
}

* Kruskal

typedef struct
{
  int u; //边的起始顶点
  int v; //边的终止顶点
  int w; //边的权值
}Edge;
void Kruskal(MGraph g)
{
  int i, j, u1, v1, sn1, sn2, k;
  int vset[MAXV];
  Edge E[MaxSize]; //存放所有边
  k = 0; //E数组的下标从0开始计
  for(i=0;i<g.n;i++)
  {
    for(j=0;j<g.n;j++){
      E[k].u = i;
      E[k].v = j;
      E[k].w = g.edges[i][j];
      k++;
    }
  }
  InsertSort(E, g.e); //采用直接插入排序队E数组按权值递增排序
  for(i=0;i<g.n;i++){ 
    // 初始化辅助数组
    vset[i] = i;
  }
  k = 1; //k 表示当前构造生成树的第几条边，初值为1
  j = 0; //E 中边的下标，初值为0
  while(k<g.n) //生成的边数小于n时循环
  {
    // 取一条边的头尾顶点
    u1 = E[j].u;
    v1 = E[j].v;

    sn1 = vset[u1]; //分别得到两个顶点所属于的集合编号
    sn2 = vset[v1];

    if(sn1 != sn2)  //两顶点属于不同的集合
    {
      printf(" (%d,%d):%d\n", u1, v1, E[j].w);
      k++;  //生成边数增1
      for(i=0;i<g.n;i++>)
      {
        if(vset[i]==sn2)  //集合编号为sn2的改为sn1
          vset[i] = sn1;
      }
    }
    j++;  //扫码下一条边
  }
}

最短路径

Dijkstra

void Dijkstra(MGraph g,int v)
{
  int dist[MAXV], path[MAXV];
  int s[MAXV];
  int mindis, i, j, u;
  for(i=0;i<g.n;i++)
  {
    dist[i] = g.edges[v][i]; //距离初始化
    s[i] = 0; //s[]置空
    if(g.edges[v][i] < INF) //路径初始化
      path[i] = v; //顶点v到i有边时，置顶点i的前一个顶点为v
    else
      path[i] = -1; //顶点v到i没边时，置顶点i的前一个顶点为-1
  }
  s[v] = 1;
  path[v] = 0;//源点编号v放入s中
  for(i=0;i<g.n;i++)  //循环直到所有顶点的最短路径都求出
  {
    mindis = INF; // mindis 置最小长度初值
    for(j=0;j<g.n;j++) //选取不在s中且具有最小距离的顶点u
      {
        if(s[j]==0 && dist[j]<mindis)
        {
          u = j;
          mindis = dist[j];
        }
      }
    s[u] = 1; //顶点u加入s中
    for(j=0;j<g.n;j++)  //修改不在s中的顶点的距离
    {
      if(s[j]==0)
        if(g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
        {
          dist[j]=dist[u]+g.edges[u][j];
          path[j]=u;
        }
    }
  }
  Dispath(dist, path, s, g.n, v); //输出最短路径
}

* Floyd

void Floyd(MGraph g)
{
  int A[MAXV][MAXV], path[MAXV][MAXV];
  for(int i=0;i<g.n;i++)
    for(int j=0;i<g.n;j++)
    {
      A[i][j] = g.edges[i][j];
      path[i][j] = -1;
    }

  for(int k=0;k<g.n;k++)
    for(int i=0;i<g.n;i++)
      for(int j=0;j<g.n;j++)
        if(A[i][j] > A[i][k] + A[k][j])
        {
          A[i][j] = A[i][k] + A[k][j];
          path[i][j] = k;
        }
  Dispath(A, path, g.n); //输出最短路径
}

拓扑排序

typedef struct
{
  erretx data;  //顶点信息
  int count;  //存放顶点入度
  ArcNode *firstarc;  //指向第一条弧
}VNode;

void TopSort(VNode adj[], int n)
{
  int St[MAXV], top =1; //栈的St的指针为top
  ArcNode *p;
  for(i=0;i<n;i++)
    if(adj[i].count == 0) //入度为0的顶点入栈
    {
      top++;
      St[top]=i;
    }
  while(top > -1) //栈不为空时循环
  {
    i = St[top];  // 弹栈，取栈顶元素找所连接的结点
    top--;
    p = adj[i].firstarc;
    while(p!=NULL)
    {
      j = p->adjvex;  // 找到该点的终点编号，并将其入度数-1
      adj[j].count--; 
      if(adj[j].count == 0) // 若入度数为0，则压栈
      {
        top++;
        St[top]=j;
      }
      p=p->nextarc; //找下一个相邻顶点
    }
  } 
}

AOE网

• 由于AOV网中各顶点的地位平等,每个顶点编号是人为的,因此可以按拓扑排序的结果 重新编号,生成AOV网的新的邻接存储矩阵,这种邻接矩阵可以是三角矩阵。（所有对角线以下的元素全为0）

算法设计问题

P-1

• 给出顶点位置为 v 的第一个邻接顶点的位置，如果找不到，则函数返回-1

  template<class Type> struct AdjTable<Type>::GetFirstNeighbor(int v){
  if(v != -1){
  Edge *p = NodeTable[v].adj;
  if(p != NULL) return p->dest;
  }
  return -1;
  }

P-2

• 输入顶点个数、数据及各条边的信息，建立邻接表

  template<class Type>AdjTable<Type>::AdjTable(int sz = DefaultSize) : MaxVertices(sz){
  int i,k,j;
  Type tail, head;
  float weight;
  Edge *p;
  NodeTable = New Vertex<Type>[MaxVertices];
  cin >> NumVertices;
  for(i = 0;i<NumVertices; i++){
  cin >> NodeTable[i].data;
  NodeTable[i].adj = NULL; 
  }
  cin >> NumEdges;
  for(i =0;i<NumEdges; i++){
  cin >> tail >> head >> weight;
  p = new Edge;
  p->dest = GetVertexPos(head);
  p->cost = weight;
  p->link = NodeTable[GetVertexPos(tail)].adj;
  NodeTable[GetVertexPos(tail)].adj = p;
  }
  }

P-3

• 返回顶点v的邻接顶点w的下一个邻接顶点的位置，若没有下一个邻接顶点，则函数返回-1

  template<class Type>int AdjTable<Type>::GetNextNeighbor(int v, int w){
  if(v != -1){
  Edge *p = NodeTable[v].adj;
  while(p != NULL){
    if(p->dest == w && p->link != NULL)
      return p->link->dest;
    p = p->link;
  }
  }
  return -1;
  }

排序

相关排序计算公式

• 多路归并排序。得到 m 个初试归并段，要利用多路平衡归并在 k 趟内完成排序，则应取的归并路数至少是 logk(m)[向上取整]
• 任何排序方式。对 m 个互异的整数进行排序，至少需要log2(m!)[向上取整]次比较。

堆排序

大根堆

• 构造：按层次遍历数组构造二叉树，从根结点遍历所有孩子结点，找出最大值并与根节点替换位置，以此类推从上往下对所有关节结点进行处理，且全部结点替换完成，实现各个父节点比孩子节点大。

置换-选择排序（生成初始归并段）

性质

• 即“蜘蛛纸牌”，生成一个指定大小的工作区，并从读取对应大小排序码到工作区中，从工作区取最小数为标准，并输出，再存入新的排序码入工作区，取大于上一次最小数标准且工作区最小的数值设为新标准，并输出，以此类推。若工作区已满且找不到新满足条件的最小值，则生成新的归并段并重置最小标准。

  答题格式（案例）

  输入文件InFile	内存工作区	输出文件OutFile	动作
  19,22,17			输出2个排序码
  17	19,22		选择19,输出19,门槛19,置换17
  	22,17	19	选择22,输出22,门槛22,无输入
  	17,-	19,22	无大于门槛的对象,输出段结束符∞
  	17,-	19,22,∞	选择17,输出17,门槛17,无输入
  	-,-	17	无大于门槛的对象,输出段结束符∞
  	-,-	17,∞	结束

最佳归并树

归并树的性质

归并树，既每个归并段看作一个叶子结点，归并段的长度作为结点权值。

最佳归并树的性质

在归并树的性质下，变成哈夫曼树的性质（WPL最小），优先取最小的归并段进行构造。

判断添加虚段的数目

若初始归并段不足以构成一棵严格 k 叉树时，需添加长度为0的“虚段”。

添加方法：

1. 若(初始归并段数量 - 1) % (k-1) = 0,说明不需要添加
2. 若(初始归并段数量 - 1) % (k-1) !=0, 则需要补充(k-1) - u 个虚段

WPL

I/O次数 = 2 * WPL

交换排序

快速排序

• 最左边为基准，先从high开始下降找出比基值小的元素，再从low开始上升找出比基值大的元素，替换两者元素，以此类推，直到low>=high，将基值放到low位置上。

各排序算法的最好最坏的比较次数和移动次数

比如n个顺序存储元素进行排序，a[0]做“哨兵”（即a[0]不存数据，而是用作辅存空间使用）的情况

1. 直接插入排序：

   • 比较次数 最少n-1次；最多(n-1)(n+2)/2
   • 移动次数 最少0； 最多(n-1)(n+4)/2
   • 使用一个辅助存储空间，是稳定的排序；

2. 折半插入排序：

   • 比较次数 最少与最多同，都是n*log2n（其中2为底，下边表示同），
   • 移动次数 最少0，最多时间复杂度为O(n2);(n的平方，以下也如此表示)；
   • 使用一个辅助存储空间，是稳定的排序；
   • 平均查找长度。画判定树，根据 (Σ 层号*该层结点个数) / 总结点数

3. 冒泡排序：

   • 比较最少为：n-1次，最多时间复杂度表示为o(n2);
   • 移动次数最少为0，最多时间复杂度表示为O(n2);
   • 使用一个辅存空间，是稳定的排序；

4. 简单选择排序：

   • 比较次数没有多少之分，均是n(n-1)/2;
   • 移动次数最少为0，最多为3(n-1);
   • 使用一个辅存空间，是稳定的排序；

5. 快速排序：

   • 比较和移动次数最少时间复杂度表示为O(n*log2n);
   • 比较和移动次数最多的时间复杂度表示为O(n2);
   • 使用的辅助存储空间最少为log2n，最多为n的平方；是不稳定的排序；

6. 堆排序：

   • 比较和移动次数没有好坏之分，都是O(n*log2n);
   • 使用一个辅存空间，是不稳定的排序；

7. 2-路归并排序：比较和移动次数没有好坏之分，都是O(n*log2n);

   • 需要n个辅助存储空间，是稳定的排序；