【正文】 } return tree。 } /*將整理完的字符串按出現(xiàn)次數(shù)從小到大的順序排列 */ linktree taxisnode(linktree tree) { linktree head,ph,pt,beforeph。 /*head 為新鏈表的表頭結(jié)點(diǎn) */ head=(linktree)malloc(sizeof(Hftree))。/*創(chuàng)建新鏈表的頭結(jié)點(diǎn) */ if(!head)return NULL。 headnext=NULL。 /*新結(jié)點(diǎn)的頭結(jié)點(diǎn)為空 ,后續(xù)結(jié) 點(diǎn)也為空 */ ph=head。 beforeph=head。 while(treenext) { pt=treenext。/*取被操作鏈表的首元結(jié)點(diǎn) */ treenext=ptnext。 ptnext=NULL。 /*取出 pt 所指向的結(jié)點(diǎn) */ ph=headnext。 beforeph=head。 if(headnext==NULL) headnext=pt。/*創(chuàng)建當(dāng)前操作鏈表首元結(jié)點(diǎn) */ else { while(phamp。amp。phweightptweight) {/*將被操作結(jié)點(diǎn)插入相應(yīng)位置 */ ph=phnext。 beforeph=beforephnext。 } ptnext=beforephnext。 beforephnext=pt。 } } free(tree)。 return head。 } /*用排完序的字符串建立霍夫曼樹(shù) */ linktree createHftree(linktree tree) { linktree p,q,newnode,beforep。 23 for(p=treenext,q=pnext。p!=NULLamp。amp。q!=NULL。p=treenext,q=pnext) { treenext=qnext。 qnext=NULL。 pnext=NULL。 newnode=(linktree)malloc(sizeof(Hftree))。/*申請(qǐng)新結(jié)點(diǎn)作為霍夫曼樹(shù)的中間結(jié)點(diǎn) */ if(!newnode)return NULL。 newnodenext=NULL。 newnodemark=0。 newnodelchild=p。/*取鏈表頭結(jié)點(diǎn)后的兩個(gè)結(jié)點(diǎn)作為新結(jié)點(diǎn)的左、右兒子 */ newnoderchild=q。 pparent=newnode。 qparent=newnode。 newnodeweight=pweight+qweight。 p=treenext。 beforep=tree。 if(p!=NULLamp。amp。pweight=newnodeweight) {/*將新結(jié)點(diǎn)插入原鏈表的相應(yīng)位置 */ Newnodenext=beforepnext。 beforepnext=newnode。 } else { while(p!=NULLamp。amp。pweightnewnodeweight) { p=pnext。 beforep=beforepnext。 } newnodenext=beforepnext。 beforepnext=newnode。 } } return (treenext)。 } /*對(duì)霍夫曼樹(shù)進(jìn)行編碼 */ void Huffmancoding(linktree tree) { int index=0。 char *code。 linktree ptr=tree。 code=(char *)malloc(10*sizeof(char))。/*此數(shù)組用于統(tǒng)計(jì)霍夫曼編碼 */ printf(字符以及它的相應(yīng)權(quán)數(shù) 霍夫曼編碼 \n\n)。 if(ptr==NULL) { printf(霍夫曼樹(shù)是空的 !\n)。 exit(0)。 } else { 24 while(ptrlchildamp。amp。ptrrchildamp。amp。ptrmark==0) { while(ptrlchildamp。amp。ptrlchildmark==0) { code[index++]=39。039。 ptr=ptrlchild。 if(!ptrlchildamp。amp。!ptrrchild) { ptrmark=1。 code[index]=39。\039。 printf(\tw[%c]=%d\t\t\t,ptrch,ptrweight)。 for(index=0。code[index]!=39。\039。index++) printf(%c,code[index])。 printf(\n)。 ptr=tree。 index=0。 } } if(ptrrchildamp。amp。ptrrchildmark==0) { ptr=ptrrchild。 code[index++]=39。139。 } if(!ptrlchildamp。amp。!ptrrchild) { ptrmark=1。 code[index++]=39。\039。 printf(\tw[%c]=%d\t\t\t,ptrch,ptrweight)。 for(index=0。code[index]!=39。\039。index++) printf(%c,code[index])。 printf(\n)。 ptr=tree。 index=0。 } if(ptrlchildmark==1amp。amp。ptrrchildmark==1) { ptrmark=1。 ptr=tree。 index=0。 } } } printf(\n)。 free(code)。 } /*解碼 */ void decode(linktree tree,char code[]) { 25 int i=0,j=0。 char *char0_1。 linktree ptr=tree。 char0_1=(char *)malloc(10*sizeof(char))。/*此數(shù)組用于統(tǒng)計(jì)輸入的 0、 1 序列 */ printf(霍夫曼編碼 相應(yīng)字符 \n\n)。 for(j=0,ptr=tree。code[i]!=39。\039。amp。amp。ptrlchildamp。amp。ptrrchild。j=0,ptr=tree) { for(j=0。code[i]!=39。\039。amp。amp。ptrlchildamp。amp。ptrrchild。j++,i++) { if(code[i]==39。039。) { ptr=ptrlchild。 char0_1[j]=39。039。 } if(code[i]==39。139。) { ptr=ptrrchild。 char0_1[j]=39。139。 } } if(!ptrlchildamp。amp。!ptrrchild) { char0_1[j]=39。\039。 for(j=0。char0_1[j]!=39。\039。j++) printf(%c,char0_1[j])。 printf(\t\t%c\n,ptrch)。 } if(code[i]==39。\039。amp。amp。ptrlchildamp。amp。ptrrchild) { char0_1[j]=39。\039。 printf(沒(méi)有與最后的幾個(gè) 0、 1 序列： %s 相匹配的字符 !\n,char0_1)。 return。 } } free(char0_1)。 } /*文件 */ void inchange() { FILE *fp。 char ch。 if((fp=fopen(,rt))==NULL) { printf(Cannot open file strike any key exit!)。 //getch()。 exit(1)。 } ch=fgetc(fp)。 while (ch!=EOF) 26 { putchar(ch)。 ch=fgetc(fp)。 } fclose(fp)。 } /*釋放霍夫曼樹(shù)所占用的空間 */ void deletenode(linktree tree) { linktree ptr=tree。 if(ptr) { deletenode(ptrlchild)。 deletenode(ptrrchild)。 free(ptr)。 } } void main() { int n。 char character[MAXLEN],code[MAXLEN]。 FILE *fp。 linktree temp,ht,htree,ptr=NULL。 printf(一、編碼 :\n 請(qǐng)輸入要測(cè)試的字符串 :\n)。 scanf(%s,character)。 printf(\n)。 temp=tidycharacter(character)。 ht=taxisnode(temp)。 htree=createHftree(ht)。 Huffmancoding(htree)。 printf(二、解碼 :\n 請(qǐng)輸入用于解碼的 0、 1 序列 :\n)。 scanf(%s,code)。 printf(\n)。 decode(htree,code)。 deletenode(htree)。 } 27 成績(jī)?cè)u(píng)定 成績(jī) 教師簽字