哈夫曼编码译码，中序遍历
从键盘接收一串电文字符，输出对应的编码，同时，能翻译由哈夫曼编码生成的代码串，输出对应的电文字符串。用c语言实现，设计要求：
（1）构造一棵哈夫曼树；
（2）输出哈夫曼树的中序遍历序列（字符及其权值）；
（3）实现哈夫曼编码，并用哈夫曼编码生成的代码串进行译码；
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_HT 100
//定义哈夫曼树节点结构体
struct MinHeapNode {
char data;
unsigned freq;
struct MinHeapNode *left, *right;
};
//定义哈夫曼树结构体
struct MinHeap {
unsigned size;
unsigned capacity;
struct MinHeapNode **array;
};
//创建一个新的哈夫曼树节点
struct MinHeapNode* newNode(char data, unsigned freq) {
struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}
//创建一个新的最小堆
struct MinHeap* createMinHeap(unsigned capacity) {
struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));
return minHeap;
}
//交换两个哈夫曼树节点
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
//最小堆调整函数
void minHeapify(struct MinHeap* minHeap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
smallest = left;
if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
smallest = right;
if (smallest != idx) {
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
//检查是否只有一个节点
int isSizeOne(struct MinHeap* minHeap) {
return (minHeap->size == 1);
}
//从最小堆中取出最小值
struct MinHeapNode* extractMin(struct MinHeap* minHeap) {
struct MinHeapNode* temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
//插入节点到最小堆中
void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {
++minHeap->size;
int i = minHeap->size - 1;
while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = minHeapNode;
}
忘采纳
如果对你有帮助还请采纳一下蟹蟹您了，
#include <stdio.h>
#include <stdlib.h>
#define MAX_LEN 1000
// 哈夫曼编码
void huffman_encode(int *data, int len, int *code) {
int i, j, code_len = 0;
for (i = 0; i < len; i++) {
int symbol = data[i];
for (j = 0; j < code_len; j++) {
if (symbol == code[j]) {
break;
}
}
if (j == code_len) {
code[code_len++] = symbol;
}
}
*code = code_len;
}
// 哈夫曼译码
int huffman_decode(int *code, int len, int *data) {
int i, j, code_len = 0;
for (i = 0; i < len; i++) {
int symbol = code[i];
for (j = 0; j < code_len; j++) {
if (symbol == code[j]) {
break;
}
}
if (j == code_len) {
data[i] = code[j];
code_len++;
}
}
return code_len;
}
int main() {
int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int len = sizeof(data) / sizeof(int);
int code[MAX_LEN];
int i, j, len_decoded;
// 哈夫曼编码
huffman_encode(data, len, code);
// 输出编码后的数据
printf("Encoded data: ");
for (i = 0; i < len; i++) {
printf("%d ", code[i]);
}
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node
{
int weight;
char data;
int parent;
int Lchild;
int Rchild;
}Node;
typedef struct
{
int number;
char s;
}Data;
typedef struct
{
char code[30];
int cnt;
}codetype;
char c;
int num = 0;
int n = 0;
Data d[100];
void creat_huffman();
void output(Node *HT);
void code(Node *HT, codetype *codeFile, int n);
void Decode(Node *HT, int n);
int main()
{
creat_huffman();
Node *HT = (Node*)malloc(sizeof(Node)*(2*n-1));
for(int i = 0; i < n; i++)
{
HT[i].parent = -1;
HT[i].Lchild = -1;
HT[i].Rchild = -1;
HT[i].data = d[i].s;
HT[i].weight = d[i].number;
}
for(int i = n; i < 2*n-1; i++)
{
HT[i].data = '#';
HT[i].parent = -1;
HT[i].Lchild = -1;
HT[i].Rchild = -1;
HT[i].weight = -1;
}
// for(int i = 0; i < 2*n-1; i++)
// {
// printf("---%d---\n", HT[i].weight);
// }
for(int i=n; i<2*n-1; i++)
{
int min = 99999;//最小值
int cmin = 99999;//次小值
int m = 0; c = 0;//记录最小值和次小值的下标
for (int j = 0; j<i; j++)
{
if (HT[j].parent == -1)
if (HT[j].weight<min)
{
c = m;
cmin = min;
min = HT[j].weight;
m = j;
}
else if (HT[j].weight<cmin)
{
cmin = HT[j].weight;
c = j;
}
}
HT[i].weight = min + cmin;//hfmTree[m].weight+hfmTree[c].weight;
//hfmTree[i].CH = ' ';//方便整体输出加个字符空格
HT[i].Lchild = m;
HT[i].Rchild = c;
HT[m].parent = i;
HT[c].parent = i;
HT[i].parent = -1;//新结点的双亲没有为-1
}
// for(int i = 0; i < 2*n-1; i++)
// {
// printf("---%d---\n", HT[i].weight);
// }
output(HT);
printf("各字符编码如下:\n");
codetype *codeFile;
codeFile = (codetype *)malloc(sizeof(codetype)*n);
code(HT, codeFile, n);
for (int i = 0; i<n; i++)
{
printf("%c字符的编码: ", HT[i].data);
printf("%s", codeFile[i].code + codeFile[i].cnt);
printf("\n");
}
Decode(HT, n);
}
void creat_huffman()
{
Node *p;
p = (Node*)malloc(sizeof(Node));
p ->parent = NULL;
int count[100] = {};
while((c = getchar()) != '\n') ///读取输入的字符
{
num++;
count[c-65]++;
}
for(int i=0; i<100; i++)
{
if(count[i] != 0)
{
d[n].number = count[i];
d[n].s = char(i+65);
n++;
}
}
}
/Huffman树构建完成
///打印哈夫曼树的结构
void output(Node *HT)
{
printf("Huffman Tree List:\n");
printf("Number\tData\tWeight\tParent\tLchild\tRchild\n");
for(int i=0; i<2*n-1; i++)
{
printf("%d\t%c\t%d\t%d\t%d\t%d\n", i,HT[i].data, HT[i].weight,HT[i].parent, HT[i].Lchild, HT[i].Rchild);
}
}
///对节点进行编码
void code(Node *HT, codetype *codeFile, int n)
{
int i, p, c;
codetype S;
for (i = 0; i<n; i++)//对N的字符进行编码
{
c = i;
p = HT[c].parent;
S.cnt = n;//把cnt的值初始化为N，后续再用数组(S->code[])存字符的编码时,倒着存
S.code[n] = '\0';
while (p != -1)
{
if (HT[p].Lchild == c)
S.code[--S.cnt] = '0';
else//否则存‘1’
S.code[--S.cnt] = '1';
c = p;
p = HT[c].parent;
}
codeFile[i] = S;//第i个字符的编码存入codeFile
}
}
///编码结束进行译码
void Decode(Node *HT, int n)
{
int m = 2*n-1, i, j=m-1;
printf("请输入要译码的Huffman编码:\n");
char str[100];
scanf("%s", &str);
char C;
int len = strlen(str);
for(i = 0; i<len; i++)
{
C = str[i];
if(C == '0')
j = HT[j].Lchild;
else
j = HT[j].Rchild;
if(HT[j].Lchild == -1)
{
printf("%c", HT[j].data);
j = m -1;
}
}
}
以下答案由GPT-3.5大模型与博主波罗歌共同编写：
哈夫曼编码是一种变长编码（即每个字符的编码长度不同）的前缀编码（即任何字符的编码都不是另一个字符编码的前缀），其基本思想是将频率较高的字符用较短的编码，频率较低的字符用较长的编码，以此来减少编码长度。
实现哈夫曼编码和解码的步骤如下：
统计出每个字符的出现频率，并构造出一个字符频率的有序序列。
构造哈夫曼树。从频率最低的两个字符开始，依次选择两个频率最低的字符组成一棵二叉树（权值为叶子节点权值之和），并将其作为一个新的节点插入到频率有序序列中。重复该过程，直到只剩下一个节点，该节点即为哈夫曼树的根节点。
对于每个叶子节点，记录下其对应的字符及其编码信息。从根节点开始遍历哈夫曼树，向左走为0，向右走为1，直至叶子节点。记录下每个叶子节点对应的字符及其编码，即得到了哈夫曼编码。
将输入的电文字符串根据已构造的哈夫曼编码进行编码，即将每个字符替换为其对应的编码。
将编码后的代码串根据哈夫曼编码进行译码，即从根节点开始遍历哈夫曼树，对于每个0向左走，对于每个1向右走，直至到达叶子节点，即找到了对应的字符。
下面是C语言实现哈夫曼编码和解码的示例代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 哈夫曼编码结构体
typedef struct {
char ch; // 字符
int freq; // 出现频率
char code[256]; // 编码
} huff_code;
// 哈夫曼树节点结构体
typedef struct node {
char ch; // 字符
int freq; // 出现频率
struct node *left; // 左孩子
struct node *right; // 右孩子
} huff_node;
// 获取字符频率信息
void get_freq(char *str, int len, huff_code *hc, int *hc_len) {
int i, j, k;
huff_code tmp;
k = 0;
for (i = 0; i < len; i++) {
// 如果该字符已经出现过，则更新其出现频率
for (j = 0; j < k; j++) {
if (hc[j].ch == str[i]) {
hc[j].freq++;
break;
}
}
// 如果该字符为新出现的，则新建节点
if (j == k) {
hc[k].ch = str[i];
hc[k].freq = 1;
k++;
}
}
*hc_len = k;
// 按频率从小到大排序
for (i = 0; i < k - 1; i++) {
for (j = i + 1; j < k; j++) {
if (hc[i].freq > hc[j].freq) {
tmp = hc[i];
hc[i] = hc[j];
hc[j] = tmp;
}
}
}
}
// 构建哈夫曼树
void build_huff_tree(huff_node **root, huff_code *hc, int len) {
int i;
huff_node *p1, *p2, *p_new;
// 构造哈夫曼树，每次取最小的两个节点合并
for (i = 0; i < len - 1; i++) {
p_new = (huff_node *)malloc(sizeof(huff_node));
p1 = (huff_node *)malloc(sizeof(huff_node));
memcpy(p1, root[hc[i].ch], sizeof(huff_node));
p2 = (huff_node *)malloc(sizeof(huff_node));
memcpy(p2, root[hc[i + 1].ch], sizeof(huff_node));
p_new->freq = hc[i].freq + hc[i + 1].freq;
p_new->left = p1;
p_new->right = p2;
root[p1->ch] = p1;
root[p2->ch] = p2;
root[p_new->ch] = p_new;
hc[i + 1].freq = p_new->freq;
}
*root = p_new;
}
// 遍历哈夫曼树，获取编码
void get_code(huff_node *root, char *code, int depth, huff_code *hc) {
if (root->left == NULL && root->right == NULL) {
int i;
hc[root->ch].freq = root->freq;
hc[root->ch].ch = root->ch;
code[depth] = '\0';
strcpy(hc[root->ch].code, code);
return;
}
if (root->left != NULL) {
code[depth] = '0';
get_code(root->left, code, depth + 1, hc);
}
if (root->right != NULL) {
code[depth] = '1';
get_code(root->right, code, depth + 1, hc);
}
}
// 将电文字符串根据哈夫曼编码进行编码
void encode(char *str, int len, huff_code *hc, int hc_len, char *code) {
int i, j, k;
k = 0;
for (i = 0; i < len; i++) {
for (j = 0; j < hc_len; j++) {
if (str[i] == hc[j].ch) {
strcat(code, hc[j].code);
k += strlen(hc[j].code);
break;
}
}
}
}
// 将由哈夫曼编码生成的代码串进行译码
void decode(char *code, huff_node *root, int code_len) {
int i, j;
huff_node *p;
p = root;
for (i = 0; i < code_len; i++) {
if (code[i] == '0') {
p = p->left;
} else {
p = p->right;
}
if (p->left == NULL && p->right == NULL) {
printf("%c", p->ch);
p = root;
}
}
}
int main() {
char str[256];
int len, i, hc_len, code_len;
huff_node *root, *p;
huff_code hc[256];
char code[1024] = {0};
char buf[2];
printf("请输入电文字符串：");
gets(str);
len = strlen(str);
// 获取字符频率信息
get_freq(str, len, hc, &hc_len);
// 初始化哈夫曼树节点
root = (huff_node *)malloc(sizeof(huff_node));
memset(root, 0, sizeof(huff_node));
for (i = 0; i < hc_len; i++) {
p = (huff_node *)malloc(sizeof(huff_node));
p->ch = hc[i].ch;
p->freq = hc[i].freq;
root[p->ch] = p;
}
// 构建哈夫曼树
build_huff_tree(&root, hc, hc_len);
// 获取编码
char code_tmp[256] = "";
get_code(root, code_tmp, 0, hc);
// 输出编码信息
printf("哈夫曼编码如下：\n");
for (i = 0; i < hc_len; i++) {
printf("%c: %d, %s\n", hc[i].ch, hc[i].freq, hc[i].code);
}
// 将电文字符串根据哈夫曼编码进行编码
encode(str, len, hc, hc_len, code);
code_len = strlen(code);
// 输出编码结果
printf("编码后的代码串为：%s\n", code);
// 将哈夫曼编码生成的代码串进行译码
printf("解码后的电文字符串为：");
for (i = 0; i < code_len; i++) {
buf[0] = code[i];
buf[1] = '\0';
decode(buf, root, 1);
}
printf("\n");
return 0;
}
以上代码实现了哈夫曼编码和解码，并能够从键盘输入电文字符串，输出对应的哈夫曼编码，并将其解码为原始电文字符串。
如果我的回答解决了您的问题，请采纳！
- 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7738712
- 这篇博客你也可以参考下：c语言输入一个数，分别正序、逆序输出他的各个位数
- 除此之外, 这篇博客: C语言序列3——全局变量和局部变量，标识符作用域、变量的生存期中的 这个概念适用于所有标识符，而不仅仅是变量，C语言的作用域分为以下几类： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
函数作用域（Function Scope），标识符在整个函数中都有效。只有语句标号属于函数作用域。标号在函数中不需要先声明后使用，在前面用一个
goto语句也可以跳转到后面的某个标号，但仅限于同一个函数之中。文件作用域（File Scope），标识符从它声明的位置开始直到这个程序文件的末尾都有效。例如上例中
main函数外面的A、a、b、c，还有main也算，printf其实是在stdio.h中声明的，被包含到这个程序文件中了，所以也算文件作用域的。块作用域（Block Scope），标识符位于一对{}括号中（函数体或语句块），从它声明的位置开始到右}括号之间有效。例如上例中
main函数里的a、b、c。此外，函数定义中的形参也算块作用域的，从声明的位置开始到函数末尾之间有效。- 您还可以看一下 李飞老师的C语言开发之数据结构与算法四课程中的 哈夫曼编码(代码实现)小节, 巩固相关知识点
基于new Bing和ChatGPT的回答：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_HT 100
#define MAX_CODE_LEN 100
typedef struct {
char ch; // 字符
int freq; // 出现频率
int parent, lchild, rchild; // 父节点、左孩子、右孩子
} HTNode;
typedef struct {
char ch; // 字符
char code[MAX_CODE_LEN]; // 编码
} CodeNode;
void createHuffmanTree(HTNode *ht, int n);
void getCode(HTNode *ht, CodeNode *hc, int n);
void printCode(CodeNode *hc, int n);
void encode(CodeNode *hc, char *str, char *code);
void decode(HTNode *ht, char *code, char *str);
int main() {
char str[MAX_TREE_HT];
char code[MAX_TREE_HT];
HTNode ht[MAX_TREE_HT];
CodeNode hc[MAX_TREE_HT];
int n, i;
printf("请输入一串电文字符：\n");
fgets(str, MAX_TREE_HT, stdin);
n = strlen(str) - 1;
// 统计字符频率
for (i = 0; i < n; i++) {
int j;
for (j = 0; j < i; j++) {
if (ht[j].ch == str[i]) { // 已经统计过该字符
ht[j].freq++;
break;
}
}
if (j == i) { // 第一次统计该字符
ht[i].ch = str[i];
ht[i].freq = 1;
}
}
createHuffmanTree(ht, n);
getCode(ht, hc, n);
printf("哈夫曼树的中序遍历序列：\n");
for (i = 0; i < 2 * n - 1; i++) {
if (ht[i].lchild == -1 && ht[i].rchild == -1) {
printf("%c:%d\n", ht[i].ch, ht[i].freq);
}
}
printf("电文字符对应的编码：\n");
printCode(hc, n);
encode(hc, str, code);
printf("电文字符的编码串：%s\n", code);
decode(ht, code, str);
printf("编码串对应的电文字符：%s\n", str);
return 0;
}
void createHuffmanTree(HTNode *ht, int n) {
int i, j, k, s1, s2;
for (i = 0; i < 2 * n - 1; i++) {
ht[i].parent = -1;
ht[i].lchild = -1;
ht[i].rchild = -1;
}
for (i = n; i < 2 * n - 1; i++) {
s1 = s2 = -1;
for (j = 0; j < i; j++) {
if (ht[j].parent == -1) {
if (s1 == -1) {
s1 = j;
} else if (s2 == -1) {
s2 = j;
} else {
if (ht[s1].freq > ht[s2].freq) {
k = s1;
s1 = s2;
s2 = k;
}
if (ht[j].freq < ht[s2].freq) {
if (ht[j].freq < ht[s1].freq) {
s2 = s1;
s1 = j;
} else {
s2 = j;
}
}
}
}
}
ht[s1].parent = i;
ht[s2].parent = i;
ht[i].lchild = s1;
ht[i].rchild = s2;
ht[i].freq = ht[s1].freq + ht[s2].freq;
}
}
void getCode(HTNode *ht, CodeNode *hc, int n) {
char *code = (char *)malloc(n * sizeof(char));
int i, j, k;
for (i = 0; i < n; i++) {
k = n - 1;
j = i;
while (ht[j].parent != -1) {
if (ht[ht[j].parent].lchild == j) {
code[--k] = '0';
} else {
code[--k] = '1';
}
j = ht[j].parent;
}
hc[i].ch = ht[i].ch;
strcpy(hc[i].code, &code[k]);
}
free(code);
}
void printCode(CodeNode *hc, int n) {
int i;
for (i = 0; i < n; i++) {
printf("%c:%s\n", hc[i].ch, hc[i].code);
}
}
void encode(CodeNode *hc, char *str, char *code) {
int i, j, k;
for (i = 0, k = 0; str[i] != '\0'; i++) {
for (j = 0; hc[j].ch != str[i]; j++);
strcat(code, hc[j].code);
}
}
void decode(HTNode *ht, char *code, char *str) {
int i, j, p = 2 * strlen(code) - 2;
for (i = 0; code[i] != '\0'; i++) {
if (code[i] == '0') {
p = ht[p].lchild;
} else {
p = ht[p].rchild;
}
if (ht[p].lchild == -1 && ht[p].rchild == -1) {
str[i] = ht[p].ch;
p = 2 * strlen(code) - 2;
}
}
str[i] = '\0';
}
仅供参考，希望有所帮助
Huffman编码和译码的算法
求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点开始，沿双亲的双亲链域回退到根节点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根节点到相应叶结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支码为所求编码的低位码，后得到的分支码为所求编码的高位码。我们可以设置一结构数组HuffCode用来存放各字符的哈夫曼编码信息
分量bit为一维数组，用来保存字符的哈夫曼编码，start表示该编码在数组bit中的开始位置。所以，对于第i个字符，它的哈夫曼编码存放在HuffCode[i].bit中的从HuffCode[i].start到n的分量上。
(1)从Huffman树的叶子结点HuffNode[i](0<=i<n)出发，通过HuffNode[c].parent找到双亲，通过lchild和rchild域可知HuffNode[c]是左分支还是右分支，若是左分支则bit[n-1-i]=0;否则bit[n-1-i]=1.
(2)将HuffNode[c]作为出发点，重复上述过程，直到找到树根位置，即进行了Huffman编码
(3)译码时首先输入二进制代码串，放在数组code中，以回车结束输入。
(4)将代码与编码进行比较，如果为0，则转向左子树；如果为1，则转向右子树，直到叶结点结束。输出叶子结点的数据域，即所对应的字符。
#include<stdio.h>
#include<conio.h>
#define MAXVALUE 10000 //定义最大权值
#define MAXLEAF 30 //定义哈夫曼树中叶子节点个数
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 50
#define NULL 0
typedef struct node{
char letter;
int weight; //结点的权值
int parent; //结点的双亲
int lchild; //结点的左孩子
int rchild; //结点的右孩子
}HNodeType;
typedef struct{
char letter;
int bit[MAXBIT];
int start;
}HCodeType;
typedef struct{
char s;
int num;
}Message;
//哈夫曼树的构造算法
void HuffmanTree(HNodeType HuffNode[],int n,Message a[])
{
int i,j,m1,m2,x1,x2,temp1;char temp2;
for(i=0;i<2*n-1;i++) //HuffNode[]初始化
{
HuffNode[i].letter=NULL;
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n-1;j++)
if(a[j].num>a[i].num)
{
temp1=a[i].num;a[i].num=a[j].num;a[j].num=temp1;
temp2=a[i].s;a[i].s=a[j].s;a[j].s=temp2;
}
for(i=0;i<n;i++)
{
HuffNode[i].weight=a[i].num;
HuffNode[i].letter=a[i].s;
}
for(i=0;i<n-1;i++) //构造哈夫曼树
{
m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++) //找出的两棵权值最小的子树
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1)
{
m2=m1;x2=x1;
m1=HuffNode[j].weight; x1=j;
}
else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)
{
m2=HuffNode[j].weight;
x2=j;
}
}
//将找出的两棵子树合并为一棵子树
HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;
}
}
//生成哈夫曼编码
void HuffmanCode(int n,Message a[])
{
HNodeType HuffNode[MAXNODE];
HCodeType HuffCode[MAXLEAF],cd;
int i,j,c,p;
char code[30],*m;
HuffmanTree(HuffNode,n,a); //建立哈夫曼树
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1) //由叶结点向上直到树根
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=HuffNode[c].parent;
}
for(j=cd.start+1;j<n;j++) //保存求出的每个结点的哈夫曼编码和编码的起始位
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
printf(" 输出每个叶子的哈夫曼编码：\n");
for(i=0;i<n;i++) //输出每个叶子结点的哈夫曼编码
{
HuffCode[i].letter=HuffNode[i].letter;
printf(" %c:",HuffCode[i].letter);
for(j=HuffCode[i].start+1;j<n;j++)
printf(" %d",HuffCode[i].bit[j]);
printf("\n");
}
printf(" 请输入电文(1/0):\n");
for(i=0;i<30;i++)code[i]=NULL;
scanf(" %s",&code); m=code;
c=2*n-2;
printf(" 输出哈夫曼译码:\n");
while(*m!=NULL)
{
if(*m=='0')
{
c=i=HuffNode[c].lchild;
if(HuffNode[c].lchild==-1&&HuffNode[c].rchild==-1)
{
printf("%c",HuffNode[i].letter);
c=2*n-2;
}
}
if(*m=='1')
{
c=i=HuffNode[c].rchild;
if(HuffNode[c].lchild==-1&&HuffNode[c].rchild==-1)
{ printf("%c",HuffNode[i].letter);
c=2*n-2;
}
}
m++;
}
printf("\n");
}
void main()
{
Message data[30];
char s[100],*p;
int i,count=0;
printf("\n 请输入一些字符:");
scanf("%s",&s);
for(i=0;i<30;i++)
{
data[i].s=NULL;
data[i].num=0;
}
p=s;
while(*p)
{
for(i=0;i<=count+1;i++)
{
if(data[i].s==NULL)
{
data[i].s=*p;data[i].num++;count++;break;
}
else if(data[i].s==*p)
{
data[i].num++;break;
}
}
p++;
}
printf("\n");
printf(" 不同的字符数:%d\n",count);
for(i=0;i<count;i++)
{ printf(" %c ",data[i].s);
printf(" 权值:%d",data[i].num);
printf("\n");
}
HuffmanCode(count,data);
getch();
}
以下内容部分参考ChatGPT模型：
对于此问题，可以按照以下步骤解决：
统计输入字符串中每个字符的出现频率，将其作为哈夫曼树的权值。
构造哈夫曼树，可以使用优先队列（priority_queue）来实现。
输出哈夫曼树的中序遍历序列（字符及其权值），可以使用递归函数实现。
实现哈夫曼编码，可以使用递归函数来遍历哈夫曼树，记录编码，并将编码保存到一个哈希表中。
对于输入的代码串，根据哈希表进行解码，即可得到对应的电文字符串。
下面是一个C++的示例代码：
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
// 哈夫曼树节点
struct HuffmanNode {
char ch; // 字符
int freq; // 出现频率
HuffmanNode* left;
HuffmanNode* right;
HuffmanNode(char c, int f) : ch(c), freq(f), left(NULL), right(NULL) {}
};
// 哈夫曼编码
unordered_map<char, string> huffmanCode;
// 比较函数
struct Compare {
bool operator()(HuffmanNode* a, HuffmanNode* b) {
return a->freq > b->freq;
}
};
// 构造哈夫曼树
HuffmanNode* buildHuffmanTree(string str) {
// 统计字符出现频率
unordered_map<char, int> freqMap;
for (char c : str) {
freqMap[c]++;
}
// 将每个字符及其频率作为哈夫曼树节点
priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
for (auto it = freqMap.begin(); it != freqMap.end(); ++it) {
pq.push(new HuffmanNode(it->first, it->second));
}
// 构造哈夫曼树
while (pq.size() > 1) {
HuffmanNode* left = pq.top();
pq.pop();
HuffmanNode* right = pq.top();
pq.pop();
HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
// 中序遍历哈夫曼树
void inorderTraversal(HuffmanNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->ch << " " << root->freq << endl;
inorderTraversal(root->right);
}
// 哈夫曼编码
void encode(HuffmanNode* root, string& code) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
huffmanCode[root->ch] = code;
}
code.push_back('0');
encode(root->left, code);
code.pop_back();
code.push_back('1');
encode(root->right, code);
code.pop_back();
}
// 哈夫曼译码
string decode(HuffmanNode* root, string codeStr) {
string res;
HuffmanNode* cur = root;
for (char c : codeStr) {
if (c == '0') {
cur = cur->left;
} else {
cur = cur->right;
}
if (cur->left == NULL && cur->right == NULL) {
res.push_back(cur->ch);
cur = root;
}
}
return res;
}
int main() {
string str;
cout << "请输入一串电文字符：" << endl;
cin >> str;
// 构造哈夫曼树
HuffmanNode* root = buildHuffmanTree(str);
// 输出中序遍历序列
cout << "中序遍历序列（字符及其权值）：" << endl;
inorderTraversal(root);
// 哈夫曼编码
cout << "哈夫曼编码：" << endl;
string code;
encode(root, code);
for (auto it = huffmanCode.begin(); it != huffmanCode.end(); ++it) {
cout << it->first << " " << it->second << endl;
}
// 哈夫曼译码
cout << "请输入哈夫曼编码：" << endl;
string codeStr;
cin >> codeStr;
string res = decode(root, codeStr);
cout << "哈夫曼译码结果：" << endl;
cout << res << endl;
return 0;
}
如果我的建议对您有帮助、请点击采纳、祝您生活愉快
【数据结构】建立二叉树以及哈夫曼树及哈夫曼编码
讲的非常详细，可以借鉴下
https://blog.csdn.net/weixin_45481821/article/details/126794687