数据结构week5

Week5树（下）

5.1 堆（heap）

什么是堆

优先队列（Priority Queue）：特殊的“队列” ，取出元素的顺序是依照元素的优先权（关键字） 大小，而不是元素进入队列的先后顺序。

问题：如何组织优先队列？

• 一般的数组、链表？
• 有序的数组或者链表？
• 二叉搜索树？ AVL树？

若采用数组或链表实现优先队列

数组 :

插入 — 元素总是插入尾部 ——————$\Theta(1)$

删除 — 查找最大（或最小）关键字 ——————$\Theta(n)$

从数组中删去需要移动元素 ——————$O(n)$

链表:****

插入 — 元素总是插入链表的头部 ——————$\Theta(1)$

删除 — 查找最大（或最小）关键字 ——————$\Theta(n)$

删去结点 ——————$\Theta(1)$

有序数组:

插入 — 找到合适的位置 ——————$O(n)或O(log_2n)$

移动元素并插入 ——————$O(n)$

删除 — 删去最后一个元素 ——————$\Theta(1)$​

有序链表:

插入 — 找到合适的位置 ——————$O(n)$​

插入元素 ——————$\Theta(1)$​

删除 — 删除首元素或最后元素 ——————$\Theta(1)$​

是否可以采用二叉树存储结构？

二叉搜索树？

如果采用二叉树结构，应更关注插入还是删除？

• 树结点顺序怎么安排？
• 树结构怎样？

优先队列的完全二叉树表示

堆的两个特性

结构性：用数组表示的完全二叉树；

有序性： 任一结点的关键字是其子树所有结点的最大值(或最小值)

• “最大堆(MaxHeap)” ,也称“大顶堆”：最大值
• “最小堆(MinHeap)” ,也称“小顶堆” ：最小值

注意：从根结点到任意结点路径上结点序列的有序性！

堆的抽象数据类型描述

类型名称： 最大堆（MaxHeap）

数据对象集： 完全二叉树，每个结点的元素值不小于其子结点的元素值

操作集：最大堆$H \in MaxHeap$，元素$item \in ElementType$，主要操作有：

MaxHeap Create(int MaxSize)			//创建一个空的最大堆。
Boolean IsFull(MaxHeap H)			//判断最大堆H是否已满。
Insert(MaxHeap H, ElementType item)	//将元素item插入最大堆H。
Boolean IsEmpty(MaxHeap H)			//判断最大堆H是否为空。
ElementType DeleteMax(MaxHeap H)	//返回H中最大元素(高优先级)。

最大堆的操作

最大堆的创建

typedef struct HeapStruct *MaxHeap;
struct HeapStruct {
    ElementType *Elements; /* 存储堆元素的数组 */
    int Size;              /* 堆的当前元素个数 */
    int Capacity;          /* 堆的最大容量 */
};
MaxHeap Create(int MaxSize) { /* 创建容量为MaxSize的空的最大堆 */
    MaxHeap H = malloc(sizeof(struct HeapStruct));
    H->Elements = malloc((MaxSize + 1) * sizeof(ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Elements[0] = MaxData;
    /* 定义“哨兵”为大于堆中所有可能元素的值，便于以后更快操作 */
    return H;
}

把MaxData换成小于堆中所有元素的MinData，同样适用于创建最小堆。

最大堆的插入

算法：将新增结点插入到从其父结点到根结点的有序序列中

void Insert(MaxHeap H, ElementType item) {
    /* 将元素item 插入最大堆H，其中H->Elements[0]已经定义为哨兵 */
    int i;
    if (IsFull(H)) {
        printf("最大堆已满");
        return;
    }
    i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
    for (; H->Elements[i / 2] < item; i /= 2)
        H->Elements[i] = H->Elements[i / 2]; /* 向下过滤结点 */
    H->Elements[i] = item;                   /* 将item 插入 */
}

向下过滤结点，比交换数据要快

$H->Element[ 0 ]$ 是哨兵元素，它不小于堆中的最大元素，控制循环结束。

最大堆的删除

取出根结点（最大值）元素，同时删除堆的一个结点。$T (N) = O ( log N )$

ElementType DeleteMax(MaxHeap H) {
    /* 从最大堆H中取出键值为最大的元素， 并删除一个结点 */
    int Parent, Child;
    ElementType MaxItem, temp;
    if (IsEmpty(H)) {
        printf("最大堆已为空");
        return;
    }
    MaxItem = H->Elements[1]; /* 取出根结点最大值 */
    /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
    temp = H->Elements[H->Size--];
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Elements[Child] < H->Elements[Child + 1]))
            Child++; /* Child指向左右子结点的较大者 */
        if (temp >= H->Elements[Child])
            break;
        else /* 移动temp元素到下一层 */
            H->Elements[Parent] = H->Elements[Child];
    }
    H->Elements[Parent] = temp;
    return MaxItem;
}

最大堆的建立

建立最大堆： 将已经存在的N个元素按最大堆的要求存放在
一个一维数组中

方法1： 通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为$O(N logN)$。

方法2： 在线性时间复杂度下建立最大堆。

（1）将N个元素按输入顺序存入，先满足完全二叉树的结构特性

（2）调整各结点位置，以满足最大堆的有序特性。

线性时间复杂度$T(n)=O(n)$

结点数	最多交换次数
$n/4$	1
$n/8$	2
$n/16$	3
$n/2^k=1$	$log_2n-1(k-1)$

$$
T(n)=\frac{n}{4}+\frac{n}{8}\times2+\frac{n}{16}\times3+\cdots+\frac{n}{2^k}\times(k-1)
$$

$$
2T(n)=\frac{n}{2}+\frac{n}{4}\times2+\frac{n}{8}\times3+\cdots+\frac{n}{2^{k-1} }\times(k-1)
$$

$$
2T(n)-T(n)=\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\cdots+\frac{n}{2^{k-1}}-\frac{n}{2^k}\times(k-1)\leq n-(log_2n-1)\leq n
$$

5.2 哈夫曼树与哈夫曼编码

什么是哈夫曼树（Huffman Tree）

例 将百分制的考试成绩转换成五分制的成绩

if (score < 60) grade = 1;
else if (score < 70) grade = 2;
else if (score < 80) grade = 3;
else if (score < 90) grade = 4;
else grade = 5;

如果考虑学生成绩的分布的概率：

分数段	0-59	60-69	70-79	80-89	90-100
比例	0.05	0.15	0.40	0.30	0.10

查找效率： 0.05 × 1 + 0.15 × 2 + 0.4 × 3 + 0.3 × 4 + 0.1 × 4 = 3.15

修改判定树：

if (score < 80) {
    if (score < 70)
        if (score < 60) grade = 1;
        else grade = 2;
    else grade = 3;
} else if (score < 90) grade = 4;
else grade = 5;

效率: 0.05 × 3 + 0.15 × 3 + 0.4 × 2 + 0.3 × 2 + 0.1× 2 = 2.2

如何根据结点不同的查找频率构造更有效的搜索树？

哈夫曼树的定义

带权路径长度$(WPL)$： 设二叉树有n个叶子结点，每个叶子结点带有权值$ w_k$，从根结点到每个叶子结点的长度为 $l_k$，则每个叶子结点的带权路径长度之和就是： $WPL=\sum_{k=1}^nw_kl_k$

最优二叉树或哈夫曼树: $WPL$最小的二叉树

哈夫曼树的构造

每次把权值最小的两棵二叉树合并

typedef struct TreeNode *HuffmanTree;
struct TreeNode {
    int Weight;
    HuffmanTree Left, Right;
} HuffmanTree
Huffman(MinHeap H) { /* 假设H->Size个权值已经存在H->Elements[]->Weight里 */
    int i;
    HuffmanTree T;
    BuildMinHeap(H); /*将H->Elements[]按权值调整为最小堆*/
    for (i = 1; i < H->Size; i++) {          /*做H->Size-1次合并*/
        T = malloc(sizeof(struct TreeNode)); /*建立新结点*/
        T->Left = DeleteMin(H);
        /*从最小堆中删除一个结点， 作为新T的左子结点*/
        T->Right = DeleteMin(H);
        /*从最小堆中删除一个结点， 作为新T的右子结点*/
        T->Weight = T->Left->Weight + T->Right->Weight;
        /*计算新权值*/
        Insert(H, T); /*将新T插入最小堆*/
    }
    T = DeleteMin(H);
    return T;
}

