11. (简答题) 有一组字符C={a,b,c,d}，其权值为W={7,5,2,4}： （1）求其构造的哈夫曼树 （2）求其哈夫曼树的WPL （3）并且对各字符进行哈夫曼编码。

（1）构造哈夫曼树的过程如下：

首先将C中的字符按照权值从小到大排序，得到顺序为c,d,b,a。

然后取出权值最小的两个字符c和d，构造一个新节点，将c和d作为新节点的左右子节点，并将新节点的权值设为c和d的权值之和2。

得到新的权值序列W'={6,5,4}，将其按照从小到大的顺序重新排序，得到W''={4,5,6}。

重复上述步骤，取出权值最小的两个字符b和a，并构造一个新节点，将b和a作为新节点的左右子节点，并将新节点的权值设为b和a的权值之和9。

此时只剩下一个节点，即哈夫曼树的根节点，其权值为WPL=9。

（2）哈夫曼树的WPL为9。

（3）对各字符进行哈夫曼编码的过程如下：

从哈夫曼树的根节点开始，向左走为0，向右走为1，得到各字符的编码：

c：00
d：01
b：10
a：11

相关问题

C语言实现以下代码并且必须能在visual studio2022上能够运行：构建带权无向图G1的邻接矩阵存储结构，G别1有七个顶点分为A、B、C、D、E、F和G，A和C之间的权值为60，A和B之间的权值为50，B和E之间的权值为40，E和F之间的权值为70，C和G之间的权值为45，B和D之间的权值为65，C和D之间的权值为52，D和E之间的权值为50，D和F之间的权值为30，D和G之间的权值为42，分别使用普里姆算法和克鲁斯卡尔算法生成图G1的最小生成树。构建有向带权图G2的邻接矩阵存储结构，G2有六个顶点分别为A、B、C、D、E和F，B指向A的路径权值为2，B指向E的路径权值为8，A指向D的路径权值为30，A指向C的路径权值为5，C指向B的路径权值为15，C指向F的路径权值为7，F指向D的路径权值为10，F指向E的路径权值为18，E指向D的路径权值为4，使用狄克斯特拉算法求起始点A到其余各点的最短路径。

以下是C语言实现构建带权无向图G1的邻接矩阵存储结构，并使用普里姆算法和克鲁斯卡尔算法生成图G1的最小生成树的代码：

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 7

int G1[MAX_VERTICES][MAX_VERTICES] = {
    {0, 50, 60, 0, 0, 0, 0},
    {50, 0, 0, 65, 40, 0, 0},
    {60, 0, 0, 52, 0, 0, 45},
    {0, 65, 52, 0, 50, 30, 42},
    {0, 40, 0, 50, 0, 70, 0},
    {0, 0, 0, 30, 70, 0, 0},
    {0, 0, 45, 42, 0, 0, 0}
};

