2024年10月哈夫曼树的编码输出程序（求用c语言实现霍夫曼编码的程序，最好能带讲解的程序感谢！）

　　⑴哈夫曼树的编码输出程序（求用c语言实现霍夫曼编码的程序，最好能带讲解的程序感谢！

　　⑵求用c语言实现霍夫曼编码的程序，最好能带讲解的程序感谢！

　　⑶//************************//哈夫曼树的构造哈夫曼树,哈夫曼编码*//************************#include《dos.h》#include《conio.h》#include《stdio.h》#include《stdlib.h》#include《string.h》typedefstruct{unsignedintweight;//结点权值unsignedintparent,lchild,rchild;//结点的父指针，左右孩子指针}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表voidCreateHuffmanTree(HuffmanTree&,unsignedint*,int);//生成一棵哈夫曼树voidHuffmanCoding(HuffmanTree,HuffmanCode&,int);//对哈夫曼树进行编码voidPrintHuffmanCode(HuffmanCode,unsignedint*,int);//显示哈夫曼编码voidSelect(HuffmanTree,int,int&,int&);//在数组中寻找权值最小的两个结点voidmain(){HuffmanTreeHT;//哈夫曼树HTHuffmanCodeHC;//哈夫曼编码表HCintn,i;//n是哈夫曼树叶子结点数unsignedint*w;//w存放叶子结点权值charj=’y’;textbackground();//设定屏幕颜色textcolor();clrscr();//程序解说printf(“本程序将演示构造哈夫曼树.

　　⑷“);printf(“首先输入叶子结点数目.

　　⑸“);printf(“然后输入每个叶子结点的权值.

　　⑹“);printf(“例如:

　　⑺“);printf(“程序会构造一棵哈夫曼树并显示哈夫曼编码.

　　⑻“);printf(“---

　　⑼“);printf(“---

　　⑽“);while(j!=’N’&&j!=’n’){printf(“请输入叶子结点数目:“);scanf(“%d“,&n);//输入叶子结点数if(n《=){printf(“该数不合理!

　　⑾“);continue;}w=(unsignedint*)malloc(n*sizeof(unsignedint));//开辟空间存放权值printf(“请输入各叶子结点的权值:

　　⑿“);for(i=;i《n;i++)scanf(“%d“,&w);//输入各叶子结点权值CreateHuffmanTree(HT,w,n);//生成哈夫曼树HuffmanCoding(HT,HC,n);//进行哈夫曼编码PrintHuffmanCode(HC,w,n);//显示哈夫曼编码printf(“哈夫曼树构造完毕，还要继续吗?(Y/N)“);scanf(“%c“,&j);}}voidCreateHuffmanTree(HuffmanTree&HT,unsignedint*w,intn){//w存放n个结点的权值，将构造一棵哈夫曼树HTinti,m;ints,s;HuffmanTreep;if(n《=)return;m=*n-;//n个叶子结点的哈夫曼树，有*n-个结点HT=(HuffmanTree)malloc((m+)*sizeof(HTNode));//开辟*n各结点空间，号单元不用for(p=HT+,i=;i《=n;++i,++p,++w)//进行初始化{p-》weight=*w;p-》parent=;p-》lchild=;p-》rchild=;}for(;i《=m;++i,++p){p-》weight=;p-》parent=;p-》lchild=;p-》rchild=;}for(i=n+;i《=m;++i)//建哈夫曼树{Select(HT,i-,s,s);//从HT中选择parent为且weight最小的两个结点，其序号分别为s和sHT.parent=i;//修改s和s结点的父指针parentHT.rchild=s;//修改i结点的左右孩子指针HT.weight;//修改权值}}voidHuffmanCoding(HuffmanTreeHT,HuffmanCode&HC,intn){//将有n个叶子结点的哈夫曼树HT进行编码，所编的码存放在HC中//方法是从叶子到根逆向求每个叶子结点的哈夫曼编码inti,c,f,start;char*cd;HC=(HuffmanCode)malloc((n+)*sizeof(char*));//分配n个编码的头指针向量cd=(char*)malloc(n*sizeof(char));//开辟一个求编码的工作空间cd=’’;//编码结束符for(i=;i《=n;++i)//逐个地求哈夫曼编码{start=n-;//编码结束位置for(c=i,f=HT.parent)//从叶子到根逆向求编码if(HT=’’;//若是左孩子编为’’elsecd=’’;//若是右孩子编为’’HC=(char*)malloc((n-start)*sizeof(char));//为第i个编码分配空间strcpy(HC);//将编码从cd复制到HC中}free(cd);//释放工作空间}voidPrintHuffmanCode(HuffmanCodeHC,unsignedint*w,intn){//显示有n个叶子结点的哈夫曼树的编码表inti;printf(“HuffmanCodeis:

　　⒀“);for(i=;i《=n;i++){printf(“%d---“,w);puts(HC);}printf(“

　　⒁“);}voidSelect(HuffmanTreeHT,intt,int&s,int&s){//在HT中选择parent不为且权值最小的两个结点，其序号分别为s和sinti,m,n;m=n=;for(i=;i《=t;i++){if(HT.weight《n))if(m《n){n=HT.weight;s=i;}else{m=HT.weight;s=i;}}if(s》s)//s放较小的序号{i=s;s=s;s=i;}}

　　⒂怎么样用c语言程序编码哈夫曼树

　　⒃#include《stdio.h》#include《stdlib.h》#include《string.h》#include《ctype.h》#include《limits.h》intfunction(charch,char*s){inti;for(i=;s!=’’;i++){if(ch==s)return;}return;}typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表//algo-.cpp求赫夫曼编码。实现算法.的程序intmin(HuffmanTreet,inti){//函数voidselect()调用intj,flag;unsignedintk=UINT_MAX;//取k为不小于可能的值for(j=;j《=i;j++)if(t.parent==)k=t.weight,flag=j;t.parent=;returnflag;}voidselect(HuffmanTreet,inti,int&s,int&s){//s为最小的两个值中序号小的那个s=min(t,i);s=min(t,i);/*if(s》s){j=s;s=s;s=j;}*/}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)//算法.{//w存放n个字符的权值(均》),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCintm,i,s,s,start;unsignedc,f;HuffmanTreep;char*cd;if(n《=)return;m=*n-;HT=(HuffmanTree)malloc((m+)*sizeof(HTNode));//号单元未用for(p=HT+,i=;i《=n;++i,++p,++w){(*p).weight=*w;(*p).parent=;(*p).lchild=;(*p).rchild=;}for(;i《=m;++i,++p)(*p).parent=;for(i=n+;i《=m;++i)//建赫夫曼树{//在HT中选择parent为且weight最小的两个结点,其序号分别为s和sselect(HT,i-,s,s);HT.parent=i;HT.rchild=s;HT.lchild=s;HT.weight;//printf(“HT.rchild:%d

　　⒄“,i,s,i,s);}//从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)malloc((n+)*sizeof(char*));//分配n个字符编码的头指针向量(不用)cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间cd=’’;//编码结束符for(i=;i《=n;i++){//逐个字符求赫夫曼编码start=n-;//编码结束符位置for(c=i,f=HT.parent)//从叶子到根逆向求编码if(HT.lchild==c)cd=’’;elsecd=’’;HC=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC);//从cd复制编码(串)到HC}free(cd);//释放工作空间}voidswap(int*a,int*b){intt;t=*a;*a=*b;*b=t;}voidswap(char*a,char*b){charch;ch=*a;*a=*b;*b=ch;}intmain(void){HuffmanTreeHT;HuffmanCodeHC;char*s,*s;inti,j=,n,count,*m,t,flag=;scanf(“%d“,&n);getchar();s=(char*)malloc((n+n)*sizeof(char));s=(char*)malloc(n*sizeof(char));memset(s,’’,n*sizeof(char));gets(s);count=strlen(s);for(i=;i《count;i++){if(!isspace(*(s+i))){if(function(*(s+i),s)){*(s+j)=*(s+i);j++;}}else;}m=(int*)malloc(j*sizeof(int));for(i=;i《j;i++)*(m+i)=;for(t=;t《j;t++){for(i=;i《count;i++){if(*(s+t)==*(s+i))*(m+t)+=;}}for(i=;i《j;i++)while(flag){flag=;for(t=;t《j-;t++){if(*(m+t)《*(m+t+)){swap(m+t,m+t+);swap(s+t,s+t+);flag=;}}}HuffmanCoding(HT,HC,m,j);for(i=,t=;i《=j;i++,t++){printf(“%c%d%s

