数据结构专业课程设计哈夫曼编码译码器.doc

题目一：哈夫曼编码与译码
一、任务
设计一种运用哈夫曼算法编码和译码系统，重复地显示并解决如下项目，直到选取退出为止。
规定：
1) 将权值数据存储在数据文献(文献名为data.txt，位于执行程序当前目录中) ；
2) 初始化：键盘输入字符集记录字符权值、自定义26个字符和26个权值、记录文献中一篇英文文章中26个字母，建立哈夫曼树；
3) 编码：运用建好哈夫曼树生成哈夫曼编码；
4) 输出编码（一方面实现屏幕输出，然后实现文献输出）；
5） 译码（键盘接受编码进行译码、文献读入编码进行译码）；
6) 界面优化设计。
二、流程图

主菜单
1.建立字符权值
2.建立并输出哈夫曼树
3.建立并查看哈弗曼编码
4.编码与译码
0.退出系统
1.从键盘输入字符集记录权值
2.从文献读入字符集记录权值
3.自定义字符及权值
0.返回上级菜单
输出哈夫曼树并保存至文献“哈夫曼树。txt”
输出哈夫曼编码并保存至文献“哈夫曼编码。txt
1.编码
2.译码
0.返回上级菜单
1.从键盘输入字符集进行编码
2.从文献读入字符集进行编码
1.从键盘输入编码进行译码

2.从文献读入编码进行译码

0.返回上级菜单
0.返回上级菜单

