huffman编码及译码

原帖及讨论：http://bbs.bc-cn.net/dispbbs.asp?boardid=56&id=157147

*/ --------------------------------------------------------------------------------------
*/ 出自： 编程中国 http://www.bc-cn.net
*/ 作者： 风动 E-mail：xidiankeda492@yahoo.com.cn QQ：３０５６８７９１０
*/ 时间： 2007-7-21 编程论坛首发
*/ 声明： 尊重作者劳动，转载请保留本段文字
*/ --------------------------------------------------------------------------------------


#include "iostream.h"
#include "math.h"
#include "stdlib.h"
#include <string.h>
#define MAXSIZE 100 //最多子叶数
#define MAXCODE 10000 //编码最大长度

typedef struct
{
char info; //关联字符信息
unsigned int weight; //每个节点的权职
unsigned int parent, lchild, rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode; //存储哈弗曼编码

void Select(HuffmanTree HT, int j,int &s1,int &s2)
{//选择双亲节点为0，并且最小的两个子叶节点
int i=1,m;
while(HT[i].parent!=0)
i ; //找第一个双亲节点为0的子叶结点
for(s2=s1=i;i<j;i )
{//确保s1中的权值最小，s2次小
if(HT[i].parent==0 && HT[i].weight<HT[s1].weight)
{
s2=s1;
s1=i;
}
else if(HT[i].parent==0 && HT[i].weight>=HT[s1].weight && HT[i].weight<=HT[s2].weight)
s2=i;
while(HT[i].parent==0 && s1==s2)
{
m=i;
m ;
while(HT[m].parent!=0)
m ;
s2=m;
}
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n, char *info)
{//哈弗曼编码
int i,m;
HuffmanTree p;
if(n<1) return;
m = 2*n-1;
HT = (HuffmanTree)malloc((m 1)*sizeof(HTNode));
for(p=HT 1,i=1;i<=n; i, p, w, info)
{//初始化任何已存在的子叶信息
p->info = *info;
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}//for
for(; i<=m; i, p)
{//构造所需要的过度根节点
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}//for
for(i=n 1;i<=m; i)
{//建立哈弗曼树
int s1,s2;
Select(HT,i-1,s1,s2);
HT[s1].parent =i;
HT[s2].parent =i;
HT[i].lchild = s2;
HT[i].rchild = s1;
HT[i].weight = HT[s1].weight HT[s2].weight;
}//for
//哈弗曼编码
HC = (HuffmanCode)malloc((n 1)*sizeof(char *));
char* cd = (char*)malloc(n*sizeof(char));
cd[n-1] = '\0';
for(i=1;i<=n; i)
{
int f;
unsigned int c;
int start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild==c)
cd[--start] = '0';
else cd[--start] = '1';
}
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i], &cd[start]);
}//for
free(cd);
}//HuffmanCoding

void CheckCoding(HuffmanTree HT, HuffmanCode HC, char *strcheck, int m)
{//查询哈弗曼编码信息
// char *strcopy=new char[MAXCODE];
for(int i=0; i<m; i )
{
for(int j=1; HT[j].info != strcheck[i]; j );
cout<<HC[j];
}
cout<<endl;
}//CheckCoding

void HuffmanTranslateCoding(HuffmanTree HT, int n,char*c)
{//译码过程
int m=2*n-1;
int i,j=0;
while(c[j]!='\0')
{
i=m;
while(HT[i].lchild && HT[i].rchild)
{
if(c[j]=='0')
i=HT[i].lchild;
else if(c[j]=='1')
i=HT[i].rchild;
j ;
}
cout<<HT[i].info;
}
cout<<endl;
}
void main()
{
int n,*w,m;
w=new int[MAXSIZE];
char *info;
char *strcheck=new char[MAXSIZE];
info=new char[MAXSIZE];
char *ch=new char[MAXSIZE];
HuffmanTree HT=new HTNode[MAXSIZE];
HuffmanCode HC=NULL;
cout<<"***********************************************************"<<endl;
cout<<"****** HuffmanCode and HUffmanTranslate ********"<<endl;
cout<<"****** 西安电子科技大学 电脑学院 030514班 ********"<<endl;
cout<<"****** 学号： 03051433 制作人：王甲楼 ********"<<endl;
cout<<"***********************************************************"<<endl;
cout<<"读入叶子节点数 n= ";
cin>>n;
for(int i=0; i<n;i )
{
cout<<"读入第"<<i 1<<"个叶子结点的权值：";
cin>>w[i];
cout<<"读入编码字符: ";
cin>>info[i];
}
HuffmanCoding( HT, HC, w, n,info);

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有