编程实现:要传输一些数据(比如英文单词),设计一个利用哈夫曼算法的编码系统,为这些单词编码,并在接收端进行译码。基本要求:
(1)将需要传输的数据存放在数据文件data.txt 中。
(2)读入数据文件并为其编码,将编码后的内容存入文件code.txt中。
(3)读入code.txt,译码。并将译码后的内容输出在屏幕上。
事先准备好date.txt文件
PS:之前代码创建哈夫曼编码时有点个错误,改正了
代码如下:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
//N为汉夫曼树叶子节点数
#define N 256
//M为哈夫曼树所含节点总数
#define M 2 * N - 1
//定义极大值
#define INFINITE 0x3f3f3f3f
//date文件中的所含字符种类,本程序可以包括整个ASCII码
#define CHAR_KINDS 256
typedef struct{
int weight;
int parent;
int LChild;
int RChild;
//用来存储汉夫曼树叶子节点的所存的信息,方便解码
int info;
}HTNode, HuffmanTree[M + 1];
//哈夫曼编码
typedef char *HuffmanCode[N + 1];
//选出两个权值最小的子树
void Select(HuffmanTree *ht, int m, int *s1, int *s2){
int minWeight = INFINITE;
int i;
for(i = 1; i <= m; i++){
if((*ht)[i].weight < minWeight && (*ht)[i].parent == 0){
minWeight = (*ht)[i].weight;
*s1 = i;
}
}
minWeight = INFINITE;
for(i = 1; i <= m ;i++){
if((*ht)[i].weight < minWeight && (*ht)[i].parent == 0 && i != *s1){
minWeight = (*ht)[i].weight;
*s2 = i;
}
}
}
//创建汉夫曼树
void CrtHuffman(HuffmanTree *ht, int w[], int tw[], int n){
int i, j = 0;
//寻找非零的权值,并且对哈夫曼树叶子节点(子树)进行初始化
for(i = 1; i <= n; i++){
(*ht)[i].weight = w[tw[i - 1]];
(*ht)[i].parent = 0;
(*ht)[i].LChild = 0;
(*ht)[i].RChild = 0;
(*ht)[i].info = tw[i - 1];
}
int m = n * 2 - 1;
//对非叶子节点进行初始化
for(i = n + 1; i <= m; i++){
(*ht)[i].weight = 0;
(*ht)[i].parent = 0;
(*ht)[i].LChild = 0;
(*ht)[i].RChild = 0;
(*ht)[i].info = -1;
}
//构造哈夫曼树
for(i = n + 1; i <= m; i++){
int s1, s2;
//选择连个权值最小的子树,创建新子树
Select(ht, i - 1, &s1, &s2);
//新子树的权值等于选出来两个权值之和
(*ht)[i].weight = (*ht)[s1].weight + (*ht)[s2].weight;
//s1子树和s2子树的双亲变成i
(*ht)[s1].parent = i;
(*ht)[s2].parent = i;
//i子树的左右孩子分别为s1和s2
(*ht)[i].LChild = s1;
(*ht)[i].RChild = s2;
}
}
//创建哈夫曼编码
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int w[], int tw[], int n){
char *cd;
cd = (char *)malloc(n * sizeof(char)));
cd[n - 1] = '