哈夫曼编码.doc

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

#define MAX 99999
#define N 27 //定义最多节点个数
#define M 2*N-1 //中间节点个数

typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
}HTNode,*HuffmanTree[M+1]; //因为零号单元不适用

typedef char *HuffmanCode[N+1];

HuffmanCode co; //创建全局变量用于存储HuffmanCode
char CH[N];
int weight[N]={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};
HuffmanTreeht;
char word[30]; //全局变量用于储存键入的内容

void Init_CH()
{
int i;
CH[26]='';
CH[0]='A';
for(i=1;i<26;i++)
CH[i]='A'+i;
for(i=0;i<27;i++)
printf("%c",CH[i]);
}

void select(int *sr,int *sl,int n)
{
int i,point;
point=MAX;
for(i=0;i<n;i++)
{
if(ht[i+1].weight<point&&ht[i+1].parent==0)
{
*sr=i+1; //*sr是最小的
point=ht[*sr].weight;
}
}
ht[*sl].parent=1;
}

void InitHuffmanCode()
{
int i,sr,sl;
for(i=1;i<=N;i++)
{
ht[i].weight=weight[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");
for(i=N+1;i<=M;i++)
{
select(&sr,&sl,i-1);
ht[i].weight=ht[sr].weight+ht[sl].weight;
ht[sr].parent=i;
ht[sl].parent=i;
ht[i].lchild=sr;
ht[i].rchild=sl;
}
for(i=1;i<=M;i++)
{
printf("%d%d\n",ht[i].parent,i);
}
}

void CreateHuffmanCode()
{
FILE *trans;
int i,start,p,c;
char *cd;
cd=(char*)malloc(N*sizeof(char));
cd[N-1]='\0';
for(i=1;i<=N;i++)
{
start=N-1;
c=i;
p=ht[i].parent;
while(p)
{
--start;
if(ht[p].lchild==c)
cd[start]='0';
else
cd[start]='1';
c=p;
p=ht[p].parent;
}
co[i]=(char*)malloc((N-start)*sizeof(char));
strcpy(co[i],&cd[start]);
printf("%s %d\n",co[i],i);
}
if((trans=fopen("C:data.txt","w"))==NULL)
{
printf("不能打开此文件!");
exit(0);
}
fputs("..........哈夫曼编码表初始化如下..........\n",trans);
for(i=0;i<N;i++)
{
fputc(CH[i],trans);
fputs(" :",trans);
fputs(co[i+1],trans);
fputs("\n",trans);
}
fclose(trans);
}

void InputHuffmanWord()
{
FILE *fp;
if((fp=fopen("C:stword.txt","w"))==NULL)
{
printf("不能打开此文件!");
exit(0);
}
printf("请输入以'#'号结束的大写字母字符串: \n");
while(strcmp(word,"#")!=0)
{
fputs(word,fp);
gets(word);
}
fclose(fp);
}

//选择原码输入类型
void SelectInputType()
{
system("cls");
int point;
while(1)
{
printf(" '0':从键盘键入编码内容\n");
printf(" '1':从文件中读取编码内容\n");
printf(" '2':退出\n");
scanf("%d",&point);
system("cls");
switch(point)
{
case 0:InputHuffmanWord();break;
case 1:printf("将编码内容保存在stword.txt文件即可. \n");
printf("请进行下一步操作! \n");
break;
case 2:printf("已经退出输入编码内容. \n");return;
default printf("输入错误! \n");break;
}
}
}

//编码
void Huffman_Encod()
{
int p=M,i,flag;
FILE *Input,*Output;
char ch;
if((Output=fopen("C:stword.txt","r"))==NULL)
{
printf("不能打开此文件!");
exit(0);
}
if((Input=fopen("C:stcode.txt","w"))==NULL)
{
printf("不能打开此文件!");
exit(0);
}
while(!feof(Output)) //遇到输入文件的结束标识
{
flag=0;
ch=fgetc(Output); //putchar(ch);
for(i=0;i<N;i++)
{
if(CH[i]==ch)
{
fputs(co[i+1],Input);
flag=1;
}
}
if(flag==0)
{
fputc('*',Input);
}
}
fclose(Output);
fclose(Input);
}

//译码
void Huffman_Decod()
{
FILE *fp,*Input;
int p=M,i=0;
char ch;
if((fp=fopen("C:stcode.txt","r"))==NULL)
{
printf("不能打开此文件!");
exit(0);
}
if((Input =fopen("C:stword_1.txt","w"))==NULL)
{
printf("不能打开此文件!");
exit(0);
}
ch = fgetc(fp);
while(!feof(fp))
{
if(ch=='0')
p=ht[p].lchild;
else if(ch =='1')
p = ht[p].rchild;
else if(ch =='*')
{
fputs("*",Input);
putchar(ch);
}
else
printf("输入错误!");
if(ht[p].lchild == 0 && ht[p].rchild == 0)
{
fputc(CH[p-1],Input);
putchar(CH[p-1]);
p = M;
}
ch = fgetc(fp);
}
fclose(fp);
fclose(Input);
printf("\n");
}

//译码与源码比较
void Compare_word()
{
char ch_1,ch_2;
int flag = 1;
FILE *origin, *decod;
if((origin =fopen("C:stword.txt","r"))==NULL)
{
printf("不能打开此文件!");
exit(0);
}
if((decod =fopen("C:stword_1.txt","r"))==NULL)
{
printf("不能打开此文件!");
exit(0);
}
while(!feof(decod))
{
ch_1 = getc(decod);
ch_2 = getc(origin);
if(ch_1 != '*')
{
if(ch_1 != ch_2)
flag = 0;
}
}
fclose(decod);
fclose(origin);
if(flag == 0)
printf("原码与译码不相符!\n");
else
printf("原码与译码相符!\n");
}

void main()
{
int point;
Init_CH();
ImitHuffmanCode();
CreateHuffmanCode();
while(l)
{
printf("..........哈夫曼编译器..........\n");
printf("\n '0':初始化哈夫曼表\n");
printf(" '1':输入编码内容\n");
printf(" '2':开始编码\n");
printf(" '3':开始译码\n");
printf(" '4':与译码与源码比较\n");
printf(" '5':退出哈夫曼编译器\n");
scanf("%d",&point);
system("cls");
switch(point)
{
case 0:printf("哈夫曼表初始化完成! \n请进行下一步操作! \n"); break;
case 1:SelectInputType(); break;
case 2:Huffman_Encod();
printf("编码结束！请进行下一步操作！\n");
break;
case 3:
Huffman_Decod();
printf("译码结束!已将译码内容存放stword_1.txt!\n");
printf("请进行下一步操作!\n");
break;
case 4:Compare_word(); break:
case 5:printf("已经退出编译器.\n"); return;
default:printf("输入错误!\n"); break;
}
}
}