c 语言huffman编码与解码

Question

Huffman解码
写出了Huffman树和Huffman编码，解码实在不会了，麻烦各位帮帮忙

#include "stdio.h"
#include "string.h"
#include "malloc.h"
#define N 100
#define BLANKFLAG -1

//存储从键盘或文件读入的字符串
typedef struct charLinkList
{
    char ch;
    struct charLinkList *pNext;
}CharLinkList;

//存储字符及字符出现的次数
typedef struct charStat
{
    char c;
    int num;
}CharStat;

//Huffman树的结点信息，前n个为叶子节点
typedef struct HTree
{
     char ch;
     int weight;
     int parent;
     int Lchild;
     int Rchild;
}HuffmanTree;
typedef struct{
    int bit[N];
    //再设置一个start用于表示编码在数组中的起始位置
    int start;
}HCodeType,*Hcode;

void getStr(CharLinkList &str,int &total);
void cStatInf(CharLinkList str,int total,CharStat *cStat,int &codeNum);
HuffmanTree *HTreeCreate(CharStat *cStat,HuffmanTree *T,int codeNum);
void CreateHuffCode(HuffmanTree *treeNode,Hcode HuffCode,char a[N],int codeNum);
void decoding(char a[],HuffmanTree *T,int codeNum);
void openhuffmancode(HuffmanTree *HT,int n,int arr[],int arrlen);
int main()
{
    int i;
    CharLinkList str,*p;
    CharStat *cStat;
    int total,codeNum;
    printf("请输入一个字符串:\n");
    getStr(str,total);
    cStat=(CharStat *)malloc(total*sizeof(CharStat));
    cStatInf(str,total,cStat,codeNum);
    HuffmanTree *treeNode,*T;
    int nodeNum=2*codeNum-1;
    treeNode=(HuffmanTree *)malloc(nodeNum*sizeof(HuffmanTree));
    T=HTreeCreate(cStat,treeNode,codeNum);
    printf("Huffman树结点的信息为:\n");
    printf("%s%s%4c%4c%4c%4c\n","num ","Code",'W','P','L','R');
    for(i=0;i<nodeNum;i++)
    {
        printf("%3d%5c%4d%4d%4d%4d\n",i,treeNode[i].ch,treeNode[i].weight,treeNode[i].parent,treeNode[i].Lchild,treeNode[i].Rchild);
    }
    Hcode HuffCode;
    char a[N];
    CreateHuffCode(treeNode,HuffCode,a,codeNum);
    int b[N];
    scanf("%d",b);
    int len=sizeof(b)/sizeof(int);
    openhuffmancode(treeNode,codeNum,b,len);
    return 0;
}

//键盘读入一个待编码的字符串，回车结束输入
void getStr(CharLinkList &str,int &total)
{
    CharLinkList *node,*p;
    char ch;
    total=0;
    p=&str;
    while(1)
    {
        ch=getchar();
        if(ch=='\n')
            break;
        total++;
        node=new CharLinkList;
        node->ch=ch;
        node->pNext=NULL;
        p->pNext=node;
        p=node;
    }
}

//统计每个字符及出现的次数
void cStatInf(CharLinkList str,int total,CharStat *cStat,int &codeNum)
{
    int i,j;
    CharLinkList *p;
    int loc;
    int newFlag;
    p=str.pNext;
    for(i=0;i<total;i++)
    {
        cStat[i].c='\0';
        cStat[i].num=0;
    }
    loc=0;
    while(p!=NULL)
    {
        newFlag=1;
        for(j=0;cStat[j].c!='\0';j++)
        {
            if(cStat[j].c==p->ch)
            {
                newFlag=0;
                cStat[j].num++;
                break;
            }
        }
        if(newFlag==1)
        {
            cStat[loc].c=p->ch;
            cStat[loc].num++;
            loc++;
        }
        p=p->pNext;
    }
    codeNum=loc++;
}

