/******************************************************************************************************
* 哈夫曼编/译码器 *
* author: *
* email:
[email protected] *
* data:2006/11/15 *
* desciption: 用哈夫曼码实现 编码 和 译码的 任务 *
* *
* 备注：不追究版权，请随便引用； *
*******************************************************************************************************/
#include<string.h>
#include<conio.h>
#include<stdio.h> //输入和输出函数的头文件
#include<stdlib.h> //exit函数的头文件
#include<malloc.h> //malloc函数的头文件
#include<iostream.h>
//**********************************************************
#define OVERFLOW -2 //溢出时的值为-2
#define OK 1 //成功时时的值为1
#define ERROR 0 //不成功时时的值为0
//**********************************************************
typedef int ElemType; //ElemType 任意的数据类型
typedef int Status; //ElemType 任意的数据类型
//
//**********************************************************
//********************Huffmantree的结点结构***************************
typedef struct{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
//**********************************************************
#define CHLENGTH 27 //8
#define WLENGTH 27 //8
void HuffmanCoding(HuffmanTree &,HuffmanCode &,int *,int );
void Select(HuffmanTree ,int ,int &,int &);
void HuffmanDecoding(char *,HuffmanTree ,HuffmanCode ,int *,int *,int );
void Treeprinting(char *,HuffmanTree ,HuffmanCode ,int *,int *,int );
void preorder(HuffmanTree HT,int root,int i,int sum,int *,int *,FILE *);
void main(void){
int ch[CHLENGTH]={' ','A','B','C','D','E','F','G',
'H','I','J','K','L','M','N',
'O','P','Q','R','S','T','U',
'V','W','X','Y','Z'}; //
int w[WLENGTH]={186,64,13,22,32,103,21,15,47,57,
1,5,32,20,57,63,15,1,48,51,80,
23,8,18,1,16,1}; //
/* int ch[CHLENGTH]={'T','H','I','S',' ','P','R','O','G','R','A','M',' ',
'I','S',' ','M','Y',' ','F','A','V','O','R','I','T','E'};
int w[WLENGTH]={80,47,57,51,186,15,48,63,15,48,64,20,186,57,51,186,20,16,21,
64,8,63,48,57,80,103};
*/
int i=1;
// int ch[CHLENGTH]={5,29,7,8,14,23,3,11};
char buff[1025];
// int w[WLENGTH]={500,2900,700,800,1400,2300,300,1100};
char c,ch1;
FILE *fp_1,*fp_2;
int flag=1,legth=0;
HuffmanTree HT;
HuffmanCode HC;
while(1){
printf("*********************************************************\n");
printf("(1) e 进行编码\n");
printf("(2) d 译码 工作\n");
printf("(3) p 打印CodeFile.txt\n");
printf("(4) t 打印HuffmanTree \n");
printf("(5) q 退出程序\n");
printf("*********************************************************\n");
scanf("%c",&c);
getchar();
switch(c){
case 'e':
HuffmanCoding(HT,HC,w,WLENGTH); //进行编码
if((fp_1=fopen("CodeFile.txt","w")) == NULL){
printf("can not open the file\n");
getch();
exit(0);
}
for(i=1;i<WLENGTH+1;i++){
printf("%c",ch[i-1]);
//putchar(ch[i-1]);
printf(" ");
fputs(HC[i],fp_1); //存储在文件中
puts(HC[i]); //打印在屏幕上
}
fclose(fp_1);//
break;
case 'd':
if((fp_1=fopen("CodeFile.txt","r")) == NULL){//此处 以只读方式 打开 是 "r "
printf("can not open the file\n");
getch();
exit(0);
}
i=0;
while( !feof(fp_1) ){
fgets(buff,1024,fp_1);
//legth=strlen(buff);//求出这个串的长度
HuffmanDecoding(buff,HT,HC,w,ch,WLENGTH);
}
break;//译码 工作
case 'p':
i=0;//每50行 打印的
if((fp_1=fopen("CodeFile.txt","r")) == NULL){//此处 以只读方式 打开 是 "r "
printf("can not open the file\n");
getch();
exit(0);
}
if((fp_2=fopen("CodePin.txt","w")) == NULL){//
printf("can not open the file\n");
getch();
exit(0);
}
ch1=fgetc(fp_1);
while( !feof(fp_1) ){ //让读者看一遍这个文件 也方便我 调试时的检查
i++;
putchar(ch1);
fprintf(fp_2,"%c",ch1);
if(i%50 == 0) {
printf("\n");
fprintf(fp_2,"%c",'\n');
}
ch1=fgetc(fp_1);
}
printf("\n");
//打印CodeFile.txt
break;
case 't': Treeprinting(buff,HT,HC,w,ch,WLENGTH);
//打印HuffmanTree
break;
case 'q': exit(0);
}
}
/*
i=1;
//HuffmanDecode
while( !feof(fp_1) ) {
buff[i]=fgetc(fp_1);
i++;
}
fclose(fp_1);
*/
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {
// 算法6.12
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j, m, s1, s2, start;
char *cd;
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(" 按任意键，继续 ...");
//getch();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1, 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("\nselect: 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(" 按任意键，继续 ...");
//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
}
printf("\n");
free(cd); // 释放工作空间
} // HuffmanCoding
void Select(HuffmanTree HT,int x,int &s1,int &s2){
int firstmin=HT[1].weight,secondmin=HT[1].weight; //第一个权值
int firstnummin=1,secondnummin=1;
int i=1,count=1,j=1;
while(1){
if(HT[i].parent == 0){
//为其赋初值
firstmin=HT[i].weight;
secondmin=HT[i].weight;
firstnummin=i;
secondnummin=i;
j=i;
break;
}
i++;
}
/*
for(i=1;i<x;i++){
if(HT[i].weight < firstmin && HT[i].parent == 0){
firstmin=HT[i].weight;
firstnummin=i;
if(secondmin < firstmin){
secondmin = firstmin;
secondnummin=i;
}
}*/
for(++i;i<=x;i++){
//取出最小值
if(HT[i].weight < firstmin && HT[i].parent == 0){
firstmin=HT[i].weight;
firstnummin=i;//返回号
}
}
i=j;
for(++i;i<=x;i++){
//取出次小值
if(HT[i].weight > firstmin && HT[i].weight < secondmin && HT[i].parent == 0){
//if( HT[i].parent == 0){
//if( i< (int)(WLENGTH/2) ){
secondmin=HT[i].weight;
secondnummin=i;//返回号
//}
//}
}
else if(secondmin == firstmin && HT[i].parent == 0){
//特殊情况 给与考虑 (就是当这俩权值相等的时候)
secondnummin=i;
break;
}
}
s1=firstnummin;
s2=secondnummin;
}
void HuffmanDecoding(char *buff,HuffmanTree HT,HuffmanCode HC,int *w,int *ch,int n){
int root=0,i=0,j=0,lchild=0,rchild=0,k=1;
char result[100];
FILE *fp;
root=2*n-1;
if((fp=fopen("TextFile.txt","w")) == NULL){
printf("can not open the file\n");
exit(0);
}
while(buff[i]!='\0'){
if(buff[i] == '0' ){
result[j]=buff[i];//把编码存入这个 结果的数组中
j++;
root=HT[root].lchild;//一种递归的方法 把左子树的root
//更新成新的root
if( HT[root].lchild == 0 ){
//。。当左子树等于空时找到了
// j=0;
/* while(w[j] != HT[root].weight) {
j++;
}*/
result[j]='\0';
while( strcmp(HC[k],result) != 0) k++;
printf("%c",ch[k-1]);
fprintf(fp,"%c",ch[k-1]);//写入文件
j=0;
k=1;
root=2*n-1;
++i;
}
else if(root != 2*n-1) ++i;
}
else if(buff[i] == '1' ){
root=HT[root].rchild;
result[j]=buff[i];
j++;
if(HT[root].rchild == 0 ){
//j=0;
/*while(w [j] != HT[root].weight) {
j++;
}
*/
result[j]='\0';
while( strcmp(HC[k],result) != 0) k++;
printf("%c",ch[k-1]);
fprintf(fp,"%c",ch[k-1]);
j=0;k=1;
root=2*n-1;
++i;
}
else if(root != 2*n-1) ++i;
}
}
fclose(fp);
printf("\n---------------------------------------------\n");
}
void Treeprinting(char *buff,HuffmanTree HT,HuffmanCode HC,int *w,int *ch,int n){
int root=0,i=1,j=0,lchild=0,rchild=0,k=1,space=0;//space是空格数
// char result[100];
FILE *fp;
if((fp=fopen("TextFile.txt","w")) == NULL){
printf("can not open the file\n");
exit(0);
}
root=2*n-1;
preorder(HT,root,i,i,ch,w,fp);
fclose(fp);
printf("\n---------------------------------------------\n");
}
void preorder(HuffmanTree HT,int root,int i,int sum,int *ch,int *w,FILE *fp){
int lchild=0,rchild=0;
if(HT == NULL){
return;
}
if(i == 1) {
sum=sum+i;
while(i<sum){
printf(" ");
fprintf(fp," ");
i++;
}
i=1;
if( HT[root].lchild == 0 && HT[root].rchild == 0 ){
fprintf(fp,"*%d\n",HT[root].weight);
printf("*%d\n",HT[root].weight);
}
if( HT[root].lchild != 0 || HT[root].rchild != 0 ){
fprintf(fp,"%d\n",HT[root].weight);
printf("%d\n",HT[root].weight);
}
}
if(i == 2) {
sum=sum+i;
while(i<sum){
printf(" ");
fprintf(fp," ");
i++;
}
i=2;
if( HT[root].lchild == 0 && HT[root].rchild == 0 ){
fprintf(fp,"*%d\n",HT[root].weight);
printf("*%d\n",HT[root].weight);
}
if( HT[root].lchild != 0 || HT[root].rchild != 0 ){
fprintf(fp,"*%d\n",HT[root].weight);
printf("%d\n",HT[root].weight);
}
}
if(HT[root].lchild != 0){
lchild=HT[root].lchild ;
i=1;
preorder( HT,lchild,i,sum,ch,w,fp);
}
if(HT[root].rchild != 0){
rchild=HT[root].rchild ;
i=2;
preorder( HT,rchild,i,sum,ch,w,fp);
}
}