　　⒅“,*(s+t),*(m+t),HC);}return;}

　　⒆哈夫曼树及哈夫曼编码译码的实现（根据程序画流程图及对每句程序注释

　　⒇这是以前写的，可是我不想加注释了，Huffman编码其实原理很简单的，你自己好好学下吧，一句一句注释也太夸张了啊。#include《string.h》#include《stdlib.h》#include《stdio.h》intm,s,s;typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreeHT,intn){inti,j;for(i=;i《=n;i++)if(HT.parent==){s=i;break;}for(j=i+;j《=n;j++)if(HT.parent==){s=j;break;}for(i=;i《=n;i++){if(HT.parent==)if(HT.weight)if(s!=i)s=i;}for(j=;j《=n;j++){if(HT.parent==)if(HT.weight)if(s!=j)s=j;}if(s》s){inttemp=s;s=s;s=temp;}}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){inti,j;char*cd;intp;intcdlen;if(n《=)return;m=*n-;HT=(HuffmanTree)malloc((m+)*sizeof(HTNode));for(i=;i《=n;i++){HT;HT.parent=;HT.lchild=;HT.rchild=;}for(i=n+;i《=m;i++){HT.weight=;HT.parent=;HT.lchild=;HT.rchild=;}//添加查看，便于调试printf(“构造过程显示：

　　⒈“);for(i=;i《=m;i++)printf(“%d%d%d%d%d

　　⒉“,i,HT.rchild);system(“pause“);for(i=n+;i《=m;i++){Select(HT,i-);HT.parent=i;HT.rchild=s;HT.weight;//添加查看，便于调试/*printf(“s=%d,s=%d

　　⒊“,s,s);for(j=;j《=i;j++)printf(“%d%d%d%d“,j,HT.rchild);system(“pause“);*/}cd=(char*)malloc(n*sizeof(char));p=m;cdlen=;for(i=;i《=m;i++)HT.weight=;while(p){if(HT.weight==){HT.weight=;if(HT.lchild!=){p=HT.lchild;cd=’’;}elseif(HT.rchild==){HC=(char*)malloc((cdlen+)*sizeof(char));cd=’’;strcpy(HC,cd);}}elseif(HT.weight==){HT.weight=;if(HT.rchild!=){p=HT.rchild;cd=’’;}}else{HT.weight=;p=HT.parent;--cdlen;}}}intmain(){HuffmanTreeHT;HuffmanCodeHC;int*w,n,i;printf(“请输入节点数：

　　⒋“);scanf(“%d“,&n);HC=(HuffmanCode)malloc(n*sizeof(HuffmanCode));w=(int*)malloc(n*sizeof(int));printf(“请输入节点的权值：

　　⒌“);for(i=;i《n;i++)scanf(“%d“,&w);HuffmanCoding(HT,HC,w,n);printf(“输出编码：

　　⒍“);for(i=;i《=n;i++)printf(“%d(%d):%s

　　⒎“,i,w);return;system(“pause“);}

　　⒏哈夫曼树怎么运行.代码完全看不懂，运行的窗口都不知道该输入什么，请指教~

