数据结构设计课程设计-哈夫曼编译码系统的设计与实现.docx

20180820

一、需求分析
1、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。

2、基本要求
（1）初始化（Initialzation）。从数据文件DataFile.txt中读入字符及每个字符的权值，建立哈夫曼树HuffTree；
（2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中；
（3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中；
（4）输出（Output）。输出DataFile.txt中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.txt及其报文Code.txt；输出CodeFile.txt及其原文Textfile.txt；

二、概要设计
1.数据结构
本程序需要用到以一个结构体HTNode，以及一个二维数组HuffmanCode。
2.程序模块
本程序包含两个模块，一个是实现功能的函数的模块，另一个是主函数模块。
系统子程序及功能设计
本系统共有七个子程序，分别是：
a.int min1(HuffmanTree t,int i)//进行比较
b.void select(HuffmanTree t,int i,int *s1,int *s2)// 求权值最小的两个数
c.void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n)// /* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */
d.void Initialzation(HuffmanTree *HT,HuffmanCode *HC)//初始化
e.int EnCoding(HuffmanTree *HT,HuffmanCode *HC)//对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中
f.int pipei(char *c,int n,HuffmanCode *HC)//在huffmancode寻找匹配的编码
g.void Decoding(HuffmanTree *HT,HuffmanCode *HC)//对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中

3. 各模块之间的调用关系以及算法设计
主函数调用Initialzation，EnCoding，Decoding。
函数HuffmanCoding调用函数select。
函数select调用函数min1
函数Initialzation调用函数HuffmanCoding
函数Decoding调用函数pipei

三、详细设计
1.数据类型定义
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
char ch;
}HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */
typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */
2.系统主要子程序详细设计
a. 构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n) /* 算法6.12 */
{ /* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
for(p=*HT+1,i=1;i<=n;++i,++p,++w,++u)
{
(*p).ch=*u;
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
(*p).parent=0;
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=(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
}
/* 从叶子到根逆向求每个字符的赫夫曼编码 */
*HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
/* 分配n个字符编码的头指针向量([0]不用) */
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 */
}
free(cd); /* 释放工作空间 */

}
b.初始化
void Initialzation(HuffmanTree *HT,HuffmanCode *HC)//初始化
{
FILE *f1;
int i,n=0;
if((f1=fopen("DataFile.txt","r"))==NULL)
{
printf("error\n");
}
int g[100];
char h[100];
printf("从数据文件DataFile.txt中读入字符及每个字符的权值\n");
for(i=1;;i++)
{
fscanf(f1,"%c",&h[i]);
if(h[i]=='#')
break;
fscanf(f1,"%d",&g[i]);
n++;
printf("%c: ",h[i]);
printf("%d\n",g[i]);
}
fclose(f1);
HuffmanCoding(HT,HC,g,h,n);

}
c.编码
int EnCoding(HuffmanTree *HT,HuffmanCode *HC)//对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中
{
int i,j,m=0,n=0;
FILE *f1,*f2,*f3;
if((f1=fopen("DataFile.txt","r"))==NULL)
{
printf("error\n");
}
int g[100];
char h[100];
for(i=1;;i++)
{
fscanf(f1,"%c",&h[i]);
if(h[i]=='#')
break;
fscanf(f1,"%d",&g[i]);
n++;
}
fclose(f1);
if((f2=fopen("ToBeTran.txt","r"))==NULL)
{
printf("error\n");
}
printf("从数据文件ToBeTran.txt中读入字符\n");
char u[100],a[100];
for(i=1;;i++)
{
fscanf(f2,"%c",&u[i]);
if(u[i]=='#')
break;
a[i]=u[i];
m++;
cout<<a[i]<<" ";
}
cout<<endl;
fclose(f2);
if((f3=fopen("Code.txt","w"))==NULL)
{
printf("error\n");
}
cout<<"输出报文"<<endl;
for(i=0;i<m;i++)
for(j=1;j<=n;++j)
{
if(*(a+i)==(*HT)[j].ch)
{
printf("%s ",(*HC)[j]);
fprintf(f3,"%s",(*HC)[j]);
}

}
fclose(f3);
cout<<endl;
return m;
}
int pipei(char *c,int n,HuffmanCode *HC)/*在huffmancode寻找匹配的编码*/
{
int i;
for(i=1;i<5;i++)
{

if(strcmp(c,(*HC)[i])==0)
{
return i;
break;
}
}

return 0;

}
d.译码
void Decoding(HuffmanTree *HT,HuffmanCode *HC)//对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中
{
int i=1,j=1,y=0,num=0,len,n=0,d,q,v,ii;
int a[2]={1,2};
char c[20];
for(i=0;i<20;i++)
c[i]='\0';
FILE *f1,*f4,*f5;
if((f1=fopen("DataFile.txt","r"))==NULL)//求权值个数n
{
printf("error\n");
}
int g[100];
char h[100];
for(i=1;;i++)
{
fscanf(f1,"%c",&h[i]);
if(h[i]=='#')
break;
fscanf(f1,"%d",&g[i]);
n++;
}
fclose(f1);
if((f4=fopen("CodeFile.txt","r"))==NULL)//读字符
{
printf("error\n");
}
printf("从数据文件CodeFile.txt中读入代码\n");
char b[100];
for(i=1;;i++)
{
fscanf(f4,"%c",&b[i]);
if(b[i]=='#')
break;
cout<<b[i];
}
cout<<endl;
fclose(f4);
if((f5=fopen("TextFile.txt","w"))==NULL)
{
printf("error\n");
}
cout<<"输出原文"<<endl;
i=1;
j=1;
y=1;
while(true)
{

if(b[y]=='#')
break;
for(j=0;j<i;j++)
{
c[j]=b[y+j];
}
q=pipei(c,n,HC);
if(q!=0)
{
printf("%c",(*HT)[q+1].ch);
fprintf(f5,"%c",(*HT)[q+1].ch);
y=y+i;
i=1;
}
else
i++;
for(ii=0;ii<20;ii++)
c[ii]='\0';
}
cout<<endl;
}
四、测试与分析
1.显示主菜单，运行程序可以显示出如下界面。

2.初始化
在主菜单下选1，初始胡，即可从数据文件DataFile.txt中读入字符及每个字符的权值。

3.编码
在主菜单下选2，编码，将给定文件ToBeTran.txt中的字符输出报文。

4.译码
在主菜单下选3，完成译码功能，读取文件CodeFile.txt中的代码并输出原文。

5.退出
在主菜单下选4，退出系统

五、附录
1.哈夫曼编译码系统.h
#include<iostream>
#include<malloc.h>
#include<string.h>
using namespace std;
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
char ch;
}HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */
typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */
int min1(HuffmanTree t,int i)
{ /* 函数void select()调用 */
int j,flag;
unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}

void select(HuffmanTree t,int i,int *s1,int *s2)
{ /* s1为最小的两个值中序号小的那个 */
int j;
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1>*s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n) /* 算法6.12 */
{ /* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
for(p=*HT+1,i=1;i<=n;++i,++p,++w,++u)
{
(*p).ch=*u;
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
(*p).parent=0;
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=(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
}
/* 从叶子到根逆向求每个字符的赫夫曼编码 */
*HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
/* 分配n个字符编码的头指针向量([0]不用) */
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 */
}
free(cd); /* 释放工作空间 */

}

void Initialzation(HuffmanTree *HT,HuffmanCode *HC)//初始化
{
FILE *f1;
int i,n=0;
if((f1=fopen("DataFile.txt","r"))==NULL)
{
printf("error\n");
}
int g[100];
char h[100];
printf("从数据文件DataFile.txt中读入字符及每个字符的权值\n");
for(i=1;;i++)
{
fscanf(f1,"%c",&h[i]);
if(h[i]=='#')
break;
fscanf(f1,"%d",&g[i]);
n++;
printf("%c: ",h[i]);
printf("%d\n",g[i]);
}
fclose(f1);
HuffmanCoding(HT,HC,g,h,n);

}

int EnCoding(HuffmanTree *HT,HuffmanCode *HC)//对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中
{
int i,j,m=0,n=0;
FILE *f1,*f2,*f3;
if((f1=fopen("DataFile.txt","r"))==NULL)
{
printf("error\n");
}
int g[100];
char h[100];
for(i=1;;i++)
{
fscanf(f1,"%c",&h[i]);
if(h[i]=='#')
break;
fscanf(f1,"%d",&g[i]);
n++;
}
fclose(f1);
if((f2=fopen("ToBeTran.txt","r"))==NULL)
{
printf("error\n");
}
printf("从数据文件ToBeTran.txt中读入字符\n");
char u[100],a[100];
for(i=1;;i++)
{
fscanf(f2,"%c",&u[i]);
if(u[i]=='#')
break;
a[i]=u[i];
m++;
cout<<a[i]<<" ";
}
cout<<endl;
fclose(f2);
if((f3=fopen("Code.txt","w"))==NULL)
{
printf("error\n");
}
cout<<"输出报文"<<endl;
for(i=0;i<m;i++)
for(j=1;j<=n;++j)
{
if(*(a+i)==(*HT)[j].ch)
{
printf("%s ",(*HC)[j]);
fprintf(f3,"%s",(*HC)[j]);
}

}
fclose(f3);
cout<<endl;
return m;
}
int pipei(char *c,int n,HuffmanCode *HC)/*在huffmancode寻找匹配的编码*/
{
int i;
for(i=1;i<5;i++)
{

if(strcmp(c,(*HC)[i])==0)
{
return i;
break;
}
}

return 0;

}

void Decoding(HuffmanTree *HT,HuffmanCode *HC)//对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中
{
int i=1,j=1,y=0,num=0,len,n=0,d,q,v,ii;
int a[2]={1,2};
char c[20];
for(i=0;i<20;i++)
c[i]='\0';
FILE *f1,*f4,*f5;
if((f1=fopen("DataFile.txt","r"))==NULL)//求权值个数n
{
printf("error\n");
}
int g[100];
char h[100];
for(i=1;;i++)
{
fscanf(f1,"%c",&h[i]);
if(h[i]=='#')
break;
fscanf(f1,"%d",&g[i]);
n++;
}
fclose(f1);
if((f4=fopen("CodeFile.txt","r"))==NULL)//读字符
{
printf("error\n");
}
printf("从数据文件CodeFile.txt中读入代码\n");
char b[100];
for(i=1;;i++)
{
fscanf(f4,"%c",&b[i]);
if(b[i]=='#')
break;
cout<<b[i];
}
cout<<endl;
fclose(f4);
if((f5=fopen("TextFile.txt","w"))==NULL)
{
printf("error\n");
}
cout<<"输出原文"<<endl;
i=1;
j=1;
y=1;
while(true)
{

if(b[y]=='#')
break;
for(j=0;j<i;j++)
{
c[j]=b[y+j];
}
q=pipei(c,n,HC);
if(q!=0)
{
printf("%c",(*HT)[q+1].ch);
fprintf(f5,"%c",(*HT)[q+1].ch);
y=y+i;
i=1;
}
else
i++;
for(ii=0;ii<20;ii++)
c[ii]='\0';
}
cout<<endl;
}

2.哈夫曼编译码. cpp（主函数）
#include"哈夫曼编译码系统.h"

int main()
{
int ch;
HuffmanTree HT;
HuffmanCode HC;
while(1)
{
cout<<"----------------哈夫曼编译码系统----------------"<<endl;
cout<<" 1.初始化 "<<endl;
cout<<" 2.编码 "<<endl;
cout<<" 3.译码 "<<endl;
cout<<" 4.退出 "<<endl;
cout<<"请输入功能编号:"<<endl;
cin>>ch;
if(ch>4|| ch<1)
{
do{
cout<<"输入有误，请重新输入!"<<endl;
cin>>ch;
}while(ch<=4&&ch>=1);
}
switch(ch)
{
case 1:
{
cout<<"初始化"<<endl;
Initialzation(&HT,&HC);
break;
}
case 2:
{
cout<<"编码"<<endl;
EnCoding(&HT,&HC);
break;
}
case 3:
{
cout<<"译码"<<endl;
Decoding(&HT,&HC);
break;
}
case 4:exit(0);
default:
break;
}
}
return 0;

}

六、用户手册
打开哈夫曼编译码系统文件夹，用VS2010运行哈夫曼编译码.sln，即可运行该哈夫曼编译吗系统并完成相应的功能。
1. 基于C8051F单片机直流电动机反馈控制系统的设计与研究
2. 基于单片机的嵌入式Web服务器的研究
3. MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究
4. 基于模糊控制的电阻钎焊单片机温度控制系统的研制
5. 基于MCS-51系列单片机的通用控制模块的研究
6. 基于单片机实现的供暖系统最佳启停自校正（STR）调节器
7. 单片机控制的二级倒立摆系统的研究
8. 基于增强型51系列单片机的TCP/IP协议栈的实现
9. 基于单片机的蓄电池自动监测系统
10. 基于32位嵌入式单片机系统的图像采集与处理技术的研究
11. 基于单片机的作物营养诊断专家系统的研究
12. 基于单片机的交流伺服电机运动控制系统研究与开发
13. 基于单片机的泵管内壁硬度测试仪的研制
14. 基于单片机的自动找平控制系统研究
15. 基于C8051F040单片机的嵌入式系统开发
16. 基于单片机的液压动力系统状态监测仪开发
17. 模糊Smith智能控制方法的研究及其单片机实现
18. 一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制
19. 基于双单片机冲床数控系统的研究
20. 基于CYGNAL单片机的在线间歇式浊度仪的研制
21. 基于单片机的喷油泵试验台控制器的研制
22. 基于单片机的软起动器的研究和设计
23. 基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究
24. 基于单片机的机电产品控制系统开发
25. 基于PIC单片机的智能手机充电器
26. 基于单片机的实时内核设计及其应用研究
27. 基于单片机的远程抄表系统的设计与研究
28. 基于单片机的烟气二氧化硫浓度检测仪的研制
29. 基于微型光谱仪的单片机系统
30. 单片机系统软件构件开发的技术研究
31. 基于单片机的液体点滴速度自动检测仪的研制
32. 基于单片机系统的多功能温度测量仪的研制
33. 基于PIC单片机的电能采集终端的设计和应用
34. 基于单片机的光纤光栅解调仪的研制
35. 气压式线性摩擦焊机单片机控制系统的研制
36. 基于单片机的数字磁通门传感器
37. 基于单片机的旋转变压器-数字转换器的研究
38. 基于单片机的光纤Bragg光栅解调系统的研究
39. 单片机控制的便携式多功能乳腺治疗仪的研制
40. 基于C8051F020单片机的多生理信号检测仪
41. 基于单片机的电机运动控制系统设计
42. Pico专用单片机核的可测性设计研究
43. 基于MCS-51单片机的热量计
44. 基于双单片机的智能遥测微型气象站
45. MCS-51单片机构建机器人的实践研究
46. 基于单片机的轮轨力检测
47. 基于单片机的GPS定位仪的研究与实现
48. 基于单片机的电液伺服控制系统
49. 用于单片机系统的MMC卡文件系统研制
50. 基于单片机的时控和计数系统性能优化的研究
51. 基于单片机和CPLD的粗光栅位移测量系统研究
52. 单片机控制的后备式方波UPS
53. 提升高职学生单片机应用能力的探究
54. 基于单片机控制的自动低频减载装置研究
55. 基于单片机控制的水下焊接电源的研究
56. 基于单片机的多通道数据采集系统
57. 基于uPSD3234单片机的氚表面污染测量仪的研制
58. 基于单片机的红外测油仪的研究
59. 96系列单片机仿真器研究与设计
60. 基于单片机的单晶金刚石刀具刃磨设备的数控改造
61. 基于单片机的温度智能控制系统的设计与实现
62. 基于MSP430单片机的电梯门机控制器的研制
63. 基于单片机的气体测漏仪的研究
64. 基于三菱M16C/6N系列单片机的CAN/USB协议转换器
65. 基于单片机和DSP的变压器油色谱在线监测技术研究
66. 基于单片机的膛壁温度报警系统设计
67. 基于AVR单片机的低压无功补偿控制器的设计
68. 基于单片机船舶电力推进电机监测系统
69. 基于单片机网络的振动信号的采集系统
70. 基于单片机的大容量数据存储技术的应用研究
71. 基于单片机的叠图机研究与教学方法实践
72. 基于单片机嵌入式Web服务器技术的研究及实现
73. 基于AT89S52单片机的通用数据采集系统
74. 基于单片机的多道脉冲幅度分析仪研究
75. 机器人旋转电弧传感角焊缝跟踪单片机控制系统
76. 基于单片机的控制系统在PLC虚拟教学实验中的应用研究
77. 基于单片机系统的网络通信研究与应用
78. 基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究
79. 基于单片机的模糊控制器在工业电阻炉上的应用研究
80. 基于双单片机冲床数控系统的研究