应用数据结构课程设计(哈夫曼树).docx

课 程 设 计题 目huffman编译码器学 院管理学院专 业信息管理与信息系统班 级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天指导教师签名： 2010年 07月02日系主任（或责任教师）签名： 2010年 07月02日1. 需求分析1.1 程序的任务：利用huffman编码进行通信可以大大提高信道利用率缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编译码系统。此程序就是为这样的信息收发站写一个huffman码的编译码系统。1.2 程序的输入和输出：从终端读入字符集大小n，以及n个字符及各个字符的权值，建立赫夫曼树，并将它存储到文件hfmtree中；利用已建好的赫夫曼树将文件中的字符编码，如果赫夫曼树不在内存中，则从文件hfmtree中读取到内存；将译得的代码存到文件codefile中；利用已建好的赫夫曼树对codefile中的代码进行译码，将结果存入文件textfile中；最后将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。1.3 程序要达到的功能：用户可以利用菜单根据自己的需要来选择要进行编码或是译码,并将转换好的字符或编码以文件的形式存到相应的文件里面。1.4 测试数据如下表：（l）利用教材中的数据调试程序。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：this program is my favorite。字符 abcdefghijklmnopqrstuvwxyz频度18664132232103211547571532205763151485180238181161 选择e，输入this program is my favorite，屏幕上显示1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010同时文件codefile里面也出现相应的代码选择d，从codefile中调入代码，终端显示this program is my favorite，并且文件textfile中也相应的存入了这段话。选择p，文件codefile以紧凑格式显示在终端上。选择t，将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。选择其他的字母，将出现出错提示，并重新回到选择菜单。2. 概要设计adt binarytree数据对象d：d是具有相同特性的数据元素集合。数据关系r：若d为空，则r为空，称huffmantree为空霍夫曼树； 若d不为空，则r=h，h是如下的二元关系：1、 h满足二叉树的所有要求；2、 h中所有数乘以该数所在节点的深度值之后和最小。基本操作p： inputhuffman(huffman hfm) 操作结果：输入并存储字符和相应权值。select(huffmantree ht,int end,int *s1,int *s2)初始条件：频率数组已经建立。操作结果：选择ht1.i-1中无双亲且权值最小的两个节点，其序号为s1，s2。huffmancoding(huffman hfm)初始条件：频率数组已经建立。操作结果：w存放n个字符的权值（均0），构造赫夫曼树ht，并求出n个字符的构造赫夫曼编码hc。 inithuffman(huffman hfm) 初始条件：频率数组已经建立。 操作结果：要求用户输入字符和相应权值，初始化赫夫曼数 encoding(huffman hfm) 初始条件：霍夫曼树huffmantree已经存在。 操作结果：利用已建好的huffman树（如不在内存，则从文件hfmtree中读入），对文件tobetran中的正文进行编码，然后将结果存入文件codefile中。 decoding(huffman hfm) 初始条件：霍夫曼树huffmantree已经存在。 操作结果：利用已建好的huffman树将文件codefile中的代码进行译码，结果存入文件textfile中。 print(huffman hfm) 初始条件：霍夫曼树hoffmantree已经存在。 操作结果：将文件codefile以紧凑格式显示在终端上，每行50 个代码。 treeprint(huffman hfm) 初始条件：霍夫曼树huffmantree已经存在。 操作结果：将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。adt huffmantree2. 2 主程序流程void main() 显示菜单； switch(k) i：初始化e：编码d：译码p：印代码文件t：印哈夫曼树q：退出运行 2.3 程序调用模块3. 详细设计3.1数据类型： typedef char *huffmancode;/动态分配数组存储霍夫曼表码表typedef struct unsigned int weight; unsigned int parent,lchild,rchild;htnode,*huffmantree;/动态分配数组存储霍夫曼树typedef struct huffmantree ht; char *c; int length; huffmancode hc;huffman;/分配数组存储字符串及其对应的霍夫曼树huffman hfm;char k; /*控制循环的标志*/3.2 伪码算法：主程序main()inithuffman(huffman hfm)；encoding(huffman hfm)；decoding(huffman hfm)；print(huffman hfm)；treeprint(huffman hfm)；其他模块：void select(huffmantree ht,int end,int *s1,int *s2)/选择ht1.i-1中无双亲且权值最小的两个节点，其序号为s1，s2 for (i=1;i*s1 if(hti.parent是次最小的) then hti.parent*s2 huffman huffmancoding(huffman hfm) /w存放n个字符的权值（均0），构造赫夫曼树ht，并求出n个字符的构造赫夫曼编码hc for(i=n+1;i=2*n-1;+i) /选择ht1.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.hti.parent;f!=0;c=f,f=hfm.htf.parent)/从叶子到根逆向求编码 if(c=hfm.htf.lchild) cd-start=0; else cd-start=1; 再从cd复制编码到hfm.hc return hfm;huffman inithuffman(huffman hfm)/初始化赫夫曼数，要求用户输入字符和相应权值 对文件hfmtree以读文本的形式打开 if(fp=null) 调用inputhuffman函数，用户输入字符和相应权值存入赫夫曼数中 else输出the huffmantree has already existed!nplease choose again!nn);读入hfmtree中文本 for(i=1;i=n;i+) 作为独立结点对结点的parent，lchild，rchild分别赋值0for(;i=2*n-1;+i) 作为独立结点对结点的weight，parent，lchild，rchild分别赋值0 hfm=huffmancoding(hfm); return hfm;void encoding(huffman hfm)/利用已建好的huffman树（如不在内存，则从文件hfmtree中读入），对文件tobetran中的正文进行编码，然后将结果存入文件codefile中。 输出nn*encoding*nn if(ffp=fopen(tobetran,rt)=null) 提示输入please input the sentence: scanf(%s,ch); printf(n); 以写文本的形式打开codefile else 读入tobetran文件中的字符; while(chj) for(i=1;i0，rchild1来输出 入到文件textfile中 关闭文件void print(huffman hfm)/将文件codefile以紧凑格式，示在终端上，每行50 个代码。 for(i=1;i=n;i+) 输出hfm.ci 输出hfm.hti.weight 以只读二进制的方式打开codefile文件 while ( feof(fprint)=0 ) 逐个输出 if (m%50=0) 输出n 关闭文件void treeprint(huffman hfm)/将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。打开hfmtree文件 将字符及其对应的代码赋给变量hfm.ci和hfm.cij 输出hfm.ci，对hfm.cij进行判断，不是n则输出*，否则停止输出 3.3函数调用关系图inputhuffman(huffman hfm)接收数据select（）供huffmancoding()调用调用huffmancoding()构造哈夫曼树编码调用encoding()译码调用decoding（）打印编码print()打印哈夫曼树treeprint()inithuffman(huffman hfm)初始化4. 调试分析4.1 调试过程中遇到的问题： 第一个问题是一直比较棘手的问题就是文件的调用与写入，因为文件方面的知识一直就掌握的不是很好，在写代码时产生很大困难，所以在解决这个问题的时候我把文件部分系统的看了一下，这才从自身角度解决了这个问题。而实际中遇到的问题就是如何判断已经有了hfmtree这个文件，并且怎么调用到内存中来。解决方案：设置一个全局结构体变量来存放已经在文件中存放的霍夫曼树。第二个问题是关于界面的美观设计方面，因为很多代码在文本中编辑时是比较整齐美观的，但是在程序运行中却出现很多问题，不对齐等等。还有就是换行符的使用，一不小心就会产生偏差。解决方案：进入程序进行调试，检查每段输出代码的显示。第三个问题是huffman树的打印，方式为凹入式打印，由于在当时学习的时候这部分内容没有留意，根本没有概念，所以在编写程序过程中出现了严重的问题。导致该项功能无法完成。解决方案：尚未完善解决，只是将内存中的哈夫曼树中各节点的值及其孩子输出。4.2 算法的时空分析：算法的时间复杂度：select(huffmantree ht,int end,int *s1,int *s2) o(n)huffmancoding(huffman hfm) o(n2)inputhuffman(huffman hfm) o(n)inithuffman(huffman hfm) o(n)encoding(huffman hfm) o(n)decoding(huffman hfm) o(n)print(huffman hfm) o(n)4.3 经验与体会：整个程序在编的时候思路是很明朗的，包括菜单的设置都是很清晰的，但是如何通过一个菜单将所有涉及到的文件与终端联系起来还有打印哈夫曼树都是比较困难的问题，由于文件这一章节我们以前学习的时候并没有很重视，所以在运用的时候遇到了很大的困难，同时通过这次的设计我也看到其实文件这一章是很重要的，我们做了一个程序，必须要把有些必要的数据进行保存，如果只是停留在内存中那就很难在以后被重复利用，会很大程度上提高我们调试的效率；另外凹入式打印哈夫曼树更是让我头疼了一整天的问题，由于根本不知道其概念是什么，更不用说去编写代码了。同时我也觉得有些细节问题是很重要的，不管是一个整型变量还是一个结构体变量，有时候对整个程序起着至关重要的作用。5. 用户使用说明1本程序的运行环境为dos操作系统，执行文件为：hfmtree.exe。2. 运行程序后出现选择菜单。3根据提示选择相应的操作，初始化，编码，译码，印代码文件，印哈夫曼树退出，每次选择完，都会再次弹出选择菜单供用户选择。结束符为回车键。6. 测试结果在进入系统以后，选择第一个初始化，按要求键入要求的字符及其频度字符 abcdefghijklmnopqrstuvwxyz频度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文本文件，记录输入的各字符及其权值7. 附录源程序文件名清单：textfile.txt 记录待编码的句子codefile.txt 记录哈夫曼编码hfmtree.txt 记录字符个数、名称及权值源代码：#include #include #include #include#include#define null 0#define ok 1#define error 0#define overflow -2#define max_num 32767#define max 60typedef char *huffmancode;/动态分配数组存储哈夫曼表码表typedef struct unsigned int weight; unsigned int parent,lchild,rchild;htnode,*huffmantree;/动态分配数组存储哈夫曼树typedef struct huffmantree ht; char *c; int length; huffmancode hc;huffman;/全局结构体变量，来存储字符与代码void select(huffmantree ht,int end,int *s1,int *s2)/选择ht1.i-1中无双亲且权值最小的两个节点，其序号为s1，s2 int i; int min1=max_num; int min2; for (i=1;i=end;i+)/遍历查找权值最小的结点s1 if (hti.parent=0&hti.weightmin1) *s1=i; min1=hti.weight; min2=max_num; for(i=1;ihti.weight) *s2=i; min2=hti.weight; huffman huffmancoding(huffman hfm) /存放n个字符的权值（均0），构造哈夫曼树ht，并求出n个字符的构造哈夫曼编码hc int i,n,m,s1,s2,start; int c,f; char *cd; n=hfm.length; if(n=1) return hfm; m=2*n-1; for(i=n+1;i=m;+i) /选择ht1.i-1中无双亲且权值最小的两个节点，其序号为s1，s2 select(hfm.ht,i-1,&s1,&s2); hfm.hts1.parent=i;/修改父亲位置 hfm.hts2.parent=i; hfm.hti.lchild=s1;/修改孩子位置 hfm.hti.rchild=s2; hfm.hti.weight=hfm.hts1.weight+hfm.hts2.weight;/父亲结点权值为左右孩子权值之和 /从叶子结点到根逆向求每个字符的哈夫曼编码 hfm.hc=(huffmancode)malloc(n+1)*sizeof(char *);/分配n个字符编码的头指针向量 cd=(char *)malloc(n*sizeof(char);/分配求编码的工作空间 cdn-1=0;/编码结束符 for(i=1;i=n;+i)/逐个字符求哈夫曼编码 start=n-1;/编码结束符位置 for(c=i,f=hfm.hti.parent;f!=0;c=f,f=hfm.htf.parent)/从叶子到根逆向求编码 if(c=hfm.htf.lchild) cd-start=0; else cd-start=1; hfm.hci=(char *)malloc(n-start)*sizeof(char); strcpy(hfm.hci,&cdstart);/从cd复制编码到hfm.hc free(cd);/释放工作空间 return hfm;huffman inputhuffman(huffman hfm)/输入函数，控制用户输入字符和相应权值 int i,n; printf(nn*initialization*n); printf(the chars and weights will be saved in the file :hfmtree n); printf(please input the number of the chars: ); scanf(%d,&n); if(n=1) printf(only one char!there is no need for coding!);/若只有一个数值则无需编码 printf(n); printf(please input the number of the chars: ); 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(please input the char: ); scanf(%s,&hfm.ci); printf(please input the weight of the char: ); scanf(%d,&hfm.hti.weight); hfm.hti.parent=0; hfm.hti.lchild=0; hfm.hti.rchild=0; for(;i=2*n-1;+i) hfm.hti.weight=0; hfm.hti.parent=0; hfm.hti.lchild=0; hfm.hti.rchild=0; hfm.length=n; return hfm; huffman inithuffman(huffman hfm)/初始化哈夫曼数，要求用户输入字符和相应权值 int n,i,x; file *fp; fp=fopen(hfmtree,rt);/对文件hfmtree以读文本的形式打开 if(fp=null) hfm=inputhuffman(hfm);/调用inputhuffman函数，用户输入字符和相应权值存入哈夫曼数中 fp=fopen(hfmtree,wt); fprintf(fp,%dn,hfm.length); for(i=1;i=hfm.length;i+) fprintf(fp,%c %d ,hfm.ci,hfm.hti.weight); rewind(fp); else printf(the huffmantree has already existed!ndo you want to make a new one?(yorn)nn);/询问是否重新初始化 scanf(%s,&x); if(x=y) hfm=inputhuffman(hfm);/调用inputhuffman函数，用户输入字符和相应权值存入哈弗曼数中 fp=fopen(hfmtree,w+); fprintf(fp,%dn,hfm.length); for(i=1;i=hfm.length;i+) fprintf(fp,%c %d ,hfm.ci,hfm.hti.weight); rewind(fp); else fscanf(fp,%dn,&n); hfm.c=(char *)malloc(n+1)*sizeof(char); hfm.ht=(huffmantree)malloc(2*n)*sizeof(htnode); for(i=1;i=n;i+) fscanf(fp,%s %d ,&hfm.ci,&hfm.hti.weight);/将已经在文件中的字符和其对应的权重输入到hfm.ci和&hfm.hti.weight中 for(i=1;i=n;i+)/对每个节点初始化 hfm.hti.parent=0; hfm.hti.lchild=0; hfm.hti.rchild=0; for(;i=2*n-1;+i) hfm.hti.weight=0; hfm.hti.parent=0; hfm.hti.lchild=0; hfm.hti.rchild=0; hfm.length=n; fclose(fp); hfm=huffmancoding(hfm); return hfm; void encoding(huffman hfm)/利用已建好的huffman树（如不在内存，则从文件hfmtree中读入），对文件tobetran中的正文进行编码，然后将结果存入文件codefile中。 int i=0,j=0,n; char chmax; file *fp,*fw; n=hfm.length; printf(nn*encoding*nn); if(fw=fopen(tobetran,r+)=null)/尝试打开tobetran printf(nplease input the sentence: ); scanf(%s,ch); printf(n); fp=fopen(codefile,wt+); else fscanf(fw,%s,ch); fclose(fw); while(chj) for(i=1;ilchild|p-rchild) if(dj=0) i=p-lchild; p=&hfm.hti; else i=p-rchild; p=&hfm.hti; j+; printf(%c,hfm.ci); fprintf(fp,%c,hfm.ci); printf(n); fclose(fp);void print(huffman hfm)/将文件codefile以紧凑格式显示在终端上，每行50 个代码。 int i,n; int m=1;/计数器 char ch; file* fprint; n=hfm.length; printf(nn*output the code of the chars*nn); for(i=1;i=n;i+)/显示每一个字符对应的哈夫曼编码 printf(n);