　　⒐有个字符,分别是A,B,C,D,E,F,对应的权值分别是,,,,,,也就是说字符A的权值是,字符B的权值是,按此顺序,最后的字符F的权值是.求这个字符的哈夫曼编码.运行程序:输入叶子结点的总个数(n):?输入个叶子结点的字符(Data)和权值(Weight):No.=》Data:A??????Weight:No.=》Data:B??????Weight:No.=》Data:C??????Weight:No.=》Data:D??????Weight:No.=》Data:E??????Weight:No.=》Data:F??????Weight:输出哈夫曼编码:A?():?B?():?C?():?D?():?E?():?F?():?对应的哈夫曼树(带权值):?????????N??????/????????????N???????N????????????????/???????/?????????????????N????????????????/????????????????????N??????????????????/????????????????????????对应的哈夫曼树(带字符):(?注:哈夫曼树的左分支代表,右分支代表?)?????????N??????/????????????N???????N????????????????/???????/??????C????B???A????N????????????????/?????????????????D???N??????????????????/???????????????????F????E?例如:从根结点N到结点A,先经历右分支,后经历左分支,结点A的编码就是从根结点N到结点F,先经历三次右分支,最后经历左分支,结点F的编码就是#include《stdio.h》#define?max?struct?huffnode{????char?data;????int?weight;????int?parent;????int?left;????int?right;};struct?huffcode{????char?cd;????int?start;};int?main()??//原代码main(){????struct?huffnode?ht;????struct?huffcode?hcd,d;????int?i,k,f,l,r,n,c,m,m;????//printf(“please?input?n

　　⒑“);????printf(“输入叶子结点的总个数(n):?“);????scanf(“%d“,&n);????printf(“输入%d个叶子结点的字符(Data)和权值(Weight):

　　⒒“,n);????for(i=;i《=n;i++)????{????????getchar();?//吸收掉回车符’

　　⒓’????????//原代码printf(“NO.&d=》Data:“,i);????????printf(“NO.%d=》Data:“,i);????????scanf(“%c“,&ht.data);????????printf(“ ?Weight:“);????????scanf(“%d“,&ht.weight);????}????for(i=;i《=*n-;i++)?//所有结点初始化????{????????ht.right=;????}????//创建“哈夫曼树“????//原代码for(i=;i《=*n-;i++)????for(i=;i《n;i++)????{????????//查找“最小值“和“次最小值“的下标????????//l是最小值的下标,r是次最小值的下标????????m=;????????l=r=;????????//原代码for(k=;k《=i-;k++)????????for(k=;k《=n+i-;k++)????????{????????????//原代码if(ht.weight==)????????????if(ht.parent==)????????????{????????????????if(ht.weight《m)????????????????{????????????????????m=m;????????????????????r=l;??//原代码r=;????????????????????m=ht.weight;????????????????????l=k;????????????????}????????????????else?if(ht.weight《m)????????????????{????????????????????m=ht.weight;????????????????????r=k;????????????????}????????????}????????}????????//原代码ht.parent=i;????????//原代码ht.parent=i;????????//原代码ht.weight;????????//原代码ht.left=l;????????//原代码ht.right=r;????????ht.parent=n+i;????????ht.parent=n+i;????????ht.weight;?//新结点????????ht.left=l;????????ht.right=r;????}????//编码过程????for(i=;i《=n;i++)????{????????d.start=n;????????c=i;????????f=ht.parent;????????while(f!=)????????{????????????if(ht.left==c)????????????{???????????????d.cd=’’;????????????}????????????else????????????{???????????????d.cd=’’;????????????}????????????d.start=d.start-;????????????c=f;????????????f=ht.parent;????????}????????//原代码hcd=d;????????hcd.start=d.start;????????for(k=d.start+;?k《=n;?k++)????????{????????????hcd;????????}????}????//输出每个叶子结点的哈夫曼编码????//printf(“output?huff_code:

　　⒔“);????printf(“输出哈夫曼编码:

　　⒕“);????for(i=;i《=n;i++)????{????????printf(“%c?(%d):?“,ht.weight);????????//原代码for(k=hcd.start;k《=n;k++)????????for(k=hcd.start+;k《=n;k++)????????{????????????printf(“%c“,hcd);????????}????????printf(“

　　⒖“);????}????return?;??//int?main()要有返回值}

　　⒗哈夫曼编码的C程序怎么写

