2022年2022年哈夫曼编译器 .pdf

《2022年2022年哈夫曼编译器 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年哈夫曼编译器 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、问题描述 ：利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试为这样的信息收发站写一个哈夫曼编译码系统。一个完整的系统应具有以下功能：（1） （1）I： 初始化。从终端读入字符集大小n ，及 n 个字符和n 个权值，建立哈夫曼树，并将其存于文件hfmtree 中。（2） C： 编码。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree 中读入） ， 对文件 tobetrans 中的正文进

2、行编码，然后将结果存入文件codefile中。（3） D： 译码。利用已建好的哈夫曼树将文件codefile 中的代码进行译码，结果存入文件 textfile 中。（4） P： 打印代码文件。将文件codefi1e 以紧凑格式显示在终端上 ,每行 50个代码。同时将此字符形式的编码文件写入文件codeprint 中。（5） T：打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹凸表形式）显示在屏幕上， 同时将此字符形式的哈夫曼树写入文件treeprint 中。实现提示：1、用户界面可以设计为 “ 菜单” 方式：显示上述功能号，再加上“E”表示结束运性行结束，用户键入一个选择功能字符，则执

3、行相应的功能， 此功能执行完毕后再显示此菜单，直至用户选择了“E”为止。2、在程序的一次执行过程中，第一次执行了I、D 或 C 命令之后，哈夫曼树已经在内存中存在了，不必再读入。每次执行中不一定执行I 命令，因为文件hfmtree 可能早已建好。我写的源程序如下：#include #include #include / /*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/ typedef struct int weight; char ch; /增加一个域用于存放该节点的字符int parent,lchild,rchild; 名师资料总结 - - -精品资料欢迎下载

4、 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - HTNode,*HuffmanTree; typedef char *HuffmanCode; /指向赫夫曼编码的指针/ /*本程序用到的函数原型*/ void welcome(); /打印操作选择界面void HuffmanCoding(HuffmanTree &,char *,int *,int);/建立赫夫曼树的算法void select(HuffmanTree HT,int j,int *s1,int *s2);

5、 /从目前已建好的赫夫曼树中选择parent为 0 且 weight 最小的两个结点void Init(); / 输入 n 个字符及其对应的权值，根据权值建立哈夫曼树void Coding(); /编码void Decoding(); /译码void Print_code(); /打印译码好的代码文件void Print_tree(); /以凹凸表形式打印哈夫曼树int Read_tree(HuffmanTree &); /从文件中读入赫夫曼树void find(HuffmanTree &HT,char *code,char *text,int i,int m);/译码时根据01 字符串寻找相

6、应叶子节点的递归算法void Convert_tree(unsigned char T100100,int s,int *i,int j);/将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; /全局变量，指向存放赫夫曼树的存储空间int n=0; / 全局变量，存放赫夫曼树叶子结点的数目int main() char select; while(1) welcome(); scanf(%c,&select); switch(select) case i: case I:Init();break; case c: case C:Coding();break; case

7、d: case D:Decoding();break; case p: case P:Print_code();break; case t: case T:Print_tree();break; case e: case E:exit(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - default :printf(Input error!n); getchar(); return 0; void welcome() /打

8、印操作选择界面 printf(*-*n); printf(| What do you want to do? |n); printf(|-|n); printf(| |n); printf(| I-Init the Huffman tree. |n); printf(| C-Code your file. |n); printf(| D-Decode the code. |n); printf(| P-Print the codefile. |n); printf(| T-Print the Huffman tree. |n); printf(| |n); printf(*-*n); / /*

9、初始化函数，输入n 个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/ void Init() FILE *fp; int i,n,w52; /w数组存放n 个字符的权值char character52; /存放 n 个字符printf(n输入字符个数n:); scanf(%d,&n); /输入字符集大小printf( 输入 %d 个字符及其对应的权值:n,n); for (i=0;in;i+) char b=getchar(); scanf(%c,&characteri); scanf(%d,&wi); /输入 n 个字符和对应的权值 HuffmanCoding(

10、HT,character,w,n); /建立赫夫曼树if(fp=fopen(hfmtree.txt,w)=NULL) printf(Open file hfmtree.txt error!n); for (i=1;i=2*n-1;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - if(fwrite(&HTi,sizeof(HTNode),1,fp)!=1) /将建立的赫夫曼树存入文件hfmtree.txt中printf(F

11、ile write error!n); printf(n建立赫夫曼树成功，已将其存于文件hfmtree.txt中n); fclose(fp); / / 建立赫夫曼树的算法/ void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n) int m,i,s1,s2; HuffmanTree p; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;ich=*character;p-weight=*w;p-paren

12、t=0;p-lchild=0;p-rchild=0; for(;ich=0;p-weight=0;p-parent=0;p-lchild=0;p-rchild=0; for(i=n+1;i=m;+i) select(HT,i-1,&s1,&s2); HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; / /*从 HT1 到 HTj中选择 parent 为 0 且 weight 最小的两个结点，用s1 和 s2 返回其序号 */ void select(Huff

13、manTree HT,int j,int *s1,int *s2) int i; /找 weight 最小的结点for (i=1;i=j;i+) if (HTi.parent=0) *s1=i;break; for (;i=j;i+) if (HTi.parent=0)&(HTi.weightHT*s1.weight) *s1=i; HT*s1.parent=1; /找 weight 次小的结点for (i=1;i=j;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，

14、共 9 页 - - - - - - - - - if (HTi.parent=0) *s2=i;break; for (;i=j;i+) if (HTi.parent=0)&(i!=*s1)&(HTi.weightHT*s2.weight) *s2=i; / /*对文件 tobetrans中的正文进行编码，然后将结果存入文件codefile 中*/ void Coding() FILE *fp,*fw; int i,f,c,start; char *cd; HuffmanCode HC; if(n=0) n=Read_tree(HT);/从文件 hfmtree.txt中读入赫夫曼树,返回叶子结

15、点数/ 以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于 HC 指向的空间中 HC=(HuffmanCode)malloc(n+1)*sizeof(char*); 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.lchild=c) cd-start=0; else cd-start=1; HCi=(char *)malloc(n-start)*sizeof(char); strcpy(HCi,

16、&cdstart); free(cd); / if(fp=fopen(tobetrans.txt,rb)=NULL) printf(Open file tobetrans.txt error!n); if(fw=fopen(codefile.txt,wb+)=NULL) printf(Open file codefile.txt error!n); char temp; fscanf(fp,%c,&temp); /从文件读入第一个字符while(!feof(fp) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

17、 - - - - - - 第 5 页，共 9 页 - - - - - - - - - for(i=1;i=n;i+) if(HTi.ch=temp) break; /在赫夫曼树中查找字符所在的位置for(int r=0;HCir!=0;r+) /将字符对应的编码存入文件fputc(HCir,fw); fscanf(fp,%c,&temp); /从文件读入下一个字符 fclose(fw); fclose(fp); printf(n对文件 hfmtree.txt编码成功 ,结果已存入codefile.txt中。 nn); / /*将文件 codefile 中的代码进行译码，结果存入文件textfi

18、le 中*/ void Decoding() FILE *fp,*fw; int m,i; char *code,*text,*p; if(n=0) n=Read_tree(HT);/从文件 hfmtree.txt中读入赫夫曼树,返回叶子结点数if(fp=fopen(codefile.txt,rb)=NULL) printf(Open file codefile.txt error!n); if(fw=fopen(textfile.txt,wb+)=NULL) printf(Open file textfile.txt error!n); code=(char *)malloc(sizeof(

19、char); fscanf(fp,%c,code); /从文件读入一个字符for(i=1;!feof(fp);i+) code=(char *)realloc(code,(i+1)*sizeof(char); /增加空间fscanf(fp,%c,&codei); /从文件读入下一个字符 codei-1=0; / 到此 codefile.txt文件中的字符已全部读入，存放在code 数组中text=(char *)malloc(100*sizeof(char); p=text; m=2*n-1; if(*code=0) find(HT,code,text,HTm.lchild,m); /从根节点

20、的左子树去找else find(HT,code,text,HTm.rchild,m); /从根节点的右子树去找名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - for(i=0;pi!=0;i+) /把译码好的字符存入文件textfile.txt 中fputc(pi,fw); fclose(fp); fclose(fw); printf(n 对 codefile.txt文件译码成功，结果已存入textfile.txt 文件。 nn)

21、; / /*将文件 codefi1e以紧凑格式显示在终端上,每行 50 个代码。同时将此字符形式的编码文件写入文件 codeprint中。 */ void Print_code() FILE *fp,*fw; char temp; int i; if(fp=fopen(codefile.txt,rb)=NULL) printf(Open file codefile.txt error!n); if(fw=fopen(codeprint.txt,wb+)=NULL)printf(Open file codeprint.txt error!n); printf(n文件 codefi1e 以紧凑格式

22、显示如下:n); fscanf(fp,%c,&temp); /从文件读入一个字符for (i=1;!feof(fp);i+) printf(%c,temp); if(i%50=0) printf(n); fputc(temp,fw); /将该字符存入文件codeprint.txt中fscanf(fp,%c,&temp); /从文件读入一个字符 printf(nn此字符形式的编码已写入文件codeprint.txt中.nn); fclose(fp); fclose(fw); / /*将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件 treeprint 中。 */

23、 void Print_tree() unsigned char T100100; int i,j,m=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - FILE *fp; if(n=0) n=Read_tree(HT);/从文件 hfmtree.txt中读入赫夫曼树,返回叶子结点数Convert_tree(T,0,&m,2*n-1); /将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T 中if(fp=fopen(tree

24、print.txt,wb+)=NULL) printf(Open file treeprint.txt error!n); printf(n以凹凸表形式打印已建好的赫夫曼树：n); for(i=1;i=2*n-1;i+) for (j=0;Tij!=0;j+) if(Tij= ) printf( );fputc(Tij,fp); else printf(%d,Tij);fprintf(fp,%dn,Tij); printf(n); fclose(fp); printf(n此字符形式的哈夫曼树已写入文件treeprint.txt中.nn); / /*从文件 hfmtree.txt中读入赫夫曼树，

25、返回叶子节点数*/ int Read_tree(HuffmanTree &HT) FILE *fp; int i,n; HT=(HuffmanTree)malloc(sizeof(HTNode); if(fp=fopen(hfmtree.txt,r)=NULL) printf(Open file hfmtree.txt error!n); for (i=1;!feof(fp);i+) HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode); /增加空间fread(&HTi,sizeof(HTNode),1,fp); /读入一个节点信息 fclose(fp

26、); n=(i-1)/2; return n; / /*译码时根据01 字符串寻找相应叶子节点的递归算法*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - void find(HuffmanTree &HT,char *code,char *text,int i,int m) if(*code!=0) /若译码未结束 code+; if(HTi.lchild=0&HTi.rchild=0) /若找到叶子节点 *text=HTi

27、.ch; /将叶子节点的字符存入text 中text+; if(*code=0) find(HT,code,text,HTm.lchild,m); /继续从根节点的左子树找else find(HT,code,text,HTm.rchild,m); /继续从根节点的右子树找 else /如果不是叶子节点if(*code=0) find(HT,code,text,HTi.lchild,m); /从该节点的左子树去找else find(HT,code,text,HTi.rchild,m); /从该节点的右子树去找 else *text=0; / 译码结束 / /*将内存中的赫夫曼树转换成凹凸表形式的

28、赫夫曼树*/ void Convert_tree(unsigned char T100100,int s,int *i,int j) int k,l; l=+(*i); for(k=0;ks;k+) Tlk= ; Tlk=HTj.weight; if(HTj.lchild) Convert_tree(T,s+1,i,HTj.lchild); if(HTj.rchild) Convert_tree(T,s+1,i,HTj.rchild); Tl+k=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -