【正文】 } return tree。 } /*將整理完的字符串按出現(xiàn)次數(shù)從小到大的順序排列 */ linktree taxisnode(linktree tree) { linktree head,ph,pt,beforeph。 /*head 為新鏈表的表頭結點 */ head=(linktree)malloc(sizeof(Hftree))。/*創(chuàng)建新鏈表的頭結點 */ if(!head)return NULL。 headnext=NULL。 /*新結點的頭結點為空 ,后續(xù)結 點也為空 */ ph=head。 beforeph=head。 while(treenext) { pt=treenext。/*取被操作鏈表的首元結點 */ treenext=ptnext。 ptnext=NULL。 /*取出 pt 所指向的結點 */ ph=headnext。 beforeph=head。 if(headnext==NULL) headnext=pt。/*創(chuàng)建當前操作鏈表首元結點 */ else { while(phamp。amp。phweightptweight) {/*將被操作結點插入相應位置 */ ph=phnext。 beforeph=beforephnext。 } ptnext=beforephnext。 beforephnext=pt。 } } free(tree)。 return head。 } /*用排完序的字符串建立霍夫曼樹 */ 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))。/*申請新結點作為霍夫曼樹的中間結點 */ if(!newnode)return NULL。 newnodenext=NULL。 newnodemark=0。 newnodelchild=p。/*取鏈表頭結點后的兩個結點作為新結點的左、右兒子 */ newnoderchild=q。 pparent=newnode。 qparent=newnode。 newnodeweight=pweight+qweight。 p=treenext。 beforep=tree。 if(p!=NULLamp。amp。pweight=newnodeweight) {/*將新結點插入原鏈表的相應位置 */ Newnodenext=beforepnext。 beforepnext=newnode。 } else { while(p!=NULLamp。amp。pweightnewnodeweight) { p=pnext。 beforep=beforepnext。 } newnodenext=beforepnext。 beforepnext=newnode。 } } return (treenext)。 } /*對霍夫曼樹進行編碼 */ void Huffmancoding(linktree tree) { int index=0。 char *code。 linktree ptr=tree。 code=(char *)malloc(10*sizeof(char))。/*此數(shù)組用于統(tǒng)計霍夫曼編碼 */ printf(字符以及它的相應權數(shù) 霍夫曼編碼 \n\n)。 if(ptr==NULL) { printf(霍夫曼樹是空的 !\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)計輸入的 0、 1 序列 */ printf(霍夫曼編碼 相應字符 \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(沒有與最后的幾個 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)。 } /*釋放霍夫曼樹所占用的空間 */ 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 請輸入要測試的字符串 :\n)。 scanf(%s,character)。 printf(\n)。 temp=tidycharacter(character)。 ht=taxisnode(temp)。 htree=createHftree(ht)。 Huffmancoding(htree)。 printf(二、解碼 :\n 請輸入用于解碼的 0、 1 序列 :\n)。 scanf(%s,code)。 printf(\n)。 decode(htree,code)。 deletenode(htree)。 } 27 成績評定 成績 教師簽字