哈弗曼编码

重庆大学实验报告实验题目：哈夫曼树的应用学院：计算机学院专业班级：信息安全1班年级：2011级姓名：******学号：2011****完成时间：2013年5月20日指导教师：涂风华重庆大学教务处制实验项目指导教师评定成绩表学号：2011****班级：信安1班项目分值参考标准评分学习态度10积极与老师、助教讨论（10分）学习马虎，纪律涣散（5分）缺勤（0分）软件/系统质量60功能考虑完善，界面友好，Bug极少，针对异常情况有处理（55-60分）功能考虑完善，界面良好，有一定Bug（49-54分）功能较完善，Bug较多（43-48分）完成程序基本功能（36-42分）部分实现，无法运行（1-35分）抄袭、被抄袭（0分）实验演示答辩10重点突出、有特色、专业知识掌握好、能流畅回答老师提问（9-10分）有一定特色、能较好地回答老师提问（7-8分）能讲解项目的关键实现，能回答基本问题（0-6分）实验报告撰写质量20文档规范，文字、图表表达清楚（18-20分）文档较规范，文字、图表表达较清楚（11-17分）文档不规范，内容空泛、结构混乱（0-10分）指导教师评定成绩：指导教师签名：年月日重庆大学本科学生实验项目任务书实验题目哈夫曼树的应用学院计算机学院专业信息安全1班年级2011任务描述：综合运用C++编程技术和数据结构知识，用VS2010或QT设计实现一个简单的哈夫曼编码解码系统，该软件能够模拟实现简单的库存、订购、发货等功能。最后提交完整的设计报告和软件程序拷贝。设计要求：CompletetheimplementationoftheHuffmancodingtree,buildingonthecodepresentedinSection5.6.Includeafunctiontocomputeandstoreinatablethecodesforeachletter,andfunctionstoencodeanddecodemessages.Thisprojectextendedtosupportfilecompression.Todosorequiresaddingtwosteps:(1)Readthroughtheinputfiletogenerateactualfrequenciesforalllettersinthefile;and(2)storearepresentationfortheHuffmantreeatthebeginningoftheencodedoutputfiletobeusedbythedecodingfunction.Ifyouhavetroublewithdevisingsucharepresentation,seeSection6.5.Youcanrefertothefigureasbelow:参考资料：DataStructuresandAlgorithmAnalysis(C++Version)CliffordA.ShafferDataStructureandAlgorithmAnalysisinC++(ThirdEdition)，MarkAllenWeiss，PearsonEducation,2006.DataStructures,Algorithms,andApplicationsinC++，SartajSahni，McGraw-Hill,1998.《数据结构（C语言版）》，严蔚敏，吴伟民编著，清华大学出版社，2007年第1版任务下达日期2013年5月5日完成日期2013年5月20日说明：学院、专业、年级均填全称，如：计算机学院、计算机科学与技术、2011。实验报告正文主要内容包括：1需求分析先统计文本文件中的总字符数和字符种类，并求出各字符的数量（权值），在根据权值建立哈弗曼树，对各字符进行编码和解码。2系统设计（类图、模块图等）3关键代码描述/*”myh.h头文件”*/#includeiostream#includestring#includestdlib.husingnamespacestd;constintMaxValue=100000;//初始设定的权值最大值constintMaxBit=40;//初始设定的最大编码位数constintMaxN=1000000;//初始设定的最大结点个数//chark[40000];structHaffNode//哈夫曼树的结点结构{intweight;//权值¦intflag;//标记intparent;//双亲结点下标intleftChild;//左孩子下标intrightChild;//右孩子下标};structCode//存放哈夫曼编码的数据元素结构{intbit[MaxN];//数组intstart;//编码的起始下标Àintweight;//字符的权值};voidHaffman(intweight[],intn,HaffNodehaffTree[])//建立叶结点个数为权值为weight的哈夫曼树haffTree{intj,m1,m2,x1,x2;//哈夫曼树haffTree初始化n个叶结点的哈夫曼树共有2n-1个结点for(inti=0;i2*n-1;i++){if(in)haffTree[i].weight=weight[i];elsehaffTree[i].weight=0;haffTree[i].parent=0;haffTree[i].flag=0;haffTree[i].leftChild=-1;haffTree[i].rightChild=-1;}//构造哈夫曼树haffTree的n-1个非叶结点for(inti=0;in-1;i++){m1=m2=MaxValue;x1=x2=0;for(j=0;jn+i;j++){if(haffTree[j].weightm1&&haffTree[j].flag==0){m2=m1;x2=x1;m1=haffTree[j].weight;x1=j;}elseif(haffTree[j].weightm2&&haffTree[j].flag==0){m2=haffTree[j].weight;x2=j;}}//将找出的两棵权值最小的子树合并为一棵子树haffTree[x1].parent=n+i;haffTree[x2].parent=n+i;haffTree[x1].flag=1;haffTree[x2].flag=1;haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;haffTree[n+i].leftChild=x1;haffTree[n+i].rightChild=x2;}}voidHaffmanCode(HaffNodehaffTree[],intn,CodehaffCode[])//编码//由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode{Code*cd=newCode;intchild,parent;//求个叶结点的哈夫曼编码?for(inti=0;in;i++){cd-start=n-1;//不等长编码的最后位为-1cd-weight=haffTree[i].weight;//取得编码对应权值的字符child=i;parent=haffTree[child].parent;//由叶结点向上直到根结点while(parent!=0){if(haffTree[parent].leftChild==child)cd-bit[cd-start]=0;//左孩子结点编码elsecd-bit[cd-start]=1;//右孩子结点编码cd-start--;child=parent;parent=haffTree[child].parent;}//保存叶结点的编和不等长编码的起始位for(intj=cd-start+1;jn;j++)haffCode[i].bit[j]=cd-bit[j];haffCode[i].start=cd-start;haffCode[i].weight=cd-weight;//保存编码对应的权值}}/*main函数代码*/#includeiostream#includefstream#includestring#includestdlib.h#includemyh.husingnamespacestd;intmain(){fstreamf1;f1.open(m.txt);charch[40];strings;floata[40];intcount[40],i=0;getline(f1,s);i=s.size();for(intm=0;m=40;m++)count[m]=0;ch[0]=s[0];intn=0;if(ch[0]!=NULL){intm=1;for(;;){intflag=0;for(intj=0;j=n;j++){if(ch[j]==s[m]){flag=1;break;}}if(flag==0){ch[n++]=s[m];m++;}elsem++;if(m==i)break;}for(intb=0;bn;b++)for(intc=0;ci;c++)if(ch[b]==s[c])count[b]++;for(intq=0;qn;q++)a[q]=(float)count[q]/i;cout............................哈弗曼树编码解码?............................endl;cout班级：信息安全班姓名：唐运河endl;coutendl文?件t中D总Á¨¹字Á?符¤?数ºy为a：êoiendl;}elsecout文件中没有内容！endl;HaffNode*myHaffTree=newHaffNode[2*n+1];Code*myHaffCode=newCode[n];if(nMaxN){cout定义的越界，修改MaxN!endl;exit(0);}Haffman(count,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode);//输出每个叶结点的哈夫曼编码for(intir=0;irn;ir++){cout字符ch[ir]的权值为：count[ir]该符号编码为：;for(intjr=myHaffCode[ir].start+1;jrn;jr++)coutmyHaffCode[ir].bit[jr];coutendl;}coutendl;cout........................................................................endlendl;stringdes;cout请输入要编码的字符串：;cindes;coutendl;intdesc=des.size();cout..........................字符串的编码结果如下..........................endl;intmycount=0;intb[40000];for(intg=0;gdesc;g++){for(inth=0;hn;h++){if(ch[h]==des[g]){for(intjr=myHaffCode[h].start+1;jrn;jr++){coutmyHaffCode[h].bit[jr];b[mycount]=myHaffCode[h].bit[jr];mycount++;}}}}intds;cinds;return0;}4系统测试报告5运行效果6总结(注明每个人的分工和工作量百分比)7源程序附件分工及工作量说明参考格式：本组由2011****组成。2011*