huffmancode.cpp

huffmancode 哈弗曼编码

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <conio.h>
#include <stdlib.h>

#define MAX 65535

typedef struct{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;

void Initialarray(char *string,char *sonce,int *w,int *wascii,int &n,int &stringn); //初始化各值
void Countw(char *string,int *w,char *sonce,int *wascii,int &n,int &stringn);       //统计每个字符出现的个数
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n);                //构造赫夫曼树HT,每个字符的赫夫曼编码保存在HC
void Select(HuffmanTree HT,int n,int &s1,int &s2);                                  //选择parent为0且weight最小的两个结点          
void PrintHuffmanCode(HuffmanCode &HC,char *sonce,int *w,char *string,int n,int stringn); //输出各字符对应的权值，编码，以及字符串对应的赫夫曼编码


void main(){
	int tmp=-1;int n;int stringn;
	HuffmanTree HT;
	HuffmanCode HC;
	char string[50];    //用户输入的字符串	
	char sonce[50];     //记录出现过的字符
	int w[50];          //保存string中的字符对应的统计个数
	int wascii[128];	//利用ASCII码表的字符位置保存对应各字符的个数
	Initialarray(string,sonce,w,wascii,n,stringn);
	

	printf( "\t\t作者: 06计算机科学与技术  SZU\n ");	
	do{
			printf( "\t\t****************赫夫曼编码****************\n ");
			printf( "\t\t1:输入一串字符进行赫夫曼编码.\n");
			printf( "\t\t2:清除屏幕.\n");
			printf( "\t\t0:退出程序.\n>");
			scanf("%d",&tmp); 
			switch(tmp){		
					case 1:
						printf( "\t\t:请输入不超过50个任意字符的字符串:\n>");
						scanf("%s",&string);
						Countw(string,w,sonce,wascii,n,stringn);
						HuffmanCoding(HT,HC,w,n);
						PrintHuffmanCode(HC,sonce,w,string,n,stringn);
						Initialarray(string,sonce,w,wascii,n,stringn);
						break;
					case 2:
						system("cls");  break;
					case 0: 
						tmp = 0;	break;
					default: 
						tmp = -1;	break;
			}
	}while (tmp != 0);    
	
}
void Initialarray(char *string,char *sonce,int *w,int *wascii,int &n,int &stringn){  //初始化各值
	int i;
	for(i=0;i<50;i++){  	
		string[i]=0;
		sonce[i]=0;
		w[i]=0;
		wascii[i]=0;
	}
	for(i=50;i<128;i++)
		wascii[i]=0;
	stringn=0;
	n=0;
}

void Countw(char *string,int *w,char *sonce,int *wascii,int &n,int &stringn){ //统计每个字符出现的个数
	int i=0,j=0;

	for(i=0;string[i]!=0;i++)                      //统计每个字符出现的个数，以ASCII码表中的位置保留统计个数。
	{
		wascii[string[i]]++;
		stringn++;
	}

	for(i=0;i<128;i++)	{						   //把ASCII码表中的数据转移到数组w和sonce
		if(wascii[i]!=0) 
		{
			w[n]=wascii[i];
			sonce[n]=char(i);
			n++;
		}
	}
	
}

void Select(HuffmanTree HT,int n,int &s1,int &s2){ //在HT[1..n]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2。
    int i;unsigned int min1=MAX-1,min2=MAX,tmp;    //次小值min1,最小值min2
	for (i=1; i<=n; i++){
		if(HT[i].parent==0&&HT[i].weight<min2){    //若结点parent为0且weight小于次小值min2
				tmp=HT[i].weight;
				if(tmp<min1) {                     //若weight比最小值min1更小,则把min1赋给min2作为次小值,更小的weight赋给min1
					min2=min1;min1=tmp;
					s2=s1;s1=i;
				} 
				else {min2=tmp;s2=i;}              //若只比次小值min2小，则weight赋给min2
		}		
	}
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {
  // w存放n个字符的权值(均>0)，构造赫夫曼树HT，
  // 并求出n个字符的赫夫曼编码HC
	int i, j, m, s1, s2, start;
	char *cd;
	unsigned int c, f;

	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;
	}
	for (i=n+1;i<=m;i++){ //初始化
		HT[i].weight=0;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}

	printf("\n赫夫曼树的构造过程如下所示：\n");
	printf("HT初始状态:\n  结点  weight  parent  lchild  rchild");
	for (i=1; i<=m; i++)
	printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild, HT[i].rchild);
	
	printf("\t按任意键继续");
	getch();

	for (i=n+1; i<=m; i++) {  // 建赫夫曼树    
		Select(HT, i-1, s1, s2);// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2。
		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;
/*
		printf("\n选择: s1=%d   s2=%d\n", s1, s2);  //每次选择的过程
		printf("  结点  weight  parent  lchild  rchild");
		for (j=1; j<=i; j++)
			printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
		
		printf("\t按任意键继续...");
		getch();*/
	}

  //--- 从叶子到根逆向求每个字符的赫夫曼编码 ---
	HC = (HuffmanCode)malloc((n+1)*sizeof(char*));
	cd = (char *)malloc(n*sizeof(char));    // 分配求编码的工作空间
	cd[n-1] = '\0';                         // 编码结束符。
	for (i=1; i<=n; ++i) {                  // 逐个字符求赫夫曼编码
		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));          // 为第i个字符编码分配空间
		strcpy(HC[i], &cd[start]);          // 从cd复制编码(串)到HC	
	}
	free(cd);   // 释放工作空间
} // HuffmanCoding



void PrintHuffmanCode(HuffmanCode &HC,char *sonce,int *w,char *string,int n,int stringn)//输出各字符对应的权值，编码，以及字符串对应的赫夫曼编码
{
	int i;int j;
	printf("\n各字符的对应赫夫曼编码为: \n");
     for(i=1;i<=n;i++)
     {
		 printf("  字符%c 权值%3d:  ",sonce[i-1],w[i-1]);     //输出字符,权值
         printf("%s\n",HC[i]);                                //输出编码         
     }

	printf("\n原字符串为: ");
	for(i=0;i<stringn;i++)
		printf("%c",string[i]);

	printf("\n得出对应的赫夫曼编码流为: ");
	for(i=1;i<=stringn;i++)
	{
		for(j=1;j<=n;j++)
		if(sonce[j-1]==string[i-1])         //输出对应的赫夫曼编码
			printf("%s",HC[j]);              
	}
	printf("\n\n");

}