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

《数据结构》 课程设计报告 专 业 计算机科学与技术 班 级 (1) 姓 名 王昕 学 号 20101308003 指导教师 顾韵华 起止时间 2011.10~2011.12 课程设计:赫夫曼编码器 任务描述 （1）建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 （2）“压缩文件”即：读文件、统计文件中的字符个数、对文件进行哈夫曼编码和译码、并将编码译码后的字符存储在文件中。 要求：根据以上说明，设计程序完成功能n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。 (2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。 三、数据结构设计 .哈夫曼树节点的数据类型定义为： typedef struct{ //赫夫曼树的结构体 char ch; int weight; //权值 int parent,lchild,rchild; }htnode,*hfmtree; 四、功能设计 （一）主控菜单设计 为实现通信录管理的操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。 程序运行后，给出6个菜单项的内容和输入提示，如下： 一个功能函数对ASCII码的初始化并需要一个数组来保存它们； 定义代表森林的数组，在创建哈夫曼树的过程当中保存被选中的字符，即给定报文中出现的字符,模拟哈夫曼树选取和删除左右子树的过程； 自底而上地创建哈夫曼树，保存根的地址和每个叶节点的地址，即字符的地址，然后自底而上检索，首尾对换调整为哈夫曼树实现哈弗曼编码； 从哈弗曼编码文件当中读入字符，根据当前字符为0或者1的状况访问左子树或者右孩子，实现解码； 使用文件读写操作哈夫曼编码和解码结果的写入； （二）程序模块结构 由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）： (1) int main() 主函数： 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入） 对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。 (2) Encoding 编码功能：对输入字符进行编码 (3) 、Decoding 译码功能： 利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat 中。 （三）函数调用关系 程序的主要结构（函数调用关系）如下图所示。 其中main()是主函数， int main(){ char code[100],h[100],hl[100]; int n,i,j,k,l; ifstream input_file; //文件输入输出流 ofstream output_file; char choice,str[100]; hfmtree HT; hfmcode HC; cout\n; cout 计算机（3）班 XXX\n; while(choice!=Qchoice!=q) //当choice的值不为q且不为Q时循环 { cout *************************赫夫曼编码/译码器*************************\n; cout I.Init E.Encoding D.Decoding Q.Exit\n; cout请输入您要操作的步骤：; cinchoice; if(choice==I||choice==i)