《课程设计报告-哈夫曼编译码器.docx》由会员分享，可在线阅读，更多相关《课程设计报告-哈夫曼编译码器.docx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、合肥学院计算机科学与技术系课程设计报告20122013学年第2学期2013 年6月if(!input_file) (coutz/can，t oen file!/zcode;cout编码码值为：codeendl;input f ile. close (); )D操作：译码功能：利用已建好的哈夫曼树将文件codefile, txt中的代码进行译码，结果 存入文件textfile, dat中。Print()打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。 else if (choice二二D | | choice二二d)/读入 CodeFile. txt 中的编码进行译码,将译出来的字符放
2、入Textfile, txt中 | input_file. open(CodeFile. txt);if (!input_file)cout，can，t oen file!，zh;input_file. close();output_file. openCTextfile. txt); if (!output_file) ( cout，/can，t oen file!z，endl; return 1;k= 0;while(hk !二0)先用编码中的前几个和字符的编码相比拟,然后往后移 (for(i=l;i=n;i+) 1 二k;for (j=0;jstrlen(HCi)；j+, 1+) hlj
3、=hl;)hlj= 0;if (strcmp(HCi, hl)=0) (output_fileHTi. ch;k=k+strlen(HCi);break;output_file. close ();input_file. open(Textfile. txt);if(!input_file)cout/，can，t oen file!，zh;couthendl;input_file. close();cout译码结束,字符已经存入Textfile, txt文件中！endlQ操作：退出。四、上机调试过程在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是假设没有定义所引用的相关头文件
4、，必定调试不通过；在执行译码操作时，不知什么原因，总是不能把要编译的二进制数与编译成的字符用连 接号连接起来，而是按顺序直接放在一起，视觉效果不是很好。这次课程设计，我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保 存数据，对文件的操作也很生疏。还需要多多学习。五、测试结果及其分析主R青青主闫青主0C主后主R青青主闫青主0C主后c *E:E08620305DebugE08620305. exeJAJAJAJA!AJAlA输输输输麻2也痢枚或板根权权或和和和和和和和.息自心自心自心自心自心自心信信信信信信信：11010：100：01010：1101101:0110I ：1010：0
5、011110：0010：01000：1100：1110：001111110：0111：1011：0001:010111:001110：01001；：001111111：00110：00111110：1111赫夫曼树己经创立完毕，并且己经放入hfmTree.txt文件中图三选择I步骤，建立哈夫曼树，输入字符信息和权值，并进行编码。I.In itE.EncodingJi入您要操作的步骤：ED.DecodingQ.Exit睛输入字符：A编同完毕，并且已经存入Co deFile.txt文件I 编码码值为：0输入一个字符，程序对字符进行编码。图四XXXXXXXXXXXXXXXXXXXXXXXX X市市毛
6、3/i举石3XXXXXXXXXXXXXXXXXXXXXXXXXE.Encoding请掇入您詈操作的步骤：E请输入字符：THISPROGRAME IS MV FOUERITED.DecodingQ.Exit编码完毕，并且已经存入Co de File . txt文件！编码码值为：图五输入题目要求的字符串，得出其编码值。XXXXXXXXXXXXXXXXXXXXXXXX X 市亦 夫昙编码予码XXXXXXXXXXXXXXXXXXXXXXXXXI.In itE.Encoding请输入您要操作的步骤：DD.DecodingQ.ExitIIHISPROGRAMEISMVFOUERITEXXMMMMXXXMX
7、MXMXXMXMXMXMX X 市市夫导编码 /j 半码含M*M*M*M*M*MM*M*M*M*M*M译码结束，字符己经存入Textfile. txt文件中!图五选择步骤D,对上图显示的编码进行译码，重新得到字符串，并存入相应文件中MXXXXXXXXXXXXXXXXMXMXMXX 共市亦夫导编码 / j 半码言言关*I.InitE.EncodingD.DecodingQ.Exit演输入您要操作的步骤：QPress any key to continue图六 选择退出。XXXXXXXXXXXXXXXXXXXXXXXX X ,并口勺XX XX XXX XXX XXX XXX XXX XXX XXX
8、I.InitE.EncodingD.DecodingQ.Exit请输入您詈操作的步骤：E请输入字符：THISPROGRAME IS MV FOUERITE1码完毕，并且己经存入Co de File. txt文件！陶码码值为：图7如截图所示得出测试结果。通过将输入字符事先进行编码，利用E步骤将THISPROGRAM IS MY FAVORITE进行编码得出结果。然后将代码进行译码，重新得到原有的字符，结果存入文件 textfile, dat 中。六、用户使用说明本系统使用的是 Microsoft Visual C+ 6.0。Visual C+（简称 VC）是 Microsoft 公司 推出的目前
9、使用极为广泛的基于Windows平台的C+可视化开发环境。Visual C+ 6. 0提供 的控制台应用程序对学习和掌握标准C+内容非常有利。在运行该程序后根据显示的提示进 行操作，首先在您要操作的步骤后输入I,开始时请输入字符数，然后输入每个字符信息和 权值。回车键后选择E步骤，输入问题要求的字符，然后选择D步骤对代码进行译码，存入 文件，最后输入Q,选择退出。七、参考文献1王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006年5月。2潘彦.算法设计与分析基础M.北京:清华大学出版社,2007. 13肖梦强、曲秀清.软件工程一一原理、方法与应用刈.中国水利水电出版社,2005. 10
10、4吕凤翥.C+语言程序设计（第2版）.电子工业出版社,2007. 25严蔚敏、吴伟民.数据结构（C语言版）M.清华大学出版社,2002. 9八、附录哈夫曼编码/译码器源代码#include#include#include#include#includetypedef struct 赫夫曼树的结构体char ch;int weight;权值int parent, Ichild,rchild;htnode, *hfmtree;typedef char *hfmcode;void Select (hfmtree &HT, int a, int *pl, int *p2) “Select 函数，选出
11、HT 树到 a 为止, 权值最小且parent为0的2个节点int i, j, x, y;for(j=l;j=a;+j) if(HTj. parent=0) x=j;break;)for (i=j+l;i=a;+i) if(HTi. weightHTx. weight&HTi. parent=0) x二i;选出最小的节点)for(j=l;j=a;+j)if(HTj. parent=O&x!=j)(y二 j;break;)for(i=j+l;i=a;+i)(ifweighty) *pl=y;*p2=x;) else (*pl=x;*p2=y;)void hfmcoding(hfmtree &HT
12、, hfmcode &HC, int n) 构建赫夫曼树 HT,并求出 n 个字符 的赫夫曼编码HC(int i, start, c, f, m, w;int pl, p2;char *cd, z;if(n=l) return;m=2*nT;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for (i=l; i=n;+i)初始化n个叶子结点(printf (请输入第%d字符信息和权值：，i);scanf (c%d，&z, &w);while (getchar () !二n )continue;)HT i.ch=z;HTi.weight=w;HTi. parent=
13、0;HTi. lchild=0;HTi.rchild=O;)for(;i=m;+i)初始化其余的结点(HTi.ch= O;HTi. weight=0;HTi.parent=0;HTi.lchild=0;HTi. rchild=0;for (i=n+l;i=m;+i)建立赫夫曼树Select(HT, i-l, &pl, &p2);HTpl. parent=i;HTp2. parent=i;HTi. lchild=pl;HTi.rchild=p2;HTi. weight=HTpl. weight+HTp2. weight;IIC=(hfmcode)malloc (n+l)*sizeof (char
14、 *);cd二(char *)malloc(n*sizeof(char);cdn-l=，0J ;for (i=l; i=n;+i)给 n 个字符编码start=n-l;for(c=i, f=HTi. parent;f!=0;c=f, f=HTf.parent) (if(HTf. lchild=c)(cd 一start=0，;else( cd一start=f ;)HCi = (char*)malloc(n-start)*sizeof (char);strcpy (HCi, &cdstart);)free (cd);int main () char code100, h100,hl100;int
15、n, i, j, k, 1;if stream input_file;文件输入输出流ofstream output_file;char choice, str100;hfmtree HT;hfmcode HC;coutn；coutz，网工(1)班，/，1104031021，/，XXn；while (choice!=，Q? &choice!=，q)当 choice 的值不为 q 且不为 Q时循环cout*AJx x|x xjx Xjs X|S XJSpw xjx xjx xjs xjs xjs x|x x|x xjs ysxjs xj% Js XJSXJS XJS coutI InitE. En
16、codingD. Decoding，choice;if (choice二二I | | choice i)初始化赫夫曼树|cout请输入字符个数：； cinn;hfmcodingOlT, IIC, n);for(i=l;i=n;+i)(coutHTi. ch，:，HCiendl;output_file. open ChfmTree. txt);if (!output_file) cout，can，t oen file!，zendl;return 1;for(i=l;i=n;i+)|output_file，CHTiL chHCi，)/，；output_file. close();cout赫夫曼树已
17、经创立完毕，并且已经放入hfmTree. txt文件中！endl; )else if (choice=E | | choice=e)进行编码，并将字符放入ToBeTran. txt,码值放入 CodeFile. txt 中(printf (请输入字符：)；gets (str);output_file. open(ToBeTran. txt);if (!output_file)(cout/zcan，t oen file! z/endl;return 1;output_filestrendl;output_file. close();output_file. open(CodeFile. txt)
18、;if (!output_file) cout，can，t oen file!z/endl;return 1;for (i=0;istrlen(str) ;i+) for(j=0;j=n;+j) (if(HTj. ch=stri)(output_fileHCj;break;)output_f ile. close ();coutn;cout”编码完毕,并且已经存入CodeFile. txt文件! n；input_file. open(CodeFile. txt);从 CodeFile. txt 中读入编码，输出在终端if(!input_file)(cout，can，t oen file!z/c
19、ode;cout”编码码值为：codeendl;input_file. close();)else if (choice二二D | | choice=二d，)读入 CodeFile. txt 中的编码进行译码，将译出来的字符放入Textfile, txt中(input_file. open(z，CodeFile. txt);if(!input_file) cout/zcan，t oen file!/zh;input_file. close();output_file. open(Textfile. txt);if (!output_file) (cout，can，t oen file!，zen
20、dl;return 1;k=0;while(hk != 0)while(hk != 0)先用编码中的前几个和字符的编码相比拟,然后往后移(for(i=l;i=n;i+) l=k；for (j=0;jstrlen(HCi);j+, 1+) hlj=hl：)hlj=0;if(strcmp(HCi, hl)=0) output_fileHTi. ch;k=k+strlen(HCi);break;)output_f ile. close ();input_file. open(Textfile， txt);if(!input_file) cout，can，t oen file!z/h;couthend
21、l;input_file. close();cout译码结束，字符已经存入Textfile, txt文件中！endl; )else if (choice二二Q | | choice二二q)退出程序(exit (0);)else如果选了选项之外的就让用户重新选择(cout您没有输入正确的步骤，请重新输入！endl;)coutendl;return 0;一、问题分析和任务定义【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成 本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据 进行译码(复原)。对于双工信道(即可以双向传输信息的信道
22、)，每端都需要一个完整的编/ 译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【基本要求】一个完整的系统应具有以下功能：(1)1：初始化(Initialization)。从终端读入字符集大小n ,以及n个字符和n个权 值，建立哈夫曼树，并将它存于文件hfmTree中。(2)E：编码(Encoding)。利用已建好的哈夫曼树(如不在内存，那么从文件hfmTree中读 人)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3)D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码, 结果存入文件TextFile中。(4)
23、P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个 代码。同时将此字符形式的编码文件写入文件CodePrin中。(5)T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹 入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】(1)利用教科书例6-2中的数据调试程序。用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITEo字符ABCDEFGHIJKLM频度18664132232103211547571
24、53220字符N0PQRSTUVWXYZ频度5763151485180238181161【选作内容】上述文件CodeFile中的每个0或 1实际上占用了一个字节的空间，只起到示意或 模拟的作用。为最大限度地利用编码存储能力，试改写你的系统，将编码结果以二进制形式 存放在文件CodeFile中。(2)修改你的系统，实现对你的系统的原程序的编码和译码(主要是将行尾符编/译码问 题)。(3)实现各个转换操作的源/目文件，均由用户在选择此操作时指定。二、数据结构的选择和概要设计哈夫曼树节点的数据类型定义为：typedef struct 赫夫曼树的结构体char ch;int weight;/权值int
25、 parent, Ichild,rchild;Jhtnode, *hfmtree;1、void hfmcoding(hfmtree &HT, hfmcode &HC, int n)初始 化哈夫 曼树，处理 InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规那么建立2叉树。此函数块调用 了 Select ()函数。2、void Select (hfmtree &HT, int a, int *pl, int *p2)/Select 函数，选出 HT树到a为止，权值最小且parent为0的2个节点3、int main ()主函数：利用已建好的哈夫曼树(如不在内存，那么从
26、文件hfmtree. txt中读入)对文件中的正文进行编码，然后将结果存入文件codefile. txt中。如果正文中没有要编码 的字符，那么键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码 好的哈夫曼编码存储到CodeFile中。4、 Encoding编码功能：对输入字符进行编码5、 Decoding译码功能：利用已建好的哈夫曼树将文件codefile, txt中的代码进行译码，结果存入文件 textfile, dat 中。Print()打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。6、主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑
27、选所实现的功能。使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码 函数来实现功能。系统结构图(功能模块图)哈夫曼编/译码器)初始化哈夫曼树)编码)译码)图一打印编码)打印哈夫I曼树)流程图结束结束哈夫曼译码图二三、详细设计和编码1、定义哈夫曼树结构体类型typedef struct 哈夫曼树的结构体char ch;int weight;权值int parent, Ichild,rchild;htnode, *hfmtree;typedef char *hfmcode;2、构建哈夫曼树(1)利用选择select函数选择IIT树中最小的结点void Select (
28、hfmtree &HT, int a, int *pl, int *p2) “Select 函数，选出 HT 树到 a 为止, 权值最小且parent为0的2个节点 (int i, j, x, y;for(j=l;j=a;+j) if(HTj. parent=O) x二 j; break;)for(i=j+l;i=a;+i) if(HTi. weightHTx. weight&HTi. parent=0) x二i;选出最小的节点)for(j=l;j=a;+j)if(HTj. parent=O&x!=j) (y二 j; break; )for(i=j+l;i=a;+i)(if(HTi. weig
29、hty) *pl=y; *p2=x; ) else (*pl=x; *p2=y; ) (2)初始化哈夫曼树，并建立哈夫曼树。void hfmcoding(hfmtree &HT, hfmcode &HC, int n) /构建赫夫曼树 HT,并求出口 个字符 的赫夫曼编码HC (int i, start, c, f, m, w;int pl, p2;char *cd, z;if (n=l)return;m=2*n-l;IIT= (hfmtree)malloc (m+1) *sizeof (htnode);for (i=l; i=n;+i)初始化n个叶子结点(printf (请输入第知字符信息和
30、权值：，i);scanf (%c%d”, &z, &w);while(getchar () !=，n，) ( continue;)HTi. ch=z;HTi.weight=w;HTi. parent=0;HTi. lchild=0;HTi.rchild=0;)for (; i=m;+i)初始化其余的结点(HTi.ch= O;HTi. weight=0;HTi.parent=0;HTi.lchild=O;HTi.rchild=O;)for (i=n+l; i=m;+i)建立赫夫曼树(Select (HT, i-l,&pl,&p2);HTpl. parent=i;HTp2 parent=i;HTi
31、. lchild=pl;HTi.rchild=p2;HTi. weight=HTpl. weight+HTp2. weight;)HC= (hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdnT=0;(3)对哈夫曼树中的n个字符进行编码for(i=l;i=n;+i)for(i=l;i=n;+i)给n个字符编码start=n-l;for (c=i, f=IITi. parent;f!=0;c=f, f=IITf. parent) (if(HTf. lchild=c)(cd一start=O; else ( c
32、d-start=1; )HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi, &cdstart);) free (cd);)2、cout1* vi ” j |coutz，I. InitE. Encoding0/n;hfmcodingOlT, HC, n);for(i=l;i=n;+i) (coutHTi. ch:z，HCiendl;output_file. open (，zhfmTree. txt);if(!output_file) cout，can，t oen file!z/endl;return 1;for (i=l;i=n;i+)outp
33、ut_file/，(，HTi, chHCiO，z；output_file. close ();cout赫夫曼树已经创立完毕，并且已经放入hfmTree. txt文件中！endl;E操作：编码功能：对输入字符进行编码。可以选择在范围之内的任意字符或字符串进行编码。else if (choice二二E |choice二二e)进行编码，并将字符放入ToBeTran. txt,码值放入 CodeFile. txt 中(printf (请输入字符：)；gets (str);output_f ile. open (ToBeTran. txt)；翻开 ToBeTran. txt 文件 if(!output_
34、file)(cout，zcan，t oen file! z/endl;return 1;output_filestrendl;output_file. close();output_file. openCCodeFile. txt);if(!output file)cout，/can，t oen file!z，endl;return 1;for (i=0; Kstrlen (str) ;i+) for(j=0;j=n;+j) (if (HTj. ch=stri)output_f ileHCj;break;)output file. close();coutn;cout”编码完毕,并且已经存入CodeFile. txt文件! n；input_file. open(CodeFile. txt);从 CodeFile. txt 中读入编码，输出在终端