哈夫曼树应用.docVIP

一．具体任务 题目：哈夫曼树应用 功能： 1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 2. 中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果。同时将此字符形式的编码文件写入文件CodePrint中。 3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。 二．软件环境 Code：：Blocks10.05 三．算法设计思想 1.建立哈夫曼树函数 void HuffTree(HNode Huff[],int n) //生成哈夫曼树 { FILE *fp; char d; int i,j,w,m1,m2,x1,x2; for(i=0;i2*n-1;i++) //对数组Huff初始化 { Huff[i].ch= ; Huff[i].weight=0; Huff[i].parent=-1; Huff[i].lchild=-1; Huff[i].rchild=-1; } printf(输入%d个字符及它的权值: \n,n);//读入数据 getchar(); for(i=0;in;i++) { printf(请输入第%d个字符:,i+1); scanf(%c,d); getchar(); Huff[i].ch=d; printf(请输入第%d个字符的权值:,i+1); scanf(%d,w); getchar(); Huff[i].weight=w; } for(i=0;in-1;i++) //构造哈夫曼树并生成该树的n-1个分支结点 { m1=m2=32767; x1=x2=0; for(j=0;jn+i;j++) //选取最小和次小两个权值结点并将其序号送x1和x2 { if(Huff[j].parent==-1Huff[j].weightm1) { m2=m1; x2=x1; m1=Huff[j].weight; x1=j; } else if(Huff[j].parent==-1Huff[j].weightm2) { m2=Huff[j].weight; x2=j; } } //将找出的两棵子树合并为一棵新的子树 Huff[x1].parent=n+i; Huff[x2].parent=n+i; Huff[n+i].weight=Huff[x1].weight+Huff[x2].weight; Huff[n+i].lchild=x1; Huff[n+i].rchild=x2; } 对哈夫曼树进行编码 void HuffmanCode(HNode Huff[],int n) //生成哈夫曼编码 { FILE *fw; HCode HuffCode[MAXSIZE/2],cd; // MAXSIZE/2为叶结点的最大个数 int i,j,c,p; for(i=0;in;i++) //求每个叶结点的哈夫曼编码 { HuffCode[i].weight=Huff[i].weight; cd.start=MAXBIT-1; c=i; p=Huff[c].parent; while(p!=-1) { if(Huff[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=Huff[c]