设计一个利用哈夫曼算法的编码系统

1、设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】1) 将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)2) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；3) 编码：利用建好的哈夫曼树生成哈夫曼编码；4) 输出（1）各个字符的编码；（2）1111111;#include#include#include#define M 50#define MAX 1000;typedef structint weight;/结点权值 int parent,lchild,rchild;HTNODE,*HUFFMANTREE

2、;typedef char* HUFFMANCODE;/动态分配数组存储哈夫曼编码表HUFFMANTREE huffmantree(int n,int weight)/构建哈夫曼树int m1,m2,k;int i,j,x1,x2;HUFFMANTREE ht;ht=(HUFFMANTREE)malloc(2*n)*sizeof(HTNODE);for(i=1;i(2*n);i+)/初始化哈夫曼树中各结点的数据，没初始值的赋值为0hti.parent=hti.lchild=hti.rchild=0;if(i=n)hti.weight=weighti;elsehti.weight=0;for(i

3、=1;in;i+)/每一重循环从森林中选择最小的两棵树组建成一颗新树m1=m2=MAX;x1=x2=0;for(j=1;j(n+i);j+)if(htj.weightm1)&(htj.parent=0)m2=m1;x2=x1;m1=htj.weight;x1=j;else if(htj.weightm2)&(htj.parent=0)m2=htj.weight;x2=j;k=n+i;htx1.parent=htx2.parent=k;htk.weight=m1+m2;htk.lchild=x1;htk.rchild=x2;return ht;void huffmancoding(const i

4、nt n,HUFFMANCODE hc,HUFFMANTREE ht,char str)int i,start,child,father;char *cd;hc=(HUFFMANCODE)malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间cdn-1=0;/编码结束符for(i=1;i=n;+i)/逐个字符求哈夫曼编码start=n-1;for(child=i,father=hti.parent;father!=0;child=father,father=htfather.paren

5、t)/*从叶子结点到根结点求逆向编码*/if(htfather.lchild=child)cd-start=0;elsecd-start=1;hci=(char*)malloc(n-start)*sizeof(char);/为i个字符编码分配空间strcpy(hci,&cdstart);/从cd复制哈夫曼编码串到hcfree(cd);/释放工作空间for(i=1;i=n;+i)printf(%c的编码:,stri);printf(%sn,hci);void main()int i,j,k;char str50;int weight50;printf(请输入字符(一次性连续输入所求的字符):);

6、/*如:abcjhjg不要输成ab cj hig,即字符间不加空格*/gets(str); for(j=0;j0;j-)strj=strj-1;strn+1=0;for(k=0;k0;k-)weightk=weightk-1;weight0=0;HUFFMANCODE hc=NULL;HUFFMANTREE ht;ht=huffmantree(n,weight);huffmancoding(n,hc,ht,str);补充：噢，我忘了你需要存档。现在太晚，明天再改一下。补充：这个是带有存盘的程序。#include#include#include#define M 50#define MAX 10

7、00;typedef int Elempe;typedef structint weight;/结点权值 int parent,lchild,rchild;HTNODE,*HUFFMANTREE;typedef char* HUFFMANCODE;/动态分配数组存储哈夫曼编码表HUFFMANTREE huffmantree(int n,int weight)/构建哈夫曼树int m1,m2,k;int i,j,x1,x2;HUFFMANTREE ht;ht=(HUFFMANTREE)malloc(2*n)*sizeof(HTNODE);for(i=1;i(2*n);i+)/初始化哈夫曼树中各结

8、点的数据，没初始值的赋值为0hti.parent=hti.lchild=hti.rchild=0;if(i=n)hti.weight=weighti;elsehti.weight=0;for(i=1;in;i+)/每一重循环从森林中选择最小的两棵树组建成一颗新树m1=m2=MAX;x1=x2=0;for(j=1;j(n+i);j+)if(htj.weightm1)&(htj.parent=0)m2=m1;x2=x1;m1=htj.weight;x1=j;else if(htj.weightm2)&(htj.parent=0)m2=htj.weight;x2=j;k=n+i;htx1.paren

9、t=htx2.parent=k;htk.weight=m1+m2;htk.lchild=x1;htk.rchild=x2;return ht;void huffmancoding(const int n,HUFFMANCODE hc,HUFFMANTREE ht,char str)int i,start,child,father;char *cd;hc=(HUFFMANCODE)malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间cdn-1=0;/编码结束符for(i=1;i=n;+

10、i)/逐个字符求哈夫曼编码start=n-1;for(child=i,father=hti.parent;father!=0;child=father,father=htfather.parent)/*从叶子结点到根结点求逆向编码*/if(htfather.lchild=child)cd-start=0;elsecd-start=1;hci=(char*)malloc(n-start)*sizeof(char);/为i个字符编码分配空间strcpy(hci,&cdstart);/从cd复制哈夫曼编码串到hcfree(cd);/释放工作空间for(i=1;i=n;+i)printf(%c的编码:

11、,stri);printf(%sn,hci);void Save(int a,const int& n)FILE *fp;int i,count=0,flag=1;fp=fopen(data.txt,wb+);for(i=1;i=n;i+)if(fwrite(&ai,sizeof(1),1,fp)=1)count+;elseflag=0;printf(数据保存失败!n);break;if(flag)printf(n数据保存成功!(有%d个权值已保存)n,count);fclose(fp);void main()FILE fp;int i,j,k;char str50;int weight50;

12、printf(请输入字符(一次性连续输入所求的字符):);/*如:abcjhjg不要输成ab cj hig,即字符间不加空格*/gets(str); for(j=0;j0;j-)strj=strj-1;strn+1=0;for(k=0;k0;k-)weightk=weightk-1;weight0=0;HUFFMANCODE hc=NULL;HUFFMANTREE ht;ht=huffmantree(n,weight);huffmancoding(n,hc,ht,str);Save(weight,n);2222222222;#include#include#define max 50struc

13、t aint weight;int parent,lchild,rchild;struct bchar cdmax;int start;void main()struct a ht2*max;struct b hcdmax,d;int i,k,n,c,s1,s2,m1,m2,f;printf(输入n:);scanf(%d,&n);for(i=1;i=n;i+)printf(输入权值:);scanf(%d,&hti.weight);hti.parent=0;for(;i=2*n-1;i+)hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i=2*n-1;i+)m1=m2=30000;s1=s2=0;for(k=1;k=i-1;k+)if(htk.parent=0 & htk.weightm1)m2=m1;s2=s1;m1=htk.weight;s1=k;else if(htk.parent=0 & htk.weightm2)m2=htk.weight;s2=k;hts1.parent=hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;for(i=1;i=n;i+)d.start=n-1;