哈夫曼编码与译码
(1)输入一组字符集的大小、字符及权值，建立哈夫曼树，显示该哈夫曼树，并给出每个字符的哈夫曼编码
(2)给出一串字符，按照已建立的哈夫曼树进行编码，显示结果或存入文件
(3)用(2)的结果，按照哈夫曼树进行译码
#include
#include
#include
#define MAXLEN 10
typedef struct
{
int weight;
int lchild;
int rchild;
int parent;
char key;
char mima[100];
}htnode;
typedef htnode hfmt[MAXLEN];
int n=0;
typedef char elemtype;
typedef struct
{
elemtype data[MAXLEN];
int front,rear;
}seqqueue;
void enqueue(seqqueue *q,char item)
{
q->data[q->rear]=item;
q->rear=q->rear+1;
}
elemtype dequeue(seqqueue *q)
{
elemtype item;
if(q->rear!=q->front)
{
item=q->data[q->front];
q->front=q->front+1;
return item;
}
}
seqqueue *initqueue(seqqueue *q)
{
q=(seqqueue *)malloc(sizeof(seqqueue));
q->front=q->rear=0;
return q;
}
void inithfmt(hfmt t)
{
int i,j,k;
FILE *p;
char ch;
i=0;
p=fopen("1.txt","r");
if(fopen("1.txt","r")==NULL)
printf("open error.");
while((ch=fgetc(p))!=EOF)
{
for(k=0;k
if(t[k].key==ch)
break;
}
if(k==i)
{
t[i].weight=0;
t[i].key=ch;
t[i].weight++;
i++;
}
else
t[k].weight++;
}
fclose(p);
n=i;
printf("\nn=%d",n);
for(i=0;i<2*n-1;i++)
{
t[i].lchild=-1;
t[i].rchild=-1;
t[i].parent=-1;
}
}
void selectmin(hfmt t,int i,int *p1,int *p2)
{
long min1=999999;
long min2=999999;
int j;
for(j=0;j<=i;j++)
{
if(t[j].parent==-1)
if(min1>t[j].weight)
{
min1=t[j].weight;
*p1=j;
}
}
for(j=0;j<=i;j++)
{
if(t[j].parent==-1)
if(min2>t[j].weight && j!=(*p1))
{
min2=t[j].weight;
*p2=j;
}
}
}
void creathfmt(hfmt t)
{
int i,p1,p2;
inithfmt(t);
for(i=n;i<2*n-1;i++)
{
selectmin(t,i-1,&p1,&p2);
t[p1].parent=i;
t[p2].parent=i;
t[i].lchild=p1;
t[i].rchild=p2;
t[i].weight=t[p1].weight+t[p2].weight;
}
}
void printhfmt(hfmt t)
{
int i;
printf("\nthe h
fmt is:\n");
printf("weight\tparent\tlchild\trchild\tkey\t");
for(i=0;i<2*n-1;i++)
{
printf("\n");
printf("%d\t%d\t%d\t%d\t%c\t%s",t[i].weight,t[i].parent,t[i].lchild,t[i].rchild,t[i].key);
}
printf("\n\n");
}
void hfnode1(hfmt t,int i,int j)
{
int a,b;
a=i;
b=j=t[i].parent;
if(t[j].parent!=-1)
{
i=j;
hfnode1(t,i,j);
}
if(t[b].lchild==a)
{
printf("0");
}
else
{
printf("1");
}
}
void huffmannode(hfmt t)
{
int i,j,a;
printf("the code is:");
for(i=0;i
j=0;
printf("\n");
printf("%c(%d):",t[i].key,t[i].weight);
hfnode1(t,i,j);
}
}
void Encoding(hfmt t)
{
char r[1000],ch;
int i=0,j;
FILE *p;
p=fopen("2.txt","r");
if(fopen("2.txt","r")==NULL)
printf("\n\nopen error.");
while((ch=fgetc(p))!=EOF)
{
r[i++]=ch;
}
fclose(p);
printf("\n\nth Encoding is:");
for(j=0;r[j]!='\0';j++)
for(i=0;i
{
hfnode1(t,i,j);
}
}
void hfnode2(hfmt t,seqqueue *q,int i,int j)
{
int a,b,c=0;
char item;
a=i;
b=j=t[i].parent;
if(t[j].parent!=-1)
{
i=j;
hfnode2(t,q,i,j);
}
if(t[b].lchild==a)
{
item='0';
enqueue(q,item);
}
else
{
item='1';
enqueue(q,item);
}
}
void decoding(hfmt t,seqqueue *q)
{
char r[100],ch;
FILE *p;
int i=0,j=0,len,x,y,s=0;
x=2*n-2;
p=fopen("3.txt","r");
if(fopen("3.txt","r")==NULL)
printf("\nopen error.");
while((ch=fgetc(p))!=EOF)
{
r[i++]=ch;
}
fclose(p);
len=strlen(r);
for(i=0;i
hfnode2(t,q,i,j);
for(j=0;j
q->rear=q->front=0;
}
for(i=0;i
t[i].mima[j]='\0';
printf("\nthe Decoding is:");
for(i=0;i
if(r[i]=='0')
{
x=t[x].lchild;
if(t[x].lchild==-1)
{
printf("%c",t[x].key);
x=2*n-2;
}
}
else if(r[i]=='1')
{
x=t[x].rchild;
if(t[x].rchild==-1)
{
printf("%c",t[x].key);
x=2*n-2;
}
}
}
printf("\n");
}
int main()
{
int i,j;
hfmt ht;
seqqueue *q;
printf("*************************信管1002-15号XXX**************************\n\n");
printf("*************************欢迎使用哈夫曼编码软件！***********************\n\n");
printf("***********************************************************************\n\n");
printf(" 使用时请在桌面或C:\\Program Files\\WINYES\\TC20H\\PROJECT\n加载这3个文件：1.hfmTree.txt 2.hfmTreeTree.txt 3.Printing.txt\n\n");
printf("***********************************************************************\n\n");
creathfmt(ht);
printhfmt(ht);
huffmannode(ht);
Encoding(ht);
q=initqueue(q);
decoding(ht,q);
system("pause");
}
题 目 ：哈夫曼编码和译码系统
基本要求：(1) 能输入字符集和各字符频度建立哈夫曼树；
(2) 产生各字符的哈夫曼编码，并进行解码。
提高要求：(1) 能设计出简捷易操作的窗口界面；
(2) 编码和译码存储在文件中。
#include
#include
#include
#define N 100
#define M 2*N-1
typedef char * HuffmanCode[2*M];//haffman编码
typedef struct
{
int weight;//权值
int parent;//父节节点
int LChild;//左子节点
int RChild;//右子节点
}HTNode,Huffman[M+1];//huffman树
typedef struct Node
{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}WNode,WeightNode[N];
/***产生叶子结点的字符和权值***/
void CreateWeight(char ch[],int *s,WeightNode CW,int *p)
{
int i,j,k;
int tag;
*p=0;//叶子节点个数
//统计字符出现个数,放入CW
for(i=0;ch[i]!='\0';i++)
{
tag=1;
for(j=0;j
{
tag=0;
break;
}
if(tag)
{
CW[++*p].c=ch[i];
CW[*p].weight=1;
for(k=i+1;ch[k]!='\0';k++)
if(ch[i]==ch[k])
CW[*p].weight++;//权值累加
}
}
*s=i;//字符串长度
}
/********创建HuffmanTree********/
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
//初始化哈夫曼树
for(i=1;i<=n;i++)
{
ht[i].weight =w[i].weight;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s1=j;
//找到第一个双亲不为零的结点
for(;j<=i-1;j++)
if(!ht[j].parent)
s1=ht[s1].weight>ht[j].weight?j:s1;
ht[s1].parent=i;
ht[i].LChild=s1;
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s2=j; //找到第二个双亲不为零的结点
for(;j<=i-1;j++)
if(!ht[j].parent)
s2=ht[s2].weight>ht[j].weight?j:s2;
ht[s2].parent=i;
ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;//权值累加
}
}
/***********叶子结点的编码***********/
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode h,WeightNode weight,int m,int n)
{
int i,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';//末尾置0
for(i=1;i<=n;i++)
{
start=n-1; //cd串每次从末尾开始
c=i;
p=ht[i].parent;//p在n+1至2n-1
while(p) //沿父亲方向遍历,直到为0
{
start--;//依次向前置值
if(ht[p].LChild==c)//与左子相同,置0
cd[start]='0';
else //否则置1
cd[start]='1';
c=p;
p=ht[p].parent;
}
weight[i].num=n-start; //二进制码的长度(包含末尾0)
h[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(h[i],&cd[start]);//将二进制字符串拷贝到指针数组h中
}
free(cd);//释放cd内存
system("pause");
}
/*********所有字符的编码*********/
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)
{
int i,k;
for(i=0;i
for(k=1;k<=n;k++) /*从weight[k].c中查找与ch[i]相等的下标K*/
if(ch[i]==weight[k].c)
break;
hc[i]=(char *)malloc((weight[k].num)*sizeof(char));
strcpy(hc[i],h[k]); //拷贝二进制编码
}
}
/*****解码*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf("***StringInformation***\n");
while(i
p=2*n-1;//从父亲节点向下遍历直到叶子节点
for(j=0;hc[i][j]!='\0';j++)
{
if(hc[i][j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf("%c",w[p].c); /*打印原信息*/
i++;
}
}
/*****释放huffman编码内存*****/
void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)
{
int i;
for(i=1;i<=n;i++)//释放叶子结点的编码
free(h[i]);
for(i=0;i
}
void main()
{
int i,n=0; /*n为叶子结点的个数*/
int m=0; /*m为字符串ch[]的长度*/
char ch[N]; /*ch[N]存放输入的字符串*/
Huffman ht; /*Huffman二叉数 */
HuffmanCode h,hc; /*h存放叶子结点的编码，hc 存放所有结点的编码*/
WeightNode weight; /*存放叶子结点的信息*/
printf("\t***HuffmanCoding***\n");
printf("please input information :");
gets(ch); /*输入字符串*/
CreateWeight(ch,&m,weight,&n); /*产生叶子结点信息，m为字符串ch[]的长度*/
printf("***WeightInformation***\n Node ");
for(i=1;i<=n;i++) /*输出叶子结点的字符与权值*/
printf("%c ",weight[i].c);
printf("\nWeight ");
for(i=1;i<=n;i++)
printf("%d ",weight[i].weight);
CreateHuffmanTree(ht,weight,n); /*产生Huffman树*/
printf("\n***HuffamnTreeInformation***\n");
printf("\ti\tweight\tparent\tLChild\tRChild\n");
for(i=1;i<=2*n-1;i++) /*打印Huffman树的信息*/
printf("\t%d\t%d\t%d\t%d\t%d\n",i,ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);
CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/
printf(" ***NodeCode***\n"); /*打印叶子结点的编码*/
for(i=1;i<=n;i++)
{
printf("\t%c:",weight[i].c);
printf("%s\n",h[i]);
}
CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的编码*/
printf("***StringCode***\n"); /*打印字符串的编码*/
for(i=0;i
system("pause");
TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/
FreeHuffmanCode(h,hc,n,m);
system("pause");
}