《哈夫曼编码译码系统实验报告-数据结构课程设计.pdf》由会员分享，可在线阅读，更多相关《哈夫曼编码译码系统实验报告-数据结构课程设计.pdf（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品归纳 哈夫曼编码译码系统实验报告-数据结构课程设计 键入文档副标题 姓名：鉏飞祥 学号：E 专业：软件工程 完成日期 2016/7/4 计算机科学与技术学院 1.需求分析 问题描述 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。基本要求 (1)输入的形式和输入值的范围；(2)输出的形式；(3)程序所能达到的功能。1.基本要求（1）初始化
2、（Initialzation）。从数据文件中读入字符及每个字符的权值，建立哈夫曼树 HuffTree；（2）编码（EnCoding）。用已建好的哈夫曼树，对文件中的文本进行编码形成报文，将报文写在文件中；（3）译码（Decoding）。利用已建好的哈夫曼树，对文件中的代码进行解码形成原文，结果存入文件中；（4）输出（Output）。输出中出现的字符以及各字符出现的频度（或概率）；输出及其报文；输出及其原文；2.概要设计 说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。(1)数据结构 哈夫曼树的节点 struct huff int weight;int
3、 parent;int l;int r;哈夫曼编码的存储 struct huff*hufftree;(2)程序模块 选择 1 到 i-1 中 parent 为 0 且权值最小的两个下标 void Select(struct huff*HT,int n,int&s1,int&s2)构建哈夫曼树：void huffmancoding(struct huff*ht,int*w,int n)对原文进行编码：void code(char*c)根据报文找到原文：void decoding(char*zifu)3.详细设计 核心技术分析：1：构建哈夫曼树及生成哈夫曼编码：根据每个字符权值不同，根据最优二叉树
4、的构建方法，递归生成哈夫曼树，并且用数组存放哈夫曼树。再从每一叶子节点向树根遍历，求得编码 例如：如图所示的四个节点 v1，v2，v3，v4，他们的权值分别为 7，11,4,5 7 11 4 5 第一步：选择两个权值最小的节点作为左右子孩子，建立一个二叉树，双亲权值为两个自孩子之和，如图 7 11 9 重复第一步：11 16 27 重复第一步：16 则此时建立的是优有二叉树，约定定左子树边编码为 1，右子树编码为 0，则可以对次二叉树进行编码，如图：1 0 1 0 1 0 则各顶点的编码为：V1 01 V2 1 V3 001 V4 000 2：将原文编码：逐个从文件读入字符，根据已经建立好的哈
5、夫曼树，找到每一字符对应的编码 3：将报文译码：步骤一：先读入一个字符，存入匹配字符串 步骤二：根据匹配串找所有的哈夫曼编码，如果找到对应的编码，则输入该编码所对应的字符，如果找不到，则读入两个字符存入匹配串，重复步骤二，找到为止。步骤三：把剩下的字符重复步骤一二 4.测试与分析 调试过程，不可能错的分配空间的语句却莫名的让整个程序崩溃，关于编译原理和内存分配的各种问题太欠缺。学了计算机组成原理与体系结构也不知道 比如在自定义函数中：Char *c;C=(char*)malloc(4*sizoef(char*);C2=(char*)malloc(4*sizeof(char);这样竟然会让程序这
6、执行到这一句时崩溃，本来不可能有错误的。而这句如果写在主函数中，就不会有问题。分配的空间不大，不可能是内存不够用。解决的方法是分开，把 C=(char*)malloc(4*sizoef(char*);放在主函数中，另外一句不变依然在自定义函数中。malloc 和 free 尽量配对使用，注意：malloc 后通常要对返回值进行判断，避免发生不必要的错误。注意，最好再 p 被 free 掉后，加上 p=NULL 这句 “野指针”不是 NULL 指针，是指向“垃圾”内存（不可用内存）的指针。人们一般不会错用 NULL 指针，因为用 if 语句很容易判断。但是“野指针”是很危险的，if 无法判断一个
7、指针是正常指针还是“野指针”。有个良好的编程习惯是避免“野指针”的唯一方法。指针 p 被 free 或者 delete 之后，没有置为 NULL，让人误以为 p是个合法的指针。别看 free 和 delete 的名字（尤其是 delete），它们只是把指针所指的内存给释放掉，但并没有把指针本身干掉。此时指针指向的就是“垃圾”内存。释放后的指针应立即将指针置为NULL，防止产生“野指针”malloc函数动态申请的内存空间是在堆里(而一般局部变量存于栈里)，并且该段内存不会被初始化，与全局变量不一样，如果不采用手动 free()加以释放，则该段内存一直存在，直到程序退出才被系统，所以为了合理使用内
8、存，在不适用该段内存时，应该调用free()。另外，如果在一个函数里面使用过 malloc，最好要配对使用 free，否则容易造成内存泄露（没有将内存还给自由存储区）。但是，往往会在 free 的时候发生段错误.正确的做法是这样：附录#include#include#include struct huff int weight;int parent;int l;int r;int mm;/*记录哈夫曼字码的个数*/struct huff*hufftree;char*huffmancode;void Select(struct huff*HT,int n,int&s1,int&s2)eight)
9、&(HTi.parent=0)min1=HTi.weight;for(i=1;i=n;i+)if(min1=HTi.weight)&(HTi.parent=0)s1=i;break;for(i=1;iHTi.weight)&(HTi.parent=0)&(i!=s1)min2=HTi.weight;for(i=1;i=n;i+)if(min2=HTi.weight)&(HTi.parent=0)&(i!=s1)s2=i;break;int pipei(char*c)/*在 huffmancode 寻找匹配的编码*/int i;for(i=1;imm;i+)if(strcmp(c,huffman
10、codei)=0)return i;break;return 0;void decoding(char*zifu)/*对哈夫曼编码进行译码*/FILE*fp,*fp1;int i,j,p,ii;int n;char c11;for(i=0;i10;i+)ci=0;printf(报文为：n);if(fp=fopen(,r)=NULL)printf(errorn);char a100;for(i=1;i+)fscanf(fp,%c,&ai);if(ai=#)break;printf(%c,ai);printf(n);fclose(fp);if(fp1=fopen(,w)=NULL)printf(e
11、rrorn);i=1;j=1;int m=1;printf(对应原文为n);while(true)if(am=#)break;for(j=0;ji;j+)cj=am+j;n=pipei(c);if(n!=0)fprintf(fp1,%c,zifun);printf(%c,zifun);m=m+i;i=1;else i+;for(ii=0;ii10;ii+)cii=0;printf(n);fclose(fp1);int main()system(color e0);arent=i;hts2.parent=i;hti.l=s1;hti.r=s2;hti.weight=hts1.weight+hts2.weight;char*cd;cd=(char*)malloc(n*sizeof(char);cdn-1=0;int start,c,f;for(i=1;i=n;+i)start=n-1;for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)if(htf.l=c)cd-start=0;else cd-start=1;huffmancodei=(char*)malloc(n-start)*sizeof(char);strcpy(huffmancodei,&cdstart);free(cd);6.用户使用手册 运行程序即可。如果改变，可以改变文件，中的值