使用C语言进行实现 ， 程序实验报告待完成！

1. (其它) 请同学们完成综合设计性实验内容，题目可以从以下选择。（二选一）

要求：将以上题目完成并填写综合设计性实验报告，报告最后附加上源代码。完成后将报告按照正确的命名格式上传

第一题

‍

输入n个字母及其权值，对其进行哈夫曼编码。

‍

代码实现：

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
105
106
107
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 50

// 结点结构体
struct Node {
    char letter; // 字母
    int freq;    // 频率
    struct Node *left, *right; // 左右子节点
};

// 哈夫曼树的结构体
struct HuffmanTree {
    struct Node *root;
};

// 创建一个新结点
struct Node* newNode(char letter, int freq) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->letter = letter;
    node->freq = freq;
    node->left = node->right = NULL;
    return node;
}

// 创建哈夫曼树
struct HuffmanTree* buildHuffmanTree(char letters[], int freqs[], int size) {
    // 创建初始节点列表
    struct Node *nodes[MAX_NODES];
    for (int i = 0; i < size; ++i) {
        nodes[i] = newNode(letters[i], freqs[i]);
    }

    // 构建哈夫曼树
    while (size > 1) {
        int min1 = 0, min2 = 1;

        // 找出频率最小的两个节点
        for (int i = 2; i < size; ++i) {
            if (nodes[i]->freq < nodes[min1]->freq) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->freq < nodes[min2]->freq) {
                min2 = i;
            }
        }

        // 创建新节点作为父节点
        struct Node* mergedNode = newNode('$', nodes[min1]->freq + nodes[min2]->freq);
        mergedNode->left = nodes[min1];
        mergedNode->right = nodes[min2];

        // 将已经处理过的节点移至列表末尾
        nodes[min1] = mergedNode;
        nodes[min2] = nodes[size - 1];
        size--;
    }

    // 创建哈夫曼树并返回
    struct HuffmanTree* tree = (struct HuffmanTree*)malloc(sizeof(struct HuffmanTree));
    tree->root = nodes[0];
    return tree;
}

// 打印哈夫曼编码
void printCodes(struct Node* root, int arr[], int top) {
    // 达到叶子节点后打印编码
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if (!(root->left) && !(root->right)) {
        printf("%c: ", root->letter);
        for (int i = 0; i < top; ++i) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

int main() {
    int n;
    printf("请输入字符的个数: ");
    scanf("%d", &n);

    char letters[MAX_NODES];
    int freqs[MAX_NODES];

    printf("请输入字符和频率:\n");
    for (int i = 0; i < n; ++i) {
        scanf(" %c %d", &letters[i], &freqs[i]);
    }

    struct HuffmanTree* tree = buildHuffmanTree(letters, freqs, n);

    int codes[MAX_NODES], top = 0;
    printf("Huffman Codes:\n");
    printCodes(tree->root, codes, top);

    return 0;
}

‍

运行结果演示：

image​

第二题

‍

用连通网中的顶点表示城市，边上的权值表示在这两个两个城市建立通信所花费的代价。求要连通所有的城市所花费的最小代价，要求构造最小生成树。

‍

代码实现：

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
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#include <stdlib.h>

#define MAX_VERTICES 20

int graph[MAX_VERTICES][MAX_VERTICES];
int numVertices;

int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < numVertices; v++) {
        if (mstSet[v] == false && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }

    return min_index;
}

void printMST(int parent[]) {
    printf("Edge \tWeight\n");
    for (int i = 1; i < numVertices; i++)
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}

void primMST() {
    int parent[MAX_VERTICES];
    int key[MAX_VERTICES];
    bool mstSet[MAX_VERTICES];

    for (int i = 0; i < numVertices; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

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

    for (int count = 0; count < numVertices - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < numVertices; v++) {
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printMST(parent);
}

int main() {
    printf("请输入城市的个数: ");
    scanf("%d", &numVertices);

    printf("请输入城市的成本矩阵:\n");
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    printf("最小生成的树为:\n");
    primMST();

    return 0;
}

运行结果演示

image​

‍

‍

‍