数据结构C语言版实验报告哈夫曼树.docx
- 文档编号:4141763
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:42
- 大小:126.98KB
数据结构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;i for(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;i for(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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言版 实验 报告 哈夫曼树