//创建Huffman树
HuffmanTree *HTreeCreate(CharStat *cStat,HuffmanTree *T,int codeNum)
{
    int i,j,k;
    int w1,w2,p1,p2;
    int nodeNum;
    nodeNum=2*codeNum-1;
    for(i=0;i<nodeNum;i++)
    {
        if(i<codeNum)
        {
            T[i].ch=cStat[i].c;
            T[i].weight=cStat[i].num;
        }
        else
        {
            T[i].ch='\0';
            T[i].weight=0;
        }
        T[i].Lchild=BLANKFLAG;
        T[i].Rchild=BLANKFLAG;
        T[i].parent=BLANKFLAG;
    }
    for(j=codeNum;j<nodeNum;j++)
    {
        w1=0xFFFFFFF;
        w2=w1;
        p1=p2=BLANKFLAG;
        for(k=0;k<j;k++)
        {
            if(T[k].weight<w1&&T[k].parent==BLANKFLAG)
            {
                w1=T[k].weight;
                p1=k;
            }
        }
        for(k=0;k<j;k++)
        {
            if(T[k].weight<w2&&k!=p1&&T[k].parent==BLANKFLAG)
            {
                w2=T[k].weight;
                p2=k;
            }
        }
        T[j].weight=w1+w2;
        T[j].Lchild=p1;
        T[j].Rchild=p2;
        T[p1].parent=j;
        T[p2].parent=j;
    }
    return T;
}
void CreateHuffCode(HuffmanTree *treeNode,Hcode HuffCode,char a[N],int codeNum)
{
    HCodeType cd;//cd用来临时存储信息
    HuffCode = (HCodeType*)malloc((2*codeNum-1)*sizeof(HCodeType));
    int i,j,c,p;
    for(i=0;i<codeNum;i++)
    {
        cd.start=codeNum-1;//编码在bit数组中的开始存储位置，数组最大下标为n-1,霍夫曼树编码是从根到叶子的编码。我们从叶子节点开始所以需要倒着存。
        c=i;
        p = treeNode[c].parent;
        while(p!=-1)
        {
            if(treeNode[p].Lchild==c)
            {   
                cd.bit[cd.start]=0;//若叶子为双亲的左节点则编码0
            }
            else
            {
                cd.bit[cd.start]=1;//若叶子为双亲的右节点则编码1
            }
            cd.start--;//最后一次运行时start指向存储编码的前一位
            c=p;
            p=treeNode[c].parent;
        }
        for(j=cd.start+1;j<codeNum;j++)
        {
            HuffCode[i].bit[j]=cd.bit[j];
        }    
        HuffCode[i].start=cd.start + 1;//记录编码在数组中开始的位置
    }
    //输出已经保存好的霍夫曼编码
    for (i=0;i<codeNum;i++)
        {
            printf ("%s的Huffman编码为:",treeNode[i]);
            for (j=HuffCode[i].start; j < codeNum; j++)
            {
                printf ("%d", HuffCode[i].bit[j]);
            }
            printf ("\n");
        }
}

/*void decoding(char a[],HuffmanTree *T,int codeNum)
{
    //num为叶子节点数,ch[]用于存放解码之后的字符，a[]存放要解码的01串
    int j=0,p=0;
    char ch[N];
    int i=0;
    while(i<strlen(a))
    {
        p = 2*codeNum-1;
        while(T[p].Lchild != -1)
        {
            if(a[i]=='0')
            {
                p = T[p].Lchild;
            }
            else
            {
                p = T[p].Rchild;
            }
            i++;
        }
        ch[j] = T[p].ch;
        j++;
    }
    ch[j] = '\0';
    for(int m=0;m<j;m++){
        printf("%c",ch[m]);
    }
    printf("\n");
}*/
void openhuffmancode(HuffmanTree *HT,int n,int arr[],int arrlen)
{
    int m=2*n-1;
    int max=m-1;//双亲为-1的下表，也即是根节点的下标 
    int HTL,HTR,i,k;
    printf("解码结果为："); 
    for(i=0;i<arrlen;i++)
    {
        if(arr[i]==0) 
        {
            HTL=HT[max].Lchild;
            max=HTL;
        }//输入的元素若为0，找左孩子 
        if(arr[i]==1) 
        {
            HTR=HT[max].Rchild;
            max=HTL;
        }//输入的元素若为1，找右孩子 
        if(max>=0&&max<n)
        {
            printf("%c",HT[max].ch);//当下表在0-n之间的节点才有字符 
        }
            
    }
}

