《精品资料（2021-2022年收藏）课程设计格式模板》由会员分享，可在线阅读，更多相关《精品资料（2021-2022年收藏）课程设计格式模板（15页珍藏版）》请在金锄头文库上搜索。
1、计算机信息工程学院数 据 结 构课 程 设 计 报 告题 目： 哈夫曼编码 专 业：计算机科学与技术（软件方向） 班 级： 15计算机软件二班 学 号： 2015220140206 姓 名： 郭琪 指导教师： 范智华 完成日期： 2016年6月24日 目 录摘 要3【关键词】3哈夫曼编码4一、需求分析4二、哈夫曼树4三、哈夫曼树的理论创建过程如下：41、构成初始集合42、选取左右子树43、删除左右子树5五、解码5六、测试分析61、62、63、6七、运行结果7参考文献8附录9致谢14山西工商学院课程设计报告摘 要在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的
2、传送时间已越来越引起人们的重视。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输的时间，减低传输成本。但是，前提要求必须在发送端通过一个编码系统对准备传输的数据进行预先编码，而在接收端将传输来的数据进行译码。本次实例要实现一个简单的哈夫曼编译器。构造哈夫曼树时，首先将由n个字符形成的n个叶子结点存放到数组HTNode的前n个分量中，然后根据前文介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HTNode数组中的前n个分量的后面。【关键词
3、】哈夫曼树； 编码； 解码； 数据压缩技术；5哈夫曼编码一、需求分析利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。二、哈夫曼树 哈夫曼树也称最优二叉树.给定一组具有确定权值的叶子结点,可以构造出不同的二叉树,将其中带权路径长度最小的二叉树称为哈夫曼树.其中,叶子结点的权值(weight)是对叶子结点赋予的一个有意义的数值量.设二
4、叉树具有n个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度(weighted path length),记为: WPL=Wklk1=n k,wk为第k个叶子结点的权值,lk为从根结点到第k个叶子结点的路径 长度.三、哈夫曼树的理论创建过程如下：1、构成初始集合对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2、选取左右子树在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的
5、权值为其左右子树的根结点的权值之和。 3、删除左右子树从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4、重复二和三两步，重复二和三两步，直到集合F中只有一棵二叉树为止。四、编码具体操作：（1） 从叶子结点开始按照所储存的夫结点的信息向上寻找，若该结点是夫结点的左孩子结点将路径记为0，是右孩子将路径记为1。（2） 用临时字符数组cd来存储路径并从后先前存储。（3） 从1找到的夫结点开始继续向上寻找，直到找到根结点，即parent=0结束。五、解码具体操作：（1） 以字符串的形式输入编码存于code中。（2） 从根结点开始编码所给的路径依次向下寻找。（3） 直到找到叶子结点
6、为止。（4） 此时，若code=0，则译码结束，否则继续从根结点开始寻找。六、测试分析1、感觉文件操作自己并不是很熟练，尽管在向显示器输出的时候并没有什么错误但是读写文件的时候就没那么顺利了，比如说当编写savewithhufcode函数时读文件，却总不执行，后来通过断点测试发现每次fgetc()返回值总为-1，于是我考虑是否是文件没有打开或者文件结束的缘故，后来想通了是之前打开的文件光标读操作结束后仍在结尾故每次总返回-1，故调用rewind函数将光标位置移动到文章开始。2、用哈夫曼编码存储文件的时候还应注意数字0,1与字符0,1的不同，不应直接在fputc()函数中直接写入0,1那么将会是
7、写入的文章中什么都没有，因为0在ASCII码中代表NULL。3、该程序函数清晰功能明确，程序具有通用性，对于不同的输入文章都可进行处理，由于采用哈夫曼编码对照表，使得查看哈夫曼编码是效率较高无需每次遍历哈夫曼树。七、运行结果参考文献1孙家广，杨长青计算机图形学M北京：清华大学出版社，199526282Skolink M IRadar HandbookM New York： McGraw-Hill, 19903李旭东，宗光华，毕树生等生物工程微操作机器人视觉系统的研究4王明亮关于中国学术期刊标准化数据系统工程的进展EB/OL http：/wwwcajcdeducn/pub/wm1txt/9808
8、10-2html,1998-08-16/1998-10-045 严蔚敏，数据结构(C语言版)，清华大学出版社，20076 郑莉，C+语言程序设计（第4版），清华大学出版社，20107 谭浩强，C程序设计（第三版），清华大学出版社，2005附录#include #include #include #include typedef struct char data; int weight; int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char * * HuffmanCode;void Select(HuffmanTree &HT,int
9、 n,int m) HuffmanTree p=HT; int tmp; for(int j=n+1;j=m;j+) int tag1,tag2,s1,s2; tag1=tag2=32767; for(int x=1;x=j-1;x+) if(px.parent=0&px.weighttag1) tag1=px.weight;s1=x; for(int y=1;y=j-1;y+) if(py.parent=0&y!=s1&py.weights2) /将选出的两个节点中的序号较小的始终赋给s1 tmp=s1; s1=s2; s2=tmp;ps1.parent=j;ps2.parent=j;pj.
10、lchild=s1;pj.rchild=s2;pj.weight=ps1.weight+ps2.weight; void HuffmanCoding(HuffmanTree &HT,int n,char *w1,int*w2) int m=2*n-1; if(n=1) return; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); HuffmanTree p=HT; for(int i=1;i=n;i+) pi.data=w1i-1; pi.weight=w2i; pi.parent=pi.lchild=pi.rchild=0; for(;i=m;i+)
11、 pi.weight=pi.parent=pi.lchild=pi.rchild=0; Select(HT,n,m); ofstream outfile; /生成hfmTree文件 outfile.open(hfmTree.txt,ios:out); for (i=1;i=m;i+)outfileHTi.weighttHTi.parenttHTi.lchild tHTi.rchildtendl; outfile.close(); cout初始化结果已保存在hfmTree文件中n;void ToBeTree() /将正文写入文件ToBeTree中ofstream outfile;outfile.
12、open(ToBeTree.txt,ios:out);outfileTHIS PROGRAM IS MYFAVORITE;outfile.close();void Encoding(HuffmanTree &HT,int n) /编码 HuffmanCode HC; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); char *cd; cd=(char *)malloc(n*sizeof(char); cdn-1=0; for(int k=1;k=n;k+) int start=n-1; for(int c=k,f=HTk.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HCk=(char *)malloc(n-start)*sizeof(char); strcpy(HCk,&cdstart); cout输出哈夫曼编码:endl; for(int h=1;h=n;h+) /输出编码 coutHTh.data:; coutHCh; cout ; if (h%8=0) coutendl; coutendl输出正文编码:
