用C++实现哈夫曼树的代码.docx

韩山师范学院数据结构中的哈夫曼树的实现班级：2015级软工班作者：黄俊聪#include #include #include #include using namespace std;typedef struct char data; int weight; int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char * HuffmanCode;void Select(HuffmanTree &HT,int n,int m) HuffmanTree p=HT; int tmp; for(int j=n+1;j=m;j+) int tag1,tag2,s1,s2; tag1=tag2=256; for(int x=1;x=j-1;x+) if(px.parent=0&px.weighttag1) tag1=px.weight; s1=x; for(int y=1;y=j-1;y+) if(py.parent=0&y!=s1&py.weights2) /将选出的两个节点中的序号较小的始终赋给s1 tmp=s1; s1=s2; s2=tmp; ps1.parent=j;ps2.parent=j;pj.lchild=s1;pj.rchild=s2;pj.weight=ps1.weight+ps2.weight; void HuffmanCoding(HuffmanTree &HT,int n,char *w1,int*w2) int m=2*n-1; if(n=1) return; HT=new HTNodem+1; HuffmanTree p=HT; for(int i=1;i=m;i+) pi.weight=pi.parent=pi.lchild=pi.rchild=0; for(int i=1;i=n;i+) pi.data=w1i-1; pi.weight=w2i; pi.parent=pi.lchild=pi.rchild=0; Select(HT,n,m); ofstream outfile(hfmTree.txt); /生成hfmTree文件 for (int i=1;i=m;i+) outfileHTi.weighttHTi.parenttHTi.lchild tHTi.rchildtendl; outfile.close(); cout初始化结果已保存在hfmTree文件中n;void ToBeTree() /将正文写入文件ToBeTree中ofstream outfile(ToBeTree.txt);outfileTHIS PROGRAM IS MYFAVORITE;outfile.close();void Encoding(HuffmanTree &HT,int n) /编码 HuffmanCode HC; HC=new char*n+1;/分配储存n个字符编码的编码表空间 char *cd; cd=new charn;/分配临时存放每个字符编码的动态数组空间 cdn-1=0;/编码结束 for(int i=1;i=n;i+)/逐个字符求哈夫曼编码 int start=n-1;/start开始时指向最后，即编码结束位置 int c=i; int f=HTi.parent;/f指向结点c的双亲结点 while(f!=0) if(HTf.lchild=c) cd-start=0;/结点c是f的左孩子，即生成代码0 else cd-start=1;/结点c是f的右孩子，即生成代码1 c=f; f=HTf.parent;/继续向上回溯 /求出第i个字符的编码 HCi=new charn-start;/为第i个字符编码分配空间 strcpy(HCi,&cdstart);/将求得的编码从临时空间cd复制到HC的当前行中 delete cd;/释放临时空间 cout输出哈夫曼编码:endl; for(int h=1;h=n;h+) /输出编码 coutHTh.data:; coutHCh; cout ; if (h%8=0) coutendl; coutendl输出正文编码:endl; ToBeTree(); /读取TOBETREE文件里的正文，并进行编码 fstream infile(ToBeTree.txt); char s80; while(!infile.eof()/判断是否到达文件尾部，以防止出现文件读取错误。 infile.getline(s,sizeof(s); infile.close(); fstream outfile(CodeFile.txt,ios:out); int count=0; for (int h=0;sh!=0;h+) for(int k=1;k=n;k+) if (sh=HTk.data) coutHCk; cout ; count+; outfileHCk; break; if (count%9=0) coutendl; /每输出7个换行 outfile.close(); coutn编码结果已保存在文件CodeFile中.; coutendl;void Decoding(HuffmanTree &HT,int n) /译码 int f=2*n-1; fstream infile(CodeFile.txt); char s1000; while(!infile.eof() infile.getline(s,sizeof(s); infile.close(); int i=0; int j=0; fstream outfile(TextFile.txt,ios:out); while(si!=0) f=2*n-1; while(HTf.lchild!=0)/以f对应的节点的左孩子的值=0作为结束 if (sj=0) f=HTf.lchild; else f=HTf.rchild; j+; i=j; coutHTf.data; outfileHTf.data; outfile.close(); coutn译码结果已保存在文件TextFile中.; coutendl;void Print() /印代码文件 int count=0;fstream infile(CodeFile.txt); char s1000;while(!infile.eof() infile.getline(s,sizeof(s); for(int i=0;si!=0;i+) coutsi; count+; if (count%50=0) coutendl; /在终端上每行显示50个代码 infile.close();coutendl;char menu() /菜单函数 cout功能菜单如下:endl; cout* * * * * * * * * * * * * * * * * * * * *endl; cout* 1:初始化(Initialization) *endl; cout* 2:编码(Encoding) *endl; cout* 3:译码(Decoding) *endl; cout* 4:印代码文件(Print) *endl; cout* 0:退出(Exit) *endl; cout* * * * * * * * * * * * * * * * * * * * *endl; coutn; return n;int main() int n; int Array100; char cArray100; HuffmanTree HT; cout输入n个字符:; cin.getline(cArray,100); n=strlen(cArray); cout一共n个字符.n; cout依次输入各个字符的权值:endl; for (int i=1;iArrayi; int tag; int x=menu(); while(1) switch (x) case 1:HuffmanCo