整体复杂度为$O(N logN)$

哈夫曼树的特点:

• 没有度为1的结点；
• 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树；
• n个叶子结点的哈夫曼树共有2n-1个结点；
• 对同一组权值{w1 ,w2 , …… , wn}， 是否存在不同构的两棵哈夫曼树呢？ （存在！）

哈夫曼编码

给定一段字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少？

假设有一段文本，包含58个字符，并由以下7个字符构： a， e， i，s， t，空格（sp），换行（nl）；这7个字符出现的次数不同。如何对这7个字符进行编码，使得总编码空间最少？

分析

（1）用等长ASCII编码： 58 × 8 = 464位；
（2）用等长3位编码： 58 × 3 = 174位；
（3）不等长编码：出现频率高的字符用的编码短些，出现频率低的字符则可以编码长些？

怎么进行不等长编码？

如何避免二义性？

前缀码（prefix code）：任何字符的编码都不是另一字符编码的前缀，可以无二义地解码

二叉树用于编码

用二叉树进行编码：

（1）左右分支： 0、 1

（2）字符只在叶结点上

怎么构造一颗编码代价最小的二叉树？ 哈夫曼编码

5.3 集合及运算

集合的表示

集合运算： 交、并、补、差， 判定一个元素是否属于某一集合

并查集：集合并、 查某元素属于什么集合

并查集问题中集合存储如何实现？

可以用树结构表示集合，树的每个结点代表一个集合元素

双亲表示法：孩子指向双亲。

采用数组存储形式

数组中每个元素的类型描述为

typedef struct {
    ElementType Data;
    int Parent;
} SetType;

负数表示根结点；非负数表示双亲结点的下标。

集合运算

（1）查找某个元素所在的集合（用根结点表示）

int Find(SetType S[], ElementType X) { /* 在数组S中查找值为X的元素所属的集合 */
    /* MaxSize是全局变量， 为数组S的最大长度 */
    int i;
    for (i = 0; i < MaxSize && S[i].Data != X; i++) ;
    if (i >= MaxSize) return -1; /* 未找到X， 返回-1 */
    for (; S[i].Parent >= 0; i = S[i].Parent) ;
    return i; /* 找到X所属集合， 返回树根结点在数组S中的下标 */
}

（ 2） 集合的并运算

分别找到X1和X2两个元素所在集合树的根结点

如果它们不同根，则将其中一个根结点的父结点指针设置成另一个根结点的数组下标。

void Union(SetType S[], ElementType X1, ElementType X2) {
    int Root1, Root2;
    Root1 = Find(S, X1);
    Root2 = Find(S, X2);
    if（ Root1 != Root2 ） S[Root2].Parent = Root1;
}

当x1和x2不属于同一子集时，才需要合并

为了改善合并以后的查找性能，可以采用小的集合合并到相对大的集合中。（修改Union函数）

代码模板

/*------------------ Heap ------------------*/
typedef int ElementType;
typedef struct HNode *Heap; /* 堆的类型定义 */
struct HNode {
    ElementType *Data; /* 存储元素的数组 */
    int Size;          /* 堆中当前元素个数 */
    int Capacity;      /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */

#define MAXDATA 1000 /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */

MaxHeap CreateHeap(int MaxSize) { /* 创建容量为MaxSize的空的最大堆 */

    MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
    H->Data = (ElementType *)malloc((MaxSize + 1) * sizeof(ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0] = MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/

    return H;
}

bool IsFull(MaxHeap H) { return (H->Size == H->Capacity); }

bool Insert(
    MaxHeap H,
    ElementType X) { /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */
    int i;

    if (IsFull(H)) {
        printf("最大堆已满");
        return false;
    }
    i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
    for (; H->Data[i / 2] < X; i /= 2) H->Data[i] = H->Data[i / 2]; /* 上滤X */
    H->Data[i] = X; /* 将X插入 */
    return true;
}

#define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */

bool IsEmpty(MaxHeap H) { return (H->Size == 0); }

ElementType DeleteMax(MaxHeap H) {
    /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */
    int Parent, Child;
    ElementType MaxItem, X;

    if (IsEmpty(H)) {
        printf("最大堆已为空");
        return ERROR;
    }

    MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */
    /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
    X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
            Child++; /* Child指向左右子结点的较大者 */
        if (X >= H->Data[Child])
            break; /* 找到了合适位置 */
        else       /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;

    return MaxItem;
}

/*----------- 建造最大堆 -----------*/
void PercDown(MaxHeap H, int p) { 
    /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    ElementType X;

    X = H->Data[p]; /* 取出根结点存放的值 */
    for (Parent = p; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
            Child++; /* Child指向左右子结点的较大者 */
        if (X >= H->Data[Child])
            break; /* 找到了合适位置 */
        else       /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
}

void BuildHeap(MaxHeap H) { /* 调整H->Data[]中的元素，使满足最大堆的有序性  */
    /* 这里假设所有H->Size个元素已经存在H->Data[]中 */

    int i;

    /* 从最后一个结点的父节点开始，到根结点1 */
    for (i = H->Size / 2; i > 0; i--) PercDown(H, i);
}

/*HUFFMAN TREE*/
typedef struct TreeNode *HuffmanTree;
struct TreeNode {
    int Weight;
    HuffmanTree Left, Right;
};
HuffmanTree Huffman(MinHeap H) { 
    /* 假设H->Size个权值已经存在H->Elements[]->Weight里 */
    int i;
    HuffmanTree T;
    BuildMinHeap(H); /*将H->Elements[]按权值调整为最小堆*/
    int size = H->Size;
    for (i = 1; i < size; i++) { /*做H->Size-1次合并*/
        T = (HuffmanTree)malloc(sizeof(struct TreeNode)); /*建立新结点*/
        T->Left = DeleteMin(H);
        /*从最小堆中删除一个结点， 作为新T的左子结点*/
        T->Right = DeleteMin(H);
        /*从最小堆中删除一个结点， 作为新T的右子结点*/
        T->Weight = T->Left->Weight + T->Right->Weight;
        /*计算新权值*/
        Insert(H, T); /*将新T插入最小堆*/
    }
    T = DeleteMin(H);
    return T;
}

/*------------------ Set ------------------*/
#define MAXN 1000        /* 集合最大元素个数 */
typedef int ElementType; /* 默认元素可以用非负整数表示 */
typedef int SetName;     /* 默认用根结点的下标作为集合名称 */
typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 */

void Union(SetType S,
           SetName Root1,
           SetName Root2) { /* 这里默认Root1和Root2是不同集合的根结点 */
    /* 保证小集合并入大集合 */
    if (S[Root2] < S[Root1]) { /* 如果集合2比较大 */
        S[Root2] += S[Root1];  /* 集合1并入集合2  */
        S[Root1] = Root2;
    } else {                  /* 如果集合1比较大 */
        S[Root1] += S[Root2]; /* 集合2并入集合1  */
        S[Root2] = Root1;
    }
}

SetName Find(SetType S, ElementType X) { /* 默认集合元素全部初始化为-1 */
    if (S[X] < 0)                        /* 找到集合的根 */
        return X;
    else
        return S[X] = Find(S, S[X]); /* 路径压缩 */
}

编程习题

1.堆中的路径

将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。

输入格式:

每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。

输出格式:

对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。

输入样例:

5 3
46 23 26 24 10
5 4 3

输出样例:

24 23 10
46 23 10
26 10

思路

建立最小堆的基本操作训练，这里采用逐个插入的方法建造堆，套模板，不赘述。

AC code

#include <stdio.h>
#define MAXN 1001
#define MINH -10001
int H[MAXN], size;
void Create() {
    size = 0;
    H[0] = MINH;
    /*设置“岗哨” */
}
void Insert(int X) {
    /* 将X插入H。这里省略检查堆是否已满的代码 */
    int i;
    for (i = ++size; H[i / 2] > X; i /= 2)
        H[i] = H[i / 2];
    H[i] = X;
}
int main() {
    int n, m, x, i, j;
    scanf("%d %d", &n, &m);
    Create();                 /* 堆初始化 */
    for (i = 0; i < n; i++) { /*以逐个插入方式建堆 */
        scanf("%d", &x);
        Insert(x);
    }
    for (i = 0; i < m; i++) {
        scanf("%d", &j);
        printf("%d", H[j]);
        while (j > 1) { /*沿根方向输出各结点*/
            j /= 2;
            printf(" %d", H[j]);
        }
        printf("\n");
    }
    return 0;
}

测试点	提示	结果	分数	耗时	内存
0	sample 调整到根、到中间位置，有不需要调整的元素	答案正确	13	3 ms	316 KB
1	路径更长，交错，index从中间开始，有负数	答案正确	6	3 ms	308 KB
2	最小N和M	答案正确	2	3 ms	184 KB
3	最大N和M随机，元素取到正负10000	答案正确	4	4 ms	320 KB

2.File Transfer

关于并查集，2005、2007年浙江大学计算机学院免试研究生上机考试题即由此题改编而来。

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

Input Specification:

Each input file contains one test case. For each test case, the first line contains N $(2≤N≤10^4)$, the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:

I c1 c2  

where I stands for inputting a connection between c1 and c2; or

C c1 c2    

where C stands for checking if it is possible to transfer files between c1 and c2; or

S

where S stands for stopping this case.

Output Specification:

For each C case, print in one line the word “yes” or “no” if it is possible or impossible to transfer files between c1 and c2, respectively. At the end of each case, print in one line “The network is connected.” if there is a path between any pair of computers; or “There are k components.” where k is the number of connected components in this network.

Sample Input 1:

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S

Sample Output 1:

no
no
yes
There are 2 components.

Sample Input 2:

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S

Sample Output 2:

no
no
yes
yes
The network is connected.

思路

此题的关键在于如何提高效率。

TSSN的实现（too simple sometimes neive）

SetName Find(SetType S, ElementType X) { /* 默认集合元素全部初始化为-1 */
    for (; S[X] >= 0; X = S[X]) ;
    return X;
}
void Union(SetType S, SetName Root1, SetName Root2) { 
    /* 这里默认Root1和Root2是不同集合的根结点 */
    S[Root2] = Root1;
}

int Find(SetType S[], ElementType X) {
    int i;
    for (i = 0; i < MaxSize && S[i].Data != X; i++) ;
    if (i >= MaxSize) return -1;
    for (; S[i].Parent >= 0; i = S[i].Parent) ;
    return i;
}
void Union(SetType S[], ElementType X1, ElementType X2) {
    int Root1, Root2;
    Root1 = Find(S, X1);
    Root2 = Find(S, X2);
    if (Root1 != Root2) S[Root2].Parent = Root1;
}

对照下文测试点即知道为何不行（doge）。

下面引入按秩归并。

为什么需要按秩归并？

因为朴素的Union$T(n)=O(n^2)$。关键在于树会越来越高！

所以应该把矮树贴到高树上！

树的高度存哪里？

S[Root] = -树高; （仍然初始化为-1）

最坏情况下的树高 =$ O(log N)$​

另一种做法：比规模

把小树贴到大树上 S[Root] = -元素个数;

两种方法统称“按秩归并”

同时还需要路径压缩 ：先找到根；把根变成 X 的父结点；再返回根。

时间复杂度

引理 （Tarjan）令$ T( M, N )$ 为交错执行$M \geq N$ 次带路径压缩的查找和$N - 1$ 次按秩归并的最坏情况时间。则存在正常数 $k_1$ 和 $k_2$使得:
$$
k_1M\alpha(M,N)\leq T(M,N)\leq k_2M\alpha(M,N)
$$
Ackermann 函数和 $\alpha( M, N )$​
$$
A(i,j)=\left\{
\begin{aligned}
& 2^j & i=1\ and\ j\geq1\newline
& A(i-1,2) & i\geq2\ and\ j=1 \newline
& A(i-1,A(i,j-1)) & i\geq 2\ and\ j\geq2
\end{aligned}
\right.
$$
http://mathworld.wolfram.com/AckermannFunction.html
$$
\alpha(M,N)=min\{i\geq1 |A(i,\lfloor M/N\rfloor)>logN\}\leq O(log^{@}N)\leq4
$$
$log^{@}N$​（Ackermann反函数）=对N求对数直到结果$\leq1$​​的次数

$log^{@}2^{65536}=5$​ 因为 $logloglogloglog(2^{65536})=1$​​

所以事实上路径压缩不会使得算法的时间复杂度有显著的下降，但也是一个可行的手段。

AC code

#include <stdio.h>
#define MaxSize 10000
typedef int ElementType; /*默认元素可以用非负整数表示*/
typedef int SetName;     /*默认用根结点的下标作为集合名称*/
typedef ElementType SetType[MaxSize];

SetName Find(SetType S, ElementType X) {
    if (S[X] < 0) /* 找到集合的根 */
        return X;
    else
        return S[X] = Find(S, S[X]);
}

void Union(SetType S, SetName Root1, SetName Root2) {
    if (S[Root2] < S[Root1]) {
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    } else {
        S[Root1] += S[Root2];
        S[Root2] = Root1;
    }
}

void Initialization(SetType S, int n) {
    for (int i = 0; i < n; ++i)
        S[i] = -1;
}

void Input_connection(SetType S) {
    ElementType u, v;
    SetName Root1, Root2;
    scanf("%d %d\n", &u, &v);
    Root1 = Find(S, u - 1);
    Root2 = Find(S, v - 1);
    if (Root1 != Root2)
        Union(S, Root1, Root2);
}

void Check_connection(SetType S) {
    ElementType u, v;
    SetName Root1, Root2;
    scanf("%d %d\n", &u, &v);
    Root1 = Find(S, u - 1);
    Root2 = Find(S, v - 1);
    if (Root1 == Root2)
        printf("yes\n");
    else
        printf("no\n");
}

void Check_network(SetType S, int n) {
    int i, counter = 0;
    for (i = 0; i < n; i++) {
        if (S[i] < 0)
            counter++;
    }
    if (counter == 1)
        printf("The network is connected.\n");
    else
        printf("There are %d components.\n", counter);
}

int main() {
    SetType S;
    int n;
    char in;
    scanf("%d\n", &n);
    Initialization(S, n);
    do {
        scanf("%c", &in);
        switch (in) {
        case 'I':
            Input_connection(S);
            break;
        case 'C':
            Check_connection(S);
            break;
        case 'S':
            Check_network(S, n);
            break;
        }
    } while (in != 'S');
    return 0;
}

测试点	提示	结果	分数	耗时	内存
0	sample 1 合并2个集合，最后不连通	答案正确	7	4 ms	316 KB
1	sample 2 最后连通	答案正确	7	4 ms	324 KB
2	最小N，无连通操作	答案正确	1	4 ms	300 KB
3	最大N，无操作	答案正确	1	6 ms	312 KB
4	最大N，递增链，卡不按大小union的	答案正确	4	7 ms	304 KB
5	最大N，递减链，卡不按大小union的	答案正确	4	9 ms	316 KB
6	最大N，两两合并，反复查最深结点，卡不压缩路径的	答案正确	1	16 ms	300 KB

3.Huffman Codes

In 1953, David A. Huffman published his paper “A Method for the Construction of Minimum-Redundancy Codes”, and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string “aaaxuaxz”, we can observe that the frequencies of the characters ‘a’, ‘x’, ‘u’ and ‘z’ are 4, 2, 1 and 1, respectively. We may either encode the symbols as {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}, or in another way as {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}, both compress the string into 14 bits. Another set of code can be given as {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}, but {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} is NOT correct since “aaaxuaxz” and “aazuaxax” can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤63), then followed by a line that contains all the N distinct characters and their frequencies in the following format:

c[1] f[1] c[2] f[2] ... c[N] f[N]

where c[i] is a character chosen from {‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}, and f[i] is the frequency of c[i] and is an integer no more than 1000. The next line gives a positive integer M (≤1000), then followed by M student submissions. Each student submission consists of N lines, each in the format:

c[i] code[i]

where c[i] is the i-th character and code[i] is an non-empty string of no more than 63 ‘0’s and ‘1’s.

Output Specification:

For each test case, print in each line either “Yes” if the student’s submission is correct, or “No” if not.

Note: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code length being optimal is considered correct.

Sample Input:

7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11结尾无空行

Sample Output:

Yes
Yes
No
No

思路

Huffman编码不唯一，并且最优编码不一定通过Huffman编码得到！

回顾Huffman Codes 的特点

1. 最优编码 —— 总长度（WPL）最小
2. 无歧义解码 —— 前缀码：数据仅存于叶子结点
3. 有度为1的结点 —— 满足1、 2则必然有3

注意：满足2、 3可不一定有1！

核心算法

1.计算最优编码长度

2.对每位学生的提交，检查

a) 长度是否正确 $Len=\sum_{i=0}^{N-1}strlen(code[i])\times f(i))$

注意：$Code[i]$的最大长度为$N-1$

b) 建树的过程中检查是否满足前缀码要求

