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之间的节点才有字符
}
}
}
以下是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编码。这里只演示了如何生成编码表，如果需要实际进行编解码需要研究更为复杂的算法。
我们这里只使用’a’,‘b’,‘c’,‘d’,'e’这五个字母，频度分别为0.2，0.3，0.1，0.25，0.15作演示用。