1、/*已解決哈夫曼編碼算法的實(shí)現(xiàn)用C+編寫懸賞分：10-解決時(shí)間：2008-12-1815:55基本要求：1 .任意性：用戶輸入任意的字符串，系統(tǒng)自動給出每個(gè)字符的哈夫曼編碼和對應(yīng)的哈夫曼樹2 .友好性：界面要友好，輸入有提示，盡量展示人性化3 .可讀性：源程序代碼清晰、有層次4 .健壯性：用戶輸入非法數(shù)據(jù)時(shí)，系統(tǒng)要及時(shí)給出警告信息*/#include#include#include#defineMAXLEN100typedefstructHuffmantreecharch;/*鍵值*/intweight,mark;/*weight為權(quán)值，mark為標(biāo)志域*/structHuffmantree*

2、parent,*lchild,*rchild,*next;Hftree,*linktree;/*整理輸入的字符串，合并相同的項(xiàng)，并求出每個(gè)字符在數(shù)組中出現(xiàn)的次數(shù)*/linktreetidycharacter(charcharacter)inti=0;linktreetree,ptr,beforeptr,node;/*鏈?zhǔn)?tree為頭結(jié)點(diǎn)，beforeptr為ptr的前一結(jié)點(diǎn),node為新申請的結(jié)點(diǎn)*/tree=(linktree)malloc(sizeof(Hftree);/*創(chuàng)建單鏈表的頭結(jié)點(diǎn)*/if(!tree)returnNULL;tree-next=NULL;/*頭結(jié)點(diǎn)為空，且后續(xù)結(jié)

3、點(diǎn)為空*/for(i=0;characteri!=0&characteri!=n;i+)/*遍歷直到字符串結(jié)束為止*/ptr=tree;beforeptr=tree;node=(linktree)malloc(sizeof(Hftree);/*新申請結(jié)點(diǎn)node*/if(!node)returnNULL;node-next=NULL;node-parent=NULL;node-lchild=NULL;node-rchild=NULL;/*置空*/node-mark=0;node-ch=characteri;node-weight=1;if(tree-next=NULL)tree-next=no

4、de;/*頭結(jié)點(diǎn)的下一結(jié)點(diǎn)為空，連接node*/elseptr=tree-next;while(ptr&ptr-ch!=node-ch)/*將指針移至鏈表尾*/ptr=ptr-next;beforeptr=beforeptr-next;/*后移*/if(ptr&ptr-ch=node-ch)/*如果鏈表中某結(jié)點(diǎn)的字符與新結(jié)點(diǎn)的字符相同*/*將該結(jié)點(diǎn)的權(quán)加一*/ptr-weight=ptr-weight+1;free(node);/*釋放node結(jié)點(diǎn)的存儲空間*/else/*新結(jié)點(diǎn)與表中結(jié)點(diǎn)不相同，將新結(jié)點(diǎn)插入鏈表后*/node-next=beforeptr-next;beforeptr-nex

5、t=node;/*node連接在beforeptr之后*/returntree;/*將整理完的字符串按出現(xiàn)次數(shù)從小到大的順序排列*/linktreetaxisnode(linktreetree)linktreehead,ph,pt,beforeph;/*head為新鏈表的表頭結(jié)點(diǎn)*/head=(linktree)malloc(sizeof(Hftree);/*創(chuàng)建新鏈表的頭結(jié)點(diǎn)*/if(!head)returnNULL;head-next=NULL;/*新結(jié)點(diǎn)的頭結(jié)點(diǎn)為空，后續(xù)結(jié)點(diǎn)也為空*/ph=head;beforeph=head;while(tree-next)(pt=tree-next;

6、/*取被操作鏈表的首元結(jié)點(diǎn)*/tree-next=pt-next;pt-next=NULL;/*取出pt所指向的結(jié)點(diǎn)*/ph=head-next;beforeph=head;if(head-next=NULL)head-next=pt;/*創(chuàng)建當(dāng)前操作鏈表首元結(jié)點(diǎn)*/else(while(ph&ph-weightweight)/*將被操作結(jié)點(diǎn)插入相應(yīng)位置*/ph=ph-next;beforeph=beforeph-next;pt-next=beforeph-next;beforeph-next=pt;free(tree);returnhead;/*用排完序的字符串建立霍夫曼樹*/linktre

7、ecreateHftree(linktreetree)linktreep,q,newnode,beforep;for(p=tree-next,q=p-next;p!=NULL&q!=NULL;p=tree-next,q=p-next)tree-next=q-next;q-next=NULL;p-next=NULL;newnode=(linktree)malloc(sizeof(Hftree);/*申請新結(jié)點(diǎn)作為霍夫曼樹的中間結(jié)點(diǎn)*/if(!newnode)returnNULL;newnode-next=NULL;newnode-mark=0;*/newnode-lchild=p;/*取鏈表頭結(jié)

8、點(diǎn)后的兩個(gè)結(jié)點(diǎn)作為新結(jié)點(diǎn)的左、右兒子newnode-rchild=q;p-parent=newnode;q-parent=newnode;newnode-weight=p-weight+q-weight;p=tree-next;beforep=tree;if(p!=NULL&p-weight=newnode-weight)/*將新結(jié)點(diǎn)插入原鏈表的相應(yīng)位置*/newnode-next=beforep-next;beforep-next=newnode;elsewhile(p!=NULL&p-weightweight)p=p-next;beforep=beforep-next;newnode-ne

9、xt=beforep-next;beforep-next=newnode;return(tree-next);/*對霍夫曼樹進(jìn)行編碼*/voidHuffmancoding(linktreetree)intindex=0;char*code;linktreeptr=tree;code=(char*)malloc(10*sizeof(char);/*此數(shù)組用于統(tǒng)計(jì)霍夫曼編碼*/printf(字符以及它的相應(yīng)權(quán)數(shù)霍夫曼編碼nn);if(ptr=NULL)printf(霍夫曼樹是空的！n);exit(0);elsewhile(ptr-lchild&ptr-rchild&ptr-mark=0)(whil

10、e(ptr-lchild&ptr-lchild-mark=0)(codeindex+=0;ptr=ptr-lchild;if(!ptr-lchild&!ptr-rchild)(ptr-mark=1;codeindex=0;printf(tw%c=%dttt,ptr-ch,ptr-weight);for(index=0;codeindex!=0;index+)printf(%c,codeindex);printf(n);ptr=tree;index=0;if(ptr-rchild&ptr-rchild-mark=0)(ptr=ptr-rchild;codeindex+=1;if(!ptr-lch

11、ild&!ptr-rchild)(ptr-mark=1;codeindex+=0;printf(tw%c=%dttt,ptr-ch,ptr-weight);for(index=0;codeindex!=0;index+)printf(%c,codeindex);printf(n);ptr=tree;index=0;if(ptr-lchild-mark=1&ptr-rchild-mark=1)(ptr-mark=1;ptr=tree;index=0;printf(n);free(code);)/*解碼*/voiddecode(linktreetree,charcode)(inti=0,j=0;c

12、har*char0_1;linktreeptr=tree;char0_1=(char*)malloc(10*sizeof(char);/*此數(shù)組用于統(tǒng)計(jì)輸入的0、1序列*/printf(霍夫曼編碼-相應(yīng)字符nn);for(j=0,ptr=tree;codei!=0&ptr-lchild&ptr-rchild;j=0,ptr=tree)(for(j=0;codei!=0&ptr-lchild&ptr-rchild;j+,i+)(if(codei=0)(ptr=ptr-lchild;char0_1j=0;)if(codei=1)(ptr=ptr-rchild;char0_1j=1;)if(!ptr

13、-lchild&!ptr-rchild)(char0_1j=0;for(j=0;char0_1j!=0;j+)printf(%c,char0_1j);printf(tt%cn,ptr-ch);)if(codei=0&ptr-lchild&ptr-rchild)(char0_1j=0;printf(沒有與最后的幾個(gè)0、1序列：%s相匹配的字符！n,char0_1);return;)free(char0_1);/*文件*/inchange()(FILE*fp;charch;if(fp=fopen(e10_1.c,rt)=NULL)(printf(Cannotopenfilestrikeanykey

14、exit!);getch();exit(1);ch=fgetc(fp);while(ch!=EOF)(putchar(ch);ch=fgetc(fp);fclose(fp);/*釋放霍夫曼樹所占用的空間*/voiddeletenode(linktreetree)(linktreeptr=tree;if(ptr)(deletenode(ptr-lchild);deletenode(ptr-rchild);free(ptr);voidmain()(intn;charcharacterMAXLEN,codeMAXLEN;FILE*f1;linktreetemp,ht,htree,ptr=NULL;printf(一、編碼:n請輸入要測試的