本题相对来说代码冗长，还有不少细节需要注意。

特别地，在此处指出慕课里给出的代码模板的一个错误，在创建HUffman树时，需要经过H->Size-1次调整，但是在for循环的条件里不能直接写成i < H->Size-1​​​，因为DeleteMin后H->Size会变化，应该提前记录H->Size的值。

AC code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 65
int Weight[128];

typedef struct TreeNode *HuffmanTree;
struct TreeNode {
    int Weight;
    char c;
    HuffmanTree Left, Right;
};
typedef HuffmanTree ElementType;
typedef struct HNode *Heap; /* 堆的类型定义 */
struct HNode {
    ElementType *Data; /* 存储元素的数组 */
    int Size;          /* 堆中当前元素个数 */
    int Capacity;      /* 堆的最大容量 */
};
typedef Heap MinHeap; /* 最小堆 */

#define MINDATA -1 /* 该值应根据具体情况定义为小于堆中所有可能元素的值 */

HuffmanTree NewHuffmanNode() {
    HuffmanTree BST = (HuffmanTree)malloc(sizeof(struct TreeNode));
    BST->Weight = 0;
    BST->Left = BST->Right = NULL;

    return BST;
}

MinHeap CreateHeap(int MaxSize) { /* 创建容量为MaxSize的空的最小堆 */

    MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
    H->Data = (ElementType *)malloc((MaxSize + 1) * sizeof(ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    HuffmanTree T = NewHuffmanNode();
    T->Weight = MINDATA; /* 定义"哨兵"为小于堆中所有可能元素的值*/
    H->Data[0] = T;

    return H;
}

int IsFull(MinHeap H) { return (H->Size == H->Capacity); }

int Insert(MinHeap H, ElementType X) {
    /* 将元素X插入最小堆H，其中H->Data[0]已经定义为哨兵 */
    int i;

    if (IsFull(H)) {
        printf("最小堆已满");
        return 0;
    }
    i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
    for (; H->Data[i / 2]->Weight > X->Weight; i /= 2)
        H->Data[i] = H->Data[i / 2]; /* 上滤X */
    H->Data[i] = X;                  /* 将X插入 */
    return 1;
}

#define ERROR NULL /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */

int IsEmpty(MinHeap H) { return (H->Size == 0); }

ElementType DeleteMin(MinHeap H) {
    /* 从最小堆H中取出键值为最大的元素，并删除一个结点 */
    int Parent, Child;
    ElementType MinItem, X;

    if (IsEmpty(H)) {
        printf("最小堆已为空");
        return ERROR;
    }

    MinItem = H->Data[1]; /* 取出根结点存放的最小值 */
    /* 用最小堆中最后一个元素从根结点开始向上过滤下层结点 */
    X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) &&
            (H->Data[Child]->Weight > H->Data[Child + 1]->Weight))
            Child++; /* Child指向左右子结点的较大者 */
        if (X->Weight <= H->Data[Child]->Weight)
            break; /* 找到了合适位置 */
        else       /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;

    return MinItem;
}

/*----------- 建造最小堆 -----------*/
void PercDown(MinHeap H, int p) {
    /* 下滤：将H中以H->Data[p]为根的子堆调整为最小堆 */
    int Parent, Child;
    ElementType X;

    X = H->Data[p]; /* 取出根结点存放的值 */
    for (Parent = p; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) &&
            (H->Data[Child]->Weight > H->Data[Child + 1]->Weight))
            Child++; /* Child指向左右子结点的较大者 */
        if (X->Weight <= H->Data[Child]->Weight)
            break; /* 找到了合适位置 */
        else       /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
}

void BuildMinHeap(MinHeap H) {
    /* 调整H->Data[]中的元素，使满足最小堆的有序性  */
    /* 这里假设所有H->Size个元素已经存在H->Data[]中 */

    int i;

    /* 从最后一个结点的父节点开始，到根结点1 */
    for (i = H->Size / 2; i > 0; i--) PercDown(H, i);
}

/*HUFFMAN TREE*/

HuffmanTree Huffman(MinHeap H) {
    /* 假设H->Size个权值已经存在H->Elements[]->Weight里 */
    int i;
    HuffmanTree T;
    BuildMinHeap(H); /*将H->Elements[]按权值调整为最小堆*/
    int size = H->Size;
    for (i = 1; i < size; i++) { /*做H->Size-1次合并*/
        T = NewHuffmanNode();    /*建立新结点*/
        T->Left = DeleteMin(H);
        /*从最小堆中删除一个结点， 作为新T的左子结点*/
        T->Right = DeleteMin(H);
        /*从最小堆中删除一个结点， 作为新T的右子结点*/
        T->Weight = T->Left->Weight + T->Right->Weight;
        /*计算新权值*/
        Insert(H, T); /*将新T插入最小堆*/
    }
    T = DeleteMin(H);
    return T;
}

