2022年2022年哈夫曼编码报告 .pdf

实验项目 :哈夫曼编码1 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。2一个完整的系统应具有以下功能：1）初始化（ Initialzation ）。读入字符及每个字符的权值，建立哈夫曼树HuffTree ；2）编码（ EnCoding）。用已建好的哈夫曼树，对输入的文本进行编码形成报文，将报文显示出来；3）译码（ Decoding）。利用已建好的哈夫曼树，对输入的代码进行解码形成原文，并将结果显示；4）输出（ Output ）: 输出出现的字符以及各字符出现的频度（或概率）；输出各个字符的编码，输出代码译出的原文；3. 实验目的：理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；通过该实验，使学生对数据结构的应用有更深层次的理解。4. 实验条件：学院提供公共机房，1 台/学生微型计算机。5. 实验步骤（含实验代码）第 1 次：完成程序的主框架设计，进行调试，验证其正确性；第 2 次：详细设计，进行调试，验证其正确性；第 3 次：进行整体调试，运行程序，对运行结果进行分析，完成实验报告。#include #include #include #define MAXWORD 100 typedef struct unsigned int weight;char data; unsigned int parent,llchild,rrchild; HTNode,*HuffmanTree; / 动态分配数组存储哈夫曼树typedef char * *HuffmanCode;/动态分配数组存储哈夫曼编码表typedef struct tnode char ch; /字符名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - int count; /出现次数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); /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(%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 个权值 ,构造赫夫曼树 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;in;+i,+p) (*p).data=stri; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - (*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*);/(0 不用) cd=(char*)malloc(n*sizeof(char); cdn-1=0; / 编码结束符for(i=1;is2) 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.weightch=c; p-count=1; p-lchild=p-rchild=NULL; else if(c=p-ch) p-count+; else if(cch) Creatree(p-lchild,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; printf( 输出哈夫曼编码 :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!=#) if(ccj=0) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 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. 实验结果与总结：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 总结：在实现哈夫曼树编码的过程中，首先构建哈夫曼树，并用动态分配数组存储，也用动态分配数组存储哈夫曼编码表。程序书上虽然有一部分可借鉴的代码，自己只需要编写几个函数即可，但在编写程序时也遇到一些问题，开始统计字符串中出现的各种字符及其次数时，将字母存放数组中，但是考虑到字母出现的不同，完全初始化再统计其出现的个数，不仅占用空间并且时间复杂度高。后来采用二叉树统计出现的字母及个数，实现了输入字母种类的灵活性。通过此次实验，明白了了解数据存储的具体方式的重要性，在这次实验中要实现两个互译码程序，就需要对数据的存储了解，编写时就容易了然于心。总的来说，数据结构实验对我们的编程能力还是有很大的帮助，锻炼我们的逻辑思维、使我们更熟练地使用c 语言编程、锻炼我们处理异常的能力。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -