-
《数据结构》
课程设计报告
设
计
学
院
专
业
姓
学
题
目
名
称
班
级
名
号
哈夫曼（
Huffman
）编译码器
信息工程学院
13
计本
1
1312219999
hhh
目录
一、实验题目
-
哈夫曼
(Huffman)
编
/
译码器
------------------------------
二、问 题描述
------------------------------------------- ----
三、设计目标
------------------------------- ----------------
四、需求分析
------------------- ----------------------------
五、概要设计
------- ----------------------------------------
1- --
系统结构图
----------------------------------- ---
2--
各个模块功能的详细描述
----------------- --------------
六、详细设计
--------------------- --------------------------
1
——详细代码
- -------------------------------------
a< br>）头文件代码
------------------------------------- -
b
）主函数代码
------------------- -------------------
2
——系统流程图
------- -------------------------------
七、测试分析
---- -------------------------------------------
八、 使用说明
------------------------------------------ -----
1
、白盒
-------------------------- ---------------------
2
、黑盒
---------- -------------------------------------
九、
课程 设计总结
------------------------------------------ ----
一
、实验题目
哈夫曼
(Huffman)
编
/
译码器
二
、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率 ，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在 接收端将传来的数据进行译
码
（复原）
。
对于双工信道
（即可以双向 传输信息的信道）
，
每端都需要一个完整的编
/
译码系统。
试为这样 的信息收发站写一个哈夫曼码的编
/
译码系统。
三、设计目标
设计一个程序，该程序可以实现哈夫曼的编码及译码过程。
四、需求分析
一个完整的系统应具有以下功能：
1)
I
：初始化（< br>Initialization
）
。从终端读入字符集大小
n
，以及< br>n
个字符和
n
个权值（见
下表）
，建立哈夫曼树，并将它存于 文件
中。
2)
E
：编码（
Encod ing
）
。利用已建好的哈夫曼树（如不在内存，则从文件
中
读入）
，对文件
ToBeTran
中的正文进行编码，然后将结果存入文件
Code File
中。
3)
D
：译码（
Decodin g
）
。利用已建好的哈夫曼树将文件
CodeFile
中的代码进行译码，结
果存入文件
TextFile
中。
4)
P：打印代码文件（
）
。将文件
CodeFile
以紧 凑格式显示在终端上，每行
50
个代
码。同时将此字符形式的编码文件写入文件
CodePrin
中。
5)T
：打印哈夫曼树（
Tree Printing
）
。将已在内存中的哈夫曼树以直观的方式（树或凹入表
形式）显示在终端上，同时将此字符 形式的哈夫曼树写入文件
TreePrint
中
五、概要设计
1
、系统结构功能图
函数功能图
menu1()
pri
ntD< br>ata
(da
ta)
;
//
输
出
数
据
bthe
ad =
crea
tebt
(dat
a);
/
/
建哈
夫曼
树
menu2()
reaH F
Data(
hmdat
a);
sortH
MC(hm
d ata)
;
载入
哈夫
曼码
并排
序
men u3()
reaD
ata(
data
);
//
载入
数据
sort
(dat
a);
/
/
对数
据进
行排
序
HuffM
anCod
ing(b
thead
, 0,
fp);
/
/
并写
入文
件
print< br>HuffM
anfil
e();
/
/
显示
哈夫
曼树
PreOr
derPr
int(b
thead
);
//
打印
哈夫
曼树
bthea
d =
destr
oybt(
bthea
d);
//
销毁
哈夫
曼树
HFDat
a(hmd
ata);
Encod
ing(h
mdata
);
Enco
ding
(hmd
ata)
;
编
码
Prin
tCod
Deco
eFil
ding
e ();
();
//
译码
打印
代码
文件
2
各个模块功能的详细描述
int reaData(mytype d[])//
载入数据
int reaHFData(HuffM d[])//
从
文件读取数据
int printData(mytype d[]) //
数据显示
字符
频度
int printHFData(HuffM d[]) //
显示哈夫曼树
字符
编码
int sort(mytype d[])//
对数据频度大小排序
建哈夫曼树时调用
int sortHMC(HuffM d[])//
对哈夫曼树字符排序
译码文件时调用
int sort1(bitree* temp[N],int n)//
对新的数据重新
频度大小排序
建树
时调用
bitree * createbt(mytype d[])//
建哈夫曼树
bitree
*
destroybt(bitree
*
head)//
销毁哈夫曼树，释放空间
递归调用
void HuffManCoding(bitree *BT, int len,FILE *fp) //
哈夫曼树编码
利用
static
函数
并写入文件
int printHuffManfile() //
输出哈夫曼树
字符
频度
编码
int Encoding(HuffM d[])//
编码
int Decoding(HuffM d[])//
编码
void PrintCodeFile()
void PreOrderPrint(bitree *HT)
六、详细设计
1
详细代码
a
）头文件
#include
#include
#define N 30
typedef struct hm{
char ch;
char code[20];
}HuffM;
typedef struct s{
char ch;
int frq;
}mytype;
typedef struct bt{
struct bt *lchild;
mytype dt;
struct bt *rchild;
}bitree;
int g_flag=0;
int Encoding(HuffM d[]);
int PreOrderPrint(bitree *HT);
void PrintCodeFile();
int Decoding(HuffM d[]);
b
）主函数
#include
int reaData(mytype d[])//
载入数据
{
FILE * fp;
int i=0;
fp=fopen(
if(NULL==fp)
{
return -1;
}
while(!feof(fp))
{
fscanf(fp,
fscanf(fp,
fseek(fp,2,SEEK_CUR);
i++;
if(i==N-2)
break;
}
g_flag=1;
fclose(fp);
return 0;
}
int reaHFData(HuffM d[])//
从
文件读取数据
{
FILE * fp;
int i=0,td;
char c,data[20];
fp=fopen(
if(NULL==fp)
{
printf(
打开哈夫曼编码数据文件出错。
n
return -1;
}
while(1)
{
fscanf(fp,
if(feof(fp))
break;
//printf(
d[i].ch=c;
strcpy(d[i].code,data);
i++;
fseek(fp,2,SEEK_CUR);=
}
g_flag=1;
fclose(fp);
return 0;
}
int printData(mytype d[]) //
数据显示
字符
频度
{
int i=0;
if(g_flag<1)
{
printf(
请先载入数据文件。
n
return 0;
}
for(;i
{
printf(
}
return 0;
}
int printHFData(HuffM d[]) //
显示哈夫曼树
字符
编码
{
int i=0;
if(g_flag<1)
{
printf(
请先载入数据文件。
n
return 0;
}
for(;i
{
printf(
}
return 0;
}
int sort(mytype d[])//
对数据频度大小排序
建哈夫曼树时调用
{
int i,j;
mytype temp;
if(g_flag<1)
{
printf(
请先载入数据文件。
n
return 0;
}
for(i=0;i
{
for(j=0;j
{
if(d[j].frq>d[j+1].frq)
{
temp=d[j];
d[j]=d[j+1];
d[j+1]=temp;
}
}
}
}
int sortHMC(HuffM d[])//
对哈夫曼树字符排序
{
int i,j;
HuffM temp;
if(g_flag<1)
{
printf(
请先载入数据文件。
n
return 0;
}
for(i=0;i
{
for(j=0;j
{
if(d[j].ch>d[j+1].ch)
{
temp=d[j];
译码文件时调用
d[j]=d[j+1];
d[j+1]=temp;
}
}
}
}
int sort1(bitree* temp[N],int n)//
对新的数据重新
频度大小排序
建树时调用
{
int i,j;
bitree* tmp;
for(i=0;i
{
for(j=0;j
{
if(temp[N-3-n+j]->>temp[N-3-n+j+1]->)
{
tmp=temp[N-3-n+j];
temp[N-3-n+j]=temp[N-3-n+j+1];
temp[N-3-n+j+1]=tmp;
}
}
}
}
bitree * createbt(mytype d[])//
建哈夫曼树
{
bitree* head=NULL;
bitree* temp[N]={NULL};
int i=0;
if(g_flag<1)
{
printf(
请先载入数据文件。
n
return 0;
}
sort(d);
while(i
{
temp[i]=(bitree *)malloc(sizeof(bitree));
temp[i]->dt=d[i];
temp[i]->lchild=NULL;
temp[i]->rchild=NULL;
i++;
}
i=0;
while(i
{
head=(bitree *)malloc(sizeof(bitree));
head->='*';
head->=temp[i]-> + temp[i+1]->;
head->lchild=temp[i];
head->rchild=temp[i+1];
temp[i+1]=head;
temp[i]=NULL;
sort1(temp,N-i-4);
i++;
}
g_flag = 11;
return head;
}
bitree * destroybt(bitree * head)//
销毁哈夫曼树，释放空间
递归调用
{
bitree *temp;
if(head==NULL)
return NULL;
temp=head;
if(head->lchild)
head->lchild=destroybt(temp->lchild);
if(head->rchild)
head->rchild=destroybt(temp->rchild);
free(head);
head=NULL;
return NULL;
}
void HuffManCoding(bitree *BT, int len,FILE *fp) //
哈夫曼树编码
利用
static
函数
并写入文件
{
static int a[10];
int i;
if(g_flag<11)
{
printf(
请先建立哈夫曼树。
n
return 0;
}
if(BT!=NULL){
if(BT->lchild==NULL&&BT->rchild==NULL){
//printf(
字符
%c
的权值为%d
的编码
:
fprintf(fp,
for(i=0;i
//printf(
fprintf(fp,
fprintf(fp,
//printf(
}
else{
a[len]=0;
HuffManCoding(BT->lchild, len+1,fp);
a[len]=1;
HuffManCoding(BT->rchild, len+1,fp);
}
}
}
int menu()
{
int n;
printf(
printf(
字符集和频度操作：
n
printf(
载入数据文件。
n
printf(
显示数据。
n
printf(
排序。
n
printf(
哈夫曼树操作：
n
printf(
建立哈夫曼树。
n
printf(
写入哈夫曼编码文件。
n
printf(
显示哈夫曼编码文件。
n
printf(
销毁哈夫曼树。
n
printf(
哈夫曼编译码操作：
n
printf(
载入哈夫曼编码。
n
printf(
显示哈夫曼编码。
n
printf(
编码
ToBeTran
文件
.n
printf(
译码
CodeFile
文件
.n
printf(打印
CodeFile
文件
.n
printf(
打印哈夫曼树< br>.n
printf(
退出
n
printf(
printf(
请输入选择：
while(1)
{
scanf(
if(n>0&&n<15)
break;
printf(
输入错误，请重输：
}
system(
return n;
}
int printHuffManfile() //
输出哈夫曼树
字符
频度
编码
{
FILE * fp;
char data[50],c;
int d;
fp=fopen(
if(NULL==fp)
{
printf(
打开文件哈夫曼编码错误。
n
return -1;
}
while(1)
{
fscanf(fp,
if(feof(fp))
break;
printf(
fseek(fp,2,SEEK_CUR);
}
fclose(fp);
}
main()
{
mytype data[N]={0};
HuffM hmdata[N]={0};
int flag;
int choose,count;
FILE *fp;
bitree * bthead=NULL;
count=0;
g_flag=0;//
刚开始时数据为空。
while(1)
{
choose=menu();
switch(choose)
{
case 1:
flag=reaData(data);
if(-1==flag)
{
printf(
return;
}
break;
case 2:
printData(data);
break;
case 3:
sort(data);
break;
case 4:
bthead=createbt(data);
break;
case 5:
fp=fopen(
if(NULL==fp)
{
printf(
写入哈夫曼编码错误！
n
return;
}
HuffManCoding(bthead,0,fp);
g_flag=111;
fclose(fp);
break;
case 6:
printHuffManfile();
break;
case 7:
if(g_flag<11)
{
printf(
请先建立哈夫曼树。
n
break;
}
bthead=destroybt(bthead);
g_flag=1;
break;
case 8:
flag=reaHFData(hmdata);
if(-1==flag)
{
printf(
return;
}
sortHMC(hmdata);
break;
case 9:
printHFData(hmdata);
break;
case 10:
Encoding(hmdata);
break;
case 11:
Decoding(hmdata);
break;
case 12:
PrintCodeFile();
break;
case 13:
PreOrderPrint(bthead,count);
break;
case 14:
destroybt(bthead);
return 0;
break;
}
}
}
int Encoding(HuffM d[])//
编码
{
FILE *fp,*pfc;
char data[256]={0},c;
fp=fopen(
pfc=fopen(
if(NULL==fp)
{
printf(
打开文件
出错，编码未完成
.n
return -1;
}
if(NULL==pfc)
{
fclose(fp);
printf(
出错，编码未完成
.n
return -1;
}
while(1)
{
fread(&c,1,1,fp);
if(c>='a'&&c<='z')
c-=32;
if(c>='A'&&c<='Z')
{
//printf(
fprintf(pfc,
}
else if (c==' ')
//printf(
fprintf(pfc,
else
//printf(
fprintf(pfc,
//printf(
if(feof(fp))
break;
}
fclose(fp);
fclose(pfc);
}
int Decoding(HuffM d[])//
编码
{
FILE *fp, *pfc;
char data[20] = { 0 },c;
int i;//, flag
fp = fopen(
pfc = fopen(
-
-
-
-
-
-
-
-
本文更新与2021-01-25 09:38，由作者提供，不代表本网站立场，转载请注明出处：https://www.bjmy2z.cn/gaokao/565146.html
-
上一篇：算法与数据结构课程设计
下一篇：公差试卷2(参考答案)