《哈夫曼编码译码器设计与实现.doc》由会员分享，可在线阅读，更多相关《哈夫曼编码译码器设计与实现.doc（22页珍藏版）》请在三一文库上搜索。
1、唐 山 学 院 数据结构 课 程 设 计 题 目 哈夫曼编码译码器设计与实现 系 (部) 计算机科学与技术系 班 级 12计本2班 姓 名 孙林川 学 号 4122006229 指导教师 王照华 2013 年 12 月 30 日至 1 月 10 日 共 2 周 2014 年 1 月 10 日数据结构 课程设计任务书一、设计题目、内容及要求1、设计题目：哈夫曼编码译码器设计与实现。2、设计内容及要求： （1）根据输入的权值建立哈夫曼树。（2）利用建好的哈夫曼树生成哈夫曼编码，并显示生成的各字符的哈夫曼编码。（3）根据输入的字符进行译码。二、要求的设计成果（课程设计说明书、设计实物、图纸等）1、用
2、C语言进行程序设计，实现程序的功能。注重算法效率，代码要有适当的注释；2、撰写课程设计说明书一份，不少于2000字。课程设计说明书应包括封面、任务书、成绩评定表、正文（设计思路、设计步骤等）、参考文献（资料）、附录（程序代码）等内容。三、进程安排12月30日：进行需求分析，确定系统的主要功能和算法思路；12月31日1月2日：进行详细设计，确定各模块的算法思路；1月3日1月6日：进行编码实现；1月7日1月9日：进行测试调试，完善设计；撰写设计说明书，准备答辩；1月10日：答辩。四、主要参考资料 1.严蔚敏，吴伟民.数据结构.清华大学出版社，2007.2.苏仕华.数据结构课程设计.机械工业出版社，
3、2010.3.滕国文.数据结构课程设计.清华大学出版社，2010.指导教师（签名）：教研室主任（签名）：课程设计成绩评定表出勤情况出勤天数 缺勤天数成绩评定出勤情况及设计过程表现（20分）课设答辩（20分）设计成果（60分）总成绩（100分）提问（答辩）问题情况综合评定 指导教师签名： 年 月 日唐山学院课程设计1引言哈夫曼是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率，加快信息传输速度，降低传输成本。数据压缩的过程称为编码，解压的过程称为译码。进行信息传递时，发送端通过一个编码系统对待传数据（明文）预先编码，而接受端将传来的数据（密文）进行译码。要求数据这样
4、一个简单的哈夫曼编码译码器。其主要功能有：(1) 可根据输入的权值及字符建立哈夫曼树。(2) 利用建好的哈夫曼树生成哈夫曼编码，并显示生成的各字符的哈夫曼编码。(3) 输入密文进行译码。本次设计使用的编程语言是C语言。采用了数据结构里的链式存贮结构和顺序存储结构。以及以孩子父亲三叉链表存储哈夫曼树。2问题分析要完成哈夫曼编码译码器需要完成下面几个部分：(1) 本题目主要设计到数组的操作和线性表。(2) 在建立哈夫曼树时要以数组的形式来存储哈夫曼树，因为要逆向求哈夫曼树，所以用数组的存储方式，操作起来更加的方便快捷。设有parent，lchlid，rchild。(3) 在哈夫曼编码译码时，由于输
5、入的字符大小不定，所以采用了链表的存储方式，实现动态存储分配。3总体设计设计哈夫曼编码译码器的总体思路：(1) 首先建立哈夫曼树，将哈夫曼树初始化，输入权值及字符建立哈夫曼树。(2) 输出哈夫曼的被编码的字符及对应的编码。(3) 输入要译码的哈夫曼编码字符串进行译码。哈夫曼编码译码器 哈夫曼树的建立哈夫曼编码及输出哈夫曼译码及输出图1 系统模块结构图开始定义各种变量调用函数输入要编码字符调用函数输入字符对应的权值建立哈夫曼树根据哈夫曼树进行编码是否输出字符及对应编码输出字符及其对应编码是否立刻译码输入要译的代码输出所译的字符是否继续译码结束是否是否否是图2 哈夫曼编码译码器总程序流程图4详细设
6、计4.1 建树模块在建立哈夫曼树时需要录入字符及其权值。4.1.1设计思路在建立哈夫曼树时输入的字符及权值的个数不确定，因此采用了动态分配存储的方法。因为在后面要输出编码的字符及对应的哈夫曼编码，要统计输入了几个字符所以输入字符函数有一个返回值，返回所输入字符的个数。并且在选最初的两个结点时，要找两个权值最小的两个，则该两个结点从原来结点中删除，在此用了给它们赋最大权值。4.1.2流程图 开始输入要编码的字符输入对应字符的权值初始化哈夫曼树依次选取最小的权值结点建立哈夫曼树结束图3 建树模块程序流程图4.2 编码模块4.2.1设计思路在已建立好的哈夫曼的基础上，逆向求哈夫曼编码。利用动态分配存
7、储的方式，因为是逆向存储，所以也应逆向存储哈夫曼编码。4.2.2流程图开始动态分配存储字符串的指针向量动态分配存储哈夫曼编码的空间逆向求哈夫曼密码将指针向量指向所求的哈夫曼编码结束是否输出编码输出以编好字符及编码是否图4 编码模块流程图4.3 译码模块4.3.1设计思路动态分配存储输入的编码，遍历哈夫曼树，若编码等于0，向左遍历其左子树，并判断其左右孩子是否为零，若为都零则输出其data域中的字符并存储。并判断输入的编码是否读到0,是也退出循环，并判断退出时结点的左右孩子是否都为零，是则为完全译码否就为不完全译码。4.3.2流程图开始定义分配存储了空间判断输入编码向右遍历哈夫曼树向左遍历哈夫曼
8、树p-lchild!=0&p-rchild!=0&L-ch!=#调用函数输出存储结点的字符L-ch!=#结束01指针指向左或右孩子是否是图5 译码模块流程图5运行测试5.1 建树模块打开运行程序出现以下界面:图6 主程序开始的界面输入字符abcdef以#结束:图7 输入要编码字符界面按下回车键后,自动统计输入字符个数并提示以下信息,请输入对应字符的权值界面: 图8 提示请输入字符的权值 输入字符的对应权值1,2,3,4,5,6,后按下回车键,提示以下信息:图9 输入字符的权值后提示是否输出编码及字符界面5.2 编码模块根据提示按下y键,敲回车后输出字符及编码，a的编码为1000，b的编码为10
9、01，c的编码为101，d的编码为00，e的编码为01，f的编码为11。界面如下：图10 输出字符后提示是否译码界面5.3 译码模块按要求按下y键，按回车键后出现如下信息:图11 提示输入要译的代码信息界面输入代码01010101001以#结束,出现下面的界面:图12 输入代码后的界面按确认键后输出所译出的字符为e，e，e，e，d和空并提示，该串代码为不完全译码并给出了原因界面如下:图13 输出译出的字符并提示是否继续译码界面按任意键结束程序出现“欢迎下次使用”信息，界面如下:图14程序运行结束时界面6总结本次课程设计我选择的题目是哈夫曼编码译码器设计。此程序适合于在文件传输过程中使用，减少传
10、输成本和提高传输效率。对于通信公司有良好的作用。在建立哈夫曼树是用了数组的存储结构，在输入权值及字符时用了动态链表的存储，这样可以动态的存储数据从而可以避免一定的局限性。就在自己写报告时有发现了自己程序的不足。但程序已经可以基本实现所要求的功能。但在一些方面还不够完善。例如在输入译码时直接输入字符的结果忘了考虑，在输入时有误时，没有输出显示，并从新输入。课程设计使我体会较大的是应用比理论学习难得多，它涉及到各种实际问题。但实习时所用到的知识记忆会比较深，理解也较透彻。在今后的学习生活中自己也要经常练习一些编程，提高自己的能力，同时我体会到在自己改程序中的错误时提高也比较大。实践非常重要因此我们
11、在以后要注重实践。并努力学习专业知识，实践与理论相结合会更大的极高自己的能力。参考文献1 严蔚敏，吴伟民数据结构北京：清华大学出版社，2008 2 田淑清，孙甲松C语言程序设计北京：高等教育出版社，2012附录#includestdio.h#includestdlib.h#includestring.h#define NULL typedef struct char data; unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedef char * *Huffm
12、anCode;/动态分配数组存储赫夫曼编码表typedef char * AC;typedef struct Wint n;struct W *next;W,*LinkW;/动态存储赫夫曼树的权值typedef struct Cchar ch;struct C *next;C,*LinkC;/动态存储要编的代码typedef struct LNodechar ch;struct LNode *next;LNode,*LinkList;void Select(HuffmanTree &HT,int i,int *s1,int *s2,int max);void HuffmanTreeing(Hu
13、ffmanTree &HT,W *w,int n,int max,C *c)/w存放n个字符的权值（均0），构造赫夫曼树HTint m,i;HuffmanTree p;if(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0号单元未使用for(p=HT+1,i=1;idata=c-ch;p-weight=w-n;w=w-next;c=c-next; p-parent=0; p-lchild=0; p-rchild=0;for(;idata=NULL;p-weight=0; p-parent=0; p-lchild=0
14、; p-rchild=0;int s1=0,s2=0;for(i=n+1;i=m;+i)/建赫夫曼树/在HT1.i选择parent为0且weight最小的两个结点，其序号分别为s1和s2。Select(HT,i-1,&s1,&s2,max);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HTs1.weight=HTs2.weight=max;/*从叶子到根逆向求每个字符的赫夫曼编码*void HuffmanCodeing(HuffmanTree &HT,Huf
15、fmanCode &HC,int n)HC=(HuffmanCode)malloc(n+1)*sizeof(AC);/分配n个字符编码的头指针向量AC cd;cd=(AC)malloc(n*sizeof(char);/分配求编码的工作空间cdn-1=0;int i,start,f;unsigned int c;for(i=1;i=n;+i)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c) cd-start=0;else cd-start=1;HCi=(AC)malloc(n-star
16、t)*sizeof(char);/为第i个字符编码分配空间strcpy(HCi,&cdstart); /从cd复制编码到HCfree(cd);/求叶子中权值最小的两个叶子的序号void Select(HuffmanTree &HT,int i, int *s1,int *s2,int max)int j,l,m=1,k2,a2; for(l=0;l=1;l+) for(j=1;j=HTj.weight)m=j; kl=m;al=HTm.weight;HTm.weight=max; *s1=k0; *s2=k1; for(l=0;lch!=#) p=HT+m; while(p-lchild!=0
17、&p-rchild!=0&L-ch!=#) if(L-ch=0)j=p-lchild;p=HT+j; else if(L-ch=1)j=p-rchild;p=HT+j; else printf(因%c字符不属于赫夫曼编码自动跳过*n,L-ch); L=L-next; r-ch=p-data; s=(LinkList)malloc(sizeof(LNode); r-next=s; r=r-next; r-next=0;int InputQuanzhi(LinkW &w,int n) int j,max=0; LinkW s,q; w=(LinkW)malloc(sizeof(W); q=w; f
18、or(j=0;jnext=s; max+=q-n; q=q-next; return max;free(s);free(q);int InputZifu(LinkC &c)int n=0; LinkC s,q;c=(LinkC)malloc(sizeof(C);q=c; while(q-ch=getchar()!=#) s=(LinkC)malloc(sizeof(C); q-next=s; q=q-next; n+; printf(*您输入的需要编码的字符的个数为:%d个*n,n); return n; free(s); free(q);void InputBianma(LinkList &
19、L) printf(*输入要译的代码,以#结束*n); LinkList q,s; L=(LinkList)malloc(sizeof(LNode); q=L; getchar(); while(q-ch=getchar()!=#) s=(LinkList)malloc(sizeof(LNode); q-next=s; q=q-next; q-next=0;void OutputBianma(HuffmanTree &HT,HuffmanCode HC,int n) int j; for(j=1;jnext) printf(%cn,R-ch); if(R-ch=NULL)tag=0 ; pri
20、ntf(*不完全译码*nn-原因为最后几位不能构成一个字符的一组编码-nn);R=R-next; if(tag)printf(*完全译码*nn); main() printf(*赫夫曼编码译码器*nn); C *c; W *w; int n,max; HuffmanTree HT; HuffmanCode HC; LinkList L,R; printf(*请输入要编码的字符以#结束:*nn); n=InputZifu(c); printf(*请输入这%d个字符对应的权值:*n,n); max=InputQuanzhi(w,n); HuffmanTreeing(HT,w,n,max,c); H
21、uffmanCodeing(HT,HC,n); printf(是否输出以编码的字符及编码是:请按Y键否:请按N键继续n); getchar(); if(getchar()=y)printf(*以编码字符及对应编码*n);OutputBianma(HT,HC,n); printf(*是否现在译码;是请按Y键;否请按任意键结束*nn); getchar(); while(getchar()=y) InputBianma(L); Huffmanyima(HT,n,L,R); OutputYima(R); printf(*是否继续译码是:请按Y键.否按任意键结束*nn); getchar(); printf(*欢迎下次使用*nn);19