应用数据结构课程方案(哈夫曼树)

学号：

个人资料整理 仅限学习使用0120803490117课程设计题目Huffman编／译码器学院管理学院专业信息管理与信息系统班级0801姓名王涛指导教师燕翔2018 年 07 月 09 日个人资料整理 仅限学习使用课程设计任务书学生姓名：

王涛

专业班级：

信管

0801指导教师：

燕翔

工作单位：

管理学院题 目：

Huffman编／译码器初始条件：利用Huffman编码进行通信可以大大提高信道利用率．缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码<复原）。对于双工信道 <即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。试为这样的信息收发站写一个Huffman码的编／译码系统。要求完成的主要任务 :<包括课程设计工作量及其技术要求、说明书撰写等具体要求）一个完整的系统应具有以下功能：<l）I：初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。<2）E：编码。利用已建好的Huffman树<如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。<3）D：译码。利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。<4）P：印代码文件。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。<5）T：印哈夫曼树。将已在内存中的哈夫曼树以直观的方式<树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。时间安排：序号设计内容所用时间1问题分析和任务定义0.5天2数据类型和系统设计0.5天3编码实现和静态检查3天4上机准备和上机调试2天5总结和整理设计报告1天合计7天指导教师签名：2018年07月02日系主任<或责任教师）签名：2018年07月02日个人资料整理 仅限学习使用需求分析1.1 程序的任务：利用Huffman编码进行通信可以大大提高信道利用率．缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码<复原）。对于双工信道 <即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。此程序就是为这样的信息收发站写一个Huffman码的编／译码系统。1.2 程序的输入和输出：从终端读入字符集大小 n，以及n个字符及各个字符的权值，建立赫夫曼树，并将它存储到文件hfmTree中；利用已建好的赫夫曼树将文件中的字符编码，如果赫夫曼树不在内存中，则从文件hfmTree中读取到内存；将译得的代码存到文件CodeFile中；利用已建好的赫夫曼树对CodeFile中的代码进行译码，将结果存入文件TextFile中；最后将已在内存中的哈夫曼树以直观的方式<树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。1.3 程序要达到的功能：用户可以利用菜单根据自己的需要来选择要进行编码或是译码 ,并将转换好的字符或编码以文件的形式存到相应的文件里面。1.4 测试数据如下表：<l）利用教材中的数据调试程序。<2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报字符

文的编码和译码："THISPROGRAMISMYFAVORITE"。A B C D E F GHI JKL MN OPQR

S T

UVWXYZ频度1866413223210321154757

