数据结构C语言版实验报告哈夫曼树.docx
《数据结构C语言版实验报告哈夫曼树.docx》由会员分享，可在线阅读，更多相关《数据结构C语言版实验报告哈夫曼树.docx（42页珍藏版）》请在冰点文库上搜索。
数据结构C语言版实验报告哈夫曼树
《数据结构与算法》实验报告
一、需求分析
1.问题描述：
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工通道（及可以双向传输信息的通道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼的编/译码系统。
2.基本要求
一个完整的系统应具有以下功能：
（1）I：
初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
（2）E：
编码（Encoding）。
利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3）D：
译码（Decoding）。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
（4）P：
印代码文件（Print）。
将文件CodeFile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码文件写入文件CodePrin中。
（5）T：
印哈夫曼树（Treeprinting）。
将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示出，同时将此字符形式的哈夫曼树写入文件TreePrint中。
3.测试数据
（1）利用教科书例6-2中的数据调试程序。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：
“THISPROGRAMISMYFAVORITE”。
字符
A
B
C
D
E
F
G
H
I
J
K
L
M
频度
64
13
22
32
103
21
15
47
57
1
5
32
20
字符
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
频度
57
63
15
1
48
51
80
23
8
18
1
16
1
4,实现提示
（1）编码结果以文本方式存储在文件CodeFile中。
（2）用户界面可以设计为“菜单”方式：
显示上述功能符号，再加上“Q”表示退出运行Quit。
请用户键入一个选择功能符。
此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。
（3）在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。
每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
二、概要设计
本程序的数据类型定义为:
typedefstruct{
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;
typedefchar**HuffmanCode;
所实现的功能函数为：
voidinitHuffmanTree（）;//选择初始化哈夫曼树的方式
intopenfileInit（）;//通过打开的data.txt文件初始化哈夫曼树该文件是为了测试数据2包涵26个字符
intinputInit（）;//通过手动输入字符初始化哈夫曼树
intHuffmanCoding（int*w）;//初始化哈夫曼数，按照哈夫曼规则建立二叉树。
此函数块调用了Select（）函数。
voidSelect（intj,int&s1,int&s2）;//选择parent为0，且weight最小的两个节点序号为s1，s2
voidencoding（）;//选择哈夫曼编码方式
voidopenfileEnco（）;//通过打开文件encode.txt的方式进行编码
voidinputEnco（）;//通过手动输入的方式进行编码
voiddecode（）;//选择译码方式
voidopenfileDeco（）;//通过打开文件CodeFile.txt的方式进行译码
voidinputDeco（）;//通过手动输入的方式进行译码
voiddispHT（HuffmanTreenodeRoot,intlevel）;//以缩进方式输出哈夫曼树直观图
主函数：
主函数主要设计的是一个分支语句，让用户挑选所实现的功能。
如图所示：
三、详细设计
//程序的头文件
#include
#include
#include
usingnamespacestd;
ofstreamoutstuf;
typedefstruct{
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;
typedefchar**HuffmanCode;
HuffmanTreeHT=NULL;
intn=0;
HuffmanCodeHC=NULL;
char*ch=NULL;
voidinitHuffmanTree（）;
intopenfileInit（）;
intinputInit（）;
intHuffmanCoding（int*w）;
voidSelect（intj,int&s1,int&s2）;
voidencoding（）;
voidopenfileEnco（）;
voidinputEnco（）;
voiddecode（）;
voidopenfileDeco（）;
voidinputDeco（）;
voiddispHT（HuffmanTreenodeRoot,intlevel）;
voidinitHuffmanTree（）{//选择初始化哈夫曼树
intsel=0;
for（;;）{
cout<<"\t*********************************************************"<cout<<"\t*"<<"字符集及权值来源\t\t\t\t\t*"<cout<<"\t*\t"<<"1.使用权值文件data.txt进行编码\t\t\t*"<cout<<"\t*\t"<<"2.自行输入字符集及权值\t\t\t\t*"<cout<<"\t*\t"<<"3.返回上层\t\t\t\t\t*"<cout<<"\t*********************************************************"<cout<<"请输入您的选择"<cin>>sel;
if（sel==3）break;
switch（sel）
{case1:
openfileInit（）;break;
case2:
inputInit（）;break;
default:
cout<<"对不起，您输入的数据有误！
请重新输入。
"<}
};
}
intopenfileInit（）{//通过打开的data.txt文件初始化哈夫曼树该文件是为了测试数据2包涵26个字符
int*w=（int*）malloc（28*sizeof（int））;
ch=（char*）malloc（28*sizeof（char））;
n=27;
ifstreaminfile（"data.txt",ios:
:
in）;
if（!
infile）{
cerr<<"openerror!
"<exit
（1）;
}
cout<<"权值文件中的信息（#代表空格）"<for（inti=1;infile.eof（）==0;i++）{
infile>>ch[i];
infile>>w[i];
}
cout<infile.close（）;
cout<<"字符:
";
for（i=1;i<10;i++）cout<cout<<"权值:
";
for（i=1;i<10;i++）cout<cout<<"字符:
";
for（i=10;i<19;i++）cout<cout<<"权值:
";
for（i=10;i<19;i++）cout<cout<<"字符:
";
for（i=19;i<28;i++）cout<cout<<"权值:
";
for（i=19;i<28;i++）cout<cout<n=27;
HuffmanCoding（w）;
cout<<"各字符编码如下：
"<for（i=1;i<=27;i++）{
cout<<""<cout<};
outstuf.open（"code.txt",ios:
:
out）;
for（i=1;i<=27;i++）{outstuf<outstuf.close（）;
return0;
}
intinputInit（）{//通过手动输入字符初始化哈夫曼树
cout<<"请输入字符集n\t";
cin>>n;
int*w=（int*）malloc（（n+1）*sizeof（int））;
if（!
w）{cout<<"ERROR";return0;}
ch=（char*）malloc（（n+1）*sizeof（char））;
if（!
ch）{cout<<"ERROR";return0;}
cout<<"请输入各字符\t";
for（inti=1;i<=n;i++）cin>>ch[i];
cout<<"请输入各权值\t";
for（i=1;i<=n;i++）cin>>w[i];
//outstuf.close（）;
outstuf.open（"hfmTree.txt",ios:
:
out）;
for（i=1;i<=n;i++）{outstuf<cout<HuffmanCoding（w）;
cout<<"各字符编码如下：
";
for（i=1;i<=n;i++）{
cout<<""<cout<};
outstuf.close（）;
outstuf.open（"code.txt",ios:
:
out）;
for（i=1;i<=n;i++）{outstuf<cout<outstuf.close（）;
return0;
}
intHuffmanCoding（int*w）{//哈夫曼编码
if（n<=1）return1;
intm=2*n-1;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
if（!
HT）{cout<<"ERROR";return0;}
for（inti=1;i<=n;++i）
{
HT[i].weight=w[i];
HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
for（;i<=m;++i）HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;
ints1=0;
ints2=0;
for（i=n+1;i<=m;++i）{
Select（i-1,s1,s2）;
HT[s1].parent=i;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*））;
char*cd=（char*）malloc（n*sizeof（char））;
if（!
cd）{cout<<"ERROR";return0;}
cd[n-1]='\0';
intstart;
for（i=1;i<=n;++i）{
start=n-1;
for（intc=i,unsignedintf=HT[i].parent;f!
=0;c=f,f=HT[f].parent）
{if（HT[f].lchild==c）cd[--start]='0';
elsecd[--start]='1';
}
HC[i]=（char*）malloc（（n-start）*sizeof（char））;
strcpy（HC[i],&cd[start]）;
}
free（cd）;
return0;
}
voidSelect（intj,int&s1,int&s2）{//选择parent为0，且weight最小的两个节点序号为s1，s2
for（inth=1;h<=j;h++）
if（HT[h].parent==0）{s1=h;break;}
h++;
for（;h<=j;h++）
if（HT[h].parent==0）{s2=h;break;}
intm;
if（HT[s1].weight>HT[s2].weight）{m=s1;s1=s2;s2=m;}
h++;
for（;h<=j;h++）
if（HT[s1].weight>HT[h].weight&&HT[h].parent==0）s1=h;
for（m=1;m<=j;m++）
if（HT[s2].weight>HT[m].weight&&m!
=s1&&HT[m].parent==0）s2=m;
}
voidencoding（）{//选择哈夫曼编码方式
intsel=0;
for（;;）{
if（!
HT）{cout<<"对不起，哈夫曼树不存在！
请先建立哈夫曼树。
"<cout<<"\t*********************************************************"<cout<<"\t*"<<"要编码的文件来源\t\t\t\t\t*"<cout<<"\t*\t"<<"1.使用已有文件encode.txt进行编码\t\t*"<cout<<"\t*\t"<<"2.自行输入文件进行编码\t\t\t\t*"<cout<<"\t*\t"<<"3.返回上层\t\t\t\t\t*"<cout<<"\t*********************************************************"<cout<<"请输入您的选择"<cin>>sel;
if（sel==3）break;
switch（sel）
{case1:
openfileEnco（）;break;
case2:
inputEnco（）;break;
default:
cout<<"对不起，您输入的数据有误！
请重新输入。
"<}
}
voidopenfileEnco（）{//通过打开文件encode.txt的方式进行编码
cout<<"encode.txt文件内容如下（#代表空格）：
"<ifstreaminfile（"encode.txt",ios:
:
in）;
if（!
infile）{
cerr<<"openerror!
"<exit
（1）;
}
char*file=（char*）malloc（200*sizeof（char））;
for（inti=1;infile.eof（）==0&&i!
=200;i++）{
infile>>file[i];
cout<}
if（i==200）{
file=（char*）realloc（file,（200+80）*sizeof（char））;
for（;infile.eof（）==0&&i!
=280;i++）{
infile>>file[i];
cout<}
}
infile.close（）;
cout<intm=i;
cout<<"编码结果是：
"<//outstuf.close（）;
outstuf.open（"CodeFile.txt",ios:
:
out）;
for（i=1;ifor（intj=1;j<=n;j++）if（file[i]==ch[j]）{cout<if（j==（n+1））{cout<"<}
cout<outstuf.close（）;
}
voidinputEnco（）{//通过手动输入的方式进行编码
cout<<"请输入您要编码的文章（以$作为文章结尾）"<char*file=（char*）malloc（200*sizeof（char））;
for（inti=1;i<200;i++）{
cin>>file[i];
if（file[i]=='$'）break;
}
if（i==200）{
file=（char*）realloc（file,（200+80）*sizeof（char））;
for（;i<280;i++）{
cin>>file[i];
if（file[i]=='$'）break;
}
}
intm=i;
cout<<"编码结果是：
"<//outstuf.close（）;
outstuf.open（"CodeFile.txt",ios:
:
out）;
for（i=1;ifor（intj=1;j<=n;j++）if（file[i]==ch[j]）{
cout<outstuf<}//将编码结果写入CodeFile.txt
if（j==（n+1））{cout<"<}
cout<outstuf.close（）;
}
voiddecode（）{//选择译码方式
intsel=0;
for（;;）{
if（!
HT）{cout<<"对不起，哈夫曼树不存在！
请先建立哈夫曼树。
"<cout<<"\t*********************************************************"<cout<<"\t*"<<"要译码的文件来源\t\t\t\t\t*"<cout<<"\t*\t"<<"1.使用已有文件CodeFile.txt进行译码\t\t*"<cout<<"\t*\t"<<"2.自行输入文件进行译码\t\t\t\t*"<cout<<"\t*\t"<<"3.返回上层\t\t\t\t\t*"<cout<<"\t*********************************************************"<cout<<"请输入您的选择"<cin>>sel;
if（sel==3）break;
switch（sel）
{case1:
openfileDeco（）;break;
case2:
inputDeco（）;break;
default:
cout<<"对不起，您输入的数据有误！
请重新输入。
"<}
}
voidinputDeco（）{//通过手动输入的方式进行译码
intm=2*n-1;
char*password=（char*）malloc（200*sizeof（char））;
cout<<"请输入要译码的文件（以$结束）"<for（inti=1;i<200&&password[i-1]!
='$';i++）cin>>password[i];
if（i==200）{
password=（char*）realloc（password,（200+80）*sizeof（char））;
for（;i<280&&password[i]!
='$';i++）cin>>password[i];
}
cout<<"译码结果为（#代表空格）"<//outstuf.close（）;
outstuf.open（"TextFile.txt",ios:
:
out）;
for（i=1;password[i]!
='$';）{
charrecord[20];
for（intj=0,q=i;password[q]!
='$';j++,q++）{
if（password[q]=='0'）{record[j]='0';m=HT[m].lchild;}
else{record[j]='1';m=HT[m].rchild;}
if（HT[m].rchild==0）{record[j+1]='\0';break;}
}
if（HT[m].rchild!
=0）{cout<此处不可译码！
"<for（intp=1;p<=n;p++）{
if（!
strcmp（record,HC[p]））{outstuf<}
i=i+strle
升级会员 