/*==============================================*/
/* */
/* huffman.c(pp) - a huffman arithmetic demonstration */
/* smith_135@163.com */
/* QQ: 58101543 */
/* version 0.9 */
/* copyright (c) meteor135 */
/* 2004.7.13 */
/* */
/*==============================================*/
#include <stdio.h>
#include <stdlib.h>
#ifdef __cplusplus
#include <conio.h>
#include <ctype.h>
#include <string.h>
#endif /*__cplusplus*/
/*树结构和全局结构指针*/
struct node
{
int num;/*结点编号*/
char c;
int weight;
int parent;
int lchild,rchild;
} * ht;
/*常量文件名*/
const char *TableFileName = "HfmTbl.txt";
const char *SourceFileName = "SrcText.txt";
const char *CodeFileName = "HfmCode.txt";
const char *DecodeFileName = "DecodeText.txt";
const char *TreeViewFileName = "TreeView.txt";
/*打印格式字符串常量*/
const char *PrintFormatStr = "%4d %13c %13d %13d %13d %13d\r\n";
/*读取格式字符串常量*/
const char *ReadFormatStr = "%d %c %d %d %d %d";
/*打印参数宏*/
#define PRINT_PARAM(i) ht[(i)].num,ht[(i)].c,ht[(i)].weight, ht[(i)].parent,ht[(i)].lchild,ht[(i)].rchild
/*读取参数宏*/
#define READ_PARAM(i) &ht[(i)].num,&ht[(i)].c,&ht[(i)].weight, &ht[(i)].parent,&ht[(i)].lchild,&ht[(i)].rchild
/*打印格式和参数宏*/
#define READ_FORMAT_PARAM(i) ReadFormatStr,READ_PARAM(i)
/*读取格式和参数宏*/
#define PRINT_FORMAT_PARAM(i) PrintFormatStr,PRINT_PARAM(i)
/************************************************************/
/** UTILITY FUNCTIONS **/
/************************************************************/
/*内存交换函数，用于结构体变量交换*/
void MemSwap(void *buf1, void *buf2, size_t buflen)
{
if(buf1!=buf2)
{
void *p = malloc(buflen);
memmove(p,buf1,buflen);
memmove(buf1,buf2,buflen);
memmove(buf2,p,buflen);
free(p);
}
}
/*打印表*/
void PrintHT(int from, int to)
{
int i;
for(i=from;i<=to;i++)
{
printf(PRINT_FORMAT_PARAM(i));
}
printf("\n");
}
/*选择法排序*/
void SelectSort(int from, int to)
{
int i,j,k;
for(i=from;i<to;i++) /*sort */
{
for(k=i,j=i+1;j<=to;j++)
if(ht[j].weight<ht[k].weight)
k=j;
if(k!=i)
MemSwap(&ht[k],&ht[i],sizeof(struct node));
PrintHT(from,to);
}
}
/*释放ht*/
void free_ht()
{
if(ht != NULL)
{
free(ht);
ht = NULL;
}
}
/*从文件读取数据保存到全局堆中，调用方要记得释放*/
int ReadFromFile()
{
int i;
int m;
FILE *h;
if((h=fopen(TableFileName,"r"))==NULL)
{
printf("cannot open %s\n", TableFileName);
getch();
return 0;
}
fscanf(h,"%d",&m);
free_ht();
ht=(struct node *)calloc(m+1,sizeof(struct node));
//printf("%d\n",m);
for(i=1;i<=m;i++)
{
fscanf(h,READ_FORMAT_PARAM(i));
// printf(PRINT_FORMAT_PARAM(i));
}
fclose(h);
return m;
}
/*吃掉无效的垃圾字符*/
void EatCharsUntilNewLine()
{
while(getchar()!='\n')
continue;
}
/*按节点序号重新排序*/
void SortByNum(int m)
{
int i = 0, j;
size_t len = sizeof(struct node);
for(i = 1; i < m; i ++)
{
for(j = i + 1; j <= m; j ++ )
{
if (ht[j].num == i)
{
MemSwap(&ht[i],&ht[j],len);
break;
}
}
}
}
/************************************************************/
/** COMMAND INSTRUCTION FUNCTIONS **/
/************************************************************/
/*初始化并写入文件*/
void Initialize()
{
int i=0,x=0,y=0,n,m;
FILE *h;
puts("input the number of the total char n:");
scanf("%d",&n);
EatCharsUntilNewLine();
m=2*n-1;
ht=(struct node *)calloc(m+1,sizeof(struct node));
/*遍历叶子结点进行初始化*/
for(i=1;i<=n;i++)
{
puts("input a char:");
scanf("%c",&ht[i].c);
EatCharsUntilNewLine();
puts("input the weight of this char:");
scanf("%d",&ht[i].weight);
EatCharsUntilNewLine();
ht[i].num=i;
}
PrintHT(1,n);
for(i=n+1;i<=m;i++) /*adding branch */
{
ht[i].c='$';
ht[i].num=i;
}
PrintHT(n+1,m);
/*用选择法将第1到n个元素从小到大排序*/
SelectSort(1,n);
PrintHT(1,n);
for(x=1,i=n+1;i<=m;i++,x+=2)
{
y=x+1;
ht[x].parent=ht[y].parent=i;
ht[i].lchild=ht[x].num;
ht[i].rchild=ht[y].num;
ht[i].weight=ht[x].weight+ht[y].weight;
/*排序*/
SelectSort(1, i);
}
/*察看排序效果*/
PrintHT(1,m);
getch();
SortByNum(m);
/*察看恢复序号效果*/
PrintHT(1,m);
getch();
/*数据写入文件并输出至屏幕*/
if((h=fopen(TableFileName,"wb"))==NULL)
{
printf("cannot open %s\n", TableFileName);
getch();
return;
}
printf("The huffmantree is:\n");
printf(" number character weight parent lchild rchild\n");
/*首行写入数据行数*/
fprintf(h,"%d\r\n",m);
/*循环写入每行同时向屏幕输出*/
for(i=1;i<=m;i++)
{
printf(PRINT_FORMAT_PARAM(i));
fprintf(h,PRINT_FORMAT_PARAM(i));
}
free_ht();
fclose(h);
}
/*编码并写入文件*/
void Encode()
{
int i,mm,c,f,start;
char wr,*cd = (char *)NULL, ch;
char **HC = (char **)NULL;
FILE *fp1, *fp2;
int m = ReadFromFile();
int n = (m+1)/2;
if(HC!=NULL) free(HC);
HC=(char **)calloc(n+1,sizeof(char *));
if(HC==NULL) return;
if(cd!=NULL) free(cd);
cd=(char *)calloc(n,sizeof(char));
if(cd==NULL) return;
for(i=1;i<=n;i++)
{
start=n-1;
for(c=i,f=ht[i].parent; f!=NULL; c=f,f=ht[f].parent)
{
/*cd[--start]='1'-(ht[f].lchild==c);*/
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);
for(i=1;i<=n;i++)
printf("%c----%s\n",ht[i].c,HC[i]);
printf("IF input the file tobetran select A or a, ELSE read from %s.\n",SourceFileName);
printf("PLEASE INPUT:");
scanf("%c",&wr);
if(wr=='a'||wr=='A')
{
if((fp1=fopen(SourceFileName,"w+"))==NULL)
{
printf("cannot open %s\n", SourceFileName);
getch();
return;
}
printf("Please input the tobetran:(end with '#')\n");
ch=getch();
while(ch!='#')
{
fputc(ch,fp1);
putchar(ch);
ch=getch();
}
rewind(fp1);
printf("\n");
}
else
{
if((fp1=fopen(SourceFileName,"r"))==NULL)
{
printf("cannot open %s\n", SourceFileName);
getch();
return;
}
}
if((fp2=fopen(CodeFileName,"w"))==NULL)
{
printf("cannot open %s\n", CodeFileName);
getch();
return;
}
while(!feof(fp1))
{
ch=fgetc(fp1);
for(i=1;i<=n;i++)
if(ht[i].c==ch)
for(mm=0;HC[i][mm]!='\0';mm++)
{
fputc(HC[i][mm],fp2);
printf("%c",HC[i][mm]);
}
}
printf("\n");
for(i=1;i<=n;i++)
fprintf(fp1,"\r\n%c----%s",ht[i].c,HC[i]);
for(i=1;i<=n;i++)
fprintf(fp2,"\r\n%s----%c",HC[i],ht[i].c);
for(i = 1; i <= n; i ++)
{
free(HC[i]);
}
free(HC);
free_ht();
fclose(fp1);
fclose(fp2);
}
/*解码写入文件并输出*/
void Decode()
{
FILE *CodeFileP, *TextFileP;
char ch = '\0';
int f;
int m = ReadFromFile();
f = m;
if((CodeFileP=fopen(CodeFileName,"r"))==NULL)
{
printf("cannot open %s\n", CodeFileName);
getch();
return;
}
if((TextFileP=fopen(DecodeFileName,"w"))==NULL)
{
printf("cannot open %s\n", DecodeFileName);
getch();
return;
}
while(!feof(CodeFileP)&&ch!='\n')
{
ch=fgetc(CodeFileP);
if(ch=='0')
f=ht[f].lchild;
if(ch=='1')
f=ht[f].rchild;
if(!ht[f].lchild&&!ht[f].rchild)
{
fputc(ht[f].c,TextFileP);
printf("%c",ht[f].c);
f=m;
}
}
free_ht();
fclose(CodeFileP);
fclose(TextFileP);
printf("\n");
}
/*不解码直接输出文件中的huffman编码*/
void PrintCode()
{
int i=0;
char ch = 0;
FILE *CodeFileP;
if((CodeFileP=fopen(CodeFileName,"r"))==NULL)
{
printf("cannot open %s\n",CodeFileName);
getch();
return;
}
while(!feof(CodeFileP)&&ch!='\n')
{
if(i++==50)
{
printf("\n");
i=0;
}
ch=fgetc(CodeFileP);
printf("%c",ch);
}
printf("\n");
fclose(CodeFileP);
}
/*输出Huffman树*/
void PrintTree()
{
int i,k,top,p;
int *level,*stack;
FILE *TreePrintFileP;
int m = ReadFromFile();
int n = (m+1)/2;
if((TreePrintFileP=fopen(TreeViewFileName,"w"))==NULL)
{
printf("cannot open %s\n", TreeViewFileName);
getch();
return;
}
printf("THE HUFFMANTREE IS :\n");
fprintf(TreePrintFileP,"THE HUFFMANTREE IS :\n");
level=(int *)malloc(n*sizeof(int));
stack=(int *)malloc(n*sizeof(int));
if(m!=0)
{
top=1;
stack[top]=m;
level[top]=3;
while(top>0)
{
p=stack[top];
k=level[top];
for(i=1;i<=k;i++)
{
printf(" ");
fprintf(TreePrintFileP," ");
}
printf("%d\n",ht[p].weight);
fprintf(TreePrintFileP,"%d\n",ht[p].weight);
top--;
if(ht[p].rchild!=0)
{
top++;
stack[top]=ht[p].rchild;
level[top]=k+3;
}
if(ht[p].lchild!=0)
{
top++;
stack[top]=ht[p].lchild;
level[top]=k+3;
}
}
}
free(level);
free(stack);
fclose(TreePrintFileP);
}
int prompt()
{
char en;
puts("\n******************* huffman arithmetic demonstration *****************");
puts("i/I---Initialize e/E---encode p/P---print file's code");
puts("t/T---print hfmtree d/D---decode q/Q---quit program");
puts("******************* huffman arithmetic demonstration *****************");
puts("please choose a menu item and press enter to continue.");
printf(">");
scanf("%c",&en);
EatCharsUntilNewLine();
return tolower(en);
}
void main()
{
while(1)
{
switch(prompt())
{
case 'i':
Initialize();
break;
case 'e':
Encode();
break;
case 'd':
Decode();
break;
case 'p':
PrintCode();
break;
case 't':
PrintTree();
break;
case 'q':
free_ht();
return;
}
}
}