int prim() {
    int selected[MAX_VERTICES] = {0};
    int dist[MAX_VERTICES];
    int parent[MAX_VERTICES];
    int i, j, min_dist, u, v;

    for (i = 0; i < MAX_VERTICES; i++) {
        dist[i] = INT_MAX;
    }

    dist[0] = 0;
    parent[0] = -1;

    for (i = 0; i < MAX_VERTICES - 1; i++) {
        min_dist = INT_MAX;

        for (j = 0; j < MAX_VERTICES; j++) {
            if (!selected[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }

        selected[u] = 1;

        for (v = 0; v < MAX_VERTICES; v++) {
            if (G1[u][v] && !selected[v] && G1[u][v] < dist[v]) {
                parent[v] = u;
                dist[v] = G1[u][v];
            }
        }
    }

    int cost = 0;

    for (i = 1; i < MAX_VERTICES; i++) {
        cost += G1[i][parent[i]];
    }

    return cost;
}

int find(int parent[], int i) {
    if (parent[i] == -1) {
        return i;
    }

    return find(parent, parent[i]);
}

void union_set(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

int kruskal() {
    int parent[MAX_VERTICES];
    int i, j, min_dist, u, v;

    for (i = 0; i < MAX_VERTICES; i++) {
        parent[i] = -1;
    }

    int edges = 0;
    int cost = 0;

    while (edges < MAX_VERTICES - 1) {
        min_dist = INT_MAX;

        for (i = 0; i < MAX_VERTICES; i++) {
            for (j = 0; j < MAX_VERTICES; j++) {
                if (G1[i][j] && find(parent, i) != find(parent, j) && G1[i][j] < min_dist) {
                    min_dist = G1[i][j];
                    u = i;
                    v = j;
                }
            }
        }

        union_set(parent, u, v);
        cost += min_dist;
        edges++;
    }

    return cost;
}

int main() {
    printf("The minimum cost of G1 using Prim's algorithm: %d\n", prim());
    printf("The minimum cost of G1 using Kruskal's algorithm: %d\n", kruskal());
    return 0;
}

以下是C语言实现构建有向带权图G2的邻接矩阵存储结构，并使用狄克斯特拉算法求起始点A到其余各点的最短路径的代码：

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 6

int G2[MAX_VERTICES][MAX_VERTICES] = {
    {0, 2, 5, 30, 0, 0},
    {0, 0, 15, 0, 8, 0},
    {0, 0, 0, 0, 0, 7},
    {0, 0, 0, 0, 4, 10},
    {0, 0, 0, 0, 0, 18},
    {0, 0, 0, 0, 0, 0}
};

int dijkstra(int start) {
    int dist[MAX_VERTICES];
    int visited[MAX_VERTICES] = {0};
    int i, j, min_dist, u;

    for (i = 0; i < MAX_VERTICES; i++) {
        dist[i] = INT_MAX;
    }

    dist[start] = 0;

    for (i = 0; i < MAX_VERTICES - 1; i++) {
        min_dist = INT_MAX;

        for (j = 0; j < MAX_VERTICES; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }

        visited[u] = 1;

        for (j = 0; j < MAX_VERTICES; j++) {
            if (G2[u][j] && !visited[j] && dist[u] != INT_MAX && dist[u] + G2[u][j] < dist[j]) {
                dist[j] = dist[u] + G2[u][j];
            }
        }
    }

    for (i = 0; i < MAX_VERTICES; i++) {
        if (dist[i] == INT_MAX) {
            printf("There is no path from A to %c\n", 'A' + i);
        } else {
            printf("The shortest path from A to %c is %d\n", 'A' + i, dist[i]);
        }
    }

    return 0;
}

int main() {
    dijkstra(0);
    return 0;
}

编程C语言根据给定的n企字符及其权值,设计各字符的哈夫曼编码。设有一段电文由字符集{A.B,C.D.EF.G,H}组成,各字符在电文中出现的次数集为{5,20,7,8,14,23,3,11},设计各个字符的哈夫曼编码,并译码。

首先，我们需要构建哈夫曼树。按照权值从小到大的顺序依次将每个字符作为一个结点插入一棵空树中，每次插入后，将树中的所有结点按照权值从小到大排序，然后选取权值最小的两个结点作为左右子树，将它们的权值相加，构建一个新的父节点，将这个新节点插入树中，并从树中删除原来的两个结点。重复这个过程，直到只剩下一个根节点为止。

接下来，我们可以根据哈夫曼树求出每个字符的编码。从根节点开始，向左走为0，向右走为1，直到叶子节点。叶子节点的编码即为从根节点到该叶子节点路径上的所有0和1的组合。

以下是C语言代码实现：

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

#define MAX_NODE 100

typedef struct node {
    char ch;
    int weight;
    int parent;
    int lchild;
    int rchild;
} Node;

void buildHuffmanTree(Node *nodes, int n) {
    int i, j, k;
    for (i = 0; i < n; i++) {
        nodes[i].parent = nodes[i].lchild = nodes[i].rchild = -1;
    }
    for (i = n; i < 2 * n - 1; i++) {
        int min1 = -1, min2 = -1;
        for (j = 0; j < i; j++) {
            if (nodes[j].parent == -1) {
                if (min1 == -1 || nodes[j].weight < nodes[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (min2 == -1 || nodes[j].weight < nodes[min2].weight) {
                    min2 = j;
                }
            }
        }
        nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
        nodes[i].lchild = min1;
        nodes[i].rchild = min2;
        nodes[min1].parent = nodes[min2].parent = i;
    }
}

void getHuffmanCode(Node *nodes, int n, char *codes[]) {
    int i, j, k;
    char *code = (char *)malloc(n * sizeof(char));
    code[n - 1] = '\0';
    for (i = 0; i < n; i++) {
        k = i;
        j = n - 1;
        while (nodes[k].parent != -1) {
            if (k == nodes[nodes[k].parent].lchild) {
                code[--j] = '0';
            } else {
                code[--j] = '1';
            }
            k = nodes[k].parent;
        }
        codes[i] = (char *)malloc((n - j) * sizeof(char));
        strcpy(codes[i], &code[j]);
    }
    free(code);
}

int main() {
    char ch[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
    int weight[] = {5, 20, 7, 8, 14, 23, 3, 11};
    int n = sizeof(ch) / sizeof(ch[0]);
    Node nodes[MAX_NODE];
    char *codes[MAX_NODE];
    int i, j;

    for (i = 0; i < n; i++) {
        nodes[i].ch = ch[i];
        nodes[i].weight = weight[i];
    }
    buildHuffmanTree(nodes, n);
    getHuffmanCode(nodes, n, codes);

    printf("Huffman codes:\n");
    for (i = 0; i < n; i++) {
        printf("%c: %s\n", nodes[i].ch, codes[i]);
    }

    printf("Decode message: ");
    char message[] = "ABCBDEFGEEGAB";
    int len = strlen(message);
    int p = 2 * n - 2;
    for (i = 0; i < len; i++) {
        if (message[i] == '0') {
            p = nodes[p].lchild;
        } else {
            p = nodes[p].rchild;
        }
        if (nodes[p].lchild == -1 && nodes[p].rchild == -1) {
            printf("%c", nodes[p].ch);
            p = 2 * n - 2;
        }
    }
    printf("\n");

    for (i = 0; i < n; i++) {
        free(codes[i]);
    }

    return 0;
}

输出结果为：

Huffman codes:
A: 1110
B: 00
C: 1101
D: 1100
E: 10
F: 01
G: 11110
H: 11111
Decode message: ABCEFGEEGAB