Answer 1

以下是C语言实现Huffman树和编码的示例代码，仅供参考：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义Huffman节点结构体
typedef struct _HuffmanNode {
    char ch;                // 字符
    int freq;               // 出现频率
    struct _HuffmanNode *leftChild, *rightChild;
} HuffmanNode;

// 构建Huffman树
void buildHuffmanTree(HuffmanNode **root, int *freqTable) {
    // 初始化所有节点，并将其插入到叶子节点队列中
    int i, j;
    HuffmanNode **queue = malloc(sizeof(HuffmanNode *) * 256);
    for (i = 0, j = 0; i < 256; i++) {
        if (freqTable[i] > 0) {
            HuffmanNode *node = malloc(sizeof(HuffmanNode));
            node->ch = (char)i;
            node->freq = freqTable[i];
            node->leftChild = node->rightChild = NULL;
            queue[j++] = node;
        }
    }
    // 不断合并叶子节点队列中两个频率最小的节点直到只剩下一个节点
    while (j > 1) {
        HuffmanNode *min1 = queue[0], *min2 = queue[1], *node = malloc(sizeof(HuffmanNode));
        int minIndex1 = 0;
        if (min2->freq < min1->freq)
            minIndex1 = 1, min1 = queue[1], min2 = queue[0];
        for (i = 2; i < j; i++) {
            if (queue[i]->freq < min1->freq)
                min2 = min1, min1 = queue[i], minIndex1 = i;
            else if (queue[i]->freq < min2->freq)
                min2 = queue[i];
        }
        node->freq = min1->freq + min2->freq;
        node->leftChild = min1;
        node->rightChild = min2;
        queue[minIndex1] = node;
        for (i = minIndex1 + 1; i < j - 1; i++)
            queue[i] = queue[i + 1];
        j--;
    }
    *root = queue[0];
    free(queue);
}

// 从根节点开始遍历Huffman树，生成字符对应的编码
void generateHuffmanCode(HuffmanNode *node, int *codeTable, int code, int depth) {
    if (node->leftChild == NULL && node->rightChild == NULL) {
        codeTable[node->ch] = ((depth == 0) ? 1 : code);      // 去掉多余的高位0
        return;
    }
    if (node->leftChild != NULL)
        generateHuffmanCode(node->leftChild, codeTable, (code << 1) + 1, depth + 1);
    if (node->rightChild != NULL)
        generateHuffmanCode(node->rightChild, codeTable, (code << 1), depth + 1);
}

int main() {
    char input[] = "hello world";
    int freqTable[256] = {0};           // 统计每个字符出现的频率
    HuffmanNode *root;
    int codeTable[256] = {0};           // 存储每个字符的编码

    // 统计每个字符出现的频率
    int i;
    for (i = 0; i < strlen(input); i++)
        freqTable[(int)input[i]]++;

    // 构建Huffman树
    buildHuffmanTree(&root, freqTable);

    // 生成Huffman编码
    generateHuffmanCode(root, codeTable, 0, 0);

    printf("Huffman编码表：\n");
    for (i = 0; i < 256; i++)
        if (codeTable[i] != 0)
            printf("%c: %d\n", (char)i, codeTable[i]);

    return 0;
}

以上代码实现了一个简单的Huffman编码器，可以统计任意字符串中各字符出现的频率，构建对应的Huffman树，并生成每个字符对应的Huffman编码。这里只演示了如何生成编码表，如果需要实际进行编解码需要研究更为复杂的算法。