hfm.cpp

JPEG的图像压缩的huffman编码c++实现

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

typedef struct { 
unsigned int weight; 
unsigned int parent,lchild,rchild,ch; 
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表 

int m,s1,s2; 
HuffmanTree HT;

void Select(int n){ //选择两个权值最小的结点
int i,j; 
for(i=1;i<=n;i++){
	if(!HT[i].parent){
		s1 = i;break;
	} 
} 
for(j=i+1;j<=n;j++){
	if(!HT[j].parent){
		s2 = j;break;
	}
} 
for(i=1;i<=n;i++){
	if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i)){
		s1=i;
	}		 
} 
for(j=1;j<=n;j++){
	if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j)){
		s2=j;
	}		 
} 
} 

void HuffmanCoding(HuffmanCode HC[], int *w, int n) { 
// w存放n个字符的权值(均>0)，构造哈夫曼树HT， 
// 并求出n个字符的哈夫曼编码HC 
int i, j; 
char *cd; 
int p; 
int cdlen;
int start;

if (n<=1) return; 
m = 2 * n - 1; 
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用 
for (i=1; i<=n; i++) {//初始化 
	HT[i].weight=w[i-1]; 
    HT[i].parent=0; 
    HT[i].lchild=0; 
    HT[i].rchild=0;
	HT[i].ch=0;
} 
for (i=n+1; i<=m; i++) {//初始化 
	HT[i].weight=0; 
    HT[i].parent=0; 
    HT[i].lchild=0; 
    HT[i].rchild=0;
	HT[i].ch=0;
}  
for (j=1,i=n+1; i<=m; i++,j++) { // 建哈夫曼树 
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点， 
// 其序号分别为s1和s2 
    Select(i-1); 
    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;
	HT[i].ch=j;
}

//-----从叶子到根逆向求每个字符的哈夫曼编码
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i){
	start=n-1;
	HT[i].ch=i;
	for(unsigned int 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]);
} 
free(cd);
}
void PTree(int n){//打印树的结构
	int r=2*n-1;
	printf("树的结构为（0表示无孩子）：\n");
	for(;r>0;r--){
		cout<<HT[r].lchild<<"<--"<<r<<"-->"<<HT[r].rchild<<endl;
	}
}

void trans(){//译码
	int i=m;
	char a;
	printf("输入0/1进行译码，输入'!'进行编码");
	cin>>a;	
	while(a=='0'||a=='1'){
		if(a=='0')i=HT[i].lchild;
		else if(a=='1') i=HT[i].rchild;
		if(HT[i].lchild==0){ 
			cout<<(char)(HT[i].ch+64);
			i=m;
		}
		else if(a=='!') return;//当接收到的输入为"!"时返回主函数进行编码
		cin>>a;
	}
}

void main() { 
HuffmanTree HT;
HuffmanCode *HC;
int *w,n,i,j;
char b,c;
puts("输入结点数："); 
scanf("%d",&n); 
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode)); 
w = (int *)malloc(n*sizeof(int)); 
printf("输入%d个结点的权值\n",n); 
for(i=0;i<n;i++){
	scanf("%d",&w[i]);
}
HuffmanCoding(HC,w,n); 
puts("\n各结点的哈夫曼编码为："); 
for(i=1;i<=n;i++){
	c=(char)i+64;
	cout<<c<<'('<<w[i-1]<<')'<<HC[i]<<endl;
}
PTree(n);
printf("\n各结点的哈夫曼译码为：\n");
trans();
cout<<"请输入源码：";//从trans函数返回进行编码
cin>>b;
j=(int)(b-64);
while(j){
	cout<<HC[j];
	cin>>b;
    j=(int)(b-64);
}
cout<<endl;
system("pause"); 
}