哈夫曼编码译码程序源代码.doc

《数据结构》课程设计哈夫曼编码译码程序源代码 #include iostream.h #include fstream.h #include iomanip.h #include string.h #include malloc.h #include stdio.h #include iomanip.h const int UINT_MAX=10000; typedef struct { int weight; int parent,lchild,rchild; }HTNode,* HuffmanTree; //动态分配数组存储赫夫曼树?? typedef char **HuffmanCode;动态分配数组存储赫夫曼编码表 //--------------------全局变量----------------------- HuffmanTree HT; HuffmanCode HC; int *w,i,j; const int n=26; char *z; int flag=0; int numb=0; // -----------------求赫夫曼编码--------------------- int min(HuffmanTree t,int i) { // 此函数将要被void select()调用 int j,flag; int k=UINT_MAX; // 取k为不小于可能的值 for(j=1;j=i;j++) if(t[j].weightkt[j].parent==0) k=t[j].weight,flag=j; t[flag].parent=1; return flag; } //--------------------slect函数---------------------- void select(HuffmanTree t,int i,int s1,int s2) { // s1为最小的两个值中序号小的那个 int j; s1=min(t,i); s2=min(t,i); if(s1s2) { j=s1; s1=s2; s2=j; } } // -------------------参考课本算法6.12------------------- void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n) { // w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC int m,i,s1,s2,start; int c,f; HuffmanTree p; char *cd; if(n=1) return;//检测结点数是否可以构成树 m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用 for(p=HT+1,i=1;i=n;++i,++p,++w) { p-weight=*w; p-parent=0; p-lchild=0; p-rchild=0; } for(;i=m;++i,++p) p-parent=0; for(i=n+1;i=m;++i) // 建赫夫曼树 { //在HT[1~i-1]中选择parent=0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2); HT[s1].parent=HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } // 从