void ReadData(MinHeap H, int N) {
    for (int i = 0; i < N; i++) {
        getchar(); //读换行
        HuffmanTree T = NewHuffmanNode();
        scanf("%c %d", &T->c, &T->Weight);
        Weight[(int)T->c] = T->Weight;
        H->Data[++(H->Size)] = T;
    }
}

int WPL(HuffmanTree T, int Depth) {
    if (!T->Left && !T->Right)
        return (Depth * T->Weight);
    else /* 否则T一定有2个孩子 */
        return (WPL(T->Left, Depth + 1) + WPL(T->Right, Depth + 1));
}

int judge(char *str1, char *str2) {
    while (*str1++ == *str2++ && *(str1 - 1) && *(str2 - 1))
        ;
    if (*--str1 && *--str2)
        return 0;
    else
        return 1;
}

int main() {
    int N, M;
    scanf("%d", &N);
    MinHeap H = CreateHeap(N); /* 创建一个空的、容量为N的最小堆 */
    ReadData(H, N);            /* 将f[]读入H->Data[]中 */
    HuffmanTree T = Huffman(H); /* 建立Huffman树 */
    int CodeLen = WPL(T, 0);
    scanf("%d", &M);
    while (M--) {
        char c, code[MAXN][MAXN];
        int sum = 0, flag = 1;
        for (int i = 0; i < N; i++) {
            getchar();
            scanf("%c %s", &c, code[i]);
            int length = strlen(code[i]);
            if (length > N - 1) flag = 0;
            if (flag) sum += Weight[(int)c] * length;
        }
        if (!flag)
            printf("No\n");
        else if (sum != CodeLen)
            printf("No\n");
        else {
            int pre = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (i == j) continue;
                    if (judge(code[i], code[j])) {
                        pre = 1;
                        break;
                    }
                }
                if (pre) break;
            }
            if (pre)
                printf("No\n");
            else
                printf("Yes\n");
        }
    }
}

测试点	提示	结果	分数	耗时	内存
0	sample 有并列、多分支，有长度错、长度对但是前缀错；仅英文大写字符	答案正确	16	3 ms	196 KB
1	小写字母，01反、且2点对换；有2点重合	答案正确	7	4 ms	176 KB
2	几组编码不等长，都对；等长但前缀错误；code长度超过N	答案正确	3	3 ms	192 KB
3	最大N&M，code长度等于63	答案正确	1	40 ms	192 KB
4	最小N&M	答案正确	1	3 ms	192 KB
5	编码的字符是双数个，而提交采用的是等长编码。卡仅判断叶结点和度的错误算法	答案正确	1	4 ms	192 KB
6	非Huffman编码，但是正确；没有停在叶子上	答案正确	1	4 ms	196 KB