三、代码分解
//头文献
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include <conio.h>
#define N 1000
#define M 2*N-1
#define MAXcode 6000
//函数声明
void count(CHar &ch,HTNode ht[]);
void editHCode(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[])； //编码函数
void printyima(HTNode ht[],HCode hcd[],int n,char bianma[])； //译码函数
void creatHT(HTNode ht[],int n);
void CreateHCode (HTNode ht[],HCode hcd[],int n);
void DispHCode(HTNode ht[],HCode hcd[],int n);
void input_key(CHar &ch);
void input_file(CHar &ch);
void input_cw(HTNode ht[]);
void bianma1(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]);
void bianma2(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]);
void yima1(HTNode ht[],HCode hcd[],int n,char bianma[]);
void yima2(HTNode ht[],HCode hcd[],int n,char bianma[]);
void creat_cw();
void bianmacaidan();
void yimacaidan();
void bianmayima();
int caidan()；
//构造体
typedef struct
{
char data;
int parent;
int weight;
int lchild;
int rchild;
}HTNode;
typedef struct
{
char cd[N];
int start;
}HCode;
typedef struct
{
char s[N];
int num;
}CHar;
CHar ch;
HTNode ht[M];
HCode hcd[N];
//主函数
int main()
{
int xh;
while(1)
{
system("color 1f")； //操作菜单背景颜色
xh=caidan()； //调用菜单函数
switch(xh) //switch语句
{
case 1:system("cls");creat_cw();break;
case 2:system("cls");creatHT(ht,n);break;
case 3:system("cls");CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);break;
case 4:system("cls");bianmayima();break;
case 0:system("cls");printf("\n\n\n\n\n\n\n\n\n\t\t\t\t感谢使用本系统!\n\n\n\n\n\n\n \t\t\t");exit(0);
default:system("cls");putchar('\a');
printf("\n\t\t输入有误，请重新输入:\n");break;
}
}
return 0;
}
//菜单函数
int caidan() //菜单函数模块//
{
int xh;
printf("\n\n\n");
printf("\t\t 欢迎使用哈夫曼编码译码系统 \n");
printf("\t\t \n");
printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");
printf("\t\t*= =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");
printf("\t\t*= 1.建立字符权值 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");
printf("\t\t*= 2.建立并输出哈夫曼树 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");
printf("\t\t*= 3.生成并查看哈夫曼编码 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");
printf("\t\t*= 4.编码与译码 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");
printf("\t\t*= 0.退出系统 =*\n");
printf("\t\t*= =*\n");
printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");
printf("\n\t\t请输入序号进行选取:");
scanf("%d"，&xh)；
return xh； //返回从键盘接受选项
}
void bianmayima()
{
int xh;
while(1)
{
printf("\n\n\n\n\n");
printf("\t\t 编码与译码 \n");
printf("\t\t \n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 1.编码 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 2.译码 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 0.返回上级菜单 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\n\t\t请输入序号进行选取:");
scanf("%d",&xh);
switch(xh) //switch语句
{
case 1:system("cls");bianmacaidan();break;
case 2:system("cls");yimacaidan();break;
case 0:system("cls");return;
default:system("cls");putchar('\a');
printf("\n\t\t输入有误，请重新输入:\n");break;
}
}
}
void yimacaidan()
{
int xh;
while(1)
{
printf("\n\n\n\n\n");
printf("\t\t 译码 \n");
printf("\t\t \n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 1.键盘输入编码进行译码 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 2.文献读入编码进行译码 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 0.返回上级菜单 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\n\t\t请输入序号进行选取:");
scanf("%d",&xh);
switch(xh) //switch语句
{
case 1:system("cls");yima1(ht,hcd,n,bianma);break;
case 2:system("cls");yima2(ht,hcd,n,bianma);break;
case 0:system("cls");return;
default:system("cls");putchar('\a');
printf("\n\t\t输入有误，请重新输入:\n");break;
}
}
}
void bianmacaidan()
{
int xh;
while(1)
{
printf("\n\n\n\n\n");
printf("\t\t 编码 \n");
printf("\t\t \n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 1.键盘输入字符集编码 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 2.文献读入文章编码 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 0.返回上级菜单 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\n\t\t请输入序号进行选取:");
scanf("%d",&xh);
switch(xh) //switch语句
{
case 1:system("cls");bianma1(ht,hcd,ch,n,bianma);break;
case 2:system("cls");bianma2(ht,hcd,ch,n,bianma);break;
case 0:system("cls");return;
default:system("cls");putchar('\a');
printf("\n\t\t输入有误，请重新输入:\n");break;
}
}
}
void creat_cw()
{
int xh2;
while(1)
{
printf("\n\n\n\n\n");
printf("\t\t 建立字符权值 \n")；
printf("\t\t \n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 1.从键盘输入字符集进行记录 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 2.从文献读入字符集记录 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 3.自定义字符权值 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\t\t*= 0.返回上级菜单 =*\n");
printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");
printf("\n\t\t请输入序号进行选取:");
scanf("%d",&xh2);
switch(xh2) //switch语句
{
case 1:system("cls");input_key(ch);break;
case 2:system("cls");input_file(ch);break;
case 3:system("cls");input_cw(ht);break;
case 0:system("cls");return;
default:system("cls");putchar('\a');
printf("\n\t\t输入有误，请重新输入:\n");break;
}
}
}
//建立字符权值模块
void input_key(CHar &ch)
{
int i,j=0;
char st[N];
printf("请输入字符集（以‘#’结束）:\n");
for(i=0;i<N;i++)
{
scanf("%c",&st[i]);
if(st[i]=='#')
{st[i]='\0';break;}
}
strcpy(ch.s,st);
ch.num=strlen(st);
count(ch,ht);
printf("按任意键返回!");
getch();
system("cls");
return;
}
void input_file(CHar &ch)
{
int i;
FILE*fp;
char filename[20];
printf("请输入要打开文献名(*.txt):");
scanf("%s",&filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("\n\t\t文献打开失败!!!");
return;
}
for(i=0;!feof(fp);i++)
{
fread(&ch.s[i],sizeof(char),1,fp)；
}
ch.num=strlen(ch.s);
printf("读入成功!\n");
printf("文献中字符集为:%s\n",ch.s);
fclose(fp);
count(ch,ht);
printf("按任意键返回!");
getch();
system("cls");
return;
}
void input_cw(HTNode ht[])
{
int i,w,s,j;
char a;
printf("要输入字符总个数是？:");
scanf("%d",&s);
n=s;
printf("请输入字符及其权值:\n");
for(i=0;i<s;i++)
{
printf("请输入第%d个字母:",i+1);
scanf("%s",&a);
ht[i].data=a;
printf("请输入其权值:");
scanf("%d",&w);
ht[i].weight=w;
}
FILE *fp;
if((fp=fopen("data.txt","w"))==0)
{
printf("\n\t\t文献打开失败!!!");
return;
}
printf("\n定义权值成功!\n\n");
printf("各字符及其权值为:\n\n");
fprintf(fp,"各字符及其权值为:\n");
printf(" 字符\t权值");
fprintf(fp," 字符\t权值");
for(j=0;j<i;j++)
{ printf("\n");
fprintf(fp,"\n");
printf(" %-8c%-8d",ht[j].data,ht[j].weight);
fprintf(fp," %-8c%-8d%",ht[j].data,ht[j].weight);
}
printf("\n");
printf("\n字符权值已输出至文献“data.txt”！");
fclose(fp);
printf("输入完毕，按任意键返回！");
getch();
system("cls");
return;
}
//记录字符权值函数
void count(CHar &ch,HTNode ht[])
{
int i,j,m=0;
char c[N];
int sum[N]={0};
for(i=0;ch.s[i]!='\0';i++)
{
for(j=0;j<m;j++)
if(ch.s[i]==c[j]||(c[j]>='a'&&c[j]<='z'&&ch.s[i]+32==c[j])) break;
if(j<m)
sum[j]++;
else
{
if(ch.s[i]>='A'&&ch.s[i]<='Z')
c[j]=ch.s[i]+32;
else c[j]=ch.s[i];
sum[j]++;
m++;
}
}
for(i=0;i<m;i++)
{
ht[i].data=c[i];
ht[i].weight=sum[i];
}
n=m;
FILE *fp;
if((fp=fopen("data.txt","w"))==0)
{
printf("\n\t\t文献打开失败!!!");
return;
}
printf("\n记录权值成功!\n\n");
printf("各字符及其权值为:\n\n");
fprintf(fp,"各字符及其权值为:\n");
printf(" 字符\t权值");
fprintf(fp," 字符\t权值");
for(j=0;j<m;j++)
{ printf("\n");
fprintf(fp,"\n");
printf(" %-8c%-8d",ht[j].data,ht[j].weight);
fprintf(fp," %-8c%-8d%",ht[j].data,ht[j].weight);
}
printf("\n");
printf("\n字符权值已输出至文献“data.txt”！");
fclose(fp);
}
//构造哈夫曼树
void creatHT(HTNode ht[],int n)
{
FILE *fp;
if((fp=fopen("哈夫曼树.txt","w"))==0)
{
printf("\n\t\t文献打开失败!!!");
return;
}
int i,j,k,lnode,rnode;
int min1,min2;
for (i=0;i<2*n-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n;i<2*n-1;i++)
{
min1=min2=32767;
lnode=rnode=-1;
for(k=0;k<=i-1;k++)
if(ht[k].parent==-1)
{
if (ht[k].weight<min1)
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if(ht[k].weight<min2)
{
min2=ht[k].weight;rnode=k;
}
}
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
}
printf("建立huffman树成功!\n");
printf("输出huffman树:\n");
fprintf(fp,"输出huffman树:\n");
printf("\t字符\t权值\t父节点\t 左子节点\t右子节点");
fprintf(fp,"\t字符\t权值\t父节点\t 左子节点\t右子节点");
for(j=1;j<i;j++)
{ printf("\n");
fprintf(fp,"\n");
printf("\t %-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,ht[i].lchild,ht[j].rchild);
fprintf(fp,"\t %-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,ht[i].lchild,ht[j].rchild);
}
printf("\n");
printf("哈夫曼树已输出至文献“哈夫曼树.txt”！按任意键返回!");
fclose(fp);
getch();
system("cls");
return;
}
//生成哈夫曼编码
void CreateHCode (HTNode ht[],HCode hcd[],int n)
{
int i,f,c,j=0;
HCode hc;
for(i=0;i<n;i++)
{
hc.start=n;c=i;
hc.cd[hc.start--]='0';
f=ht[i].parent;
while(f!=-1)
{
if (ht[f].lchild==c)
hc.cd[hc.start--]='0';
else
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;
}
hc.start++；
for(j=0;j<hc.start;j++)
hc.cd[j]=' ';
hcd[i]=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
FILE *fp;
if((fp=fopen("哈夫曼编码.txt","w"))==0)
{
printf("\n\t\t文献打开失败!!!");
return;
}
int i,k;
int sum=0,m=0,j;
printf("输出字符哈夫曼编码:\n");
fputs("输出字符哈夫曼编码:\n",fp);
for (i=0;i<n;i++)
{
j=0;
printf("%c:\t",ht[i].data);
fprintf(fp,"\n%c:\t",ht[i].data);
for (k=hcd[i].start;k<=n;k++)
{
printf("%c",hcd[i].cd[k]);
j++;
fprintf(fp,"%c",hcd[i].cd[k]);
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
printf("\n哈夫曼编码已保存至文献“哈夫曼编码.txt!按任意键返回！”");
fclose(fp);
getch();
system("cls");
}
//编码函数
void bianma1(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[])
{
int i;
char str[N];
printf("请输入要编码字符集（以‘#’结束）:\n");
for(i=0;i<N;i++)
{
scanf("%c",&str[i]);
if(str[i]=='#')
{str[i]='\0';break;}
}
strcpy(ch.s,str);
ch.num=strlen(str);
editHCode(ht,hcd,ch,n,bianma);
getch();
system("cls");
return;
}
void bianma2(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[])
{
int i;
FILE*fp;
char filename[20];
printf("请输入要打开文献名(*.txt):");
scanf("%s",&filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("\n\t\t文献打开失败!!!");
return;
}
for(i=0;!feof(fp);i++)
{
fread(&ch.s[i],sizeof(char),1,fp)；
}
ch.num=strlen(ch.s);
printf("\n读入成功!\n");
printf("文献中字符集为:\n%s",ch.s);
fclose(fp);
editHCode(ht,hcd,ch,n,bianma);
getch();
system("cls");
return;
}
//译码函数
void yima1(HTNode ht[],HCode hcd[],int n,char bianma[])
{
int i;
char code[MAXcode];
printf("请输入编码进行译码（以‘#’结束）:\n");
for(i=0;i<MAXcode;i++)
{
scanf("%c",&code[i]);
if(code[i]=='#')
{code[i]='\0';break;}
}
strcpy(bianma,code);
printyima(ht,hcd,n,bianma);
printf("\n译码完毕！按任意键返回!");
getch();
system("cls");
return;
}
void yima2(HTNode ht[],HCode hcd[],int n,char bianma[])
{
int i;
FILE*fp;
char filename[20];
printf("请输入要打开文献名(*.txt):");
scanf("%s",&filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("\n\t\t文献打开失败!!!");
return;
}
for(i=0;!feof(fp);i++)
{
fread(&bianma[i],sizeof(char),1,fp)；
}
printf("读入成功!\n");
printf("文献中编码是:%s\n",bianma);
printyima(ht,hcd,n,bianma);
printf("\n译码完毕！按任意键返回!");
getch();
system("cls");
}
四、调试成果

主菜单

建立字符权值

选取2.从文献读入字符进行记录
输入测试文献名“cs.txt”
输出个字符权值

建立哈夫曼树并输出至文献

生成哈夫曼编码并保存至文献

编码

选取2.从文献读入字符集编码 编码成果保存至文献

译码

选取2.从文献读入编码，读入上一步编码

译码完毕，返回！

退出系统