数据结构课程设计说明书哈夫曼编译码器

1、课 程 设 计 说 明 书 课程名称： 数据结构 设计题目： 哈夫曼编/译码器 学 院： 计算机科学与信息工程学院 学生姓名： 学生学号： 专业班级： 网络工程13-01 指导教师： 2015年 6月 25日课 程 设 计 任 务 书设计题目哈夫曼编/译码器学生姓名申恒恒所在院部计算机科学与信息工程学院专业、班级网络工程13-1设计要求：1、根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码；2、读取文本文件，并对文件内容编码，生成编码文件；3、对编码文件进行译码，获得恢复文件；4、比较恢复文件和原文件是否相同。学生应完成的工作：1. 学生应认真学习参考程序，理解每个文件、每个函数以及各个

2、变量的作用和意义。在此基础上进一步改进程序，最后正确地运行程序。2. 对程序进行测试，设计详细的测试计划，然后根据测试计划设计测试用例，对程序进行测试。测试时应注意对各种边缘情况进行测试。3. 完成课程设计报告。参考文献：1. 严蔚敏 数据结构（c语言版） 清华大学出版社 20112. 谭浩强 c程序设计（第四版） 清华大学出版社2010工作计划：1. 小组审题，查阅资料，进行设计前的必要资料准备（3天）。 2. 把程序完整运行出来（4天）。 3. 增加改进程序（3天）。 4. 写课程设计报告（3天）。 5. 提交课程设计报告及答辩（1天）任务下达日期：2015 年 6 月 9 日 任务完成日

3、期：2015 年 6 月 22 日指导教师（签名）： 学生（签名）：申恒恒哈夫曼编/译码器摘 要：采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长度不小于5000字节。读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件和原文件必须完全一致。关键词：哈夫曼编码 哈夫曼译码 解码19目 录哈夫曼编/译码器21. 设计背景41.1程序的功能41.2输入输出的要求42.设计方案52.1程序结构52.2数据结构53. 方案实施63.1详细设计63.2 调试分析63.2.1 发现问题63.2.2 逐步解决

4、问题63.2.3 代码实现过程73.3 核心源程序清单124. 结果与结论144.1程序运行结果图144.2结论与心得体会155. 参考文献161. 设计背景1.1程序的功能(1) 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmtree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；(2) 利用已经建好的哈夫曼树（如不在内存，则从文件htmtree中读入），对文件tobetran中的正文进行编码，然后将结果存入文件codefile中，并输出结果，将文件codefile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件cod

5、eprint中；(3) 利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中，并输出结果。1.2输入输出的要求先在执行文件的同根目录下创建abc.txt文件，在abc文件中输入各字母及相应的权值。测试数据：字符空格abcdefghijklm频度1866413223210321154757153220字符nopqrstuvwxyz频度57631514851802381811612.设计方案2.1程序结构 2.2数据结构typedef struct int weight; /权重 int parent,lchild,rchild; /父亲节点，左孩子，右孩子h

6、tnode,* huffmantree; /定义节点和哈夫曼树结构体3. 方案实施3.1详细设计初始化哈夫曼链表: void initialization();输入带编码的字符并写入文件：void inputcode();编码: encoding();译码: decoding(); 打印编码:code_printing();3.2 调试分析3.2.1 发现问题如何根据输入的字符和使用频率构建哈夫曼树并得到它的哈夫曼编码？3.2.2 逐步解决问题哈夫曼树是什么？给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(huffman tre

7、e)。如何构建哈夫曼树？假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、wn，则哈夫曼树的构造规则为：(1) 将w1、w2、，wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。哈夫曼编码是什么？哈夫曼编码(huffman coding)是一种编码方式，哈夫曼编码是可变字长编码(vlc)的一种。huffman于1

8、952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作huffman编码。如何得到哈夫曼编码？通过从哈夫曼树根结点开始，对左子树分配代码“0”，右子树分配代码“1”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。3.2.3 代码实现过程/ -哈夫曼编码- / w存放n个字符的权值(均0),构造哈夫曼树ht,并求出n个字符的哈夫曼编码hcvoid huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n) int m,i,s1,

9、s2,start; int c,f; huffmantree p; char *cd; if(n=1)return; /检测结点数是否可以构成树 m=2*n-1; /需要构造多少个顶点 ht=(huffmantree)malloc(m+1)*sizeof(htnode); /0号单元未用 for(p=ht+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) / 建哈夫曼树 select(ht,i-1,s1,s2); / 在ht1i-1中选择parent为0且weight最

10、小的两个结点,其序号分别为s1和s2 hts1.parent=hts2.parent=i; /建立父亲节点 hti.lchild=s1; /初始化左右孩子节点 hti.rchild=s2; hti.weight=hts1.weight+hts2.weight; /把孩子节点的权值累加到父亲节点 hc=(huffmancode)malloc(n+1)*sizeof(char*); / 从叶子到根逆向求每个字符的哈夫曼编码 cd=(char*)malloc(n*sizeof(char); / 分配n个字符编码的头指针向量(0不用) cdn-1=0; / 编码结束符 for(i=1;i=n;i+)

11、/ 逐个字符求哈夫曼编码 start=n-1; / 编码结束符位置 for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) / 从叶子到根逆向求编码 if(htf.lchild=c) cd-start=0; /左子树为0 else cd-start=1; /右子树为1 hci=(char*)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间 strcpy(hci,&cdstart); /从cd复制编码(串)到hc free(cd); / 释放工作空间编码：上面已经得到了相应的字符的编码。直接输出即可。如何进行哈夫曼编码的译码？

12、知道了编码用的哈夫曼树后。从根结点出发，逐个读入编码的二进制码；若代码为“0”，则走左子树的根结点，否则走向右子树的根结点；一旦到达叶子结点，便译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制编码结束。编码和译码的代码如下：/-编码函数-void encoding() printf(下面对目录下文件tobetran.txt中的字符进行编码n); file *tobetran,*codefile; if(tobetran=fopen(tobetran.txt,rb)=null) /打开将要编码的文件 printf(不能打开文件n); if(codefile=fopen(codef

13、ile.txt,wb)=null) /保存编码结果的文件 printf(不能打开文件n); char *tran; i=99; tran=(char*)malloc(100*sizeof(char); while(i=99) if(fgets(tran,100,tobetran)=null) printf(不能打开文件n); break; for(i=0;*(tran+i)!=0;i+) for(j=0;jn) printf(字符错误，无法编码!n); break; printf(n编码完成n编码写入目录下的codefile.txt中nn); fclose(tobetran); fclose(

14、codefile); free(tran);/-译码函数-void decoding() printf(下面对根目录下文件codefile.txt中的字符进行译码n); file *codef,*txtfile; if(txtfile=fopen(textfile.txt,w)=null) /打开译码结果保存的文件 printf(不能打开文件n); if (codef=fopen(codefile.txt,r)=null) /打开将要译码的文件 printf(不能打开文件n); char *work,*work2,i2;int i4=0,i,i3; unsigned long length=1

15、0000; work=(char*)malloc(length*sizeof(char);fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char);i3=2*n-1; /n=26 i3=huffman树的全部节点数i=0;doi2=*(work+i); /求编码后的二进制if(hti3.lchild=0&hti3.rchild=0) /如果到达叶子节点 *(work2+i4)=*(z+i3-1);i4+;i3=2*n-1; /重新从根节点开始查找i-;else if(i2=0) i3=hti3.lchild; /左子树为0

16、else if(i2=1) i3=hti3.rchild; /右子树为1i+;while(*(work+i-1)!=0);*(work2+i4)=0;fputs(work2,txtfile);printf(译码完成n内容写入根目录下的文件textfile.txt中nn);free(work);free(work2); fclose(txtfile); fclose(codef);3.3 核心源程序清单void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n) int m,i,s1,s2,start; int c,f; huf

17、fmantree p; char *cd; if(n=1)return; /检测结点数是否可以构成树 m=2*n-1; /需要构造多少个顶点 ht=(huffmantree)malloc(m+1)*sizeof(htnode); /0号单元未用 for(p=ht+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) / 建哈夫曼树 select(ht,i-1,s1,s2); / 在ht1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 hts

18、1.parent=hts2.parent=i; /建立父亲节点 hti.lchild=s1; /初始化左右孩子节点 hti.rchild=s2; hti.weight=hts1.weight+hts2.weight; /把孩子节点的权值累加到父亲节点 hc=(huffmancode)malloc(n+1)*sizeof(char*); / 从叶子到根逆向求每个字符的哈夫曼编码 cd=(char*)malloc(n*sizeof(char); / 分配n个字符编码的头指针向量(0不用) cdn-1=0; / 编码结束符 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; /左子树为0 else cd-start=1; /右子树为1 hci=(char*)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间 strcpy(hci,&cdstart); /从cd复制编码(串