实验报告哈夫曼编译码系统的设计与实现

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

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

3、extfile.txt；备注：1）数据文件DataFile.dat中，元素类型为（字符，权值） , DataFile.dat的建立可以根据用户输入的一段原文，通过统计出现的字符及各字符出现的次数（与出现的概率作用相同）而得到。另：为了使输出的哈夫曼树不太大，规定报文中只能出现A-H的8个字符，当然对程序稍加修改就可以对出现的所有可输和字符进行处理。2）ToBeTran.dat中的内容由用户在程序执行时从键盘随机输入得到；3）CodeFile.dat中的内容由用户在程序执行时从键盘随机输入得到；DataFile.dat、ToBeTran.dat、CodeFile.dat在程序运行时建立是为了保证

4、编/译码系统的通用性； 三总的设计思想，及环境语言、工具等总的设计思想：1根据实验要求，先创建文件DataFile.dat、ToBeTran.dat和CodeFile.dat；用下面三个函数实现；void creatDataFile( )； /创建数据文件void creatToBeTran( )；/创建原文文件 void creatCodeFile( )；/创建报文文件 2.从文件DataFile.dat中读出各字符及相应的权值，创建哈夫曼树HT；3.根据构造的哈夫曼树，求相应字符的哈夫曼编码；4从文件ToBeTran.dat中读出要翻译的原文，将其翻译成译文存入文件Code.txt中5从文

5、件CodeFile.dat中读出要翻译的报文，将其翻译成原文存入文件Textfile.txt中环境语言：Windows下的Microsoft VC+四、数据结构与模块说明下面是编译码系统中所用的数据结构。在这个系统中，哈夫曼树的存储结构采用顺序存储；其结点结构为：程序中用到的头文件、类型定义及主要的函数原型如下：#include"stdio.h"#include"malloc.h"#include"string.h"#define char_num 8 typedef struct char ch ; int w; DFileNode

6、 ;/ 定义数据文件的元素类型typedef struct /赫夫曼树和赫夫曼编码的存储表示 char ch; /相应字符 int weight;/字符的权值 int parent,lchild,rchild;/双亲、左、右孩子指针（下标） char *next; / 指向该字符的编码的指针 HTNode,*HuffmanTree; / 动态分配数组存储赫夫曼树HuffmanTree HT;void creatDataFile( )/创建数据文件void creatToBeTran( )/创建原文文件 void creatCodeFile( )/创建报文文件int min(HuffmanTre

7、e t,int i)；/ 求无双亲且权值最小的结点，函数void select()调用void select(HuffmanTree t,int i,int &s1,int &s2)；/ s1为最小的两个值中序号小的那个void print_huff_tree(HuffmanTree HT ,int n)；/输出哈夫曼树，在必要时调用以验证算法的正确性 void creatHuffmanTree( HuffmanTree &HT, int n)； /创建含n叶子结点的哈夫曼树,字符及权值在文件DataFile.dat中即初始化 void HuffmanCoding(Hu

8、ffmanTree &HT,int n)； /对有n个叶子结点的哈夫曼树上的叶子结点进行编码void EnCoding()/编码:对文件ToBeTran.dat中的文本进行编码，放在文件Code.txt中void Decoding( )；/译码:对文件CodeFile.dat中的报文进行译码，放在文件Textfile.txt中void output( )；/输出原文和对应的译文；输出报文和对应的原文；五、主要算法的设计与实现void creatHuffmanTree( HuffmanTree &HT, int n) /创建含n叶子结点的哈夫曼树,字符及权值在文件DataFile

9、.dat中即初始化Initialzation FILE *f1; int m,i,s1,s2; HuffmanTree p; DFileNode s; /从文件中读数据时用； m=2*n-1; f1=fopen("DataFile.dat","rb"); HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0号单元未用 printf("字符及相应的权值为："); for(p=HT+1,i=1;i<=n;+i,+p) fread(&s,1,sizeof(DFileNode),f1);

10、/从文件中读一个数给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<=m;+i,+p) (*p).ch=' '(*p).parent=0;(*p).lchild=0;(*p).rchild=0;(*p).next=NULL; for(i=n+1;i<=m;+i)

