分析方案哈夫曼编译码系统与实现

1、数据结构实验报告学号0928724099姓名李晓松年级2009班级网络工程5班机号：学院机房时间周三下午2点半-4点 周四上午8点-10点指导教师张石石实验题目:理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的 哈夫曼树进行编码和译码；通过该实验，对数据结构的应用有更深层次的理解。实验要求：1.问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译 码复原）。对于双工信道 即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的

2、信息收发站设计一个哈夫曼编/译码系统。2 . 一个完整的系统应具有以下功能:1） 初始化lnitialzation）。从数据文件 DataFile.dat中读入字符及每个字符的权值，建立哈夫曼树HuffTree ;2） 编码EnCoding）。用已建好的哈夫曼树,对文件ToBeTran.dat中的文本进行编码形成报文，将报文写在文件Code.txt中；3） 译码Decoding ）。利用已建好的哈夫曼树，对文件 CodeFile.dat中的代码进行译码形成原文，结果存入文件Textfile.txt 中；4)输出 ；/创建数据文件void creatToBeTra n( ；/创建原文文件void

3、 creatCodeFile( 2.从文件 DataFile.dat；/创建报文文件中读出各字符及相应的权值，创建哈夫曼树HT；3.根据构造的哈夫曼树，求相应字符的哈夫曼编码；4 .从文件ToBeTran.dat中读出要翻译的原文，将其翻译成译文存入文件Code.txt中5.从文件CodeFile.dat中读出要翻译的报文，将其翻译成原文存入文件Textfile.txt 中环境语言：Windows下的 Microsoft VC +四、数据结构与模块说明下面是编译码系统中所用的数据结构。在这个系统中，哈夫曼树的存储结构采用顺序存储；其结点结构为：厂hwe 1 e htpa rent1 chi L

4、dr c hi 1 dn ez t =字符权值 双亲 左孩孑 右孩孑指向其輪码的指针程序中用到的头文件、类型定义及主要的函数原型如下：#i ncludestdio.h#i ncludemalloc.h#i ncludestri ng.h#defi ne char_ num 8typedef struct char ch。int w 。 DFileNode 。/ 定义数据文件的元素类型typedef struct II赫夫曼树和赫夫曼编码的存储表示char ch 。 II相应字符int weight 。 II字符的权值int parent,lchild,rchild。 II双亲、左、右孩子指针

5、II 创建数据文件void creatToBeTran( II 创建原文文件void creatCodeFile( II 创建报文文件int min(HuffmanTree t,int i; II 求无双亲且权值最小的结点，函数 void select( 调用void select(Huffma nTree t,i nt i,i nt &s1,i nt &s2;II si为最小的两个值中序号小的那个void prin t_huff_tree(Huffma nTree HT ,int n;II输出哈夫曼树，在必要时调用以验证算法的正确性void creatHuffma nTree( Huffma

6、 nTree &HT, int n;II创建含n叶子结点的哈夫曼树,字符及权值在文件 DataFile.dat中即初始化void Huffma nCod in g(Huffma nTree &HT,i nt n ;II对有n个叶子结点的哈夫曼树上的叶子结点进行编码void EnCoding(编码：对文件ToBeTran.dat中的文本进行编码，放在文件Code.txt中void Decoding( ; II译码：对文件CodeFile.dat中的报文进行译码，放在文件Textfile.txt 中void output( ; II输出原文和对应的译文；输出报文和对应的原文；五、主要算法的设计与实

7、现void creatHuffma nTree( Huffma nTree &HT, int nII创建含n叶子结点的哈夫曼树,字符及权值在文件DataFile.dat中即初始化InitialzationFILE *f1。int m,i,s1,s2。Huffma nTree p 。DFileNode s 。 / 从文件中读数据时用； m=2*n-1 。f1=fopen(DataFile.dat,rb 。HT=(HuffmanTreemalloc(m+1*sizeof(HTNode 。 /0 号单元未用 printf( 字符及相应的权值为： 。for(p=HT+1,i=1 。 i fread(&

8、s,1,sizeof(DFileNode,f1 。 / 从文件中读一个数给 s, 构造叶子 printf(%c,%d,s.ch,s.w 。(*p.ch=s.ch 。(*p.weight=s.w 。(*p.parent=0。(*p.lchild=0。(*p.rchild=0。(*p.next=NULL 。fclose(f1 。 printf(n 。for( 。 i (*p.ch= 。 (*p.parent=0 。 (*p.lchild=0。 (*p.rchild=0。 (*p.next=NULL 。for(i=n+1。i 建n-1 个分支结点 II 在HT1i-1中选择pare nt为0且wei

9、ght最小的两个结点,其序号分别为si和s2 select(HT,i-1,s1,s2。HTs1.parent=HTs2.parent=i。HTi.lchild=s1。HTi.rchild=s2。HTi.weight=HTs1.weight+HTs2.weight。void HuffmanCoding(HuffmanTree &HT,int nII对有n个叶子结点的哈夫曼树上的叶子结点进行编码char *cd 。int i,start,c,f。cd=(char*malloc(n*sizeof(char。 II 分配求编码的工作空间cdn-1=0。 II 编码结束符for(i=1 。 i II 逐

10、个字符求赫夫曼编码start=n-1 。 II 编码结束符位置for(c=i,f=HTi.parent。 f!=0 。 c=f,f=HTf.parentII 从叶子到根逆向求编码if(HTf.lchild=ccd-start=0。elsecd-start=1HTi.next=(char*malloc(n-start*sizeof(char 。/ 为第 i 个字符编码分配空间strcpy(HTi.next,&cdstart。/从cd复制编码(串到 HCfree(cd 。 / 释放工作空间void EnCoding(/ 编码 : 对文件 ToBeTran.dat 中的文本进行编码，放在文件 Cod

11、e.txt 中FILE *f1, *f2 。char c 。int s,i 。f1=fopen(ToBeTran.dat,r 。 / 打开文件 ToBeTran.dat 为了读 f2=fopen(Code.txt,w 。 / 打开文件 Code.txt 为了写/ printf( 原文： 。while(fread(&c,1,sizeof(char,f1 i=1。while(HTi.ch!=c i+。/printf(%c,c 。fputs(HTi.next,f2 。/printf(n 。fclose(f1 。fclose(f2。/f2=fopen(Code.txt,r。/printf(译文： 。/

12、while(fread(&c,1,sizeof(char,f2 putchar(c。/printf(n 。fclose(f2 。void Decoding( / 译码 : 对文件 CodeFile.dat 中的报文进行译码，放在文件 Textfile.txt 中FILE *f1, *f2 。char c 。int s,i,p 。f1=fopen(CodeFile.dat,rb 。 f2=fopen(Textfile.txt,w。/printf( 报文： 。p=2*char_num-1 。 /P 指向哈夫曼树的根while(fread(&s,1,sizeof(int,f1/ printf(%d,

13、s。if(s=0 p=HTp.lchild 。 else p=HTp.rchild。if(HTp.lchild=0 c=HTp.ch 。 fputc(c,f2 。 p=2*char_num-1 。 / 让P重新指向哈夫曼树的根 printf(n 。 fclose(f1 。 fclose(f2 。/f2=fopen(Textfile.txt,r 。 /printf( 原文： 。/while(fread(&c,1,sizeof(char,f2 putchar(c /printf(n 。/fclose(f2 。六、源程序见电子稿 ( 文件名为 : Huffman_Tree .cpp 。七、运行结果与

14、运行情况 第一次运行： 创建数据文件 DataFile.dat 请输入一段仅包含大写字母 A-H 的一段文字以 #结束 ABCHHDHFGEHDBCHDGFA# 字符及每个字符出现的次数 ( 字符，出现次数 (A ,2 , (B ,2 , (C ,2 ,(D ,3 ,(E ,1 , (F ,2 , (G ,2 , (H ,5初始的哈夫曼树 :字符权值双亲左孩子 右孩子 指向编码的指针A2900-(nullB21000-(nullC21000-(nullD31200-(nullE1900-(nullF21100-(nullG21100-(nullH51400-(null31215-(null41

15、323-(null41367-(null61449-(null8151011-(null1115812-(null1901314-(null编码后的哈夫曼树字符权值双亲左孩子 右孩子 指向编码的指针A2900-1110B21000-000C21000-001D31200-110E1900-1111F21100-010G21100-011H 51400-1031215-(null41323-(null41367-(null61449-(null8151011-(null1115812-(null1901314-(null字符 A 的编码为 :1110字符 D 的编码为 :110字符 B 的编码为

16、 :000字符 E 的编码为 :1111字符 C 的编码为 :001字符 F 的编码为 :010字符 G 的编码为 :011字符 H 的编码为 :10创建原文文件 , 请输入一段仅包含大写字母 A-H 的一段文字作为原文以 #结束ABCGDBCHFE#原文： ABCGDBCHFE译文： 1110000001011110000001100101111创建报文文件 , 请输入一段仅包含 0 和 1的一段文字作为原文以 2 作为结束标志 输入报文中的第一个代码 0 或 1 0 0 0 0 1 1 1 0 0 1 0 1 0 报文 :0000111001010 原文 :BGHFH 第二次运行 创建数据

17、文件 DataFile.dat 请输入一段仅包含大写字母 A-H 的一段文字以 #结束 AABABABABABAEGHF#字符及每个字符出现的次数 ( 字符，出现次数 (A ,7 , (B ,5 , (C ,0 , (D ,0 , (E ,1 , (F ,1 , (G ,1 , (H ,1 , 初始的哈夫曼树 :字符权值双亲左孩子右孩子 指向编码的指针A71500-(nullB51400-(nullC0900-(nullD0900-(nullE11000-(nullF11100-(nullG11100-(nullH11200-(null01034-(null11259-(null21367-(

18、null213810-(null4141112-(null915213-(null160114-(null编码后的哈夫曼树字符权值双亲左孩子 右孩子指向编码的指针A71500-0B51400-10C0900-111110D0900-111111E11000-11110F11100-1100G11100-1101H11200-111001034-(null11259-(null21367-(null213810-(null4141112-(null915213-(null160114-(null字符 A 的编码为:0字符 B 的编码为:10字符 C 的编码为:111110字符 D 的编码为:111111字符 E 的编码为:11110字符 F 的编码为:1100字符 G 的编码为:1101字符 H 的编码为:1110创建原文文件 , 请输入一段仅包含大写字母 A-H 的一段文字作为原文以 #结束ABCBDGFBCGD#原文： ABCBDGFBCGD译文： 0101111101011111111011100101111101101111111创建报文文件 , 请输入一段仅包含 0 和 1的一段文字作为原文以 2 作为结束标志 .输入报文中的第一个代码 0 或 10 0 0 1 0 1 0 1 0 1 0 0 0 20 0 0 1 0 1 0 1 0 1 0 0 0