906 Chapter 20. Less-Numerical Algorithms #include "nrutil.h" typedef struct unsigned long *icod,*ncod,*left,*right,nch,nodemax; huffcode; void hufmak(unsigned long nfreq[],unsigned long nchin,unsigned long *ilong, unsigned long *nlong,huffcode *hcode) Given the frequency of occurrence table nfreq[1..nchin]of nchin characters,construct the Huffman code in the structure hcode.Returned values ilong and nlong are the character number that produced the longest code symbol,and the length of that symbol.You should check that nlong is not larger than your machine's word length. void hufapp(unsigned long index[],unsigned long nprob[],unsigned long n, uns1g即ed1ong1) int ibit: nted for 18881892 long node,*up; unsigned long j,k,*index,n,nused,*nprob; 1-800 static unsigned long setbit [32]={0x1L,Ox2L,0x4L,0x8L,0x10L,Ox20L, 0x40L,0x80L,0x100L,0x200L,0x400L,0x800L,0x1000L,0x2000L, 0x4000L,0x8000L,0x10000L,0x20000L,0x40000L,0x80000L,0x100000L, Cambridge 0x200000L,0x400000L,0x800000L,0x1000000L,0x2000000L,0x4000000L, from NUMERICAL RECIPES IN 0x8000000L,0x10000000L,0x20000000L,0x40000000L,0x80000000L]; (North to make hcode->nch=nchin; Initialization. index=lvector(1,(long)(2*hcode->nch-1)); THE up=(long *)lvector(1,(long)(2*hcode->nch-1)); Vector that will keep track of America server computer, e University Press. nprob=lvector(1,(long)(2*hcode->nch-1)); heap. one paper ART for (nused=0,j=1;j<=hcode->nch;j++) nprob[j]=nfreq[]: hcode->icod[j]=hcode->ncod[j]=0; Programs if (nfreg[j])index[++nused]=j; for (j=nused;j>=1;j--)hufapp(index,nprob,nused,j); strictly prohibited Sort nprob into a heap structure in index. k=hcode->nch; Combine heap nodes,remaking to dir while (nused 1){ node=index[1]; the heap at each stage. index[1]-index [nused--]; 1788-1982 OF SCIENTIFIC COMPUTING(ISBN hufapp(index,nprob,nused,1); nprob[++k]=nprob[index[1]]+nprob[node]; hcode->left[k]=node; Store left and right children of a v@cam hcode->right [k]=index[1]; node 10-621 up[index[1]]-(long)k; Indicate whether a node is a left up[node]=index[1]=k; or right child of its parent. hufapp(index,nprob,nused,1); Numerical Recipes -43108 up[hcode->nodemax=k]=0; for (j=1;j<=hcode->nch;j++){ Make the Huffman code from (outside if (nprob[j]) the tree. for (n=0,ibit=0,node=up[j];node;node=up[node],ibit++){ North Software. if (node 0){ n I=setbit[ibit]; node =-node; hcode->icod[j]=n; hcode->ncod[j]=ibit; *nlong=0; for (j=1;j<=hcode->nch;j++){ if (hcode->ncod[j]*nlong){ *nlong=hcode->ncod[j];906 Chapter 20. Less-Numerical Algorithms Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). #include "nrutil.h" typedef struct { unsigned long *icod,*ncod,*left,*right,nch,nodemax; } huffcode; void hufmak(unsigned long nfreq[], unsigned long nchin, unsigned long *ilong, unsigned long *nlong, huffcode *hcode) Given the frequency of occurrence table nfreq[1..nchin] of nchin characters, construct the Huffman code in the structure hcode. Returned values ilong and nlong are the character number that produced the longest code symbol, and the length of that symbol. You should check that nlong is not larger than your machine’s word length. { void hufapp(unsigned long index[], unsigned long nprob[], unsigned long n, unsigned long i); int ibit; long node,*up; unsigned long j,k,*index,n,nused,*nprob; static unsigned long setbit[32]={0x1L,0x2L,0x4L,0x8L,0x10L,0x20L, 0x40L,0x80L,0x100L,0x200L,0x400L,0x800L,0x1000L,0x2000L, 0x4000L,0x8000L,0x10000L,0x20000L,0x40000L,0x80000L,0x100000L, 0x200000L,0x400000L,0x800000L,0x1000000L,0x2000000L,0x4000000L, 0x8000000L,0x10000000L,0x20000000L,0x40000000L,0x80000000L}; hcode->nch=nchin; Initialization. index=lvector(1,(long)(2*hcode->nch-1)); up=(long *)lvector(1,(long)(2*hcode->nch-1)); Vector that will keep track of nprob=lvector(1,(long)(2*hcode->nch-1)); heap. for (nused=0,j=1;j<=hcode->nch;j++) { nprob[j]=nfreq[j]; hcode->icod[j]=hcode->ncod[j]=0; if (nfreq[j]) index[++nused]=j; } for (j=nused;j>=1;j--) hufapp(index,nprob,nused,j); Sort nprob into a heap structure in index. k=hcode->nch; while (nused > 1) { Combine heap nodes, remaking node=index[1]; the heap at each stage. index[1]=index[nused--]; hufapp(index,nprob,nused,1); nprob[++k]=nprob[index[1]]+nprob[node]; hcode->left[k]=node; Store left and right children of a hcode->right[k]=index[1]; node. up[index[1]] = -(long)k; Indicate whether a node is a left up[node]=index[1]=k; or right child of its parent. hufapp(index,nprob,nused,1); } up[hcode->nodemax=k]=0; for (j=1;j<=hcode->nch;j++) { Make the Huff man code from if (nprob[j]) { the tree. for (n=0,ibit=0,node=up[j];node;node=up[node],ibit++) { if (node < 0) { n |= setbit[ibit]; node = -node; } } hcode->icod[j]=n; hcode->ncod[j]=ibit; } } *nlong=0; for (j=1;j<=hcode->nch;j++) { if (hcode->ncod[j] > *nlong) { *nlong=hcode->ncod[j];