综合训练4利用哈夫曼树进行编码与解码

1、综合训练四 利用哈夫曼树进行编码与解码一、目的和要求：使学生理解哈夫曼树的概念、掌握哈夫曼树的建立以及利用利用哈夫曼树进行哈夫曼编码的算法思想。要求：1、使用文件流方式。2、要求提供编码和解码两种方式3、能够打开input.txt文件，统计其中字符出现的频率，并以此进行哈夫曼编码，并将编码后的结果输出到output1.txt文件中。4、能够根据3中得到的字符编码，将output1.txt文件中的码文进行解码，并将解码后的结果输出到output2.txt文件中。二、主要数据类型与变量#include #include #include using namespace std;struct Num

2、char C;int n;double percent;int len;int *c;typedef Num ElemType;struct BTreeNodeElemType data;BTreeNode *left;BTreeNode *right;三、程序测试及运行结果解密表：a 1110b c 11001d 0010e 100f 01101g 10100h 11110i 1011j k l 11000m n 000o 1101p q r 0011s 0111t 010u v w x y z 密文：100*译文：amongthemostimportantdirectionsfortech

3、nologyandonethattheusdepartmentofducationisworkingtoaccelerateissupportingtheeffortsofteacherstotailorlearningtotheneedsofeachstudentoneofthemostenduringandvalidcriticismsofoureducationsystemisthatithastakenaonesizefitsallapproachtoourkidsinthefaceoftheiruniquecombinationsofgiftsandchallengesersonal

4、izinglearningistheideathatthepaceapproachandcontextofthelearningexperienceshouldbetailoredtotheneedsandinterestsofindividualstiseasyandcommontotellateachertoadaptalessontotheneedsofeachchildbuthardtodoittechnologycanhelpyblendingfacetofaceandonlinelearningteacherscanenablestudentstoworkattheirownpac

5、ebeflexibleingroupingstudentsaccordingtoabilityandgetadynamicstreamofinformationaboutwherestudentsaredoingwellandwheretheyarestruggling四、源代码编码：#include #include #include using namespace std;struct Numchar C;int n;double percent;int len;int *c;typedef Num ElemType;struct BTreeNodeElemType data;BTreeN

6、ode *left;BTreeNode *right;Num num26;void sort(Num *num)int i,j;for(i=0;ii;j-)if(numj.nnumj-1.n)swap(numj,numj-1);void ClearBTree(BTreeNode*& BT)if(BT!=NULL) ClearBTree(BT-left); ClearBTree(BT-right); delete BT;BT=NULL;void InitBTree(BTreeNode *BT)BT=NULL;int DepthBTree(BTreeNode *BT)if(BT=NULL)retu

7、rn 0;else int dep1=DepthBTree(BT-left);int dep2=DepthBTree(BT-right);if(dep1dep2)return dep1+1;elsereturn dep2+1;BTreeNode* CreateHuffman(ElemType a, int n) BTreeNode *b,*q; b=new BTreeNode*n; int i,j; for(i=0; idata=ai; bi-left=bi-right=NULL; for(i=1; in; i+) int k1=-1,k2; for(j=0; jn; j+) if(bj!=N

8、ULL & k1=-1) k1=j;continue; if(bj!=NULL) k2=j;break; for(j=k2; jdata.ndata.n) k2=k1;k1=j; else if(bj-data.ndata.n) k2=j; q=new BTreeNode; q-data.n=bk1-data.n+bk2-data.n; q-left=bk1; q-right=bk2; bk1=q; bk2=NULL; delete b; return q;void HuffManCoding(BTreeNode* FBT, int len)static int a10;if(FBT!=NUL

9、L)if(FBT-left=NULL & FBT-right=NULL) int d=0;while(1)if(numd.C=FBT-data.C)break;d+;numd.len=len;numd.c=new intnumd.len;for(int i=0;ileft,len+1);alen=1;HuffManCoding(FBT-right,len+1);int main()ifstream infile(原文.txt,ios:in);if(!infile)cerropen error!ai;len=i-1;for(k=0,m=a;k26;k+,m+)numk.C=m;numk.n=0;

10、for(j=0;jlen;j+)int x=(int)aj-97;numx.n+;for(j=0;j26;j+)numj.percent=(double)numj.n/len;BTreeNode *fbt=NULL;fbt=CreateHuffman(num,26);HuffManCoding(fbt,0);ClearBTree(fbt);ofstream outfile(解密表.txt,ios:out);if(!outfile)cerropen error!n;exit(1);/sort(num);for(i=0;i26;i+)outfilenumi.C ;for(k=0;k10-numi.

11、len;k+)outfile ;for(j=0;jnumi.len;j+)outfilenumi.cj;outfilen;ofstream onfile(密文.txt,ios:out);if(!onfile)cerropen error!n;exit(1);for(i=0;ilen;i+)char x=ai;for(j=0;j26;j+)if(numj.C=x)for(k=0;knumj.len;k+)onfilenumj.ck;onfilen*;infile.close();outfile.close();cout成功加密！请查阅密文与加密表！n;return 0;解码：#include #

12、include #include using namespace std;struct unLockstring code;char c;unLock u26;string s=;int find(string z);int main()ifstream infile(解密表.txt,ios:in);if(!infile)cerropen error!n;exit(1);int i,j,k,len;char z;for(i=0;iui.c;infileui.code;ifstream onfile(密文.txt,ios:in);if(!onfile)cerropen error!zi;len=

13、i-1;string temp=;for(i=0;ilen;i+)for(j=i;jlen;j+)temp+=zj;if(find(temp)temp=;i=j;break;ofstream outfile(译文.txt,ios:out);if(!outfile)cerropen errorn;exit(1);outfiles;infile.close();outfile.close();cout成功解密！请查阅译文！n;return 0;int find(string z)staticint j=0;for(int i=0;i26;i+)if(z=ui.code)s+=ui.c;j+;if(

14、j%100=0)s+=n;return 1;return 0;原文：among the most important directions for technology and one that the us department of Education is working to accelerate is supporting the efforts of teachers to tailor learning to the needs of each student one of the most enduring and valid criticisms of our educati

15、on system is that it has taken a one size fits all approach to our kids in the face of their unique combinations of gifts and challenges personalizing learning is the idea that the pace approach and context of the learning experience should be tailored to the needs and interests of individuals It is easy and common to tell a teacher to adapt a lesson to the needs of each child but hard to do it technology can help By blending face t