Mki's Blog

数据结构(七):哈夫曼树和并查集操作

题目描述

题目要求

05-树8 File Transfer (25 分) 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?

输入格式:

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.

输出格式:

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.

输入样例1:

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

输出样例1:

no no yes There are 2 components.

输入样例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

输出样例2:

no no yes yes The network is connected.

基础知识

哈夫曼树

哈夫曼树(Huffman Tree),又叫最优二叉树,该树的带权路径(WPL 节点到根的距离乘结点权值)是所有相同结点构成的二叉树里面最小的。显然,类似于频率,节点出现的次数越多离根节点越近。

而哈夫曼树的作用是什么呢,一般来说会和编码的问题相关联。比如一个一万字的文件,假如每个字都是用八个字节来表示,那么这个文件就有八万个字节,倘若我们把出现最多的一个字用四个字节来表示,那么就大大减小了文件的大小。

哈夫曼树构造

首先,我们肯定有一堆东西用来构造,这时要把他们的权值拿出来。 (这个图上的“数字”其实是指权值,忘记改过来了) 1.jpg

找两个最小的权值来造一棵小树 2.jpg

重复操作 3.jpg

4.jpg

在某些情况下,我们可能遇到最小的两个数中有一个数的权值出现了两次,这个时候其实无论选哪个都是可以的,它们的带权路径和最终还是一样的。比如上面的那个例子还有一种结果。 5.jpg

代码实现

这里要用到上一篇讲到的堆的操作

typedef struct TreeNode * HuffmanTree;

struct TreeNode {
    int Weight;
    HuffmanTree Left, Right;
};
HuffmanTree Huffman(MinHeap) {
    int i;
    HuffmanTree T;
    BuildMinHeap(H);  //先初始化一个最小堆
    for (i = 1; i < H->Size; i++) {
        T = malloc(sizeof(struct TreeNode)); 
        T->Left = DeleteMin(H);  //弹出最小值,调整堆,使其还是最小堆
        T->Right = DeleteMIn(H); //弹出最小值
        T->Weight = T->Left->Weight + T->Right->Weight;
        Insert(H, T);            //把新的节点放进去
    }
    T = DeletaMin(H);            //重新把T变成最小的节点
    return T;
}

并查集

并查集是用在集合的相关操作里面的,在最开始的题目里边,要求给出了一堆数字,然后建立/查看每两个数字之间的关系。(是否是同一个集合内的,然后整个集合有几个最小划分)

在此处,我们用数组来实现并查集的操作。首先,数组有下标,0-N,这是一个可以加以利用的好东西,我们可以用0-N表示N个不同的节点,在现实中就是n台计算机或者其他什么,反正就是集合里的元素。然后用这个下标的键值表示父节点的位置(即父节点的下标)。

此时我们就会考虑一个问题,假如1的父节点是2,2的父节点是3,3的父节点是4……以此类推,我们在查找父节点的时候就会很麻烦,虽然这种情况有点极端,但是,出现二叉树严重失衡的状况也是很有可能的。此时,重新审题,我们在这里是做一个集合的问题,集合里每个元素都是平等的,那么,不妨跳出二叉树的限制,将多个节点指向同一个节点(这个节点是随便的,只要是集合里一个就好),来表示它们的关系。这种方法就叫做路径压缩。

路径压缩

一般我们在做并查集的时候,对于节点连接会用按秩归并的方法,但是个人不太喜欢这种操作,况且在大量重复查询父节点的时候,路径压缩能做到更省空间和时间,何乐而不为呢?

路径压缩的代码

这个操作可以说是很妙了。

SetName Find(SetType S, ElementType X) {
    if (S[X] < 0)
        return X;
    else
        return S[X] = Find(S, S[X]);  //返回的永远是最前面的父节点
}

AC代码

#include<stdio.h>
#define MaxSize 1000
typedef int ElementType;
typedef int SetName;
typedef ElementType SetType[MaxSize];

/*连接*/
void Union(SetType S, SetName Root1, SetName Root2) {
    S[Root1] = Root2;
}
/*查找父节点顺便路径压缩*/
SetName Find(SetType S, ElementType X) {
    if (S[X] < 0)
        return X;   //S[X] < 0 表示这是一个总父节点或者一个独立的节点
    else
        return S[X] = Find(S, S[X]);  //尾递归,永远是总父节点返回并赋值
}
/*输入连接*/
void Input_connection(SetType S) {
    ElementType u, v;
    SetName Root1, Root2;
    scanf_s("%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_s("%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;  //counter是不同的总父节点数,它代表了划分数目
    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);

}
/*初始化数组*/
void Initialization(SetType S, int n) {
    for (int i = 0; i < n; i++) {
        S[i] = -1;
    }
}
int main(void) {
    SetType S;
    int n;
    char in;
    scanf_s("%d\n", &n);
    Initialization(S, n);
    do {
        scanf_s("%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;
}

写在最后

明天会把计网的东西整理下,我感觉还要去复习下前面的搜索树等内容。