哈夫曼编码译码系统

1、 数 据 结 构 课 程 设 计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)

2、熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。2.需求分析(1) 为信息收发站写一个哈夫曼编/译码系统。(2) 要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。(3) 要求可以将哈夫曼树以树状或凹入法打印到屏幕。3电文的编码和译码的设计3.1概要设计3.1.1主界面设计图 1主界面，如图1所示，包含初始化，编码，译码，代码文件，哈夫曼树五个菜

3、单。其中，菜单1用来从终端读入n个字符和n个权值，建立哈夫曼树，并将它存于文件中; 菜单2用来利用已建好的哈夫曼树，对文件中或直接输入的正文进行编码，然后将结果存入文件中，如果哈夫曼树不在内存可通过初始化或文件读入到内存；菜单3利用已建好的哈夫曼树将文件中的代码进行译码，译码结果存入文件中，若哈夫曼树不在内存中，处理方式与菜单2相同；菜单4将编码文件以紧凑格式显示在终端上，每行50个代码,同时将此字符形式的编码写入文件中；菜单5将已在内存中的哈夫曼树以凹入法显示在终端上。3.1.2存储结构这里使用了4个结构体。结构体HTNode存放哈夫曼树的结点，包含权值weight，以及父节点parent、

4、左孩子lchild、右孩子rchild所在位置。结构体Huffmantree保存哈夫曼树, 其中num是结点数，参与哈夫曼编码的各个字符alphabet，hftree是HTNode类型存放构建的哈夫曼树的表，HCnum是每个字符编码的长度，HC是编码字符数组。结构体Text保存正文，其中num存放正文的长度，content存放正文内容。Code存放编码结果，num是编码长度，bin是编码内容。3.1.3系统功能设计本系统的功能描述如下：1 可输入字符和其对应的权值，以构建哈夫曼树。2 可输入或读入正文，根据构建的哈夫曼树，对正文进行编码,若哈夫曼树未存在，可从文件中读入或者初始化输入，若正文中

5、字符在哈夫曼树中不存在，则会提示编码出错。3 可读入编码文件，根据存在的哈夫曼树，对文件进行解码，若哈夫曼树不存在会进行和2一样的操作，若解码时，编码在哈夫曼树中不存在，则提示解码出错。4 可根据内存中的哈夫曼树用凹入表示法输出树形界面。3.2详细设计3.2.1系统子程序及功能设计本系统设置32个函数，函数名及功能说明如下：void HufftreeInit(Huffmantree & H)/对结构体Huffmantree初始化void HufftreeMalloc(Huffmantree & H,int num)/给结构体Huffmantree分配空间void TextIni

6、t(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)/保存结构体Huffmantreein

7、t 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和

8、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)/编码菜单in

9、t 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)/凹入法印

10、哈夫曼树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)Code

11、Save(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

12、 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,

13、int s)/找到parent为0且weight最小的两个结点,序号放在s0和s1int j,flag=0;for(j=1;j<=i&&flag<2;j+)if(!HTj.parent)sflag+=j;if(HTs0.weight>HTs1.weight)exchange(s);for(;j<=i;j+)if(!HTj.parent)if(HTj.weight<HTs1.weight)/左子树放较小值，右子树放较大值s1=j;if(HTs0.weight>HTs1.weight)exchange(s);void Huffmancoding(

14、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

15、 *)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

16、);给正文编码: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<<"

17、正文不存在,请输入或读入正文后编码!"<<endl;system("pause");return;char code26*N=0;for(int i=0;i<text.num;i+)/i<text.numfor(int j=1;j<=HT.num;j+)if(text.contenti=HT.alphabetj)break;if(j>HT.num)cout<<"编码出错!"<<endl;system("pause");return;elsestrcat(code,H