11、/建n-1个分支结点 / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和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 n) /对有n个叶子结点的哈夫曼树上的叶子结点进行编码 char *cd; int i,start,c,f; cd=(char*)malloc(n*sizeof(cha

12、r); / 分配求编码的工作空间 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' HTi.next=(char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(HTi.next,&

13、cdstart); / 从cd复制编码(串)到HC free(cd); / 释放工作空间 void EnCoding()/编码:对文件ToBeTran.dat中的文本进行编码，放在文件Code.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(fr

14、ead(&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("译文："); /while(fread(&c,1,sizeof(char),f2) putchar(c); /printf("n"); f

15、close(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) / p

16、rintf("%d",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) pu

17、tchar(c); /printf("n"); /fclose(f2);六、源程序见电子稿(文件名为: Huffman_Tree .cpp ); 七、运行结果与运行情况第一次运行：创建数据文件DataFile.dat请输入一段仅包含大写字母A-H的一段文字以#结束ABCHHDHFGEHDBCHDGFA#字符及每个字符出现的次数(字符，出现次数)(A ,2) , (B ,2) , (C ,2) , (D ,3) , (E ,1) , (F ,2) , (G ,2) , (H ,5)初始的哈夫曼树:字符 权 值 双 亲 左孩子 右孩子 指向编码的指针 A 2 9 0 0 -&g

18、t;(null) B 2 10 0 0 ->(null) C 2 10 0 0 ->(null) D 3 12 0 0 ->(null) E 1 9 0 0 ->(null) F 2 11 0 0 ->(null) G 2 11 0 0 ->(null) H 5 14 0 0 ->(null) 3 12 1 5 ->(null) 4 13 2 3 ->(null) 4 13 6 7 ->(null) 6 14 4 9 ->(null) 8 15 10 11 ->(null) 11 15 8 12 ->(null) 1

19、9 0 13 14 ->(null)编码后的哈夫曼树:字符 权 值 双 亲 左孩子 右孩子 指向编码的指针 A 2 9 0 0 ->1110 B 2 10 0 0 ->000 C 2 10 0 0 ->001 D 3 12 0 0 ->110 E 1 9 0 0 ->1111 F 2 11 0 0 ->010 G 2 11 0 0 ->011 H 5 14 0 0 ->10 3 12 1 5 ->(null) 4 13 2 3 ->(null) 4 13 6 7 ->(null) 6 14 4 9 ->(null)

20、8 15 10 11 ->(null) 11 15 8 12 ->(null) 19 0 13 14 ->(null)字符A的编码为:1110 字符B的编码为:000 字符C的编码为:001字符D的编码为:110 字符E的编码为:1111 字符F的编码为:010字符G的编码为:011 字符H的编码为:10创建原文文件,请输入一段仅包含大写字母A-H的一段文字作为原文以#结束ABCGDBCHFE#原文：ABCGDBCHFE译文：0101111创建报文文件,请输入一段仅包含0和1的一段文字作为原文以2作为结束标志.输入报文中的第一个代码0或1（为整数类型)0 0 0 0 1 1

21、1 0 0 1 0 1 0 20 0 0 0 1 1 1 0 0 1 0 1 0 报文:0原文:BGHFH第二次运行创建数据文件DataFile.dat请输入一段仅包含大写字母A-H的一段文字以#结束AABABABABABAEGHF#字符及每个字符出现的次数(字符，出现次数)(A ,7) , (B ,5) , (C ,0) , (D ,0) , (E ,1) , (F ,1) , (G ,1) , (H ,1) ,初始的哈夫曼树:字符 权 值 双 亲 左孩子 右孩子 指向编码的指针 A 7 15 0 0 ->(null) B 5 14 0 0 ->(null) C 0 9 0 0

22、->(null) D 0 9 0 0 ->(null) E 1 10 0 0 ->(null) F 1 11 0 0 ->(null) G 1 11 0 0 ->(null) H 1 12 0 0 ->(null) 0 10 3 4 ->(null) 1 12 5 9 ->(null) 2 13 6 7 ->(null) 2 13 8 10 ->(null) 4 14 11 12 ->(null) 9 15 2 13 ->(null) 16 0 1 14 ->(null)编码后的哈夫曼树:字符 权 值 双 亲 左孩子

23、 右孩子 指向编码的指针 A 7 15 0 0 ->0 B 5 14 0 0 ->10 C 0 9 0 0 ->111110 D 0 9 0 0 ->111111 E 1 10 0 0 ->11110 F 1 11 0 0 ->1100 G 1 11 0 0 ->1101 H 1 12 0 0 ->1110 0 10 3 4 ->(null) 1 12 5 9 ->(null) 2 13 6 7 ->(null) 2 13 8 10 ->(null) 4 14 11 12 ->(null) 9 15 2 13 ->(null) 16 0 1 14 ->(null)字符A的编码为:0 字符B的编码为:10 字符C的编码为:111110字符D的编码为:111111 字符E的编码为:11110 字符F的编码为:1100字符G的编码为:1101 字符H的编码为:1110创建原文文件,请输入一段仅包含大