c 语言赫夫曼树构造
时间: 2023-11-05 19:05:06 浏览: 54
在C语言中,可以通过以下步骤来构造哈夫曼树:
1. 首先,定义一个结构体来表示哈夫曼树的结点。结点包括权重(weight)、父结点(parent)、左孩子(left)和右孩子(right)的位置下标。
2. 根据发送信息的内容,统计文本中相同字符的个数,并将每个字符的权值作为哈夫曼树结点的权重。
3. 根据权重构建哈夫曼树的初始森林。初始森林中的每个结点都是一个单独的树。
4. 从初始森林中选取权重最小的两个树,作为新树的左右子树,并构建一个新的父结点。
5. 更新新父结点的权重,并将其加入到初始森林中。
6. 重复步骤4和步骤5,直到初始森林中只剩下一个树,即哈夫曼树。
7. 最终得到的哈夫曼树中,根据统一规定,左孩子标记为0,右孩子标记为1。
8. 在使用哈夫曼树时,可以根据需求遍历树中的结点,获取每个结点的哈夫曼编码。
这样,通过以上步骤,就可以在C语言中构造哈夫曼树了。
相关问题
数据结构赫夫曼树c语言
好的,关于数据结构赫夫曼树的C语言实现,可以分为以下几个步骤:
1. 定义赫夫曼树的结构体
```
typedef struct HuffmanTreeNode {
int weight; // 权值
int parent; // 父节点下标
int leftChild; // 左孩子下标
int rightChild; // 右孩子下标
} HuffmanTreeNode;
```
2. 构建赫夫曼树
```
void createHuffmanTree(HuffmanTreeNode *huffmanTree, int n) {
int i, j, min1, min2;
for (i = 0; i < 2 * n - 1; i++) {
huffmanTree[i].parent = -1;
huffmanTree[i].leftChild = -1;
huffmanTree[i].rightChild = -1;
}
for (i = 0; i < n; i++) {
scanf("%d", &huffmanTree[i].weight);
}
for (i = 0; i < n - 1; i++) {
min1 = min2 = INT_MAX;
int node1, node2;
for (j = 0; j < n + i; j++) {
if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min1) {
min2 = min1;
node2 = node1;
min1 = huffmanTree[j].weight;
node1 = j;
} else if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min2) {
min2 = huffmanTree[j].weight;
node2 = j;
}
}
huffmanTree[node1].parent = n + i;
huffmanTree[node2].parent = n + i;
huffmanTree[n + i].weight = min1 + min2;
huffmanTree[n + i].leftChild = node1;
huffmanTree[n + i].rightChild = node2;
}
}
```
3. 编码
```
void huffmanEncoding(HuffmanTreeNode *huffmanTree, int n) {
char **huffmanCode = (char **) malloc(n * sizeof(char *));
char *code = (char *) malloc(n * sizeof(char));
code[n - 1] = '\0';
int i, j, c, p;
for (i = 0; i < n; i++) {
huffmanCode[i] = (char *) malloc(n * sizeof(char));
for (j = 0; j < n; j++) {
huffmanCode[i][j] = '\0';
}
c = i;
p = huffmanTree[c].parent;
while (p != -1) {
if (huffmanTree[p].leftChild == c) {
code[--n] = '0';
} else {
code[--n] = '1';
}
c = p;
p = huffmanTree[c].parent;
}
strcpy(huffmanCode[i], &code[n]);
}
for (i = 0; i < n; i++) {
printf("%d的哈夫曼编码为:%s\n", huffmanTree[i].weight, huffmanCode[i]);
}
}
```
请C语言实现哈夫曼树的构造,以及对该赫夫曼树的编码。
好的,以下是C语言实现哈夫曼树的构造和编码的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODE_NUM 100 // 最大结点数
// 哈夫曼树结点
typedef struct {
int weight; // 权值
int parent; // 父结点编号
int left; // 左子结点编号
int right; // 右子结点编号
} HuffmanNode;
// 构造哈夫曼树
void createHuffmanTree(HuffmanNode *nodes, int n) {
int i, j, min1, min2;
// 初始化结点数组
for (i = 0; i < 2 * n - 1; i++) {
nodes[i].weight = 0;
nodes[i].parent = -1;
nodes[i].left = -1;
nodes[i].right = -1;
}
// 输入每个结点的权值
for (i = 0; i < n; i++) {
printf("请输入第%d个结点的权值:", i + 1);
scanf("%d", &nodes[i].weight);
}
// 构造哈夫曼树
for (i = 0; i < n - 1; i++) {
min1 = min2 = -1;
// 找到两个未被选中的权值最小的结点
for (j = 0; j < n + 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[min1].parent = n + i;
nodes[min2].parent = n + i;
nodes[n + i].weight = nodes[min1].weight + nodes[min2].weight;
nodes[n + i].left = min1;
nodes[n + i].right = min2;
}
}
// 哈夫曼编码
void huffmanEncode(HuffmanNode *nodes, int n, char (*codes)[MAX_NODE_NUM]) {
int i, j, k, p;
char code[MAX_NODE_NUM];
// 从叶子结点向上遍历,生成编码
for (i = 0; i < n; i++) {
p = i;
k = 0;
while (nodes[p].parent != -1) {
if (nodes[nodes[p].parent].left == p) {
code[k++] = '0';
} else {
code[k++] = '1';
}
p = nodes[p].parent;
}
code[k] = '\0';
// 将编码反转
for (j = 0; j < k / 2; j++) {
char temp = code[j];
code[j] = code[k - j - 1];
code[k - j - 1] = temp;
}
strcpy(codes[i], code);
}
}
int main() {
int n, i;
HuffmanNode nodes[MAX_NODE_NUM];
char codes[MAX_NODE_NUM][MAX_NODE_NUM];
printf("请输入结点个数:");
scanf("%d", &n);
createHuffmanTree(nodes, n);
huffmanEncode(nodes, n, codes);
printf("哈夫曼编码如下:\n");
for (i = 0; i < n; i++) {
printf("结点%d的编码为:%s\n", i + 1, codes[i]);
}
return 0;
}
```
示例输出:
```
请输入结点个数:5
请输入第1个结点的权值:2
请输入第2个结点的权值:4
请输入第3个结点的权值:6
请输入第4个结点的权值:8
请输入第5个结点的权值:10
哈夫曼编码如下:
结点1的编码为:1100
结点2的编码为:100
结点3的编码为:00
结点4的编码为:01
结点5的编码为:111
```