18、T.HCj);CodeMalloc(c,strlen(code);strcpy(c.bin,code);cout<<"编码结果为:"<<code<<endl;cout<<"编码结果将保存到文件."<<endl;if(CodeSave(c)cout<<"保存成功!"<<endl;elsecout<<"保存失败!"<<endl;system("pause");正文解码：void decode(

19、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<<"将从文件中读取编码."

20、;<<endl;CodeInit(co);if(CodeRead(co)co.binco.num=0;cout<<"读取内容为:"<<co.bin<<endl;cout<<"读取成功!"<<endl;elsecout<<"读取失败!返回!"<<endl;return ;for(i=0;i<co.num;i=j+1)for(j=i;j<co.num;j+)flag=0;s=substring(co,i,j);for(k=1;k&l

21、t;=HT.num;k+)if(strcmp(s,HT.HCk)=0)flag=1;temptexttextindex+=HT.alphabetk;break;if(flag)break;if(j=co.num&&k>HT.num)cout<<"解码出错!"<<endl;system("pause");return;temptexttextindex=0;cout<<"译码结果为:"<<temptext<<endl;cout<<"是

22、否保存译码结果到文件?"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;凹入法印哈夫曼树：voi

23、d treeprinting(Huffmantree HT,int index,int level,char * filename,int flag)/凹入打印哈夫曼树if(index<1|index>2*HT.num-1)return;ofstream outfile(filename,ios:app);for(int i=0;i<level;i+)if(flag)outfile<<" "cout<<" "if(index<=HT.num)if(HT.alphabetindex=' ')i

24、f(flag)outfile<<"blank"<<endl;/空格用blank表示cout<<"blank"<<endl;elsecout<<HT.alphabetindex<<endl;outfile<<HT.alphabetindex<<endl;elseif(flag)outfile<<(int)HT.hftreeindex.weight<<endl;cout<<(int)HT.hftreeindex.weight&l

25、t;<endl;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)

26、。解码函数中，每次从编码中取出一定长的子串与哈夫曼编码比较，逐渐增加子串长度，直到找到相同子串，得到解码后的字符。用凹入法打印哈夫曼树，先输出最顶端的结点，然后根据包含关系，将子树的结点缩进一定长度，用递归调用实现该打印。调试中遇到的问题及解决方法：1. 空格的输入。在C+中用cin输入，空格作为截止符，无法正常输入，于是改成了C语言的scanf函数，接收空格。2. 空格的读入和保存。在C+中用outfile<<和infile>>的方式读入或保存空格，功能类似于cin中的功能，即作为输入输出的截止符。无法正常保存和读出。于是用二进制读入读出字符，但这样存在一个弊端：直接

27、打开保存的文件将无法直接查看其中的内容，解决方法还有待改善。3. 当同一个函数中同时存在puts与cout时，输出会出错。于是一个函数中要么用C语言的输入输出和puts，要么只有cout函数。3.4用户手册1 本程序执行文件为huffmancoding.exe。2 用户进入系统后可输入相应数字选择菜单，本系统可实现哈夫曼树的建立，以及利用哈夫曼编码对字符进行编码、解码的功能、哈夫曼树的凹入法打印功能。3 运行期间产生的哈夫曼树建立、字符编码、字符解码、哈夫曼树打印等中间结果均可保存在文件。4总结1. 关于哈夫曼编码的思考：哈夫曼编码冗余度很低，充分地缩小了存储正文所需的存储空间，方便传输。但从

28、本次实验来看，哈夫曼编码在解码时由于不知道到底多长截取为一段来解码成字符，需要一点一点地试。这次实验是从最小1比特截为一段，后面逐渐增加截取长度，直到这个字符解码成功。还可以优化一点，先根据哈夫曼编码的最短长度，以最短长度截取一段，然后逐渐增加，以降低运行耗时。2. 关于调试过程中的感受：在以往的实验中，大都是用C语言完成实验，而这次为了使保存的文件不是乱码，用了C+. 但因为空格的问题，直接保存有一定的问题，最终还是用了二进制的方式保存，使程序能够正常运行。主要可能是因为对文件的使用方式不太熟悉，以后还有待提高。除此之外，这次因为马虎给自己添了不少麻烦，浪费了很多时间，是一次小小的教训。5、

29、程序清单:(见附录)7、程序运行结果主界面初始化：编码：1. 从文件读入哈夫曼树2. 直接输入正文3. 从文件读入正文4. 正文编码译码：2.正文译码印代码文件：凹入法印哈夫曼树附录1#include <stdlib.h>#include <string.h>#include <iostream.h>#include <stdio.h>#include <fstream.h>#define Elemtype double#define BIN char#define N 500#define N2 100#define Tree 1/

30、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(Huffm

31、antree & 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(c

32、har *);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 *)mall

33、oc(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)cout<<"t 输入非法,请重新输入

34、:"elsecout<<"t 输入数字0-"<<n<<"选择:"flag=1;cin>>s;while(strlen(s)>1|s0-'0'<0|s0-'0'>n);return s0-'0'int TreeRead(Huffmantree &H)/读取哈夫曼树文件char filenameN2;cout<<"文件名称为:"cin>>filename;ifstream infile

35、;int flag; infile.open(filename,ios:binary); if(!infile) infile.open("hfmTree.txt",ios:binary);if(!infile)cout<<filename<<"无法打开!"<<endl;return 0;elsecout<<"原"<<filename<<"无法被打开,默认打开htmTree"<<endl; infile.read(char*)&am

36、p;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,si

37、zeof(int);H.HCi=(BIN *)malloc(sizeof(BIN)*(H.HCnumi+1);for(int j=0;j<H.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*)&

38、amp;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;cout<<"文件名称为:"cin>>filename;ofstream outfile(filename,ios:binary); if(!outfile) cout<<

39、filename<<"无法打开!"<<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(un

40、signed j=0;j<strlen(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*)&

41、amp;H.hftreei.weight,sizeof(Elemtype); outfile.close(); return 1;int TextSave(Text c)/保存结构体Textchar filenameN2;int flag=2;cout<<"文件名称为:"cin>>filename;ofstream outfile;outfile.open(filename,ios:binary);if(!outfile)cout<<filename<<"无法打开!"<<endl;return

42、0;outfile.write(char*)&flag,sizeof(int);/保存的是正文outfile.write(char*)&c.num,sizeof(int);for(int i=0;i<c.num;i+)outfile.write(char*)&c.contenti,sizeof(char);outfile.close();return 1;int TextRead(Text &c)/读取结构体Textchar filenameN2;cout<<"文件名称为:"cin>>filename;ifstr

43、eam infile;int flag;infile.open(filename,ios:binary);if(!infile)cout<<filename<<"无法打开!"<<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;i

44、<c.num;i+)infile.read(char*)&c.contenti,sizeof(char);cout<<c.contenti;infile.close();return 1;int CodeSave(Code & co)/保存结构体Codechar filenameN2;cout<<"文件名称为:"cin>>filename;ofstream outfile;outfile.open(filename,ios:out);if(!outfile)cout<<filename<<&q

45、uot;无法打开!"<<endl;return 0;outfile<<3<<endl;outfile<<co.num<<endl;for(int i=0;i<co.num;i+)outfile<<co.bini<<" "outfile<<endl;outfile.close();return 1;int CodeSave2(Code & co)/以紧凑形式保存结构体Codechar filenameN2;cout<<"文件名称为:&q

46、uot;cin>>filename;ofstream outfile;outfile.open(filename,ios:out);if(!outfile)cout<<filename<<"无法打开!"<<endl;return 0;for(int i=0;i<co.num;i+)outfile<<co.bini;if(i+1)%50=0)outfile<<endl;outfile<<endl;outfile.close();return 1;int CodeRead(Code &am

47、p; co)/读取结构体Codechar filenameN2;cout<<"文件名称为:"cin>>filename;ifstream infile;int flag=2233;infile.open(filename,ios:in);if(!infile)cout<<filename<<"无法打开!"<<endl;return 0;infile>>flag;if(flag!=3)cout<<"文件读取格式不对!"<<endl;retur

48、n 0;infile>>co.num;CodeMalloc(co,co.num);for(int i=0;i<co.num;i+)infile>>co.bini;infile.close();return 1;int istrue()/判断是否输入了Ychar s100;int flag=0;cout<<"(输入Y/y表示是,输入N/n表示否):"doif(flag)cout<<endl<<"输入非法,请重新输入:"cin>>s;flag=1;while(strlen(s)&g

49、t;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(

50、j=1;j<=i&&flag<2;j+)if(!HTj.parent)sflag+=j;if(HTs0.weight>HTs1.weight)exchange(s);for(;j<=i;j+)if(!HTj.parent)if(HTj.weight<HTs1.weight)/左子树放较小值，右子树放较大值s1=j;if(HTs0.weight>HTs1.weight)exchange(s);void Huffmancoding(Huffmantree &HT)/哈弗曼编码int m,i,start,f,n=HT.num;int s2;

51、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+)st

52、art=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是否与其他结点

53、重复for(int i=1;i<index;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);/输入结点数

54、目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",&HT.alphabeti,&HT.hftreei.weight);if(exist(HT,i)cout<<"该条记录已存在,本次

55、输入无效!"<<endl;i-;Huffmancoding(HT);/哈夫曼编码printf("生成完成,是否保存到文件?");if(istrue()if(TreeSave(HT)puts("保存成功!");elseputs("保存失败!");elseputs("返回上级菜单!");getchar();system("pause");int encodingcourse()/编码菜单cout<<"tt -n"cout<<"tt 正文编码 n"cout<<"tt -n"cout<<"ttt 1. 从文件读入哈夫曼树"<<endl;cout<<"