153220576315 1485180238181161选择E，输入THISPROGRAMISMYFAVORITE，屏幕上显示1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010同时文件codefile 里面也出现相应的代码选择D，从codefile 中调入代码，终端显示 THISPROGRAMISMYFAVORITE，并且文件textfile 中也相应的存入了这段话。个人资料整理 仅限学习使用选择P，文件CodeFile以紧凑格式显示在终端上。选择T，将已在内存中的哈夫曼树以直观的方式 <树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。选择其他的字母，将出现出错提示，并重新回到选择菜单。概要设计ADTBinaryTree{数据对象D：D是具有相同特性的数据元素集合。数据关系R：若D为空，则R为空，称Huffmantree为空霍夫曼树；若D不为空，则R={H}，H是如下的二元关系：1、H满足二叉树的所有要求；2、H中所有数乘以该数所在节点的深度值之后和最小。基本操作P：InputHuffman(HuffmanHfm>操作结果：输入并存储字符和相应权值。Select(HuffmanTreeHT,intend,int*s1,int*s2>初始条件：频率数组已经建立。操作结果：选择 HT[1....i-1] 中无双亲且权值最小的两个节点，其序号为s1，s2。HuffmanCoding(HuffmanHfm>初始条件：频率数组已经建立。操作结果：w存放n个字符的权值<均>0），构造赫夫曼树HT，并求出n个字符的构造赫夫曼编码HC。InitHuffman(HuffmanHfm>初始条件：频率数组已经建立。操作结果：要求用户输入字符和相应权值，初始化赫夫曼数Encoding(HuffmanHfm>初始条件：霍夫曼树 HuffmanTree已经存在。操作结果：利用已建好的 Huffman树<如不在内存，则从文件 hfmTree个人资料整理 仅限学习使用中读入），对文件 ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。Decoding(HuffmanHfm>初始条件：霍夫曼树 HuffmanTree已经存在。操作结果：利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。Print(HuffmanHfm>初始条件：霍夫曼树 HoffmanTree已经存在。操作结果：将文件CodeFile以紧凑格式显示在终端上，每行50个代码。Treeprint(HuffmanHfm>初始条件：霍夫曼树 HuffmanTree已经存在。操作结果：将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。}ADTHuffmanTree2主程序流程Voidmain(>{显示菜单；Switch(k>{：初始化E：编码D：译码P：印代码文件T：印哈夫曼树Q：退出运行}}个人资料整理 仅限学习使用2.3 程序调用模块Main函数InitHuffman Encoding Decoding Print Treeprint Quit详细设计3.1数据类型：typedefchar**HuffmanCode 。//typedefstruct{unsignedint weight 。unsignedint parent,lchild,rchild

动态分配数组存储霍夫曼表码表。}HTNode,*HuffmanTree。//动态分配数组存储霍夫曼树typedefstruct{HuffmanTreeHT 。char *c 。int length 。HuffmanCodeHC。}Huffman。//分配数组存储字符串及其对应的霍夫曼树HuffmanHfm。chark。/*控制循环的标志*/3.2 伪码算法：主程序main(>{InitHuffman(HuffmanHfm> ；Encoding(HuffmanHfm>；Decoding(HuffmanHfm>；Print(HuffmanHfm> ；Treeprint(HuffmanHfm> ；}其他模块：个人资料整理 仅限学习使用voidSelect(HuffmanTreeHT,intend,int*s1,int*s2> //选择 HT[1....i-1] 中无双亲且权值最小的两个节点，其序号为 s1，s2FOR(i=1。i<=end。i++>{IF(HT[i].parent 是最小的>THENHT[i].parent ——>*s1IF(HT[i].parent 是次最小的>THENHT[i].parent ——>*s2}HuffmanHuffmanCoding(HuffmanHfm>//w存放n个字符的权值<均〉0），构造赫夫曼树HT，并求出n个字符的构造赫夫曼编码HC{FOR(i=n+1。i<=2*n-1。++i>// 选择HT[1....i-1] 中无双亲且权值最小的两个节点，其序号为s1，s2{Select(Hfm.HT,i-1,&s1,&s2> 。修改父亲位置；修改孩子位置；父亲结点权值为左右孩子权值之和；}从叶子结点到根逆向求每个字符的赫夫曼编码FOR(i=1。i<=n。++i>逐个字符求赫夫曼编码{start=n-1。//编码结束符位置for(c=i,f=Hfm.HT[i].parent。f!=0。c=f,f=Hfm.HT[f].parent>//从叶子到根逆向求编码{IF(c==Hfm.HT[f].lchild>cd[--start]='0' 。ELSEcd[--start]='1' 。}再从cd复制编码到Hfm.HC}RETURNHfm。}HuffmanInitHuffman(HuffmanHfm> //初始化赫夫曼数，要求用户输入字符和相应权个人资料整理 仅限学习使用值{对文件hfmTree以读文本的形式打开IF(fp==NULL>调用

InputHuffman

函数，用户输入字符和相应权值存入赫夫曼数中ELSE输出"TheHuffmantreehasalreadyexisted!\nPleasechooseagain!\n\n">读入hfmTree中文本FOR(i=1。i<=n。i++>

。作为独立结点对结点的

parent

，lchild

，rchild

分别赋值

0FOR(。i<=2*n-1。++i>作为独立结点对结点的

weight

，parent

，lchild

，rchild

分别赋值

0Hfm=HuffmanCoding(Hfm>。RETURNHfm。}voidEncoding(HuffmanHfm>

//利用已建好的

Huffman

树<如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。{输出"\n\n*******************Encoding**************************\n\n"IF((ffp=fopen("ToBeTran","rt">>==NULL>提示输入"Pleaseinputthesentence:"scanf("%s",ch> 。printf("\n"> 。以写文本的形式打开 CodeFileELSE读入ToBeTran文件中的字符。WHILE(ch[j]>FOR(i=1。i<=n。i++>IF(ch[j]==Hfm.c[i]>分别在终端和文件 CodeFile输入Hfm.HC[i]voidDecoding(HuffmanHfm>//利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。{ 定义chard[500]输出"\n\n******************Decoding************************\n\n"IF((fp=fopen("CodeFile","rt">>==NULL>输出Pleaseinputthecode: 。ELSE将文件Codefile 中的内容读到d数组中输出Thefileis:以写文本的方式打开 TextFileWHILE(d[j]>根到叶子结点遍历，并按照 lchild ——>0，rchild ——>1来输出个人资料整理 仅限学习使用入到文件TextFile 中关闭文件}voidPrint(HuffmanHfm> //将文件 CodeFile 以紧凑格式，示在终端上，每行 50个代码。{FOR(i=1。i<=n。i++>输出Hfm.c[i]输出Hfm.HT[i].weight以只读二进制的方式打开 CodeFile文件while(feof(fprint>==0>逐个输出IF(m%50==0>输出"\n"关闭文件}voidTreeprint(HuffmanHfm> //将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件

TreePrint

中。{打开hfmTree文件将字符及其对应的代码赋给变量输出Hfm.c[i] ，对Hfm.c[i][j]

Hfm.c[i] 和Hfm.c[i][j]进行判断，不是\n则输出*，否则停止输出}3.3函数调用关系图InitHuffman(HuffmanHfm>初始化Select< ） 供InputHuffman(HuffmanHfm>HuffmanCoding(>接收数据调用调 用HuffmanCoding(>构造哈夫曼树编 码 调Encoding(>

用

译 码 调 用Decoding<）

打 印Print(>

编 码

打印哈夫曼树Treeprint(>个人资料整理 仅限学习使用调试分析4.1 调试过程中遇到的问题：第一个问题是一直比较棘手的问题就是文件的调用与写入，因为文件方面的知识一直就掌握的不是很好，在写代码时产生很大困难，所以在解决这个问题的时候我把文件部分系统的看了一下，这才从自身角度解决了这个问题。而实际中遇到的问题就是如何判断已经有了hfmtree这个文件，并且怎么调用到内存中来。解决方案：设置一个全局结构体变量来存放已经在文件中存放的霍夫曼树。第二个问题是关于界面的美观设计方面，因为很多代码在文本中编辑时是比较整齐美观的，但是在程序运行中却出现很多问题，不对齐等等。还有就是换行符的使用，一不小心就会产生偏差。解决方案：进入程序进行调试，检查每段输出代码的显示。第三个问题是Huffman树的打印，方式为凹入式打印，由于在当时学习的时候这部分内容没有留意，根本没有概念，所以在编写程序过程中出现了严重的问题。导致该项功能无法完成。解决方案：尚未完善解决，只是将内存中的哈夫曼树中各节点的值及其孩子输出。4.2 算法的时空分析：算法的时间复杂度：Select(HuffmanTreeHT,intend,int*s1,int*s2> O(n>HuffmanCoding(HuffmanHfm>O(n2>InputHuffman(HuffmanHfm>O(n>InitHuffman(HuffmanHfm>O(n>Encoding(HuffmanHfm>O(n>Decoding(HuffmanHfm>O(n>Print(HuffmanHfm>O(n>4.3 经验与体会：整个程序在编的时候思路是很明朗的，包括菜单的设置都是很清晰的，但是如何通过一个菜单将所有涉及到的文件与终端联系起来还有打印哈夫曼树都是比较困难的问题，由于文件这一章节我们以前学习的时候并没有很重视，所以在运用的时候遇到了很大的困难，同时通过这次的设计我也看到其实文件这一章是很重要的，我们做了一个程序，必须要把有些必要的数据进行保存，如果只是停留在内存中那就很难在以后个人资料整理 仅限学习使用被重复利用，会很大程度上提高我们调试的效率；另外凹入式打印哈夫曼树更是让我头疼了一整天的问题，由于根本不知道其概念是什么，更不用说去编写代码了。同时我也觉得有些细节问题是很重要的，不管是一个整型变量还是一个结构体变量，有时候对整个程序起着至关重要的作用。用户使用说明1．本程序的运行环境为 DOS操作系统，执行文件为： hfmtree.exe。运行程序后出现选择菜单。3．根据提示选择相应的操作，初始化，编码，译码，印代码文件，印哈夫曼树退出，每次选择完，都会再次弹出选择菜单供用户选择。结束符为回车键。测试结果在进入系统以后，选择第一个初始化，按要求键入要求的字符及其频度字符— A B C D E F GH I JKL MN OP QR S T U VWXY Z频度18664132232103211547571532205763151485180238181161截图如下所示：图1进入程序，显示的菜单界面个人资料整理 仅限学习使用图2输入I，选择进行初始化图3初始化时对字符的个数进行限制，不得少于 2个。个人资料整理 仅限学习使用图4、5在字符个数处输入“27”，之后依次输入各字符及其权值。图6在菜单界面选择E，出现提示语句，要求输入句子。图7输入“THIS_PROGRAM_IS_MY_FAVORITE”，回车之后，显示出该句的哈夫曼编码。<此处为求简捷，将空格用下划线“_”作为代替）个人资料整理 仅限学习使用图8在菜单界面选择 D，则对文件中已有的哈夫曼编码进行反译，将译出的字符显示出来。图9在菜单界面选择P，将文件中的哈夫曼编码紧凑输出，每行 50个。结果如下图：个人资料整理 仅限学习使用图10、11该程序中，我加入了将初始化的各字符的编码输出的语句，可以看到各个字符的哈弗曼编码。图12这3行数字便是紧凑输出哈夫曼编码的结果。图13同时，不同的人使用本程序进行不同的哈夫曼编码时，由于前一位使用者初始化的数据后一位不一定同样适用，为了避免这种情况，因此当已经初始化后再进行初始化时会出现提示是否重新初始化的信息提示，如上图所示。个人资料整理 仅限学习使用图14在菜单界面选择T，打印处内存中的哈夫曼树各节点的值及其双亲节点和子节点。图15TEXTFILE.TXT文本文件，记录用户输入的需要进行编码的句子。图16CODEFILE.TXT文本文件，记录 TEXTFILE.TXT文本文件中字符的哈弗曼编码。图17HFMTREE.TXT文本文件，记录输入的各字符及其权值个人资料整理 仅限学习使用附录源程序文件名清单：TEXTFILE.TXTCODEFILE.TXTHFMTREE.TXT

记录待编码的句子记录哈夫曼编码记录字符个数、名称及权值源代码：#include<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>#include<ctype.h>#defineNULL0#defineOK1#defineERROR0#defineOVERFLOW-2#defineMAX_NUM32767#defineMAX60个人资料整理 仅限学习使用typedefchar**HuffmanCode 。//动态分配数组存储哈夫曼表码表typedefstruct{unsignedint weight 。unsignedint parent,lchild,rchild 。}HTNode,*HuffmanTree。//动态分配数组存储哈夫曼树typedefstruct{HuffmanTreeHT 。char *c 。int length 。HuffmanCodeHC。}Huffman。//全局结构体变量，来存储字符与代码voidSelect(HuffmanTreeHT,intend,int*s1,int*s2>// 选择HT[1....i-1] 中无双亲且权值最小的两个节点，其序号为 s1，s2{inti 。intmin1=MAX_NUM。intmin2 。for(i=1 。i<=end。i++>//遍历查找权值最小的结点 S1个人资料整理 仅限学习使用{if(HT[i].parent==0&&HT[i].weight<min1>{*s1=i 。min1=HT[i].weight 。}}min2=MAX_NUM。for(i=1 。i<=end。i++>//遍历查找除S1外权值最小的结点 S2{if(HT[i].parent==0&&(*s1!=i>&&min2>HT[i].weight>{*s2=i 。min2=HT[i].weight 。}}}个人资料整理 仅限学习使用HuffmanHuffmanCoding(HuffmanHfm>//存放n个字符的权值<均〉0），构造哈夫曼树HT，并求出n个字符的构造哈夫曼编码HC{inti,n,m,s1,s2,start 。intc,f 。char*cd 。n=Hfm.length 。if(n<=1>returnHfm 。m=2*n-1。for(i=n+1 。i<=m。++i>// 选择HT[1....i-1] 中无双亲且权值最小的两个节点，其序号为s1，s2{Select(Hfm.HT,i-1,&s1,&s2> 。Hfm.HT[s1].parent=i 。//修改父亲位置Hfm.HT[s2].parent=i 。Hfm.HT[i].lchild=s1 。//修改孩子位置Hfm.HT[i].rchild=s2 。Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight 。//父亲结点权值为左右孩子权值之和}从叶子结点到根逆向求每个字符的哈夫曼编码个人资料整理 仅限学习使用Hfm.HC=(HuffmanCode>malloc((n+1>*sizeof(char*>> 。//分配n个字符编码的头指针向量cd=(char*>malloc(n*sizeof(char>> 。//分配求编码的工作空间cd[n-1]='\0' 。//编码结束符for(i=1 。i<=n。++i>//逐个字符求哈夫曼编码{start=n-1 。//编码结束符位置for(c=i,f=Hfm.HT[i].parent 。f!=0。c=f,f=Hfm.HT[f].parent>// 从叶子到根逆向求编码{if(c==Hfm.HT[f].lchild>cd[--start]='0' 。elsecd[--start]='1' 。}Hfm.HC[i]=(char*>malloc((n-start>*sizeof(char>> 。strcpy(Hfm.HC[i],&cd[start]> 。//从cd复制编码到Hfm.HC}free(cd> 。//释放工作空间returnHfm 。}个人资料整理 仅限学习使用HuffmanInputHuffman(HuffmanHfm>// 输入函数，控制用户输入字符和相应权值{inti,n 。printf("\n\n********************Initialization*********************\n"> 。printf("Thecharsandweightswillbesavedinthefile:\hfmTree\\n">。printf("Pleaseinputthenumberofthechars:"> 。scanf("%d",&n> 。if(n<=1>{printf("OnlyOneChar!ThereIsNoNeedForCoding!"> 。//若只有一个数值则无需编码printf("\n"> 。printf("Pleaseinputthenumberofthechars:"> 。scanf("%d",&n> 。}Hfm.HT=(HuffmanTree>malloc((2*n>*sizeof(HTNode>> 。Hfm.c=(char*>malloc((n+1>*sizeof(char>> 。for(i=1 。i<=n。i++>{printf("Pleaseinputthechar:"> 。scanf("%s",&Hfm.c[i]> 。个人资料整理 仅限学习使用printf("Pleaseinputtheweightofthechar:"> 。scanf("%d",&Hfm.HT[i].weight> 。Hfm.HT[i].parent=0 。Hfm.HT[i].lchild=0 。Hfm.HT[i].rchild=0 。}for( 。i<=2*n-1。++i>{Hfm.HT[i].weight=0 。Hfm.HT[i].parent=0 。Hfm.HT[i].lchild=0 。Hfm.HT[i].rchild=0 。}Hfm.length=n 。returnHfm 。}HuffmanInitHuffman(HuffmanHfm>// 初始化哈夫曼数，要求用户输入字符和相应权值个人资料整理 仅限学习使用{intn,i,x 。FILE*fp 。fp=fopen("hfmTree","rt"> 。//对文件hfmTree以读文本的形式打开if(fp==NULL>{Hfm=InputHuffman(Hfm>。//调用InputHuffman函数，用户输入字符和相应权值存入哈夫曼数中fp=fopen("hfmTree","wt"> 。fprintf(fp,"%d\n",Hfm.length> 。for(i=1 。i<=Hfm.length 。i++>fprintf(fp,"%c%d",Hfm.c[i],Hfm.HT[i].weight> 。rewind(fp> 。}else{printf("TheHuffmantreehasalreadyexisted!\nDoYouWantToMakeANewOne?('Y'or'N'>\n\n">。//询问是否重新初始化scanf("%s",&x> 。if(x=='Y'>{Hfm=InputHuffman(Hfm>。//调用InputHuffman函数，用户输入字符和相应权值存入哈弗曼数中fp=fopen("hfmTree","w+"> 。个人资料整理 仅限学习使用fprintf(fp,"%d\n",Hfm.length> 。for(i=1 。i<=Hfm.length 。i++>fprintf(fp,"%c%d",Hfm.c[i