数据结构课程设计报告--赫夫曼编码译码器讲解

1、赫夫曼编码译码器专 业 班 级 ：网络工程13-2班学 号 ：03,15,20姓 名 ：陈希，李陇钢，陆峰指 导 教 师 ：姜卓课程设计时间：2014.6.29-7.3目录任务书 -3一需求分析-4 二实验目的-5三运行环境-6四开发工具和编程语言-8六程序清单-9七调试分析-288 测试结果-299 参考文献-33十课程设计总结-33网络工程专业 数据结构 课程设计任务书学生姓名陈希、李陇钢、陆峰专业班级网络13-2学号03、15、20题 目哈弗曼编码译码器课题性质工程设计课题来源数据结构实验与课程设计指导教师姜卓同组姓名李陇钢，陆峰主要内容 设计一个哈弗曼编码译码器，实现赫夫曼树的建立，树

2、形输出，编码和解码。任务要求1研究哈弗曼树的数据存储方式2实现哈弗曼编码译码器的主要算法3分析算法的运行效率4具有良好的运行界面5算法具有良好的健壮性6按要求撰写课程设计报告和设计总结。参考文献1数据结构（C语言版），严蔚敏、吴伟民，清华大学出版社，1997.审查意见指导教师签字： 教研室主任签字： 年 月 日 一、需求分析 设计一个哈弗曼编码译码器，实现赫夫曼树的建立，树形输出，编码和解码。 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非

3、数值处理的计算机程序打下坚实的理论、方法和技术基础。 算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示

4、，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。二、实验目的 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常

5、，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。 在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。 数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、

6、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软

7、件开发，培养软件工作者所应具备的科学的工作方法和作风。3、 概要设计（1).小组分工小组成员分工内容陈希（组长）功能1(建立赫夫曼树）、功能4（赫夫曼文件编码）、功能5（赫夫曼文件编码解码）、使得子函数在主函数里被调用使设计成型。李陇钢功能2（查看赫夫曼编码）、将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)。陆峰功能3（树形输出赫夫曼树）、将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)。main(2)流程图 退出系统帮助 赫夫曼文件解码 赫夫曼文件编码 树形输出赫夫曼树查看赫夫曼编码建立赫夫曼树 四、运行环境（软、硬件环境）1)

8、硬件：PC机2) 操作系统：Windows 2000/XP/20033) 编译环境：Visual C+6.0五、开发工具和编程语言开发工具：VISCALL c+6.0；编程语言：C语言。六、程序清单#include #include#includeint Number=0;typedef struct / 结点的结构 unsigned int weight; / 结点的权值unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; / 动态分配数组存储赫夫曼树typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码H

9、uffmanTree HT;HuffmanCode HC;int n=26;const char menu=|1 建立赫夫曼树 |n|2 查看赫夫曼编码 |n|3 树形输出赫夫曼树 |n|4 赫夫曼文件编码 |n|5 赫夫曼文件解码 |n|6 帮助 |n|7 退出系统 |n;const char helpsabout=|主要功能: |n | 利用赫夫曼编码进行通信可以大大提高信道的利用率，缩短信息的传输时间，降低 |n|传输成本。但是，这要求在发送端通过一个编码系统对待传输的数据预先编码，在接收 |n|端将传来的数据进行译码（复原）。对于双工信道，每端都要有一个完整的编/译码系 |n|统。本系

10、统即是为这样的信息收发站写一个赫夫曼码的编/译系统。 |n|网络13-2班 陈希、李陇钢、陆峰制作 学号：03、15、20 |n| |n; void Huffmantree(); void Huffmancode(); void preorder(); void stringcopy(); int min(); void select(); void decode(); void encode(); void int_huffmantree(); void print_end(); void print_title(); void print_menu(); void print_helpab

11、out(); void print_huffmancode(); void print_tree();/-先序遍历-void preorder(int root,int depth)int i;for(i=1;i=depth;i+)printf( );if(depth!=0)printf();elseprintf( );printf(%d,HTroot.weight);if(root=n)printf( : %sn,HCroot); / 依次输出赫夫曼编码elseprintf(n);if(HTroot.lchild!=0)depth+;preorder(HTroot.lchild,depth)

12、;/递归if(HTroot.rchild!=0)preorder(HTroot.rchild,depth);/-字符串拷贝函数-void stringcopy(char *strDest,char *strSrc) char *strDestCopy=strDest; if (!(strDest&strSrc) printf(ERROR!); while (*strDest+=*strSrc+)!=0); /-返回赫夫曼树t的前i个结点中权值最小的树的根结点序号，函数select()调用- int min(HuffmanTree t,int i) int j,m; unsigned int k

13、=0xffffffff; / k存最小权值，初值取为不小于可能的值 for(j=1;j=i;j+) / 对于前i个结点 if(tj.weights2) / s1的序号大于s2的 / 交换 j=s1; s1=s2; / s1是权值最小的2个中序号较小的 s2=j; / s2是权值最小的2个中序号较小的 /-w存放n个字符的权值(均0)，构造赫夫曼树HT- void Huffmantree(int *w) /*文件保存*/ FILE *fp=NULL;/*保存权值数据*/ char save20=data.txt; fp=fopen(save,w); for(int i=0;in;i+) fpri

14、ntf(fp,%d ,*(w+i); fclose(fp);/*文件保存*/ int m,i,s1,s2; HuffmanTree p; if(n=1) / 叶子结点数不大于n return ; m=2*n-1; / n个叶子结点的赫夫曼树共有m个结点 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1;i=n;+i,+p,+w) / 从1号单元开始到n号单元，给叶子结点赋值 / p的初值指向1号单元 (*p).weight=*w; / 赋权值 (*p).parent=0; / 双亲域为空(是根结点) (*p)

15、.lchild=0; / 左右孩子为空(是叶子结点，即单结点树) (*p).rchild=0; for(;i=m;+i,+p) / i从n+1到m (*p).parent=0; / 其余结点的双亲域初值为0 for(i=n+1;i=m;+i) / 建赫夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; / i号单元是s1和s2的双亲 HTi.lchild=s1; / i号单元的左右孩子分别是s1和s2 HTi.rchild=s2; HTi.weig

16、ht=HTs1.weight+HTs2.weight; / i号单元的权值是s1和s2的权值之和 /-并求出n个字符的赫夫曼编码HC-void Huffmancode() int start; unsigned int f; int i; unsigned int c; char *cd; 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; /

17、编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 从叶子到根逆向求编码 if(HTf.lchild=c) / c是其双亲的左孩子 cd-start=0; / 由叶子向根赋值0 else / c是其双亲的右孩子 cd-start=1; / 由叶子向根赋值1 HCi=(char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 stringcopy(HCi,&cdstart); / 从cd复制编码串到HC矩阵 free(cd); / 释放工作空间/-译码- void encode() FILE *f

18、p1=NULL,*fp2=NULL;char input20=input.txt,output20=output.txt;printf(请输入输入文件名(input.txt)：);scanf(%s,input);if (fp1=fopen(input,r)=NULL)printf(无此文件！);getchar();getchar();return ;printf(请输入输出文件名(output.txt)：);scanf(%s,output);if(fp2=fopen(output,w)=NULL)printf(不能创建文件！);getchar();getchar();return ;int i

19、,k;unsigned int *w,p,m=0,j;for(k=0;!feof(fp1);k+)/读文件fp1里面的字符，如果没有读完，则返回0.否则返回1if(fgetc(fp1)= )m+;printf(赫夫曼编码为:);fp1=fopen(input,r); w=(unsigned int*)malloc(m*sizeof(unsigned int); / 动态生成存放m个权值的空间 for(j=0;j=m-1;j+)/ fscanf(fp1,%d,w+j); / 依次输入原码*(w+j)=fgetc(fp1);for(p=0;pm;p+) for(i=0;in;i+) if(*(w+

20、p)=HTi+1.weight) fprintf(fp2,%s,HCi+1); printf(%s,HCi+1); fclose(fp1); fclose(fp2);printf(n输出完成.按任意键继续.);getchar();getchar(); /-解码-void decode()FILE *fp1=NULL,*fp2=NULL;char input20,output20;char *code;code=(char*)malloc(n*sizeof(char);printf(请输入输入文件名(input.txt)：);scanf(%s,input);if (fp1=fopen(input

21、,r)=NULL)printf(无此文件！);getchar();getchar();return ;printf(请输入输出文件名(output.txt)：);scanf(%s,output);if(fp2=fopen(output,w)=NULL)printf(不能创建文件！);getchar();getchar();return ;int i,j;printf(赫夫曼译码为:);for(i=0;!feof(fp1);i+)*(code+i)=fgetc(fp1);/读取字符100111. *(code+i+1)=0;for(j=0;j1)：);scanf(%d,&n);w=(int*)m

22、alloc(n*sizeof(int); / 动态生成存放n个权值的空间printf(请依次输入%d个权值(整型)：n,n);for(i=0;in;i+)scanf(%d,w+i); Huffmantree(w); / 根据w所存的n个权值构造赫夫曼树HT，Huffmancode(); /n个赫夫曼编码存于HCprint_end();printf(赫夫曼编码为：n);for(i=1;i=n;i+)printf(%5d: %sn,*(w+i-1),HCi);print_end();printf(按任意键返回.);getchar();getchar();/-赫夫曼编码菜单-void print_h

23、uffmancode()int i;system(cls);print_title(); printf(赫夫曼编码为：n); for(i=1;i请选择17);scanf(%d,&selected);if(selected7)printf(错误的选择！（请输入17）.按任意键继续.);getchar();getchar();switch(selected)case 1:int_huffmantree();break;case 2:print_huffmancode();break;case 3:print_tree();break;case 4:encode();break;case 5:decode();break;case 6:print_helpabout();break;case 7:exit(0);break;void print_title() printf(+=+n); printf(| 赫夫曼编码译码器 |n); printf(| Designed By chenxi |n); pri