📄 huffman.txt
字号:
Huffman编码是最优变长码，请设计一个Huffma编码程序，实现以下功能：
（1）接收原始数据：从终端读入字符集大小n,以及n个字符和权值，建立Huffman 树，并将它文件hfmtree.dat中。
（2）编码：利用已建立的哈夫曼树，对文件中的正文进行编码，将结果存入文件codefile.dat中。
（3）译码：利用已建立号的哈夫曼树将sodefile.dat中的代码进行译码，结果存入文件textfile.dat中。
（4）打印编码规：即字符与编码之间的一一对应关系。
（5）打印Huffman树，将已存入内存中的哈夫曼树以直观的方式显示在终端上。
二．设计思路
HUFFMAN编码是一种最优变长码，即带权路径最小，这种编码有着很强的应用背景，是数据压缩中的一个重要理论依据，很多压缩酸法也都用到了HUFFMAN编码。本程序实现了最简单的一种HUFFMAN编码，可以实现把一个文件中的字符集合进行编码，转换为相应的0 /1代码。同时可以把0/1代码进行译码还原原始文件等功能。
经过分析可以发现，此问题需多次用到文件的存取。再由要求中的最后一条，将已经存入内存中的HUFFMAN树以直观的方式显示在终端上，此问题还用到了图形系统，所以在程序运行的一开始须初始化系统。
要进行HUFFMAN编码首先要知道字符集合， 字符本身和它在电文中出现的频率，以构造HUFFMAN树。本程序提供了两种输入方式，从文件中读取和手工一个个输入。得到HUFFMAN编码后，可以把编码打印在屏幕上。当文件进行编码时，不失一般性，可以只提供文件读取形式，对文件中的正文进行编码后，把结果存于一个文件中，对结果文件进行译码时，直接文件中读取0/1代码，把译码结果一方面显示在屏幕上，另一方面存入另一个文件中。
三．数据结构设计：
#include <stdio.h>
#define MAX 1000
#define MAXSYMBS 30
#define MAXNODE 59
typedef struct
{
int weight;
int flag;
int parent;
int lchild;
int rchild;
}huffnode;
typedef struct
{
int bits[MAXSYMBS];
int start;
}huffcode;
四， 功能函数设计：
（1） 哈夫曼树的初始函数InitHuffman( ).
（2） 建立哈夫曼树函数HUFFMAN TREE( ).
（3） 编码函数HUFFMANCODE( )
（4） 译码函数HENCODE( )
（5） 查看编码规则函数HSHOWCODE（）
（6） 对一些字母进行编码函数CHARCODE( )
（7） 查看已建立的HUFFMAN树函数HUFFMANSHOW TREE( )
（8） 哈夫曼树主选择函数HUFFMANmenu（）。
（9）
#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
#include <malloc.h>
//#include<graphics.h>
#include <conio.h>//getch()的头文件
#define MAXVALUE 1000//权值最大值
#define MAXLEAF 50//叶子最多个数
#define MAXCHARNUM 100//读入字符最大个数
#define MAXCODENUM 400//读0/1代码最大的个数
//#define r 7//圆的半径
void HuffmanMenu(void);
void HuffmanCode(void);
void HuffmanTree(void);
void HuffmanMenu(void);
void HuffmanShowTree(void);
typedef struct hnode//接点类型定义
{
char letter;
char weight,parent,lchild,rchild;
}HuffmanNode;
typedef struct//编码类型定义
{
char letter,bit[MAXLEAF];
int start;
}HCode;
HuffmanNode HuffNode[2*MAXLEAF-1];//全局变量定义
HCode HuffCode[MAXLEAF];
int HuffmanLeaf=0;
int SaveHfmTree(void)//保存Huffman 树
{
FILE *fp;
//int i;
if((fp=fopen("hfmtree.dat","wb"))==NULL)
{
printf("Create file error!\n");
getch();
system("cls");
HuffmanMenu();
}
fwrite(HuffNode,sizeof(struct hnode),2*HuffmanLeaf-1,fp);
printf("\nSave to hfmtree.dat Success!\n");
getch();
system("cls");
fclose(fp);
return 0;
}
/*调入Huffman树进内存*/
void LoadHuffmanTree(void)
{
FILE *fp;
int i=0;
if((fp=fopen("hfmtree.daat","rb"))==NULL)
{
printf("\nLoad file error!(File hfmtree Not Exist!\n");
getch();
system("cls");
HuffmanMenu();
}
/*得到总的结点数i*/
for(i=0;i<MAXLEAF;i++)
if(fread(&HuffNode[i],sizeof(HuffmanNode),1,fp)!=1)
break;
fclose(fp);
HuffmanLeaf=(i+1)/2;/*因为i=2*HuffmanLeaf-1*/
printf("\nLoad Huffman Tree Success!\n");
getch();
HuffmanCode();
system("cls");
HuffmanMenu();
}
/*调入0/1代码进内存*/
void LoadCode(char s[MAXCODENUM])
{
FILE *fp;
char ch[2];
int i;
for(i=0;i<MAXCODENUM;i++)
s[i]=NULL;
if((fp=fopen("codefile.dat","rb"))=NULL)
{
printf("Load codefile error!\n");
getch();
system("cls");
HuffmanMenu();
}
ch[1]='\0';
while((ch[0]=fgetc(fp))!=EOF)
strcat(s,ch);
}
/*从文件中读入字符串进行编码*/
void CharCodeFile(char s[MAXCHARNUM])
{
FILE *fp;
char ch[2],filename[15];
int i;
for(i=0;i<MAXCHARNUM;i++)
s[i]=NULL;
printf("\n Please input filename to code:(For Example:'test.txt')\n");
scanf("%S",filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("Load %s error!\n",filename);
getch();
system("cls");
HuffmanMenu();
}
printf("\n Load File %s Success!\n",filename);
ch[1]='\0';
ch[0]=fgetc(fp);
while(ch[0]!=EOF)
{
strcat(s,ch);
ch[0]=fgetc(fp);
}
fclose(fp);
printf("\n File %s Infotmation id:\n%s\n",filename,s);
}
/*读入文件中字符及其权值*/
int WriteHuffman(HuffmanNode HuffNode[])
{
FILE *fp;
char ch,filename[10];
int weight,i=0;
printf("\nPlease input load file name:(For example:'test.dat')\n");
scanf("%s",filename);
if((fp=fopen(filename,"rb"))==NULL)
{
printf("Can't open %s file!\n",filename);
getch();
system("cls");
HuffmanMenu();
}
printf("\n Load File %s Success!\n",filename);
while(!feof(fp))
{
fscanf(fp,"%c,%d",&ch,&weight);
HuffNode[i].letter=ch;
HuffNode[i].weight=weight;
i++;
}
fclose(fp);
return i;
}
/*Huffman 树初始化*/
void InitHuffman(void)
{
char s[MAXLEAF],ch;
int i;
printf("\n\n1.Computer Loading.\n2.Man Create.");
ch=getch();
if(ch==2)
{
printf("\nPlease input some char:(<=%d)",MAXCHARNUM);
scanf("%s",s);
HuffmanLeaf=strlen(s);
for(i=0;s[i]!='\0';i++)
HuffNode[i].letter=s[i];
printf("\nPlease input some weight:\n");
for(i=0;i<HuffmanLeaf;i++)
scanf("%d",&HuffNode[i].weight);
}
else HuffmanLeaf=WriteHuffman(HuffNode);
HuffmanTree();
HuffmanCode();
system("cls");
HuffmanMenu();
}
/*建立huffman树*/
void HuffmanTree(void)
{
int i,j,m1,m2,x1,x2,temp1;
char temp2;
for(i=0;i<2*HuffmanLeaf-1;i++)/*结点初始化*/
HuffNode[i].parent=HuffNode[i].lchild=HuffNode[i].rchild=-1;
for(i=HuffmanLeaf;i<2*HuffmanLeaf-1;i++)
{
HuffNode[i].letter=NULL;
HuffNode[i].weight=0;
}
for(i=0;i<HuffmanLeaf-1;i++)
for(j=i+1;j<HuffmanLeaf-1;j++)/*对输入权值的大小进行排序*/
if(HuffNode[j].weight>HuffNode[i].weight)
{
temp1=HuffNode[i].weight;
HuffNode[i].weight=HuffNode[j].weight;
HuffNode[j].weight=temp1;
temp2=HuffNode[i].letter;
HuffNode[i].letter=HuffNode[j].letter;
HuffNode[j].letter=temp2;
}
/*构造huffma树*/
for(i=0;i<HuffmanLeaf-1;i++)
{
m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<HuffmanLeaf-1;j++) /*寻找权值最小和次小的结点*/
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1)
{
m2=m1;x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)
{
m2=HuffNode[j].weight;
x1=j;
}
}
HuffNode[x1].parent=HuffmanLeaf+i;
HuffNode[x2].parent=HuffmanLeaf+i;/*权值最小和次小的结点进行组合*/
HuffNode[HuffmanLeaf+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[HuffmanLeaf+i].lchild=x1;
HuffNode[HuffmanLeaf+i].rchild=x2;
}
printf("\nCreate Huffman Tree Success!Save it?(Y/N)\n");/*保存文件hfmtree.dat*/
temp2=getch();
if(temp2=='y'||temp2=='Y') SaveHfmTree();
}
/*生成编码*/
void HuffmanCode(void)
{
HCode cd;
int i,j,c,p/**q*/;
// char code[30];
/*按结点位置进行编码*/
for(i=0;i<HuffmanLeaf;i++)
{
cd.start=HuffmanLeaf-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1)
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]='0';
else
cd.bit[cd.start]='1';
cd.start--;
c=p;
p=HuffNode[c].parent;
}
/*存储编码*/
for(j=cd.start+1;j<HuffmanLeaf;j++)
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
/*字符复制*/
for(i=0;i<HuffmanLeaf;i++)
HuffCode[i].letter=HuffNode[i].letter;
printf("\nCode Create Success!");
}
/*查看编码规则*/
void HShowCode(void)
{
int i;
if(HuffmanLeaf==0)
{
printf("\nHUffman Tree NOt Be Init Yet!\n");
getch();
system("cls");
HuffmanMenu();
}
printf("\n\nThe Huffmaan code are:\n");
for(i=0;i<HuffmanLeaf;i++)
{
printf(" %c:",HuffCode[i].letter);
printf("%s\n",HuffCode[i].bit+HuffCode[i].start+1);
}
getch();
system("cls");
HuffmanMenu();
}
/*对一些字母进行编码*/
void CharCode(void)
{
FILE *fp;
char s[MAXCHARNUM];
int i,j,n;
if(HuffmanLeaf==0)
{printf("\nHUffman Tree NOt Be Init Yet!\n");
getch();
//system("cls");
HuffmanMenu();
}
if((fp=fopen("codefile.dat","wb"))==NULL)
{
printf("\ncreate file error!\n");
getch();
system("cls");
HuffmanMenu();
}
CharCodeFile(s);
n=strlen(s);
for(i=0;i<n;i++)
{
for(j=0;j<HuffmanLeaf;j++)
if(s[i]==HuffCode[j].letter) break;
fprintf(fp,"%s",HuffCode[j].bit+HuffCode[j].start+1);
}
fclose(fp);
getch();
system("cls");
HuffmanMenu();
}
/**********译码**************/
void HEncode(void)
{
int c;
char code[MAXCODENUM],*m;
FILE *fp;
if((fp=fopen("textfile.dat","wb"))==NULL)
{
printf("\ncreate file error!\n");
getch();
//system("cls");
HuffmanMenu();
}
if(HuffmanLeaf==0)
{
printf("\nHUffman Tree NOt Be Init Yet!\n");
getch();
//system("cls");
HuffmanMenu();
}
LoadCode(code);
printf("\nAfter Encoding,The String id:\n");
m=code;
c=2*HuffmanLeaf-1;
while(*m!=NULL)
{
if(*m=='0')
{
c=HuffNode[c].lchild;
if(HuffNode[c].lchild==-1&&HuffNode[c].rchild==-1)
{
printf("%c",HuffNode[c].letter);
fprintf(fp,"%c",HuffNode[c].letter);
c=2*HuffmanLeaf-2;
}
/*译码成功，下一组继续*/
else if(*m=='1')
{
c=HuffNode[c].rchild;
if(HuffNode[c].lchild==-1&&HuffNode[c].rchild==-1)
{
printf("%c",HuffNode[c].letter);
fprintf(fp,"%c",HuffNode[c].letter);
c=2*HuffmanLeaf-2;
}
}/*译码成功，下一组继续*/
m++;
}
printf("\n\n");
fclose(fp);
printf("\n Save to textfile.dat Success!\n");
getch();
//system("cls");
HuffmanMenu();
}
}
/* void draw(float x,float y,float alph,float beta,float i,float derta,int c)
}{
float x1,x2,y1,y2;
int left,ringht;
char t[2]=" ",*p=&t[0];
beta=beta-0.0773;
alph-=beta;
setcolor(RED);/*设置背景色*/
/* *p=HuffNode[c].letter;
circle(x,y,r);/*以xy为圆心画圆*/
/* if(*p=='')
outtrxtxy(x-2,y-3,"^");
else
outtrxtxy(x-2,y-3,p);
if(HuffNode[c].lchild!=-1&&HuffNode[c].rchild!=-1)
{
x1=x-1*sin(alph);
y1=y+1*cos(alph);
x2=x+1*sin(alph);
y2=y+1*cos(alph);
line(x-r*sin(alph),y+r*cos(alph),x1+r*sin(alph),y1-r*cos(alph));
line(x+r*sin(alph),y+r*cos(alph),x2-r*sin(alph),y2-r*cos(alph));
left=HuffNode[c].lchild;
right=HuffNode[c].rchild;
i_=derta;
derta-=11.5;
draw(x1,y1,alph,beta,1,derta,left);
draw(x2,y2,alph,beta,1,derta,right);
}
}*/
/*查看以建立的树*/
/*void HuffmanShowTree(void)
{
double x=321,y=0,alph=90,beta=6.95,l=120,derta=33;
int c;
clrscr();
c=2*HuffmanLeaf-1;
if(HuffmanLeaf==0)
{printf("\nHUffman Tree NOt Be Init Yet!\n");
getch();
clrscr();
HuffmanMenu();
}
printf("\nThe huffmantree :\n");
deraw(x,y,alph,beta,l,derta,c);
getch();
clrscr();
HuffmanMenu();
}*/
/*Huffman 树主选择函数*/
void HuffmanMenu(void)
{
char ch;
printf("\n1.Create Huffman tree.\n2.Load Huffman tree From File...\n");
printf("3.View Code Rule\n4.Coding....\n5.Encoding...\n");
printf("6.Show Huffman Tree.\n0.exit..\n");
printf("Please choose: ");
ch=getch();
switch(ch-'0')
{
case 0: /*closegraph();*/exit(0);break;
case 1:InitHuffman();break;
case 2:LoadHuffmanTree();break;
case 3:HShowCode();break;
case 4:CharCode();break;
case 5:HEncode();break;
case 6:HuffmanShowTree();break;
default:HShowCode();
}
}
void main()
{
// int gdiver,gmode;
//gdrive=DETECT;
// initgraph(&gdrive,&gmode," ");
//textbackground(BLACK);
system("cls");
HuffmanMenu();
// closegraph();
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -