c语言创建哈夫曼数
时间: 2023-12-03 12:04:43 浏览: 82
哈夫曼树的创建过程可以分成以下几步:
1. 统计字符出现频率并存储为一个数组或链表
2. 将数组或链表按照出现频率从小到大进行排序
3. 取出频率最小的两个节点,合并成一个新的节点,其权值为两个节点的权值之和
4. 将新节点插入到数组或链表中,保持有序
5. 重复步骤 3 和 4,直到只剩下一个节点,即为哈夫曼树的根节点
以下是一个简单的 C 语言程序实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 哈夫曼树节点定义
typedef struct {
char data; // 节点存储的字符
int weight; // 节点的权值(出现频率)
int parent, lchild, rchild; // 父节点、左子节点、右子节点的下标
} HuffmanNode, *HuffmanTree;
// 创建哈夫曼树
void createHuffmanTree(HuffmanTree *tree, int n) {
// 创建 n 个叶子节点
*tree = (HuffmanTree) malloc(sizeof(HuffmanNode) * (2 * n - 1));
for (int i = 0; i < n; i++) {
getchar();
printf("请输入第 %d 个字符及其出现频率(格式:字符 频率):", i + 1);
scanf("%c%d", &((*tree)[i].data), &((*tree)[i].weight));
(*tree)[i].parent = -1;
(*tree)[i].lchild = -1;
(*tree)[i].rchild = -1;
}
// 创建 n-1 个非叶子节点
for (int i = n; i < 2 * n - 1; i++) {
int min1 = -1, min2 = -1;
for (int j = 0; j < i; j++) {
if ((*tree)[j].parent == -1) {
if (min1 == -1) {
min1 = j;
} else if (min2 == -1) {
min2 = j;
} else {
if ((*tree)[j].weight < (*tree)[min1].weight) {
min2 = min1;
min1 = j;
} else if ((*tree)[j].weight < (*tree)[min2].weight) {
min2 = j;
}
}
}
}
(*tree)[min1].parent = i;
(*tree)[min2].parent = i;
(*tree)[i].lchild = min1;
(*tree)[i].rchild = min2;
(*tree)[i].weight = (*tree)[min1].weight + (*tree)[min2].weight;
}
}
int main() {
int n;
printf("请输入字符个数:");
scanf("%d", &n);
HuffmanTree tree;
createHuffmanTree(&tree, n);
// 输出哈夫曼树的结构
printf("哈夫曼树的结构如下:\n");
for (int i = 0; i < 2 * n - 1; i++) {
printf("%c %d %d %d %d\n", tree[i].data, tree[i].weight, tree[i].parent, tree[i].lchild, tree[i].rchild);
}
return 0;
}
```
注意,在以上代码中,我们假设输入的字符都是单字节字符。如果需要支持多字节字符,需要对输入和存储方式进行相应的修改。