数据结构课程设计实验报告(赫夫曼编码)(1) 2

1、数据结构课程设计哈夫曼编码学 院：计算机科学与技术学院 专 业：计算机科学与技术 学 生： 学 号： 指导教师： 2013年4月16日 目录1、 课程设计的目的、功能及要求-12、 主要功能模块流程图-23、 算法的基本思想-34、 系统测试-65、 结论-76、 源程序-8第 0 页 共 21 页 一、课程设计的目的、功能及要求目的：1. 解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2. 件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3. .合运用所学的理论知识和方法独立分析和解决问题的能力； 4. 用系统的观点和软件开发一般规范进行软件开发，培养软

2、件工作者所应具备的科学的工作方法和作风。功能： 1首先读入待压缩源文件； 2然后建立并分析字母表，对每种字符的出现频度进行统计，以频度作为建立Huffman 树的权值； 3频度表建好后，就可以根据算法建立Huffman 树，对出现的每种字符进行Huffman编码； 4此时，再次读入源文件，逐字节编码，将得到的编码流写入到磁盘文件，并且计算压缩率。要求：1、核心数据结构用到的结构体要采用动态内存分配和链表结构。 2 、不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 3 、对系统进行功能模块分析、画出总流程图和各模块流程图。 4 、用

3、户界面要求使用方便、简洁明了、美观大方、格式统一。 5 所有程序需调试通过。 二、主要功能模块流程图开始编码信息读取文档输入并存入文档计算压缩率统计频率生成哈夫曼编码编码文件译码信息结束译码文件 三、算法的基本思想（1）构造Hufffman树的方法Hufffman算法构造Huffman树步骤：I. 根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj。II. 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和III. 在森林中删除这两棵树，同时将新得到的二叉树加入森林中。IV. 重复上述两步，直到只含一棵树

4、为止，这棵树即哈夫曼树。（2）Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。流程图：开始读入各字符的权重寻找权值最小的字符将两个字符分别作为左右孩子节点建立Huffman树计算从根节点到每个叶子节点的路径得出编码输出Huffman编码结束部分程序：（1） 构造哈夫曼树void HaffmanTree(HNodeType HuffNodeMAXNODE) int i,j,m1,m2,x1,

