哈夫曼编、译码器2

韶关学院学生实验报告册实验课程名称：数据结构与算法实验项目名称：实验六树及其应用哈夫曼编/译码器实验类型（打√）：（基础、综合、设计√）院系：信息工程学院计算机系专业：*****姓名：***学号：*****指导老师：陈正铭韶关学院教务处编制一、实验预习报告内容预习日期：2007年实验预习报告内容原则上应包括实验目的、实验所用的主要仪器药品、实验原理与公式、实验预习疑问等项目。【实验目的】熟练掌握非线性数据结构二叉树树的操作，熟悉树的各种存储结构特性，以及如何应用树解决具体问题。【需要分析】利用哈夫曼编码进行通信可以大大提高信道利用率，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。试为这样的信息收发写一个哈夫曼编/译码系统，要求具备以下功能：初始化、编码、译码、印代码文件、印哈夫曼树。一个完整的哈夫曼码的编译码系统系统应具有以下功能：（1）I:初始化(Initialization)。从终端读入字符集大小n，几个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree中。（2）C:编码(Coding)。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。（3）D:译码(Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。（4）P:打印代码文件(Print)。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。（5）T:打印哈夫曼树(Treeprinting)。将已在内存中的哈夫曼树以直观的方式（数或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。【软件平台】Windows2000，VisualC＋＋6.0或WINTC【概要设计】ADTArray{数据对象:D是具有相同特性的数据元素的集合。数据关系:若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。基本操作：StatusinitHTree(HuffmanTree&T,intn)//初始化一个n个字符集的哈夫曼树StatusDestroyHTree(HuffmanTree&T)//销毁哈夫曼树StatusSelect(int&s1,int&s2,intn,PHTNodeH)//从二叉树位置从0~n集合中找到2个根结点的权值最小的位置StatusHEncoding(charstring[SIZE])//哈夫曼编码,并把结果保存在string文件中StatusHDecoding(charstring[SIZE])//哈夫曼译码,并把结果保存在string文件中}ADTArray【疑问】（这部分内容因人而异，也可不写）实验预习评分：二、实验原始（数据）记录实验时间：2007年6月13日（星期三第7，8节）实验同组人：如有实验实验数据表格，学生在实验预习时应画好实验数据表格，供实验填写数据。*******************************************************************************本程序的命令:(1)创建哈夫曼树C;(2)对指定的文件现行编码E;(3)对指定的代码进行译码D;(4)退出程序Q.*******************************************************************************请输入命令(C,E,D,Q):C请输入字符集的大小(n):27请输入字集的保存路径\名称:c:\charset.txt请输入字符集对应的权值::186A:64D:32E:103F:H:47I:57J:1K:5L:32M:20P:15Q:1R:48S:51T:80U:23V:8W:18X:1Y:16Z:1请输入哈夫曼树的保存路径\名称:c:\hfmtree.txt请输入任意键继续运行程序请输入命令(C,E,D,Q):E请输入保存哈夫曼树的保存路径\名称:c:\hfmtree.txt请输入要编码文件的保存路径\名称:c:\textfile.txt请输入代码文件的保存路径\名称:codefile.txt哈夫曼编码的结果:1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010请输入任意键继续运行程序请输入命令(C,E,D,Q):D请输入保存哈夫曼树的保存路径\名称:c:\hfmtree.txt请输入代码文件的保存路径\名称:c:\codefile.txt请输入译码文件的保存路径\名称:c:\decode.txt哈夫曼译码的结果:THISPROGRAMISMYFAVORITE指导教师批阅及签名三、实验报告内容

2007年6实验报告内容原则上应包括主要实验步骤、实验数据计算（实验操作）结果、实验结果（疑问）分析等项目。【主程序模块】：voidmain(){初始化;do{接受命令;处理命令;}while(命令!=“退出”)；}【功能模块调用关系图】主程序模块主程序模块创建哈夫曼树创建哈夫曼树模块哈夫曼编码哈夫曼编码模块哈夫曼译码哈夫曼译码模块【详细设计】typedefstructHTNode//哈夫曼树结点类型{intweight;//结点的权值intparent,lchild,rchild;//结点的双亲parent,结点的左子树lchild,结点的右子树rchild}*PHTNode;structHuffmanTree//哈夫曼树类型{HTNode*HT;//哈夫曼树ElemTypech;//哈夫曼树的字符集intn;//哈夫曼树的字符集个数};StatusinitHTree(HuffmanTree&T,intn)//初始化一个n个字符集的哈夫曼树StatusDestroyHTree(HuffmanTree&T)//销毁哈夫曼树StatusSelect(int&s1,int&s2,intn,PHTNodeH)//从二叉树位置从0~n集合中找到2个根结点的权值最小的位置StatusHEncoding(charstring[SIZE])//哈夫曼编码,并把结果保存在string文件中StatusHDecoding(charstring[SIZE])//哈夫曼译码,并把结果保存在string文件中StatusOpenWriteFile(PFILE&fp,charstring[SIZE])//打开写的文件StatusOpenReadFile(PFILE&fp,charstring[SIZE])//打开读的文件StatusPrintFile(charstring[SIZE])//输出文件名为string的字符【调试分析】（这部分内容因人而异）这里最大的问题就是文件的运用了，一开始，我用的是freopen()函数，这个函数能完成在文件里面的输入输出操作，但是无法完成在屏幕上显示出来。后来，查了课本，发现fopen(),fclose()更好用。【用户手册】本程序运行环境为ＤＯＳ，执行文件为：haffman.exe.进入演示程序后，出现提示信息：——进行相应输入后程序执行相应操作，显示相应结果。实验报告评分：注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。【源程序】#include<iostream.h>#include<stdlib.h>#include<process.h>#include<conio.h>#include<stdio.h>#defineERROR0#defineOK1typedefboolStatus;#defineSIZE20typedefFILE*PFILE;typedefchar*ElemType;typedefstructHTNode//哈夫曼树结点类型{intweight;//结点的权值intparent,lchild,rchild;//结点的双亲parent,结点的左子树lchild,结点的右子树rchild}*PHTNode;structHuffmanTree//哈夫曼树类型{HTNode*HT;//哈夫曼树ElemTypech;//哈夫曼树的字符集intn;//哈夫曼树的字符集个数};StatusOpenWriteFile(PFILE&fp,charstring[SIZE])//打开写的文件{if(!(fp=fopen(string,"wb"))){cout<<"文件打开失败"<<endl;exit(ERROR);cout<<"Pressanykeytoexit"<<endl;getch(); }returnOK;}StatusOpenReadFile(PFILE&fp,charstring[SIZE])//打开读的文件{if(!(fp=fopen(string,"rb"))){cout<<"文件打开失败"<<endl;cout<<"Pressanykeytoexit"<<endl;getch();exit(ERROR);}returnOK;}StatusPrintFile(charstring[SIZE])//输出文件名为string的字符{FILE*fp;charc;OpenReadFile(fp,string);while(!feof(fp)){for(inti=1;i<=50&&!feof(fp);i++){c=getc(fp);cout<<c;}cout<<endl;}fclose(fp);returnOK;}StatusinitHTree(HuffmanTree&T,intn)//初始化一个n个字符集的哈夫曼树{T.n=n;if(!(T.HT=newHTNode[2*T.n])){cout<<"分配哈夫曼树的存储空间失败"<<endl;exit(ERROR);}if(!(T.ch=newchar[T.n+1])){cout<<"分配字符集的存储空间失败"<<endl;exit(ERROR);}returnOK;}StatusDestroyHTree(HuffmanTree&T)//销毁哈夫曼树{delete(T.HT);delete(T.ch);returnOK;}StatusSelect(int&s1,int&s2,intn,PHTNodeH)//从二叉树位置从0~n集合中找到2个根结点的权值最小的位置{inti,leap=0;for(i=1;i<=n;i++)if(!H[i].parent)if(leap){if(H[i].weight<H[s1].weight) s1=i;}else{s1=i;leap=1;}leap=0;H[s1].parent=1;for(i=1;i<=n;i++)if(!H[i].parent)if(leap){if(H[i].weight<H[s2].weight) s2=i;}else{s2=i;leap=1;}returnOK; }StatusCreateHTree()//创建哈夫曼树并把结果保存在string为文件名的文件里{inti,s1,s2;FILE*fp,*cfp;charc,string[SIZE];HuffmanTreeT;intn;cout<<"请输入字符集的大小(n):";cin>>n;initHTree(T,n);cout<<"请输入字集的保存路径\\名称:";cin>>string;OpenReadFile(cfp,string);cout<<"请输入字符集对应的权值:"<<endl;for(i=1;i<=T.n;i++){c=getc(cfp);cout<<c<<":";T.ch[i]=c;cin>>T.HT[i].weight;T.HT[i].parent=0;T.HT[i].rchild=0;T.HT[i].lchild=0;}for(;i<2*T.n;i++){T.HT[i].weight=0;T.HT[i].parent=0;T.HT[i].rchild=0;T.HT[i].lchild=0;}for(i=T.n+1;i<2*T.n;i++){Select(s1,s2,i-1,T.HT);T.HT[i].lchild=s1;T.HT[i].rchild=s2;T.HT[s1].parent=i;T.HT[s2].parent=i;T.HT[i].weight=T.HT[s1].weight+T.HT[s2].weight;}cout<<"请输入哈夫曼树的保存路径\\名称:";cin>>string;OpenWriteFile(fp,string);fwrite(&T.n,sizeof(int),1,fp);fwrite(T.HT,sizeof(HTNode),2*T.n,fp);fwrite(T.ch,sizeof(char),T.n+1,fp);fclose(fp);fclose(cfp);DestroyHTree(T);returnOK;}StatusHEncoding(charstring[SIZE])//哈夫曼编码,并把结果保存在string文件中{HuffmanTreeT;FILE*fp,*hfp,*cfp;inti,j,k;charch[SIZE],c,*cd;cout<<"请输入保存哈夫曼树的保存路径\\名称:";cin>>ch;OpenReadFile(hfp,ch);cout<<"请输入要编码文件的保存路径\\名称:";cin>>ch;OpenReadFile(fp,ch);cout<<"请输入代码文件的保存路径\\名称:";cin>>string;OpenWriteFile(cfp,string);fread(&T.n,sizeof(int),1,hfp);if(!(cd=newchar[T.n])){cout<<"编码工作空间分配失败"<<endl;exit(ERROR);}initHTree(T,T.n);fread(T.HT,sizeof(HTNode),2*T.n,hfp);fread(T.ch,sizeof(char),T.n+1,hfp);c=getc(fp);while(!feof(fp)){for(i=1;i<=T.n&&c!=T.ch[i];i++);j=T.n;k=i; while(T.HT[k].parent)if(T.HT[T.HT[k].parent].lchild==k){cd[--j]='0'; k=T.HT[k].parent;}else{cd[--j]='1'; k=T.HT[k].parent;}for(j;j<T.n;j++)putc(cd[j],cfp);c=getc(fp);}DestroyHTree(T);delete(cd);fclose(cfp);fclose(hfp);fclose(fp);returnOK;}StatusHDecoding(charstring[SIZE])//哈夫曼译码,并把结果保存在string文件中{HuffmanTreeT;charch[SIZE],c;FILE*fp,*hfp,*cfp;cout<<"请输入保存哈夫曼树的保存路径\\名称:";cin>>ch;OpenReadFile(hfp,ch);fread(&T.n,sizeof(int),1,hfp);initHTree(T,T.n);fread(T.HT,sizeof(HTNode),2*T.n,hfp);fread(T.ch,sizeof(char),T.n+1,hfp);voidPrintHTree(HuffmanTreeT);cout<<"请输入代码文件的保存路径\\名称:";cin>>ch;OpenReadFile(cfp,ch);cout<<"请输入译码文件的保存路径\\名称:";cin>>string;OpenWriteFile(fp,string);c=ge