typedef struct Node
{
int weight
int parent, LChild,RChild
} HTNode, * HTree
typedef char *HuffmanCode
创建哈夫曼树并求哈夫曼编码的算法如下：
viod CreatHTree(HTree ht , HuffmanCode hc,int * w, int n)
{ /*w存放n个权值,构造哈夫曼树ht,并求出哈夫曼编码hc */
int start
m=2*n-1
ht=(HTree)malloc((m+1)*sizeof(HTNode))
for(i=1i<=ni++)
ht[i] ={ w[i],0,0,0}
for(i=n+1i<=mi++)(* ht)[i] ={0,0,0,0}/* 初始化*/
for(i=n+1i<=mi++)
{
select(ht,i-1,&s1,&s2)
/* 在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回，select函数要求在上机调试使补充定义*/
ht[s1].parent=i
ht[s2].parent=i
ht[i].LChild=s1
ht[i].RChild=s2
ht[i].weight=ht[s1].weight+ht[s2].weight
} /*哈夫曼树建立完毕*/
/*以下程序是从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码的过程*/
hc=(HuffmanCode)malloc((n+1)*sizeof(char *))
cd=(char * )malloc(n * sizeof(char))
cd[n-1]＝’\0’；
for(i=1i<=ni++)
{
start=n-1
for(c=i,p=ht[i].parentp!=0c=p,p=ht[p].parent)
if(ht[p].LChild==c) cd[--start]=‘0’
else cd[--start]=‘1’
hc[i]=(char *)malloc((n-start)*sizeof(char))
strcpy(hc[i],&cd[start])
}
free(cd)
}
数组ht的前n个单元存放叶子结点的信息，最后一个单元存放的是根结点。
自己写个主程序，把八个字符的频率读入，调用CreatHTree就可以了
写了个代码，测试了一下，"0101011010"这个串不能正确译码，是不是题干有误？#include "stdafx.h"// Huffman.cpp : 定义控制台应用程序的入口点。
#include <stdio.h>
#include <string.h>
#define N 50 /*叶子结点数*/
#define M 2*N-1 /*树中结点总数*/typedef struct
{
char data[5]/*结点值*/
int weight/*权重*/
int parent/*双亲结点*/
int lchild/*左孩子结点*/
int rchild/*右孩子结点*/
} HTNodetypedef struct
{
char cd[N]/*存放哈夫曼码*/
int start
} HCodevoid CreateHT(HTNode ht[],int n)
{
int i,k,lnode,rnode
int min1,min2
for (i=0i<2*n-1i++) /*所有结点的相关域置初值-1*/
ht[i].parent=ht[i].lchild=ht[i].rchild=-1
for (i=ni<2*n-1i++) /*构造哈夫曼树*/
{
min1=min2=32767/*lnode和rnode为最小权重的两个结点位置*/
lnode=rnode=-1
for (k=0k<=i-1k++)
if (ht[k].parent==-1) /*只在尚未构造二叉树的结点中查找*/
{
if (ht[k].weight<min1)
{
min2=min1rnode=lnode
min1=ht[k].weightlnode=k
}
else if (ht[k].weight<min2)
{
min2=ht[k].weightrnode=k
}
}
ht[lnode].parent=iht[rnode].parent=i
ht[i].weight=ht[lnode].weight+ht[rnode].weight
ht[i].lchild=lnodeht[i].rchild=rnode
}
}void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c
HCode hc
for (i=0i<ni++) /*根据哈夫曼树求哈夫曼编码*/
{
hc.start=nc=i
f=ht[i].parent
while (f!=-1) /*循序直到树根结点*/
{
if (ht[f].lchild==c) /*处理左孩子结点*/
hc.cd[hc.start--]='0'
else /*处理右孩子结点*/
hc.cd[hc.start--]='1'
c=ff=ht[f].parent
}
hc.start++/*start指向哈夫曼编码最开始字符*/
hcd[i]=hc
}
}void DispHCode(HTNode ht[],HCode hcd[],int n)
{
int i,k
int sum=0,m=0,j
printf(" 输出哈夫曼编码:\n")/*输出哈夫曼编码*/
for (i=0i<ni++)
{
j=0
printf(" %s:\t",ht[i].data)
for (k=hcd[i].startk<=nk++)
{
printf("%c",hcd[i].cd[k])
j++
}
m+=ht[i].weight
sum+=ht[i].weight*j
printf("\n")
}
printf("\n 平均长度=%g\n",1.0*sum/m)
}
int findsubstr(char* S, int cS, HCode hcd[],int n, int &pos)
{
int i,k, j
if (pos >cS) return -1
for (i=0i<ni++)
{
j = pos
for (k=hcd[i].startk<=nk++)
{
if (S[j] == hcd[i].cd[k])
j++
else
break
}
if (k >n)
{
pos = j
return i
}
}
return -1
}bool Recode(char* S, int cS, HTNode ht[],HCode hcd[],int n){
char strresult[80]
strcpy(strresult,"")
int pos = 0
while (pos <cS)
{
int result = findsubstr(S, cS, hcd, n, pos)
if (result != -1)
{
strcat(strresult, ht[result].data)
}
else
return false
}
printf("译码结果为：%s\n\n", strresult)
return true
}
void main()
{
int i, n=6
// char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"}
// int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123}
char *str[]={"a","e","r","t","d","f"}
int fnum[]={8,4,6,3,1,1}HTNode ht[M]
HCode hcd[N]
for (i=0i<ni++)
{
strcpy(ht[i].data, str[i])
ht[i].weight=fnum[i]
}
printf("\n")
CreateHT(ht,n)
CreateHCode(ht,hcd,n)
DispHCode(ht,hcd,n)
printf("\n")char* strtest1="01011101111100011"
printf("破译原文是：%s\n", strtest1)
int clength = strlen(strtest1)
if (!Recode(strtest1, clength, ht, hcd, n))
printf("译密失败\n")char* strtest2="0101011010"
printf("破译原文是：%s\n", strtest2)
clength = strlen(strtest2)
if (!Recode(strtest2, clength, ht, hcd, n))
printf("译密失败\n")
system("pause")
}
我写了一个注释较为完整且压缩、解压缩比较全面的：#include <stdio.h>
#include <conio.h>
#define MAX_FILE 5000/* 假设的文件最大长度 */
#define MAXLIST 256/* 最大MAP值 */
#define MAX_HOFFMAN_LENGTH 50/* 哈夫曼编码长度 */
char dictionary[MAXLIST][2]={0}/* Hash映射,[][0]为权值,[][1]为字符 */
char fileContent[MAX_FILE]/* 处理的字符串大小 */
int Hoffman[MAXLIST][MAX_HOFFMAN_LENGTH]={2}/* 哈夫曼编码序列 */
char HoffmanList[MAXLIST]={0}/* 哈夫曼编码对应的字符有序序列 */
char HoffFileCode[MAX_FILE]={0}/* 哈夫曼编码字符串序列 */
char HoffFile[MAX_FILE]={0}
/* 编码到假设的文件的哈夫曼压缩格式： 依次存储 原字符串长度(1字节存储:可扩展到2字节)、哈夫曼编码数(1字节)、每个哈夫曼编码的长度序列、每个哈夫曼编码对应的字符序列、编码过的哈夫曼字符串 */
char GetFile[MAX_FILE]={0}/* 解码序列 */
void ShellSort(char pData[MAXLIST][2],int Count)/* Shell排序，用于准备有序化要构造的编码权值构造哈夫曼树做准备 */
{
int step[4]={9,5,3,1}/* 增量序列 */
int iTemp,cTemp
int k,s,w,i,j
for(i=0i<4i++)
{
k=step[i]
s=-k
for(j=kj<Countj++)
{iTemp=pData[j][0]
cTemp=pData[j][1]
w=j-k
if(s==0)
{
s=-k
s++
pData[s][0]=iTemp
pData[s][1]=cTemp
}
while((iTemp<pData[w][0])&&(w>=0)&&(w<=Count))
{
pData[w+k][0]=pData[w][0]/* 权值交换 */
pData[w+k][1]=pData[w][1]/* 字符交换 */
w=w-k
}
pData[w+k][0]=iTemp
pData[w+k][1]=cTemp
}
}
}
struct TNode/* 哈夫曼树结点 */
{
struct TNode* pNode
struct TNode* lNode
struct TNode* rNode
char dictionary
char weight
}
void TNode_init(struct TNode*tn,char dic,char wei)
{
tn->pNode=0
tn->lNode=0
tn->rNode=0
tn->dictionary=dic
tn->weight=wei
}
struct LNode/* 链表结点,用于存储哈夫曼树结点,进而构造哈夫曼树(保证每一步链表结点包含的哈夫曼结点都是有序的) */
{
struct LNode* prev
struct LNode* next
struct TNode* tnode
}
void LNode_init(struct LNode* ln)
{
ln->prev=ln->next=0
ln->tnode=0
}
int len=0/* 哈夫曼编码数 */
int deep=-1/* 深度 */
void Preorder(struct TNode * p)/* 前序遍历 */
void byLeft(struct TNode*p)/* 经由左结点 */
{
deep++
Hoffman[len][deep]=0
Preorder(p)
Hoffman[len][deep]=2
deep--
}
void byRight(struct TNode*p)/* 经由右结点 */
{
deep++
Hoffman[len][deep]=1
Preorder(p)
Hoffman[len][deep]=2
deep--
}
void Preorder(struct TNode * p)
{
int i
if(p->lNode!=0)/* 当左子结点非空则遍历 */
{
byLeft(p->lNode)
}
if(p->rNode!=0)/* 当右子结点非空则遍历 */
{
byRight(p->rNode)
}
if((p->lNode==0)&&(p->rNode==0))/* 当左右结点都为空，则增加哈夫曼编码数到另一个记录 */
{
Hoffman[len][deep+1]=2
i=0
for(Hoffman[len][i]!=2i++)
{
Hoffman[len+1][i]=Hoffman[len][i]
}
Hoffman[len+1][i]=2
HoffmanList[len]=p->dictionary
len++
}
}
char generateOne(int k)/* 产生k个连续1的二进制串,比如111,1111,111111,用于编码进假设的文件 */
{
char c=0
for(k!=0k--)
{
c|=(1<<(k-1))
}
return c
}
int compareBits(char b1,char b2,char c,int l,int d)/* 判断由 [b1,b2] 组成的16位二进制数以d为起点,是否是长度为l的c二进制串（哈夫曼编码）的前缀 */
{
unsigned char t=(((((0x00ff&b1)<<8)|(0x00ff&b2))>>(8-d))&0x00ff)
return (((t)&((generateOne(l)<<(8-l))&0xff))==((c<<(8-l))&0xff))
}
int main()
{
struct LNode* t,*p
struct LNode* head
struct TNode *tempTNode,*k1
int i=0,j,k
unsigned short fileLen=0
int len=0,l,b1,b2,d
char c
int code[500],h=0
int codeLen=0,total=0
/* 或许假定的文件字符串向量中的字符串 */
printf("please Enter string to be pressed:")
scanf("%s",&fileContent)
/* Hash进dictionary */
for(fileContent[i]!='\0'i++,fileLen++)
{
++dictionary[fileContent[i]][0]
dictionary[fileContent[i]][1]=fileContent[i]
}
/* 把Hash了的dictionary向前靠拢 */
{
for(i=0i!=MAXLISTi++)
{
if(dictionary[i][0]!=0)
{
dictionary[len][0]=dictionary[i][0]
dictionary[len][1]=dictionary[i][1]
len++
}
}
}
printf("the number of Huffman's codes:%d\n",len)
/* 对dictionary按权值进行排序 */
ShellSort(dictionary,len)
/* 构造链表,链表中放有序dictionary权值的树结点 */
head=(struct LNode*)malloc(sizeof(struct LNode)),p=head
LNode_init(head)
head->next=(struct LNode*)malloc(sizeof(struct LNode))
LNode_init(head->next)
tempTNode=(struct TNode*)malloc(sizeof(struct LNode))
TNode_init(tempTNode,dictionary[0][1],dictionary[0][0])
head->tnode=tempTNode
{
for(i=0i!=len-1i++)
{
p->next->prev=p->next
p=p->next
p->next=(struct LNode*)malloc(sizeof(struct LNode))
LNode_init(p->next)
tempTNode=(struct TNode*)malloc(sizeof(struct TNode))
TNode_init(tempTNode,dictionary[i+1][1],dictionary[i+1][0])
p->tnode=tempTNode
}
}
free(p->next)
p->next=0
/* 每次最小权值的前面两个链表结点中的树结点组成一个子树,子树有合权值,子数的根按权值排序进链表*/
for(p=headp->next!=0)
{
p->tnode->pNode=(struct TNode*)malloc(sizeof(struct TNode))
TNode_init(p->tnode->pNode,'\0',(p->tnode->weight)+(p->next->tnode->weight))
p->next->tnode->pNode=p->tnode->pNode
p->tnode->pNode->lNode=p->tnode
p->tnode->pNode->rNode=p->next->tnode
head=p->next
free(p)
p=head
p->tnode=p->tnode->pNode
for(t=headt->next!=0t=t->next)
{
if(t->tnode->weight>t->next->tnode->weight)
{
k1=t->tnode
t->tnode=t->next->tnode
t->next->tnode=k1
}
}
}
/* 前序遍历构造哈夫曼编码 */
Preorder(p->tnode)
{
for(i=0i!=leni++)
dictionary[HoffmanList[i]][0]=i
}
/* 存储字符串的哈夫曼压缩编码串,并且打包文件格式 */
{
for(i=0i!=fileLeni++)
{
int j=dictionary[fileContent[i]][0]
for(k=0Hoffman[j][k]!=2k++)
{
HoffFileCode[codeLen]|=(Hoffman[j][k]<<(7-total%8))
code[h++]=Hoffman[j][k]
if(((total+1)%8)==0)
{
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen]
codeLen++
}
total++
}
}
}
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen]
HoffFile[0]=(fileLen)
/* 解压缩假定的文件HoffFile成为原字符串序列 */
printf("Huffman's code list:\n")
HoffFile[1]=len
{
for(i=0,j=0i!=leni++,j=0)
{
for(Hoffman[i][j]!=2j++)
HoffFile[i+2]=j
HoffFile[i+2+2*len]=HoffmanList[i]
for( k=0k!=jk++)
{
printf("%d",Hoffman[i][k])
HoffFile[i+2+len]|=(Hoffman[i][k]<<(j-1-k))
}
printf(":%d\n",HoffmanList[i])
}
}
{
for(i=0,j=0i!=(HoffFile[0]&0xff)i++)
{
for(k=0k!=HoffFile[1]k++)
{
l=HoffFile[2+k],d=j%8,b1=HoffFile[j/8+2+HoffFile[1]*3],b2=HoffFile[j/8+1+2+HoffFile[1]*3]
c=HoffFile[HoffFile[1]+2+k]
if(compareBits(b1,b2,c,l,d))
{
j+=HoffFile[2+k]
GetFile[i]=HoffFile[2+HoffFile[1]*2+k]
break
}
}
}
}
{
printf("Huffman code List Pressed :\n")
for(i=0i!=hi++)
{
printf("%c",code[i])
if((i+1)%8==0)
printf(" ")
}
}
printf("\n")
{
printf("Huffman code packaged:\n")
for(i=0i!=HoffFile[0]+HoffFile[1]*3i++)
{
printf("%c",HoffFile[i])
}
printf("\n")
}
printf("The initial len :%d\n",fileLen)
printf("The string len pressed:%d\n",(h)/8+1)
printf("The rate%.2f\%",((h/8.0+1)/fileLen)*100)
{
printf("The number of bytes:%d\n",(HoffFile[0]&0xff))
printf("The string decoded:")
for(i=0i!=(HoffFile[0]&0xff)i++)
{
printf("%c",GetFile[i])
}
printf("\n")
}
getch()
return 1
}
