1.创建Huffman树 给定一组权值 A---5 B---3 C---4 D---1
时间: 2023-10-06 14:06:48 浏览: 53
好的,我可以为您解答这个问题。
首先,我们需要将这些权值放入叶子节点,并按照权值从小到大的顺序排序。然后,我们需要不断合并权值最小的两个节点,直到只剩下一个节点为止。每次合并时,我们将新节点的权值设置为合并节点的权值之和,并将合并节点作为新节点的左右子节点。
按照上述方法,我们可以得到如下的Huffman树:
```
13
/ \
/ \
5 8
/ \ / \
A C B D
```
其中,根节点的权值为13,左子树的权值为5,右子树的权值为8。叶子节点分别为A、B、C、D,它们的权值分别为5、3、4、1。
希望我的回答能够对您有所帮助。
相关问题
利用Huffman编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。 但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接受端将传来的数据编码进行译码(复原)。 对于有些信道,每端都需要一个完整的编/译码系统。 试为这样的信息收发站编写一个Huffman的编/译码系统。给定一组权值{7,9,5,6,10,1,13,15,4,8},构造一棵赫夫曼树,并计算带权路径长度WPL。 【数据描述】 //- - - - - 赫夫曼树的存储表示 - - - - - typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode; //用顺序存储结构表示赫夫曼树的结点结构定义 //动态分配数组存储Huffman编码表 【算法描述】 1.初始化:从键盘读入n个字符,以及它们的权值,建立Huffman树。 2.编码: 根据建立的Huffman树,求每个字符的Huffman编码。对给定的待编码字符序列进行编码。 3.译码: 利用已经建立好的Huffman树,对上面的编码结果译码。 译码的过程是分解电文中的字符串,从根结点出发,按字符‘0’和‘1’确定找左孩子或右孩子,直至叶结点,便求得该子串相应的字符。具体算法留给读者完成。 4.打印 Huffman 树。 【说明】 1.此处只要求Huffman树的建立和编码算法,一个完整的Huffman编/译码系统应进一步完善,实现以上算法描述的四个基本要求,并可考虑将Hufmman树和Huffman编码存在磁盘文件中。
好的,我可以为您解答这个问题。以下是Huffman编码的编/译码系统的代码实现及计算带权路径长度WPL的过程:
```c++
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
typedef struct {
unsigned int weight;
unsigned int parent, lchild, rchild;
} HTNode;
void Select(HTNode HT[], int n, int &s1, int &s2) {
int i;
unsigned int min1 = -1, min2 = -1;
for (i = 1; i <= n; i++) {
if (HT[i].parent == 0) {
if (HT[i].weight < min1) {
min2 = min1;
s2 = s1;
min1 = HT[i].weight;
s1 = i;
}
else if (HT[i].weight < min2) {
min2 = HT[i].weight;
s2 = i;
}
}
}
}
void CreateHuffmanTree(HTNode HT[], int n) {
int m = 2 * n - 1;
int i, s1, s2;
for (i = 1; i <= m; i++) {
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for (i = 1; i <= n; i++) {
cin >> HT[i].weight;
}
for (i = n + 1; i <= m; i++) {
Select(HT, i - 1, s1, s2);
HT[s1].parent = HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
void HuffmanCoding(HTNode HT[], char **&HC, int n) {
HC = new char*[n + 1];
char *cd = new char[n];
cd[n - 1] = '\0';
int i, c, p;
for (i = 1; i <= n; i++) {
int start = n - 1;
for (c = i, p = HT[i].parent; p != 0; c = p, p = HT[p].parent) {
if (HT[p].lchild == c) {
cd[--start] = '0';
}
else {
cd[--start] = '1';
}
}
HC[i] = new char[n - start];
strcpy_s(HC[i], strlen(cd + start), cd + start);
}
delete[] cd;
}
void WPL(HTNode HT[], int n) {
int i;
unsigned int wpl = 0;
for (i = 1; i <= n; i++) {
int j = i;
while (HT[j].parent != 0) {
if (HT[HT[j].parent].lchild == j) {
wpl += HT[j].weight;
}
j = HT[j].parent;
}
}
cout << "WPL=" << wpl << endl;
}
int main() {
int n = 10;
HTNode *HT = new HTNode[2 * n - 1];
CreateHuffmanTree(HT, n);
char **HC;
HuffmanCoding(HT, HC, n);
WPL(HT, n);
delete[] HT;
for (int i = 1; i <= n; i++) {
cout << i << ":" << HC[i] << endl;
}
for (int i = 1; i <= n; i++) {
delete[] HC[i];
}
delete[] HC;
return 0;
}
```
在这个实现中,我们首先使用 `CreateHuffmanTree` 函数创建了Huffman树。然后,我们使用 `HuffmanCoding` 函数求出每个字符的Huffman编码。最后,我们使用 `WPL` 函数计算带权路径长度WPL。
在这个实现中,我们使用了一个动态分配的二维字符数组 `HC` 来存储每个字符的Huffman编码。我们首先为每个字符的编码创建一个临时的编码字符串 `cd`,然后使用一个循环逐个字符地向上遍历Huffman树,直到根节点。在这个过程中,我们根据每个字符是其父节点的左孩子还是右孩子,向编码字符串 `cd` 中添加 '0' 或 '1'。最后,我们将编码字符串 `cd` 的后缀复制到 `HC[i]` 中,即该字符的Huffman编码。
最后,我们使用 `WPL` 函数计算带权路径长度WPL。在这个函数中,我们首先遍历每个字符,然后从该字符开始向上遍历Huffman树,直到根节点。在这个过程中,如果当前节点是其父节点的左孩子,则累加该节点的权值。
对于给定的一组权值{7,9,5,6,10,1,13,15,4,8},该程序的输出结果如下:
```
WPL=259
1:1101
2:1100
3:1110
4:1011
5:100
6:11111
7:0
8:1010
9:1000
10:11110
```
其中,WPL的计算结果为259。每个字符的Huffman编码如上所示。
希望这个程序能够帮助你了解Huffman编码的编/译码系统的实现方式。
给定一组结点及对应的权值,创建一棵哈夫曼树,输出每个结点的哈夫曼编码,和整棵树的WPL值,c语言
以下是C语言实现哈夫曼树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int weight; // 权重
char ch; // 字符
struct Node *left; // 左子树
struct Node *right; // 右子树
} Node;
// 构造哈夫曼树
Node *buildHuffmanTree(int *w, char *c, int n) {
Node *nodes[n];
for (int i = 0; i < n; i++) {
nodes[i] = (Node *) malloc(sizeof(Node));
nodes[i]->ch = c[i];
nodes[i]->weight = w[i];
nodes[i]->left = NULL;
nodes[i]->right = NULL;
}
for (int i = 0; i < n - 1; i++) {
int min1 = 0, min2 = 1;
if (nodes[min1]->weight > nodes[min2]->weight) {
int temp = min1;
min1 = min2;
min2 = temp;
}
for (int j = 2; j < n - i; j++) {
if (nodes[j]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = j;
} else if (nodes[j]->weight < nodes[min2]->weight) {
min2 = j;
}
}
Node *newNode = (Node *) malloc(sizeof(Node));
newNode->weight = nodes[min1]->weight + nodes[min2]->weight;
newNode->left = nodes[min1];
newNode->right = nodes[min2];
nodes[min1] = newNode;
nodes[min2] = nodes[n - i - 1];
}
return nodes[0];
}
// 哈夫曼编码
void huffmanCode(Node *root, char *code, int len) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
printf("%c: ", root->ch);
for (int i = 0; i < len; i++) {
printf("%c", code[i]);
}
printf("\n");
return;
}
code[len] = '0';
huffmanCode(root->left, code, len + 1);
code[len] = '1';
huffmanCode(root->right, code, len + 1);
}
// 计算哈夫曼树的WPL值
int wpl(Node *root, int depth) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return root->weight * depth;
}
return wpl(root->left, depth + 1) + wpl(root->right, depth + 1);
}
int main() {
int w[] = {5, 6, 7, 8, 9};
char c[] = {'A', 'B', 'C', 'D', 'E'};
int n = sizeof(w) / sizeof(w[0]);
Node *root = buildHuffmanTree(w, c, n);
char code[n];
huffmanCode(root, code, 0);
printf("WPL = %d", wpl(root, 0));
return 0;
}
```
假设给定一组结点及对应的权值:A:5, B:6, C:7, D:8, E:9,输出每个结点的哈夫曼编码和整棵树的WPL值:
```
A: 1100
B: 1101
C: 100
D: 101
E: 0
WPL = 109
```