5、x2;for(i=0;i<MAXNODE;i+)HuffNodei.parent=-1;HuffNodei.lchild=-1;HuffNodei.rchild=-1;for(i=0;i<num-1;i+)m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<num+i;j+)if(HuffNodej.parent=-1&&HuffNodej.weight<m1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j;elseif(HuffNodej.parent=-1&&HuffNodej.weight&l

6、t;m2)m2=HuffNodej.weight;x2=j;HuffNodex1.parent=num+i;HuffNodex2.parent=num+i;HuffNodenum+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNodenum+i.lchild=x1;HuffNodenum+i.rchild=x2;（2）哈夫曼编码LinkList Bianma(LinkList l,Code codeMAXNODE) /写编码文件LinkList p,q,p1,p2;int i,j;p=l->next ;q=new LNode;q->

7、;next=NULL;p1=new LNode;p2=q;while(p)for(i=0;i<num;i+)if(p->data=codei.data) j=0;while(codei.bitj!='0')p1->data=codei.bitj;j+;p2->next=p1;p2=p1;p1=new LNode;p=p->next ;p2->next=NULL;return q;SeqStack Init()SeqStack s;s=new StackNode;s->top=-1;return s;void HaffmanCode(HN

8、odeType HuffNodeMAXNODE,HCodeType HuffCodeMAXLEAF) /哈夫曼编码算法int i,j,c,p;HCodeType cd;for(i=0;i<num;i+)cd.start=MAXBIT-1;c=i;p=HuffNodec.parent ;while(p!=-1)if(HuffNodep.lchild=c)cd.bitcd.start='0'elsecd.bitcd.start='1'cd.start -;c=p;p=HuffNodec.parent;for(j=cd.start+1;j<MAXBIT;j

9、+)HuffCodei.bitj=cd.bitj;HuffCodei.start=cd.start ;四、系统测试1、主界面2、输入并保存编码 五、结论 本次课程设计的目的是：把一个随机输入的字符串中不同字符作为叶子结点元素，把其在该字符串中出现的次数作为权值构造一个赫夫曼树，并得到各个叶子结点的赫夫曼编码和整个输入的字符串的赫夫曼编码。在写代码前，首先，对问题进行了分析，明确了目标，列出了大的框架，然后逐渐细化，划分出不同的功能模块，由具体的子函数去实现，先在纸上编写代码，写好后进行了反复的逻辑推理，发现并解决逻辑问题，然后，上机调试，方法是：一个一个功能模块分开进行调试，主要看调试的模块能

10、否达到预期的结果，这样可以缩小排错的范围，便以纠错和提高编程的效率，当每个功能模块都调试好后，就把各个部分组合起来，再进行调试，主要检查各函数接口是否正确，当达到预期的结果，调试结束，编程部分完成，然后按实验要求完成实验报告。由于写代码前做了充分的准备工作，所以写起代码来比较顺利，使编程的效率有不少的提高并且最终达到实验预期的结果。心得体会：每一次的课程设计对我来说都是一个不小的提高，哲学上说：“实践是检验真理正确性的唯一标准”，尤其是学编程，自己不动手操作，只看书永远都编不出像Windows之类的东西，正如老师说的那样，课程设计非常锻炼人，每完成一个项目，不仅是知识体系的完善和知识的验证，更

11、是编程技术的提升，当自己编的多了，就会开始摸索编程的捷径，想着用更高效的方法去完成一个个项目，就这样在一次次的锻炼中自己会从一个菜鸟迅速的成长，终将成为一个优秀的软件工程师。一个成功的项目必须在写代码前，先要对课题有充分的思考和规划，否则即使完成了项目也会浪费很多的时间和精力，我认为科学合理的编程方法是我这次课程设计的最大收获。六、源程序#include<iostream>#include<fstream>#include"heads.h"#define NULL 0#define MAXVALUE 10000 /最大权值#define MAXLEA

12、F 100 /叶子结点个数#define MAXNODE MAXLEAF*2-1 /哈夫曼树结点个数#define MAXBIT 12 /最大长度using namespace std;int num;int power(int x)/2的x次方int i;for(i=1;i<=x;i+)i*=2;return i;float pration(int a,int b)/计算压缩率,a为压缩前字长，b为压缩后字长float s;s=(float)(float)b/(float)a);return s;void Show(LinkList l) /输出LinkList p=l->nex

13、t;while(p)cout<<p->data ;p=p->next;cout<<endl;LinkList Create() /写入字符串 int total=0;int x=1,y;int p=0;LinkList l,p1,p2;l=new LNode;l->next=NULL;cout<<"请输入:"<<endl<<endl;cout<<"1.输入并存入文档n2.从文档读取,并计算出压缩率!"<<endl<<endl;cout<

14、<"请输入要进行的操作:"<<endl;int choose;cin>>choose;if(choose!=1&&choose!=2)cout<<"输入错误,请重新输入!"<<endl;cin>>choose; if(choose=1)ofstream outfile;outfile.open("code.txt",ios:out);if(!outfile)cout<<"输出时打开code文档出错!"<<end

15、l;exit(1);cout<<"请输入所要编译的字符串,以#结束:"<<endl; p1=new LNode; p2=l; cin>>p1->data;outfile<<p1->data; while(p1->data!='#') p2->next=p1; p2=p1; p1=new LNode; cin>>p1->data;outfile<<p1->data; p2->next=NULL; p2=l; return l; else ifstr

16、eam infile("wenjian.txt",ios:in);if(!infile)cout<<"输出时打开文档出错!n或文档不存在!"<<endl;cout<<"请确认本目录下有相关文件后再重试!"<<endl;exit(1);l=Read("wenjian.txt");p1=new LNode; p2=l; infile>>p1->data; while(infile.eof() p2->next=p1; p2=p1; p1=new L

17、Node; infile>>p1->data;p1->data='#'p1->next=NULL;infile.close();printf("读取完成！n");Show(l);/*以下计算压缩率*/p2=l;while(p2)total+;p2=p2->next;for(;power(x)<total;)x+;p=x; /记录正常编码一个字符需要的比特位数y=(total-1)*x;/正常所需的总比特数printf("y is %dn",y);/*编码后的位数计算*/int c; FILE *f

18、p; if(fp=fopen("Code.txt","rb")=NULL) printf("文件打开失败！n"); exit(0); while(!feof(fp)c=fgetc(fp);x=x+1;printf("x is %d",x);/*计算完成*/printf("压缩率为%4.2f%",pration(y,x)*100);return l; void Write(LinkList l,char wenjian)LinkList p1;ofstream outfile(wenjian,io

19、s:out);p1=l->next ;while(p1)outfile<<p1->data;p1=p1->next;outfile<<"#"outfile.close();LinkList Read(char wenjian) /读文件中字符串LinkList l,p1,p2;l=new LNode;l->next=NULL;p1=new LNode;p2=l;ifstream infile(wenjian,ios:in);if(!infile)cout<<"打开文档出错!n或文档不存在!"&l

20、t;<endl;cout<<"请确认本目录下有相关文件后再重试!"<<endl;exit(1);infile>>p1->data;while(p1->data!='#')p2->next=p1;p2=p1;p1=new LNode;infile>>p1->data;p2->next=NULL;infile.close();return l;void Create(HNodeType aMAXNODE,LinkList l) /统计字符个数,做出哈夫曼树的结点 LinkList

21、 p;int i;p=l->next ; /全局变量num在这里的作用while(p)for(i=0;i<num;i+)if(ai.data=p->data)ai.weight+;break; if(i=num)ai.data=p->data;ai.weight=1;num+;p=p->next;/printf("num is %d ",num);可以看到num在这里的作用for(i=0;i<num;i+)ai.lchild=NULL;ai.rchild=NULL;ai.parent=-1;void HaffmanTree(HNodeTy

22、pe HuffNodeMAXNODE) /构造哈夫曼树int i,j,m1,m2,x1,x2;for(i=0;i<MAXNODE;i+)HuffNodei.parent=-1;HuffNodei.lchild=-1;HuffNodei.rchild=-1;for(i=0;i<num-1;i+)m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<num+i;j+)if(HuffNodej.parent=-1&&HuffNodej.weight<m1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j;elseif(Huf

23、fNodej.parent=-1&&HuffNodej.weight<m2)m2=HuffNodej.weight;x2=j;HuffNodex1.parent=num+i;HuffNodex2.parent=num+i;HuffNodenum+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNodenum+i.lchild=x1;HuffNodenum+i.rchild=x2;/哈夫曼编码LinkList Bianma(LinkList l,Code codeMAXNODE) /写编码文件LinkList p,q,p1,

24、p2;int i,j;p=l->next ;q=new LNode;q->next=NULL;p1=new LNode;p2=q;while(p)for(i=0;i<num;i+)if(p->data=codei.data) j=0;while(codei.bitj!='0')p1->data=codei.bitj;j+;p2->next=p1;p2=p1;p1=new LNode;p=p->next ;p2->next=NULL;return q;SeqStack Init()SeqStack s;s=new StackNode

25、;s->top=-1;return s;void HaffmanCode(HNodeType HuffNodeMAXNODE,HCodeType HuffCodeMAXLEAF) /哈夫曼编码算法int i,j,c,p;HCodeType cd;for(i=0;i<num;i+)cd.start=MAXBIT-1;c=i;p=HuffNodec.parent ;while(p!=-1)if(HuffNodep.lchild=c)cd.bitcd.start='0'elsecd.bitcd.start='1'cd.start -;c=p;p=HuffN

26、odec.parent;for(j=cd.start+1;j<MAXBIT;j+)HuffCodei.bitj=cd.bitj;HuffCodei.start=cd.start ;void bianma(HCodeType HuffCodeMAXLEAF,HNodeType aMAXNODE,Code codeMAXNODE) /字符编码int i,j,k;for(i=0;i<num;i+) codei.data=ai.data;for(j=HuffCodei.start+1,k=0;j<MAXBIT;j+,k+)codei.bitk=HuffCodei.bitj;codei

27、.bitk='0'int panduan(char aMAXBIT,char bMAXBIT)if(strcmp(a,b)=0)return 1;elsereturn 0;void bianma(Code codeMAXNODE,LinkList l)/读取编码int i,flag;SeqStack s;s=Init();LinkList p;p=l->next;while(p)s->top+;flag=0;s->datas->top=p->data;s->datas->top+1='0'for(i=0;i<num

28、;i+)if(panduan(s->data,codei.bit)=1) cout<<codei.data;flag=1;break;if(flag)s=Init();p=p->next;cout<<endl;void ShowTree(HNodeType nodeMAXNODE)printf("输出");int i;cout.width(8);cout.setf(ios:left);cout<<"统计字符频率结果为:"<<endl;cout<<"频率 "cout

29、.width(8);cout<<"字符"<<endl;for(i=0;i<num;i+)cout.width(8);cout<<nodei.weight;cout.width(8);cout<<nodei.data<<endl;cout<<endl;cout<<"哈弗曼树编码为:"<<endl;cout<<"字符"cout<<" "cout<<"编码"cout

30、<<endl;void ShowCode(Code coodMAXNODE)for(int i=0;i<num;i+)cout<<coodi.data<<"t"<<coodi.bit<<endl;void bianma(HNodeType nodeMAXNODE,HCodeType codeMAXLEAF,Code CODEMAXNODE)LinkList l,c;l=Create(); /写字符串Write(l,"wenjian.txt");l=Read("wenjian.txt");cout<<"文件内容:"&l