数据结构(C语言版)实验报告(哈夫曼树)(共28页).docx

《数据结构(C语言版)实验报告(哈夫曼树)(共28页).docx》由会员分享，可在线阅读，更多相关《数据结构(C语言版)实验报告(哈夫曼树)(共28页).docx（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构与算法实验报告一、 需求分析1. 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工通道（及可以双向传输信息的通道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。2. 基本要求一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利

2、用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。（5）T：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示出，同时将此字符形式的哈夫曼树写入文件TreePrint中。3. 测试

3、数据（1） 利用教科书例6-2中的数据调试程序。（2） 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符ABCDEFGHIJKLM频度6413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811614,实现提示（1） 编码结果以文本方式存储在文件CodeFile中。（2） 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为

4、止。（3） 在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。二、 概要设计 本程序的数据类型定义为:typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char* HuffmanCode;所实现的功能函数为：void initHuffmanTree();/选择初始化哈夫曼树的方式int openfileInit();/通过打开的data.txt文件

5、初始化哈夫曼树 该文件是为了测试数据2 包涵26个字符int inputInit();/通过手动输入字符初始化哈夫曼树int HuffmanCoding(int *w); /初始化哈夫曼数，按照哈夫曼规则建立二叉树。此函数块调用了Select（）函数。void Select(int j,int &s1,int &s2); /选择parent为0，且weight最小的两个节点 序号为s1，s2void encoding();/选择哈夫曼编码方式void openfileEnco();/通过打开文件encode.txt的方式进行编码void inputEnco();/通过手动输入的方式进行编码vo

6、id decode();/选择译码方式void openfileDeco();/通过打开文件CodeFile.txt的方式进行译码void inputDeco();/通过手动输入的方式进行译码void dispHT( HuffmanTree nodeRoot, int level ); /以缩进方式输出哈夫曼树直观图主函数：主函数主要设计的是一个分支语句，让用户挑选所实现的功能。如图所示：initHuffmanTree();初始化哈夫曼树HuffmanCoding()构造哈夫曼树编码调用Encoding()译码调用Decode（）dispHT()打印哈夫曼树Select（）供HuffmanCo

7、ding()调用三、 详细设计/程序的头文件#include#include#includeusing namespace std;ofstream outstuf;typedef structunsigned int weight;unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char* HuffmanCode; HuffmanTree HT=NULL;int n=0;HuffmanCode HC=NULL;char *ch=NULL;void initHuffmanTree();int openfileInit

8、();int inputInit();int HuffmanCoding(int *w);void Select(int j,int &s1,int &s2);void encoding();void openfileEnco();void inputEnco();void decode();void openfileDeco();void inputDeco();void dispHT( HuffmanTree nodeRoot, int level );void initHuffmanTree() /选择初始化哈夫曼树 int sel=0; for(;) coutt*endl; coutt

9、* 字符集及权值来源ttttt*endl; coutt*t1.使用权值文件data.txt进行编码ttt*endl; coutt*t2.自行输入字符集及权值tttt*endl; coutt*t3.返回上层ttttt*endl; coutt*endl; cout请输入您的选择endlsel; if(sel=3) break; switch(sel) case 1:openfileInit();break; case 2:inputInit();break; default:cout对不起，您输入的数据有误！请重新输入。endl; ; int openfileInit() /通过打开的data.t

10、xt文件初始化哈夫曼树 该文件是为了测试数据2 包涵26个字符 int *w=(int*)malloc(28*sizeof(int); ch=(char*)malloc(28*sizeof(char); n=27; ifstream infile(data.txt,ios:in); if(!infile) cerropen error!endl; exit(1); cout 权值文件中的信息（#代表空格）endlchi; infilewi; coutendl; infile.close(); cout 字符:; for(i=1;i10;i+) coutchit; cout 权值:; for(i

11、=1;i10;i+) coutwit; cout 字符:; for(i=10;i19;i+) coutchit; cout 权值:; for(i=10;i19;i+) coutwit; cout 字符:; for(i=19;i28;i+) coutchit; cout 权值:; for(i=19;i28;i+) coutwit; coutendl; n=27; HuffmanCoding(w); cout 各字符编码如下：endl; for(i=1;i=27;i+) cout chit; coutHCiendl; ; outstuf.open(code.txt,ios:out); for(i=

12、1;i=27;i+) outstufchi;outstufHCi; /将各个字符的编码写入文件code.txtoutstuf.close(); return 0; int inputInit() /通过手动输入字符初始化哈夫曼树 coutn; int *w=(int *)malloc(n+1)*sizeof(int); if(!w) coutERROR;return 0; ch=(char *)malloc(n+1)*sizeof(char); if(!ch) coutERROR;return 0; cout 请输入各字符t; for(int i=1;ichi; cout 请输入各权值t; f

13、or(i=1;iwi; /outstuf.close(); outstuf.open(hfmTree.txt,ios:out); for(i=1;i=n;i+)outstufchi; outstufwi; /将各个字符的权值写入文件hfmTree.txt coutendl; HuffmanCoding(w); cout 各字符编码如下：; for(i=1;i=n;i+) cout chit; coutHCi; ; outstuf.close(); outstuf.open(code.txt,ios:out); for(i=1;i=n;i+)outstufchi; outstufHCi;/将各个

14、字符的编码写入文件code.txt coutendl;outstuf.close(); return 0;int HuffmanCoding(int *w) /哈夫曼编码 if(n=1) return 1; int m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); if(!HT) coutERROR;return 0; for(int i=1; i=n; +i) HTi.weight=wi; HTi.parent=HTi.lchild=HTi.rchild=0; for(;i=m; +i) HTi.weight=HTi.parent=HT

15、i.lchild=HTi.rchild=0; int s1=0; int s2=0; for(i=n+1;i=m; +i) Select(i-1, s1, s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+ HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); char *cd=(char*) malloc(n*sizeof(char); if(!cd) coutERROR;return 0; cdn-1=0;

16、int start; for(i=1;i=n;+i) start=n-1; for(int c=i,unsigned int f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd); return 0;void Select(int j,int &s1,int &s2) /选择parent为0，且weight最小的两个节点 序号为s1，s2 fo

17、r(int h=1;h=j;h+) if(HTh.parent=0) s1=h;break; h+; for(;hHTs2.weight) m=s1;s1=s2;s2=m; h+; for(;hHTh.weight&HTh.parent=0) s1=h; for(m=1;mHTm.weight&m!=s1&HTm.parent=0) s2=m;void encoding() /选择哈夫曼编码方式 int sel=0; for(;) if(!HT) cout对不起，哈夫曼树不存在！请先建立哈夫曼树。endl; break; coutt*endl; coutt* 要编码的文件来源ttttt*end

18、l; coutt*t1.使用已有文件encode.txt进行编码tt*endl; coutt*t2.自行输入文件进行编码tttt*endl; coutt*t3.返回上层ttttt*endl; coutt*endl; cout请输入您的选择endlsel; if(sel=3) break; switch(sel) case 1:openfileEnco();break; case 2:inputEnco();break; default:cout对不起，您输入的数据有误！请重新输入。endl; void openfileEnco() /通过打开文件encode.txt的方式进行编码 cout e

19、ncode.txt文件内容如下（#代表空格）：endl; ifstream infile(encode.txt,ios:in); if(!infile) cerropen error!filei; coutfilei; coutfilei; infile.close(); coutendl; int m=i; cout 编码结果是：endl; /outstuf.close(); outstuf.open(CodeFile.txt,ios:out); for(i=1;im-1;i+) for(int j=1;j=n;j+)if(filei=chj) coutHCj; outstufHCj;bre

20、ak;/将编码结果写入 CodeFile.txt if(j=(n+1) coutendl此处编码出现错误，含有不可编码的字符！endl; break; coutendl; outstuf.close();void inputEnco() /通过手动输入的方式进行编码 cout 请输入您要编码的文章（以$作为文章结尾）endl; char *file=(char *)malloc(200*sizeof(char); for(int i=1;ifilei; if(filei=$) break; if(i=200) file=(char *)realloc(file,(200+80)*sizeof(

21、char); for(;ifilei; if(filei=$) break; int m=i; cout 编码结果是：endl; /outstuf.close(); outstuf.open(CodeFile.txt,ios:out); for(i=1;im;i+) for(int j=1;j=n;j+)if(filei=chj) coutHCj;outstufHCj; break;/将编码结果写入 CodeFile.txt if(j=(n+1) coutendl此处编码出现错误，含有不可编码的字符！endl; break; coutendl; outstuf.close(); void de

22、code() /选择译码方式 int sel=0; for(;) if(!HT) cout对不起，哈夫曼树不存在！请先建立哈夫曼树。endl; break; coutt*endl; coutt* 要译码的文件来源ttttt*endl; coutt*t1.使用已有文件CodeFile.txt进行译码tt*endl; coutt*t2.自行输入文件进行译码tttt*endl; coutt*t3.返回上层ttttt*endl; coutt*endl; cout请输入您的选择endlsel; if(sel=3) break; switch(sel) case 1:openfileDeco();brea

23、k; case 2:inputDeco();break; default:cout对不起，您输入的数据有误！请重新输入。endl; void inputDeco() /通过手动输入的方式进行译码 int m=2*n-1; char *password=(char *)malloc(200*sizeof(char); cout 请输入要译码的文件(以$结束）endl; for(int i=1;ipasswordi; if(i=200) password=(char *)realloc(password,(200+80)*sizeof(char); for(;ipasswordi; cout译码结

24、果为（#代表空格）endl; /outstuf.close(); outstuf.open(TextFile.txt,ios:out); for(i=1;passwordi!=$;) char record20; for(int j=0,q=i;passwordq!=$;j+,q+) if(passwordq=0) recordj=0;m=HTm.lchild; else recordj=1;m=HTm.rchild; if(HTm.rchild=0) recordj+1=0;break; if(HTm.rchild!=0) coutendl译码在此处出现错误！此处不可译码！endl; bre

25、ak; for(int p=1;p=n;p+) if(!strcmp(record,HCp) outstufchp; coutchp;break; i=i+strlen(record); m=2*n-1; coutendl; outstuf.close();void openfileDeco() /通过打开文件CodeFile.txt的方式进行译码 int m=2*n-1; cout CodeFile.txt文件内容如下：endl; ifstream infile(CodeFile.txt,ios:in); if(!infile) cerropen error!passwordi; coutp

26、asswordi; coutpasswordi; infile.close(); password+i=$; coutendl; cout译码结果为（#代表空格）endl; /outstuf.close(); outstuf.open(TextFile.txt,ios:out); for(i=1;passwordi!=$;) char record20; for(int j=0,q=i;passwordq!=$;j+,q+) if(passwordq=0) recordj=0;m=HTm.lchild; else recordj=1;m=HTm.rchild; if(HTm.rchild=0)

27、 recordj+1=0;break; if(HTm.rchild!=0) coutendl译码在此处出现错误！此处不可译码！endl; break; for(int p=1;p=n;p+) if(!strcmp(record,HCp) outstufchp;coutchp;break; i=i+strlen(record); m=2*n-1; coutrchild) dispHT(HT+nodeRoot-rchild,level+1); for(int i=0;ilevel;i+) if(ilevel-1)cout ;outstuf ;else cout-;outstuf-; coutweightendl; outstufweightlchild!=0 ) dispHT(HT+nodeRoot-lchild,level+1); int main() int sel=0; cout欢迎使用哈夫曼编码/译码器-endl; for(;) coutt*endl; coutt*t1.构建哈夫曼树ttttt*endl; coutt*t2.输出哈夫曼树ttttt*endl; coutt*t3.编码tttttt*endl; coutt*t4.译码tttttt*endl; coutt*t5.退出tttttt*endl; coutt*e