哈夫曼编码译码系统.doc

数 据 结 构 课 程 设 计6.5电文的编码和译码姓 名: XXX院系: 计算机学院专 业: 计算机科学与技术年 级: 13级学 号: E11314XXX指导教师:XXX2015年 10月 30 日目录1.课程设计的目的32.需求分析33电文的编码和译码的设计33.1概要设计33.1.1主界面设计33.1.2存储结构43.1.3系统功能设计43.2详细设计43.2.1系统子程序及功能设计43.2.2数据类型定义63.2.3系统主要子程序详细设计73.3调试分析113.4用户手册124总结125、程序清单:(见附录)127、程序运行结果12附录118 39 / 391.课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。2.需求分析(1) 为信息收发站写一个哈夫曼编/译码系统。(2) 要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。(3) 要求可以将哈夫曼树以树状或凹入法打印到屏幕。3电文的编码和译码的设计3.1概要设计3.1.1主界面设计图 1主界面，如图1所示，包含初始化，编码，译码，代码文件，哈夫曼树五个菜单。其中，菜单1用来从终端读入n个字符和n个权值，建立哈夫曼树，并将它存于文件中; 菜单2用来利用已建好的哈夫曼树，对文件中或直接输入的正文进行编码，然后将结果存入文件中，如果哈夫曼树不在内存可通过初始化或文件读入到内存；菜单3利用已建好的哈夫曼树将文件中的代码进行译码，译码结果存入文件中，若哈夫曼树不在内存中，处理方式与菜单2相同；菜单4将编码文件以紧凑格式显示在终端上，每行50个代码,同时将此字符形式的编码写入文件中；菜单5将已在内存中的哈夫曼树以凹入法显示在终端上。3.1.2存储结构这里使用了4个结构体。结构体HTNode存放哈夫曼树的结点，包含权值weight，以及父节点parent、左孩子lchild、右孩子rchild所在位置。结构体Huffmantree保存哈夫曼树, 其中num是结点数，参与哈夫曼编码的各个字符alphabet，hftree是HTNode类型存放构建的哈夫曼树的表，HCnum是每个字符编码的长度，HC是编码字符数组。结构体Text保存正文，其中num存放正文的长度，content存放正文内容。Code存放编码结果，num是编码长度，bin是编码内容。3.1.3系统功能设计本系统的功能描述如下：1 可输入字符和其对应的权值，以构建哈夫曼树。2 可输入或读入正文，根据构建的哈夫曼树，对正文进行编码,若哈夫曼树未存在，可从文件中读入或者初始化输入，若正文中字符在哈夫曼树中不存在，则会提示编码出错。3 可读入编码文件，根据存在的哈夫曼树，对文件进行解码，若哈夫曼树不存在会进行和2一样的操作，若解码时，编码在哈夫曼树中不存在，则提示解码出错。4 可根据内存中的哈夫曼树用凹入表示法输出树形界面。3.2详细设计3.2.1系统子程序及功能设计本系统设置32个函数，函数名及功能说明如下：void HufftreeInit(Huffmantree & H)/对结构体Huffmantree初始化void HufftreeMalloc(Huffmantree & H,int num)/给结构体Huffmantree分配空间void TextInit(Text & c)/结构体Text初始化void TextMalloc(Text & c,int num)/给结构体Text分配存储空间void CodeInit(Code & co)/给结构体code初始化void CodeMalloc(Code & co,int num)/给结构体code分配存储空间int inputselection(int n)/输入菜单选择，返回值为输入的选项int TreeRead(Huffmantree &H)/读取哈夫曼树文件int TreeSave(Huffmantree H)/保存结构体Huffmantreeint TextSave(Text c)/保存结构体Textint TextRead(Text &c)/读取结构体Textint CodeSave(Code & co)/保存结构体Codeint CodeSave2(Code & co)/以紧凑形式保存结构体Codeint CodeRead(Code & co)/读取结构体Codeint istrue()/判断是否输入了Yvoid exchange(int s)/交换s0和s1中的内容void Select(HTNode HT,int i,int s)/找到parent为0且weight最小的两个结点,序号放在s0和s1void Huffmancoding(Huffmantree &HT)/哈弗曼编码int exist(Huffmantree HT,int index)/判断HT.alphabetindex是否与其他结点重复void initialization(Huffmantree &HT)/初始化int encodingcourse()/编码菜单void inputtext(Text &text)/输入正文void encode(Huffmantree HT,Text text)/编码保存至文件void encoding(Huffmantree &HT)/编码菜单int decodingcourse()/解码菜单char * substring(Code co,int beginning,int ending)/求子串，从beginning到endingvoid decode(Huffmantree HT)/解码void decoding(Huffmantree &HT)/解码菜单void print()/印代码文件int maincourse()/主菜单void welcom()/欢迎界面void treeprinting(Huffmantree HT,int index,int level,char*filename,int fla)/凹入法印哈夫曼树void hfmtreeprinting(Huffmantree HT)/用凹入法印哈弗曼树,包含文件输入各主要函数之间的调用关系如下:(见下页)主菜单Huffmancoding(Huffmantree &HT);TreeSave(Huffmantree H);initialization(Huffmantree &HT)inputtext(Text &text)encode(Huffmantree HT,Text text)TreeRead(Huffmantree &H)TextSave(Text c)TextRead(Text &c)CodeSave(Code & co)encoding(Huffmantree &HT)TreeRead(Huffmantree &H)decode(Huffmantree HT)CodeRead(Code & co)decoding(Huffmantree &HT)print()treeprinting()hfmtreeprinting(Huffmantree H)3.2.2数据类型定义struct HTNode/哈夫曼树的结点Elemtype weight;int parent,lchild,rchild;struct Huffmantree/哈夫曼树int num;char * alphabet;/字符数组HTNode * hftree;/结点数组int * HCnum;/每个字符对应编码的长度BIN * * HC;/每个字符的编码;struct Text/正文int num;/正文长度char * content;/正文;struct Code/编码，用字符型数字表示int num;/编码长度BIN * bin;/编码;3.2.3系统主要子程序详细设计哈夫曼编码:void exchange(int s)/交换s0和s1中的内容int temp;temp=s0;s0=s1;s1=temp;void Select(HTNode HT,int i,int s)/找到parent为0且weight最小的两个结点,序号放在s0和s1int j,flag=0;for(j=1;j=i&flagHTs1.weight)exchange(s);for(;j=i;j+)if(!HTj.parent)if(HTj.weightHTs1.weight)exchange(s);void Huffmancoding(Huffmantree &HT)/哈弗曼编码int m,i,start,f,n=HT.num;int s2;unsigned c;char * cd;m=2*n-1;for(i=n+1;i=m;i+)Select(HT.hftree,i-1,s);HT.hftrees0.parent=i;HT.hftrees1.parent=i;HT.hftreei.lchild=s0;HT.hftreei.rchild=s1;HT.hftreei.parent=0;HT.hftreei.weight=HT.hftrees0.weight+HT.hftrees1.weight;cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=HT.hftreei.parent;f!=0;c=f,f=HT.hftreef.parent)if(HT.hftreef.lchild=c) cd-start=0;else cd-start=1;HT.HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HT.HCi,&cdstart);HT.HCnumi=strlen(HT.HCi);free(cd);给正文编码:void encode(Huffmantree HT,Text text)/编码保存至文件system(cls);Code c;cout-n;cout 正文编码 n;cout-n;if(HT.num=0)cout哈夫曼树不存在,请初始化或读入后编码!endl;system(pause);return;if(text.num=0)cout正文不存在,请输入或读入正文后编码!endl;system(pause);return;char code26*N=0;for(int i=0;itext.num;i+)/itext.numfor(int j=1;jHT.num)cout编码出错!endl;system(pause);return;elsestrcat(code,HT.HCj);CodeMalloc(c,strlen(code);strcpy(c.bin,code);cout编码结果为:codeendl;cout编码结果将保存到文件.endl;if(CodeSave(c)cout保存成功!endl;elsecout保存失败!endl;system(pause);正文解码：void decode(Huffmantree HT)/解码system(cls);cout-n;cout 读取文件译码 n;cout-n;if(HT.num=0)cout哈夫曼树不存在,请初始化或读入后编码!endl;return;Code co;int flag,i,j,k;char * s;char temptextN+1;int textindex=0;cout将从文件中读取编码.endl;CodeInit(co);if(CodeRead(co)co.binco.num=0;cout读取内容为:co.binendl;cout读取成功!endl;elsecout读取失败!返回!endl;return ;for(i=0;ico.num;i=j+1)for(j=i;jco.num;j+)flag=0;s=substring(co,i,j);for(k=1;kHT.num)cout解码出错!endl;system(pause);return;temptexttextindex=0;cout译码结果为:temptextendl;cout是否保存译码结果到文件?;if(istrue()Text text;TextInit(text);text.num=strlen(temptext);TextMalloc(text,text.num);strcpy(text.content,temptext);if(TextSave(text)cout保存成功!endl;elsecout保存失败!endl;elsecout返回上级菜单!endl;凹入法印哈夫曼树：void treeprinting(Huffmantree HT,int index,int level,char * filename,int flag)/凹入打印哈夫曼树if(index2*HT.num-1)return;ofstream outfile(filename,ios:app);for(int i=0;ilevel;i+)if(flag)outfile ;cout ;if(index=HT.num)if(HT.alphabetindex= )if(flag)outfileblankendl;/空格用blank表示coutblankendl;elsecoutHT.alphabetindexendl;outfileHT.alphabetindexendl;elseif(flag)outfile(int)HT.hftreeindex.weightendl;cout(int)HT.hftreeindex.weightendl;if(HT.hftreeindex.rchild)treeprinting(HT,HT.hftreeindex.rchild,level+1,filename,1);/左右子树深度相同if(HT.hftreeindex.lchild)treeprinting(HT,HT.hftreeindex.lchild,level+1,filename,1);if(flag)outfile.close();3.3调试分析测试数据及测试结果在7中有详细给出，这里省略。算法分析：编码函数中，每次都要将待编码字符与正文字符比较，相当于顺序表查找，哈夫曼树中有n个字符，时间复杂度为O(n2)。解码函数中，每次从编码中取出一定长的子串与哈夫曼编码比较，逐渐增加子串长度，直到找到相同子串，得到解码后的字符。用凹入法打印哈夫曼树，先输出最顶端的结点，然后根据包含关系，将子树的结点缩进一定长度，用递归调用实现该打印。调试中遇到的问题及解决方法：1. 空格的输入。在C+中用cin输入，空格作为截止符，无法正常输入，于是改成了C语言的scanf函数，接收空格。2. 空格的读入和保存。在C+中用outfile的方式读入或保存空格，功能类似于cin中的功能，即作为输入输出的截止符。无法正常保存和读出。于是用二进制读入读出字符，但这样存在一个弊端：直接打开保存的文件将无法直接查看其中的内容，解决方法还有待改善。3. 当同一个函数中同时存在puts与cout时，输出会出错。于是一个函数中要么用C语言的输入输出和puts，要么只有cout函数。3.4用户手册1 本程序执行文件为huffmancoding.exe。2 用户进入系统后可输入相应数字选择菜单，本系统可实现哈夫曼树的建立，以及利用哈夫曼编码对字符进行编码、解码的功能、哈夫曼树的凹入法打印功能。3 运行期间产生的哈夫曼树建立、字符编码、字符解码、哈夫曼树打印等中间结果均可保存在文件。4总结1. 关于哈夫曼编码的思考：哈夫曼编码冗余度很低，充分地缩小了存储正文所需的存储空间，方便传输。但从本次实验来看，哈夫曼编码在解码时由于不知道到底多长截取为一段来解码成字符，需要一点一点地试。这次实验是从最小1比特截为一段，后面逐渐增加截取长度，直到这个字符解码成功。还可以优化一点，先根据哈夫曼编码的最短长度，以最短长度截取一段，然后逐渐增加，以降低运行耗时。2. 关于调试过程中的感受：在以往的实验中，大都是用C语言完成实验，而这次为了使保存的文件不是乱码，用了C+. 但因为空格的问题，直接保存有一定的问题，最终还是用了二进制的方式保存，使程序能够正常运行。主要可能是因为对文件的使用方式不太熟悉，以后还有待提高。除此之外，这次因为马虎给自己添了不少麻烦，浪费了很多时间，是一次小小的教训。5、程序清单:(见附录)7、程序运行结果主界面初始化：编码：1. 从文件读入哈夫曼树2. 直接输入正文3. 从文件读入正文4. 正文编码译码：2.正文译码印代码文件：凹入法印哈夫曼树附录1#include #include #include #include #include #define Elemtype double#define BIN char#define N 500#define N2 100#define Tree 1/1表示树#define BeTran 2/2表示正文#define CoFile 3/3表示编码后结果struct HTNode/哈夫曼树的结点Elemtype weight;int parent,lchild,rchild;struct Huffmantree/哈夫曼树int num;char * alphabet;HTNode * hftree;int * HCnum;BIN * * HC;struct Text/正文int num;char * content;struct Code/编码，用字符型数字表示int num;BIN * bin;void HufftreeInit(Huffmantree & H)/对结构体Huffmantree初始化H.num=0;H.alphabet=NULL;H.hftree=NULL;H.hftree=NULL;void HufftreeMalloc(Huffmantree & H,int num)/给结构体Huffmantree分配空间H.num=num;H.alphabet=(char *)malloc(H.num+1)*sizeof(char);H.hftree=(HTNode *)malloc(2*H.num*sizeof(HTNode);H.HC=(char * *)malloc(H.num+1)*sizeof(char *);H.HCnum=(int *)malloc(H.num+1)*sizeof(int);for(int i=1;i=2*num-1;i+)H.hftreei.lchild=0;H.hftreei.parent=0;H.hftreei.rchild=0;H.hftreei.weight=0;void TextInit(Text & c)/结构体Text初始化c.num=0;c.content=NULL;void TextMalloc(Text & c,int num)/给结构体Text分配存储空间c.num=num;c.content=(char *)malloc(sizeof(char)*(c.num+1);void CodeInit(Code & co)/给结构体code分配存储空间co.num=0;co.bin=NULL;void CodeMalloc(Code & co,int num)/给结构体code分配存储空间co.num=num;co.bin=(BIN *)malloc(co.num+1)*sizeof(BIN);int inputselection(int n)/输入菜单选择，返回值为输入的选项int flag=0;char s100;doif(flag)coutt 输入非法,请重新输入:;elsecoutt 输入数字0-ns;while(strlen(s)1|s0-0n);return s0-0;int TreeRead(Huffmantree &H)/读取哈夫曼树文件char filenameN2;coutfilename;ifstream infile;int flag; infile.open(filename,ios:binary); if(!infile) infile.open(hfmTree.txt,ios:binary);if(!infile)coutfilename无法打开!endl;return 0;elsecout原filename无法被打开,默认打开htmTreeendl; infile.read(char*)&flag,sizeof(int); /判断flag是否为1，保存的是否为哈夫曼树if(flag!=1)cout读取的数据格式不对!endl; return 0;/读取失败infile.read(char*)&H.num,sizeof(int);HufftreeMalloc(H,H.num);/分配空间 for(int i=1;i=H.num;i+)/读取字母infile.read(char*)&H.alphabeti,sizeof(char);infile.read(char*)&H.HCnumi,sizeof(int);H.HCi=(BIN *)malloc(sizeof(BIN)*(H.HCnumi+1);for(int j=0;jH.HCnumi;j+)infile.read(char*)&H.HCij,sizeof(char);H.HCij=0; for(i=0;i(2*H.num-1);i+)/读取结构体HTNodeinfile.read(char*)&H.hftreei.lchild,sizeof(int);infile.read(char*)&H.hftreei.parent,sizeof(int);infile.read(char*)&H.hftreei.rchild,sizeof(int);infile.read(char*)&H.hftreei.weight,sizeof(Elemtype); infile.close();return 1;int TreeSave(Huffmantree H)/保存结构体Huffmantreechar filenameN2;int flag=1;coutfilename;ofstream outfile(filename,ios:binary); if(!outfile) coutfilename无法打开!endl;return 0; outfile.write(char*)&flag,sizeof(int); /表示文件存储的是结构体Huffmantreeoutfile.write(char*)&H.num,sizeof(int); for(int i=1;i=H.num;i+)/保存字母outfile.write(char*)&H.alphabeti,sizeof(char);outfile.write(char*)&H.HCnumi,sizeof(int);for(unsigned j=0;jstrlen(H.HCi);j+)outfile.write(char*)&H.HCij,sizeof(char);for(i=1;i=2*H.num-1;i+)/保存结构体HTNodeoutfile.write(char*)&H.hftreei.lchild,sizeof(int);outfile.write(char*)&H.hftreei.parent,sizeof(int);outfile.write(char*)&H.hftreei.rchild,sizeof(int);outfile.write(char*)&H.hftreei.weight,sizeof(Elemtype); outfile.close(); return 1;int TextSave(Text c)/保存结构体Textchar filenameN2;int flag=2;coutfilename;ofstream outfile;outfile.open(filename,ios:binary);if(!outfile)coutfilename无法打开!endl;return 0;outfile.write(char*)&flag,sizeof(int);/保存的是正文outfile.write(char*)&c.num,sizeof(int);for(int i=0;ic.num;i+)outfile.write(char*)&c.contenti,sizeof(char);outfile.close();return 1;int TextRead(Text &c)/读取结构体Textchar filenameN2;coutfilename;ifstream infile;int flag;infile.open(filename,ios:binary);if(!infile)coutfilename无法打开!endl;return 0;infile.read(char*)&flag,sizeof(int);if(flag!=2)cout读取的数据格式不对!; return 0;infile.read(char*)&c.num,sizeof(int);TextMalloc(c,c.num);for(int i=0;ic.num;i+)infile.read(char*)&c.contenti,sizeof(char);coutc.contenti;infile.close();return 1;int CodeSave(Code & co)/保存结构体Codechar filenameN2;coutfilename;ofstream outfile;outfile.open(filename,ios:out);if(!outfile)coutfilename无法打开!endl;return 0;outfile3endl;outfileco.numendl;for(int i=0;ico.num;i+)outfileco.bini ;outfileendl;outfile.close();return 1;int CodeSave2(Code & co)/以紧凑形式保存结构体Codechar filenameN2;coutfilename;ofstream outfile;outfile.open(filename,ios:out);if(!outfile)coutfilename无法打开!endl;return 0;for(int i=0;ico.num;i+)outfileco.bini;if(i+1)%50=0)outfileendl;outfileendl;outfile.close();return 1;int CodeRead(Code & co)/读取结构体Codechar filenameN2;coutfilename;ifstream infile;int flag=2233;infile.open(filename,ios:in);if(!infile)coutfilename无法打开!flag;if(flag!=3)cout文件读取格式不对!co.num;CodeMalloc(co,co.num);for(int i=0;ico.bini;infile.close();return 1;int istrue()/判断是否输入了Ychar s100;int flag=0;cout(输入Y/y表示是,输入N/n表示否):;doif(flag)coutendls;flag=1;while(strlen(s)1|s0!=y&s0!=Y&s0!=n&s0!=N);if(s0=y|s0=Y)return 1;elsereturn 0;void exchange(int s)/交换s0和s1中的内容int temp;temp=s0;s0=s1;s1=temp;void Select(HTNode HT,int i,int s)/找到parent为0且weight最小的两个结点,序号放在s0和s1int j,flag=0;for(j=1;j=i&flagHTs1.weight)exchange(s);for(;j=i;j+)if(!HTj.parent)if(HTj.weightHTs1.weight)exchange(s);void Huffmancoding(Huffmantree &HT)/哈弗曼编码int m,i,start,f,n=HT.num;int s2;int c;char * cd;m=2*n-1;for(i=n+1;i=m;i+)Select(HT.hftree,i-1,s);HT.hftrees0.parent=i;HT.hftrees1.parent=i;HT.hftreei.lchild=s0;HT.hftreei.rchild=s1;HT.hftreei.parent=0;HT.hftreei.weight=HT.hftrees0.weight+HT.hftrees1.weight;cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=HT.hftreei.parent;f!=0;c=f,f=HT.hftreef.parent)if(HT.hftreef.lchild=c) cd-start=0;else cd-start=1;HT.HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HT.HCi,&cdstart);HT.HCnumi=strlen(HT.HCi);free(cd);int exist(Huffmantree HT,int index)/判断HT.alphabetindex是否与其他结点重复for(int i=1;iindex;i+)if(HT.alphabeti=HT.alphabetindex)return 1;return 0;void initialization(Huffmantree &HT)/初始化system(cls);int num;int i;puts(-);puts( 初 始 化 );puts(-);printf(参与Huffman编码的数目:);scanf(%d,&num);/输入结点数目if(num=0)puts(结点数目为0);getchar();system(pause);return;HufftreeInit(HT);HufftreeMalloc(HT,num);for(i=1;i=num;i+)/输入结点信息printf(请输入第%d个字符及权值:,i);getchar();scanf(%c%lf,