哈夫曼编码报告

1、精选优质文档-倾情为你奉上 实验项目:哈夫曼编码 1 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。2一个完整的系统应具有以下功能：1）初始化（Initialzation）。读入字符及每个字符的权值，建立哈夫曼树HuffTree；2）编码（EnCoding）。用已建好的哈夫曼树，对输入的文本进行编码形成报文，将报文显示出来；3）译码（De

2、coding）。利用已建好的哈夫曼树，对输入的代码进行解码形成原文，并将结果显示；4）输出（Output）: 输出出现的字符以及各字符出现的频度（或概率）；输出各个字符的编码，输出代码译出的原文；3.实验目的：理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；通过该实验，使学生对数据结构的应用有更深层次的理解。 4.实验条件：学院提供公共机房，1台/学生微型计算机。5.实验步骤（含实验代码）第1次：完成程序的主框架设计，进行调试，验证其正确性；第2次：详细设计，进行调试，验证其正确性；第3次：进行整体调试，运行程序，对运行结果进行分析，完

3、成实验报告。#include<stdio.h>#include<string.h>#include<malloc.h>#define MAXWORD 100typedef struct unsigned int weight;char data; unsigned int parent,llchild,rrchild; HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树 typedef char * *HuffmanCode; / /动态分配数组存储哈夫曼编码表typedef struct tnode char ch; /字符 int co

4、unt; /出现次数 struct tnode *lchild,*rchild;BTree,*BT;int a=0,b=0;int sMAXWORD;char strMAXWORD;void main() int n;int i=0; HuffmanTree HT;HuffmanCode HC; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n); void DispHCode(HuffmanTree HT,HuffmanCode HC,int n); void Creatree(BT &p,char c)

5、; /Creatree()和InOrderTraverse() void InOrderTraverse(BT p); /利用二叉树统计出现的字符及个数 void TTranChar(HuffmanTree HT,HuffmanCode HC,int n); void Tran(HuffmanTree HT,int n); printf("请输入要用几种字符："); scanf("%d",&n); BT root=NULL; printf("n"); printf("请输入字符串:n"); scanf(&q

6、uot;%s",str); while(stri!='0') Creatree(root,stri);i+; printf("字符及出现次数:n"); InOrderTraverse(root); printf("n"); HuffmanCoding(HT,HC,n); DispHCode(HT,HC,n); Tran(HT,n);TTranChar(HT,HC,n);void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n) / w放n个权值,构造赫夫曼树

7、HT,n个字符编码HC void select(HuffmanTree t,int i,int &s1,int &s2); int m,i,s1,s2,start;char *cd;unsigned c,f; HuffmanTree p; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;i<=n;+i,+p) (*p).parent=0; (*p).llchild=0; (*p).rrchild=0; for(p=HT+1,i=0;i<n;

8、+i,+p) (*p).data=stri; (*p).weight=si;for(;i<=m;+i,+p) (*p).parent=0; for(i=n+1;i<=m;+i) / 建赫夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个,分别s1、s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.llchild=s1; HTi.rrchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char

9、*);/(0不用) cd=(char*)malloc(n*sizeof(char); 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.llchild=c) cd-start='0' else cd-start='1' HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); / 复制 free(cd);

10、 void select(HuffmanTree t,int i,int &s1,int &s2) / s1为较小 int min(HuffmanTree t,int i); int j; s1=min(t,i); s2=min(t,i); if(s1>s2) j=s1; s1=s2; s2=j; int min(HuffmanTree t,int i) / 函数void select()调用 int j,flag; unsigned int k=100; / 取k比任何权值都大 for(j=1;j<=i;j+) if(tj.weight<k&&

11、;tj.parent=0) k=tj.weight,flag=j; tflag.parent=1; return flag; void Creatree(BT &p,char c) /采用递归方式构造一棵二叉排序树if(p=NULL) /p为NULL，则建立一个新结点p=(BTree * )malloc(sizeof(BTree);p->ch=c;p->count=1;p->lchild=p->rchild=NULL;else if(c=p->ch) p->count+;else if(c<p->ch) Creatree(p->lc

12、hild,c); else Creatree(p->rchild,c);void InOrderTraverse(BT p) /中序遍历if(p!=NULL) InOrderTraverse(p->lchild);printf("%c的个数为:%dn",p->ch,p->count); sb=p->count;b+;stra=p->ch;a+; InOrderTraverse(p->rchild);void DispHCode(HuffmanTree HT,HuffmanCode HC,int n) /显示0、1编码int i; p

13、rintf("输出哈夫曼编码:n"); for(i=1;i<=n;i+) printf("%c:t",HTi.data); puts(HCi);void Tran(HuffmanTree HT,int n) /将含0、1的编码翻译成字符 int i,j=0; char ccMAXWORD; i=2*n-1; printf("输入发送的(0、1)编码(以'#'为结束标志)："); scanf("%s",cc); printf("译码后的字符为"); while(ccj!=&#

14、39;#') if(ccj='0') i=HTi.llchild; else i=HTi.rrchild; if(HTi.llchild=0) printf("%c",HTi.data);i=2*n-1; j+; printf("n"); void TTranChar(HuffmanTree HT,HuffmanCode HC,int n) char ss50;int i,j; /将字符串翻译成0、1代码 printf("输入字符串:");scanf("%s",ss);i=0;while(ssi!='0') j=1; while(HTj.data!=ssi)&&(j<=n) j+; printf("%s",HCj); i+; printf("n");6.实验结果与总结：总结：在实现哈夫曼树编码的过程中，首先构建哈夫曼树，并用动态分配数组存储，也用动态分配数组存储哈夫曼编码表。程序书上虽然有一部分可借鉴的代码，自己只需要编写几个函数即可，但在编写程序时也遇到一些问题，开始统计字符串中出现的