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

河南师范大学计算机与信息技术学院实验报告数据结构实验报告学号0928724099姓名李晓松年级2009班级网络工程5班机号：学院机房时间周三下午2点半-4点周四上午8点-10点指导教师张磊实验题目：理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；通过该实验,对数据结构的应用有更深层次的理解。实验要求：1．问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。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及其原文Textfile.txt；[备注]：1）数据文件DataFile.dat中，元素类型为（字符，权值）,DataFile.dat的建立可以根据用户输入的一段原文，通过统计出现的字符及各字符出现的次数（与出现的概率作用相同）而得到。另：为了使输出的哈夫曼树不太大，规定报文中只能出现A-H的8个字符，当然对程序稍加修改就可以对出现的所有可输和字符进行处理。2）ToBeTran.dat中的内容由用户在程序执行时从键盘随机输入得到；3）CodeFile.dat中的内容由用户在程序执行时从键盘随机输入得到；DataFile.dat、ToBeTran.dat、CodeFile.dat在程序运行时建立是为了保证编/译码系统的通用性；三．总的设计思想，及环境语言、工具等总的设计思想：1．根据实验要求，先创建文件DataFile.dat、ToBeTran.dat和CodeFile.dat；用下面三个函数实现；voidcreatDataFile()；//创建数据文件voidcreatToBeTran()；//创建原文文件voidcreatCodeFile()；//创建报文文件河南师范大学计算机与信息技术学院实验报告2.从文件DataFile.dat中读出各字符及相应的权值，创建哈夫曼树HT；3.根据构造的哈夫曼树，求相应字符的哈夫曼编码；4．从文件ToBeTran.dat中读出要翻译的原文，将其翻译成译文存入文件Code.txt中5．从文件CodeFile.dat中读出要翻译的报文，将其翻译成原文存入文件Textfile.txt中环境语言：Windows下的MicrosoftVC++四、数据结构与模块说明下面是编译码系统中所用的数据结构。在这个系统中，哈夫曼树的存储结构采用顺序存储；其结点结构为：程序中用到的头文件、类型定义及主要的函数原型如下：#includestdio.h#includemalloc.h#includestring.h#definechar_num8typedefstruct{charch;intw;}DFileNode;//定义数据文件的元素类型typedefstruct//赫夫曼树和赫夫曼编码的存储表示{charch;//相应字符intweight;//字符的权值intparent,lchild,rchild;//双亲、左、右孩子指针（下标）char*next;//指向该字符的编码的指针}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树HuffmanTreeHT;voidcreatDataFile()//创建数据文件voidcreatToBeTran()//创建原文文件voidcreatCodeFile()//创建报文文件intmin(HuffmanTreet,inti)；//求无双亲且权值最小的结点，函数voidselect()调用voidselect(HuffmanTreet,inti,int&s1,int&s2)；//s1为最小的两个值中序号小的那个voidprint_huff_tree(HuffmanTreeHT,intn)；//输出哈夫曼树，在必要时调用以验证算法的正确性voidcreatHuffmanTree(HuffmanTree&HT,intn)；//创建含n叶子结点的哈夫曼树,字符及权值在文件DataFile.dat中即初始化voidHuffmanCoding(HuffmanTree&HT,intn)；//对有n个叶子结点的哈夫曼树上的叶子结点进行编码voidEnCoding()//编码:对文件ToBeTran.dat中的文本进行编码，放在文件Code.txt中voidDecoding()；//译码:对文件CodeFile.dat中的报文进行译码，放在文件Textfile.txt中voidoutput()；//输出原文和对应的译文；输出报文和对应的原文；五、主要算法的设计与实现voidcreatHuffmanTree(HuffmanTree&HT,intn){//创建含n叶子结点的哈夫曼树,字符及权值在文件DataFile.dat中即初始化InitialzationFILE*f1;intm,i,s1,s2;河南师范大学计算机与信息技术学院实验报告HuffmanTreep;DFileNodes;//从文件中读数据时用；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);//从文件中读一个数给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)//建n-1个分支结点{//在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}}voidHuffmanCoding(HuffmanTree&HT,intn)//对有n个叶子结点的哈夫曼树上的叶子结点进行编码{char*cd;inti,start,c,f;cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间cd[n-1]='\0';//编码结束符for(i=1;i=n;i++){//逐个字符求赫夫曼编码start=n-1;//编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]='0';else河南师范大学计算机与信息技术学院实验报告cd[--start]='1';HT[i].next=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HT[i].next,&cd[start]);//从cd复制编码(串)到HC}free(cd);//释放工作空间}voidEnCoding()//编码:对文件ToBeTran.dat中的文本进行编码，放在文件Code.txt中{FILE*f1,*f2;charc;ints,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(HT[i].ch!=c)i++;//printf(%c,c);fputs(HT[i].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);fclose(f2);}voidDecoding()//译码:对文件CodeFile.dat中的报文进行译码，放在文件Textfile.txt中{FILE*f1,*f2;charc;ints,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,s);if(s==0)p=HT[p].lchild;elsep=HT[p].rchild;if(HT[p].lchild==0){c=HT[p].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);七、运行结果与运行情况第一次运行：创建数据文件DataFile.dat请输入一段仅包含大写字母A--H的一段文字以#结束ABCHHDHFGEHDBCHDGFA#字符及每个字符出现的次数(字符，出现次数)(A,2),(B,2),(C,2),(D,3),(E,1),(F,2),(G,2),(H,5)初始的哈夫曼树:字符权值双亲左孩子右孩子指向编码的指针A2900-(null)B21000-(null)C21000-(null)D31200-(null)E1900-(null)F21100-(null)G21100-(null)H51400-(null)31215-(null)41323-(null)41367-(null)61449-(null)8151011-(null)1115812-(null)1901314-(null)编码后的哈夫曼树:字符权值双亲左孩子右孩子指向编码的指针A2900-1110B21000-000C21000-001D31200-110E1900-1111F21100-010河南师范大学计算机与信息技术学院实验报告G21100-011H51400-1031215-(n