哈夫曼编码

编程实现：要传输一些数据（比如英文单词），设计一个利用哈夫曼算法的编码系统，为这些单词编码，并在接收端进行译码。基本要求:

（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] = '

相关推荐