《数据结构课程设计报告哈夫曼编码器.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告哈夫曼编码器.doc（19页珍藏版）》请在三一办公上搜索。
1、计算机工程学院课程设计报告课程名称：数据结构课程设计设计题目： 哈夫曼编码器 院 系： 计算机工程学院 班 级： 软件1102 组 别： 15 学生姓名: 吴超 学 号: 1101306229 起止日期: 2011 年 12 月 26 日 31 日 目 录 1、设计目的22、需求分析32.1选题的意义及背景2.2基本要求 2.3运行环境及开发工具3、概要设计43.1设计思想3.2程序框图 3.3方法及原理3.4主要数据结构4、详细设计74.1创建哈夫曼树 4.2编码4.3源程序5、调试与操作说明146、总结与体会157、致谢16 设计目的1、 利用学过的数据结构知识设计一个简单的哈夫曼编/译码
2、器系统。2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2需求分析2.1、选题的意义和背景利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这是要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统
3、。2.2、基本要求(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；(2)编码：利用建好的哈夫曼树生成哈夫曼编码；(3)输出编码；(4)设字符集及频度如下表：字符 A B C D E F G H I J K L M频度186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符N O P Q R S T U V W X Y Z频度57 63 15 1 48 51 80 23 8 18 1 16 12.3、运行环境及开发工具本程序采用Visual C+6.0编程实现。 3概要设计3.1设计思想本程序的主要功能是实现对用户输入的字符编码，然后再把编码
4、结果翻译成原字符。但在进行这些操作之前必须做一项工作，就是创建Huffman树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N个权值Wi(i=1,2,.n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,.n)。可以证明哈夫曼树的WPL是最小的。哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编
5、码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。 43.2程序框图及流程图哈夫曼编/译码器初始化退出编码 3.3 方法及原理3.3.1创建Huffman树 本文创建Huffman树是在顺序链表的基础上进行的，建树原理如下： 1、根据给定的n个权值w1,w2,w3,wn，构造具有n棵二叉树的森林F=T1,T2,T3,Tn，其中每棵二叉树Ti只有一个带权值wi的根结点，其左右子树均为空。2、重复以下步骤，直到F中仅剩下一棵树为止： (1)在F中选取两棵根结点的权值最小的二叉树，作为左右子树构造一棵新的二叉树。使新的二叉树的根结点的权值为其左右子树
6、上根结点的权值之和。 (2)在F中删去这两棵二叉树，把新的二叉树加入F。最后得到的就是Huffman树。3.3.2 编码 编码操作需在建立好Huffman树的基础上进行。二叉树的叶子结点标记字符，由根结点沿着二叉树路径下行，左分支标记为0，右分支标记为1，则每条从根结点到叶子结点的路径唯一表示了该叶结点的二进制编码。编码的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点是其父结点的左孩子，则编码为0，如果是右孩子，则编码为1，如此回溯，直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。 3.4 主要的
7、数据结构3.4.1 Huffman结点结构 Huffman结点结构是本程序的基本结构，所有操作都在此上进行。其中包括存储字符的元素data，字符的权值weight，以及左右孩子指针和父指针。 typedef struct char ch;/结点值 int weight;/权值 int parent;/父结点指针 int lchild; /左孩子结点指针 int rchild;/右孩子结点指针huffnode;详细设计4.1 创建Huffman树4.1.1 功能描述 Huffman树是整个程序的核心部分，是编码译码操作的前提。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。根据字符出现的
8、概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。4.1.2 算法原理首先根据用户输入创建n棵子树的森林，然后对所有子树扫描，找出权值最小的两个子树，把它们合并成一棵新的子树，同时把它们的权值之和作为新树的权值。把这两棵子树删掉，再把新树加如到森林中，然后再扫描出权值最小的两棵子树，接着进行同样的操作，直到只剩下一棵树即为Huffman树。 4.1.3 算法流程 74.2 编码 4.2.1 功能描述 编码的功能就是把字符转换成二进制数来存储 4.2.2 算法原理编码的时候，我们采用从叶子结点向上回溯
9、的方法编码，如果当前结点是其父结点的左孩子，则编码为0，如果是右孩子，则编码为1，如此回溯，直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。 4.2.3 算法流程 4.4源程序#include#include#include#include#includetypedef struct /哈夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtre
10、e &HT,int a,int *p1,int *p2) /Select函数，选出HT树到a为止，权值最小且parent为0的2个节点int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /选出最小的节点for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void hf
11、mcoding(hfmtree &HT,hfmcode &HC,int n) /构建哈夫曼树HT，并求出n个字符的哈夫曼编码HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i) /初始化n个叶子结点printf(请输入第%d字符信息和权值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HT
12、i.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的结点HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立哈夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)mall
13、oc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /给n个字符编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件输入输出ofstream
14、output_file;char choice,str100;hfmtree HT;hfmcode HC;coutn;cout 软件1102班 1101306229 吴超n;while(choice!=Q&choice!=q) /当choice的值不为q且不为Q时循环cout *哈夫曼编码器*n;cout I.Init E.Encoding Q.Exitn;coutchoice;if(choice=I|choice=i) /初始化哈夫曼树coutn;hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfm
15、Tree.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();cout哈夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!endl;else if(choice=E|choice=e) /进行编码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中printf(请输入字符：);gets(str);output_file.open(ToBeTran.txt);if(!output_file)co
16、utcant oen file!endl;return 1;output_filestrendl;output_file.close();output_file.open(CodeFile.txt);if(!output_file)coutcant open file!endl;return 1;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)output_fileHCj;break;output_file.close();coutn;cout编码完毕，并且已经存入CodeFile.txt文件！n;input_file.open(Co
17、deFile.txt); /从CodeFile.txt中读入编码，输出在终端if(!input_file)coutcant oen file!code;cout编码码值为：codeendl;input_file.close();else /如果选了选项之外的就让用户重新选择cout您没有输入正确的步骤，请重新输入！endl;coutendl;return 0;14调试与操作说明在运行程序时，需先输入需要编码的字符串，然后根据输入的字符的权重创建Huffman树，接着再进行编码操作，最后再把所得的编，各步操作之间存在先后关系，因此在运行程序时必须注意所选择的操作的先后顺序。 15总结与体会在当今
18、的信息化时代，先进的技术成为了科技的主流。哈夫曼是一种应用广泛且非常有效的数据压缩技术。这次课程设计我做的是哈夫曼编码和译码器。由于自身对数据结构的掌握有限，我只能做哈夫曼树的建立，编码和译码这部分内容。但是通过这次课程设计，我看到了自身的不足，让我有机会进一步学习了数据结构的知识。平时的学习中，我们不能单单地只学习理论知识，而应当把理论知识与实践结合起来。不然如果只有理论知识，而不能把理论运用到实际中，那也没多大用。总之，这次课程设计让我受益匪浅！ 致谢感谢所有在这次课程设计中给我提出建议和提供指导的老师们，感谢帮助我解决很多问题的同学们。 16指导教师评语： 指导教师签名： 年 月 日成绩评定项 目权重成绩1、设计过程中出勤、学习态度等方面0.22、课程设计（实践周）质量与答辩0.53、设计报告书写及图纸规范程度0.3总 成 绩