　　⒘去年做的课程设计，有什么不合要求的自己改改#include《string.h》#include《stdlib.h》#include《stdio.h》intm,s,s;typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar*HuffmanCode;//动态分配数组存储哈夫曼编码表voidSelect(HuffmanTreeHT,intn){inti,j;for(i=;i《=n;i++)if(!HT.parent){s=i;break;}for(j=i+;j《=n;j++)if(!HT.parent){s=j;break;}for(i=;i《=n;i++)if((HT.parent)&&(s!=i))s=i;for(j=;j《=n;j++)if((HT.parent)&&(s!=j))s=j;}voidHuffmanCoding(HuffmanTree&HT,HuffmanCodeHC,int*w,intn){//算法.//w存放n个字符的权值(均》)，构造哈夫曼树HT，//并求出n个字符的哈夫曼编码HCinti,j;char*cd;intp;intcdlen;if(n《=)return;m=*n-;HT=(HuffmanTree)malloc((m+)*sizeof(HTNode));//号单元未用for(i=;i《=n;i++){//初始化HT;HT.parent=;HT.lchild=;HT.rchild=;}for(i=n+;i《=m;i++){//初始化HT.weight=;HT.parent=;HT.lchild=;HT.rchild=;}puts(“

　　⒙哈夫曼树的构造过程如下所示：“);printf(“HT初态:

　　⒚结点weightparentlchildrchild“);for(i=;i《=m;i++)printf(“

　　⒛%d%d%d%d%d“,i,HT.weight,HT.rchild);printf(“按任意键，继续...“);getchar();for(i=n+;i《=m;i++){//建哈夫曼树//在HT中选择parent为且weight最小的两个结点，//其序号分别为s和s。Select(HT,i-);HT.parent=i;HT.rchild=s;HT.weight;printf(“

　　select:s=%ds=%d

　　“,s,s);printf(“结点weightparentlchildrchild“);for(j=;j《=i;j++)printf(“

　　%d%d%d%d%d“,j,HT.weight,HT.rchild);printf(“按任意键，继续...“);getchar();}//------无栈非递归遍历哈夫曼树，求哈夫曼编码cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间p=m;cdlen=;for(i=;i《=m;++i)//遍历哈夫曼树时用作结点状态标志HT.weight=;while(p){if(HT.weight==){//向左HT.weight=;if(HT=’’;}elseif(HT.rchild==){//登记叶子结点的字符的编码HC=(char*)malloc((cdlen+)*sizeof(char));cd,cd);//复制编码(串)}}elseif(HT.weight==){//向右HT.weight=;if(HT=’’;}}else{//HT.weight==，退回退到父结点，编码长度减HT.parent;--cdlen;}}}//HuffmanCodingvoidmain(){HuffmanTreeHT;HuffmanCode*HC;int*w,n,i;puts(“输入结点数:“);scanf(“%d“,&n);HC=(HuffmanCode*)malloc(n*sizeof(HuffmanCode));w=(int*)malloc(n*sizeof(int));printf(“输入%d个结点的权值

　　“,n);for(i=;i《n;i++)scanf(“%d“,&w);HuffmanCoding(HT,HC,w,n);puts(“

　　各结点的哈夫曼编码:“);for(i=;i《=n;i++)printf(“%d(%d):%s

　　“,i,w);getchar();}

　　手打的,你最好编译一下以免我哪里敲错了(百度不能显示行首空格真是不爽)//哈夫曼树和~编码的存储表示typedefstruct{unsignedintweight;//权值unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表voidHoffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n个字符的权值(均》),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HCif(n《=)return;m=*n-;HT=(HuffmanTree)malloc((m+)*sizeof(HTNode));//号单元未采用for(p=HT,i=;i《=n;++i,++p,++w)*p={*w,,,};for(;i《=m;++i;++p)*p={,,,}for(i=n+;i《=m;++i){//建哈夫曼树//在HT选择parent为且weight最小的两个结点编号分别为s,sSelect(HT,i-,s,s);HT.parent=i;HT.rchild=s;HT.weight;}//从叶子到根逆向求每个字符的哈夫曼编码HC=(HuffmanCode)malloc((n+)*sizeof(char*));//分配n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间cd=““;//编码结束符for(i=;i《=n;++i){//逐个字符求哈夫曼编码start=n-;//编码结束符位置for(c=i,f=HT.parent)//从叶子逆向向根求编码if(HT=““;elsecd=““;HC=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC);//从cd复制编码(串)到HC}free(cd);//释放工作空间}//HuffmanCoding

　　编写一个程序，构造一棵哈夫曼树

　　#include《stdio.h》#include《string.h》#defineN//叶子结点数#defineM*N-//树中结点总数typedefstruct{chardata;}printf(“

　　“);createht(ht,n);createhcode(ht,hcd,n);disphcode(ht,hcd,n);printf(“

　　哈夫曼编码C语言实现

　　我写了一个注释较为完整且压缩、解压缩比较全面的：#include《stdio.h》#include《conio.h》#defineMAX_FILE/*假设的文件最大长度*/#defineMAXLIST/*最大MAP值*/#defineMAX_HOFFMAN_LENGTH/*哈夫曼编码长度*/chardictionary为字符*/charfileContent;/*处理的字符串大小*/intHoffman={};/*哈夫曼编码序列*/charHoffmanList={};/*哈夫曼编码对应的字符有序序列*/charHoffFileCode={};/*哈夫曼编码字符串序列*/charHoffFile={};/*编码到假设的文件的哈夫曼压缩格式：依次存储原字符串长度(字节存储:可扩展到字节)、哈夫曼编码数(字节)、每个哈夫曼编码的长度序列、每个哈夫曼编码对应的字符序列、编码过的哈夫曼字符串*/charGetFile={};/*解码序列*/voidShellSort(charpData,intCount)/*Shell排序，用于准备有序化要构造的编码权值构造哈夫曼树做准备*/{intstep={,,,};/*增量序列*/intiTemp,cTemp;intk,s,w,i,j;for(i=;i《;i++){k=step;s=-k;for(j=k;j《Count;j++){iTemp=pData;cTemp=pData;w=j-k;if(s==){s=-k;s++;pData=iTemp;pData=cTemp;}while((iTemp《pData)&&(w》=)&&(w《=Count)){pData;/*权值交换*/pData;/*字符交换*/w=w-k;}pData=iTemp;pData=cTemp;}}}structTNode/*哈夫曼树结点*/{structTNode*pNode;structTNode*lNode;structTNode*rNode;chardictionary;charweight;};voidTNode_init(structTNode*tn,chardic,charwei){tn-》pNode=;tn-》lNode=;tn-》rNode=;tn-》dictionary=dic;tn-》weight=wei;}structLNode/*链表结点,用于存储哈夫曼树结点,进而构造哈夫曼树(保证每一步链表结点包含的哈夫曼结点都是有序的)*/{structLNode*prev;structLNode*next;structTNode*tnode;};voidLNode_init(structLNode*ln){ln-》prev=ln-》next=;ln-》tnode=;}intlen=;/*哈夫曼编码数*/intdeep=-;/*深度*/voidPreorder(structTNode*p);/*前序遍历*/voidbyLeft(structTNode*p)/*经由左结点*/{deep++;Hoffman=;Preorder(p);Hoffman=;deep--;}voidbyRight(structTNode*p)/*经由右结点*/{deep++;Hoffman=;Preorder(p);Hoffman=;deep--;}voidPreorder(structTNode*p){inti;if(p-》lNode!=)/*当左子结点非空则遍历*/{byLeft(p-》lNode);}if(p-》rNode!=)/*当右子结点非空则遍历*/{byRight(p-》rNode);}if((p-》lNode==)&&(p-》rNode==))/*当左右结点都为空，则增加哈夫曼编码数到另一个记录*/{Hoffman=;i=;for(;Hoffman!=;i++){Hoffman;}Hoffman=;HoffmanList=p-》dictionary;len++;}}chargenerateOne(intk)/*产生k个连续的二进制串,比如,,,用于编码进假设的文件*/{charc=;for(;k!=;k--){c|=(《《(k-));}returnc;}intpareBits(charb,charb,charc,intl,intd)/*判断由组成的位二进制数以d为起点,是否是长度为l的c二进制串（哈夫曼编码的前缀*/{unsignedchart=(((((xff&b)《《)|(xff&b))》》(-d))&xff);return(((t)&((generateOne(l)《《(-l))&xff))==((c《《(-l))&xff));}intmain(){structLNode*t,*p;structLNode*head;structTNode*tempTNode,*k;inti=,j,k;unsignedshortfileLen=;intlen=,l,b,b,d;charc;intcode,h=;intcodeLen=,total=;/*或许假定的文件字符串向量中的字符串*/printf(“pleaseEnterstringtobepressed:“);scanf(“%s“,&fileContent);/*Hash进dictionary*/for(;fileContent!=’’;i++,fileLen++){++dictionary;dictionary;}/*把Hash了的dictionary向前靠拢*/{for(i=;i!=MAXLIST;i++){if(dictionary!=){dictionary;dictionary;len++;}}}printf(“thenumberofHuffman’scodes:%d

　　“,len);/*对dictionary按权值进行排序*/ShellSort(dictionary,len);/*构造链表,链表中放有序dictionary权值的树结点*/head=(structLNode*)malloc(sizeof(structLNode)),p=head;LNode_init(head);head-》next=(structLNode*)malloc(sizeof(structLNode));LNode_init(head-》next);tempTNode=(structTNode*)malloc(sizeof(structLNode));TNode_init(tempTNode,dictionary);head-》tnode=tempTNode;{for(i=;i!=len-;i++){p-》next-》prev=p-》next;p=p-》next;p-》next=(structLNode*)malloc(sizeof(structLNode));LNode_init(p-》next);tempTNode=(structTNode*)malloc(sizeof(structTNode));TNode_init(tempTNode,dictionary);p-》tnode=tempTNode;}}free(p-》next);p-》next=;/*每次最小权值的前面两个链表结点中的树结点组成一个子树,子树有合权值,子数的根按权值排序进链表*/for(p=head;p-》next!=;){p-》tnode-》pNode=(structTNode*)malloc(sizeof(structTNode));TNode_init(p-》tnode-》pNode,’’,(p-》tnode-》weight)+(p-》next-》tnode-》weight));p-》next-》tnode-》pNode=p-》tnode-》pNode;p-》tnode-》pNode-》lNode=p-》tnode;p-》tnode-》pNode-》rNode=p-》next-》tnode;head=p-》next;free(p);p=head;p-》tnode=p-》tnode-》pNode;for(t=head;t-》next!=;t=t-》next){if(t-》tnode-》weight》t-》next-》tnode-》weight){k=t-》tnode;t-》tnode=t-》next-》tnode;t-》next-》tnode=k;}}}/*前序遍历构造哈夫曼编码*/Preorder(p-》tnode);{for(i=;i!=len;i++)dictionary=i;}/*存储字符串的哈夫曼压缩编码串,并且打包文件格式*/{for(i=;i!=fileLen;i++){intj=dictionary;for(k=;Hoffman!=;k++){HoffFileCode《《(-total%));code;if(((total+)%)==){HoffFile;codeLen++;}total++;}}}HoffFile;HoffFile=(fileLen);/*解压缩假定的文件HoffFile成为原字符串序列*/printf(“Huffman’scodelist:

　　“);HoffFile=len;{for(i=,j=;i!=len;i++,j=){for(;Hoffman!=;j++);HoffFile=j;HoffFile;for(k=;k!=j;k++){printf(“%d“,Hoffman);HoffFile《《(j--k));}printf(“:%d

　　“,HoffmanList);}}{for(i=,j=;i!=(HoffFile&xff);i++){for(k=;k!=HoffFile;k++){l=HoffFile;c=HoffFile;if(pareBits(b,b,c,l,d)){j+=HoffFile;GetFile;break;}}}}{printf(“HuffmancodeListPressed:

　　“);for(i=;i!=h;i++){printf(“%c“,code);if((i+)%==)printf(““);}}printf(“

　　“);{printf(“Huffmancodepackaged:

　　“);for(i=;i!=HoffFile*;i++){printf(“%c“,HoffFile);}printf(“

　　“);}printf(“Theinitiallen:%d

　　“,fileLen);printf(“Thestringlenpressed:%d

　　“,(h)/+);printf(“Therate%.f%“,((h/.+)/fileLen)*);{printf(“Thenumberofbytes:%d

　　“,(HoffFile&xff));printf(“Thestringdecoded:“);for(i=;i!=(HoffFile&xff);i++){printf(“%c“,GetFile);}printf(“

　　“);}getch();return;}

　　哈夫曼树和编码应用用C++实现

　　#include《stdio.h》#defineMAXBIT/*定义哈夫曼编码的最大长度*/#defineMAXVALUE/*定义最大权值*/#defineMAXLEAF/*定义哈夫曼树中最多叶子节点个数*/#defineMAXNODEMAXLEAF*-/*哈夫曼树最多结点数*/typedefstruct{/*哈夫曼编码信息的结构*/intbit;intstart;}Hcodetype;typedefstruct{/*哈夫曼树结点的结构*/intweight;intparent;intlchild;intrchild;}Hnodetype;voidhuffmantree(Hnodetypehuffnode,intn)/*构造哈夫曼树的函数*/{inti,j,m,m,x,x;for(i=;i《*n-;i++)/*存放哈夫曼树结点的数组huffnode初始化*/{huffnode.weight=;huffnode.parent=-;huffnode.lchild=-;huffnode.rchild=-;}for(i=;i《n;i++)/*输入入N个叶子节点的权值*/{printf(“pleaseinput%dcharacter’sweight

　　“,i);scanf(“%d“,&huffnode.weight);}for(i=;i《n-;i++)/*开始循环构造哈夫曼树*/{m=m=MAXVALUE;x=x=;for(j=;j《n+i;j++){if(huffnode.parent==-){m=m;x=x;m=huffnode.weight;x=j;}elseif(huffnode.parent==-){m=huffnode.weight;x=j;}}huffnode.parent=n+i;huffnode.parent=n+i;huffnode.weight;huffnode.lchild=x;huffnode.rchild=x;}}voidmain(){Hnodetypehuffnode;Hcodetypehuffcode,cd;inti,j,c,p,n;printf(“pleaseinputn

　　“);scanf(“%d“,&n);/*输入叶子节点个数*/huffmantree(huffnode,n);/*建立哈夫曼树*/for(i=;i《n;i++)/*该循环求每个叶子节点对应字符的哈夫曼编码*/{cd.start=n-;c=i;p=huffnode.parent;while(p!=-){if(huffnode.lchild==c)cd.bit=;elsecd.bit=;cd.start--;c=p;p=huffnode.parent;}for(j=cd.start+;j《n;j++)/*保存求出的每个叶节点的哈夫曼编码和编码的起始位*/huffcode;huffcode.start=cd.start;}for(i=;i《n;i++)/*输出每个叶子节点的哈夫曼编码*/{printf(“%dcharacteris:“,i);for(j=huffcode.start+;j《n;j++)printf(“%d“,huffcode);printf(“

　　已经构造好了一颗哈夫曼树，怎么输出哈弗曼编码

　　以先根次序遍历二叉树。然后还要定义一整数a，初始值为。在访问某一节点时将其作为参数传入，如果访问的是左节点传入a*，访问右节点传入a*+，也就是在a的二进制数据中，向左走在末尾加个，向右走加个（初始化为是为了避免开始时向左走，无法加零的情况，输出时要将首位的去掉，即visit（root，a，visit（left，a*，visit（right，a*+。访问到叶子节点时将a转化成二进制，再将首位的去掉即可。当然你也可以定义一个字符串，然后在末尾加加，只是这样递归起来开销比较大，用整数*的方法比较简单，但是最后需要转化处理。