赫夫曼编码器数据结构课程设计

《赫夫曼编码器数据结构课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构》课程设计报告专业计算机科学与技术班级(1)姓名王昕学号20101308003指导教师顾韵华起止时间2011.10~2011.12课程设计:赫夫曼编码器一、任务描述（1）建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。（2）“压缩文件”即：读文件、统计文件中的字符个数、对文件进行哈夫曼编码和译码、并将编码译码后的字符存储在文件中。要求：根据以上任务说明，设计程序完成功能。二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：(1)I：初始化（In

2、itialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。(2)E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3)D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。三、数据结构设计.哈夫曼树节点的数据类型定义为：typedefstruct{//赫夫曼树的结构体charch;intweight;//权值intp

3、arent,lchild,rchild;}htnode,*hfmtree;四、功能设计（一）主控菜单设计为实现通信录管理的操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出6个菜单项的内容和输入提示，如下：1.一个功能函数对ASCII码的初始化并需要一个数组来保存它们；2.定义代表森林的数组，在创建哈夫曼树的过程当中保存被选中的字符，即给定报文中出现的字符,模拟哈夫曼树选取和删除左右子树的过程；1.自底而上地创建哈夫曼树，保存根的地址和每个叶节点的地址，即字符的地址，然后自底而上检索，首尾对换调整为哈夫曼树实现哈弗曼编

4、码；2.从哈弗曼编码文件当中读入字符，根据当前字符为0或者1的状况访问左子树或者右孩子，实现解码；3.使用文件读写操作哈夫曼编码和解码结果的写入；（二）程序模块结构由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：(1)intmain()主函数：利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入）对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。(2)Encodi

5、ng编码功能：对输入字符进行编码(3)、Decoding译码功能：利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat中。（三）函数调用关系程序的主要结构（函数调用关系）如下图所示。Main()decodingencodingquit其中main()是主函数，它进行菜单驱动，根据选择项0~5调用相应的函数。main()函数使用for循环实现重复选择。其循环结构如下：intmain(){charcode[100],h[100],hl[100];intn,i,j,k,l;ifstreaminput_file;//文件输入输

6、出流ofstreamoutput_file;charchoice,str[100];hfmtreeHT;hfmcodeHC;cout<<"";cout<<""<<"计算机（3）班"<<""<<"Q07620307"<<""<<"XXX";while(choice!='Q'&&choice!='q')//当choice的值不为q且不为Q时循环{cout<<""<<"*************************赫夫曼编码/译码器*************************";cout<<""<<"I.Init"<<""<<"E.Encoding"<<

7、""<<"D.Decoding"<<""<<"Q.Exit";cout<<"请输入您要操作的步骤：";cin>>choice;if(choice=='I'

8、

9、choice=='i')//初始化赫夫曼树{cout<<"请输入字符个数：";cin>>n;hfmcoding(HT,HC,n);for(i=1;i<=n;++i){cout<