为了账号安全,请及时绑定邮箱和手机立即绑定

哈夫曼树编码问题,求大神帮我改一改。。。

哈夫曼树编码问题,求大神帮我改一改。。。

C C++
可可wrh 2017-12-18 21:50:47
#include<stdio.h> #include<stdlib.h> #include<string.h> #define OK 1 #define ERROR 0 typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,* HuffmanTree; //动态分配数组存储哈夫曼树 typedef char * *HuffmanCode;//动态分配数组存储哈夫曼编码表 void SelectMin(HuffmanTree HT,int nNode,int &s1,int &s2){ int i,j; for(i=1;i<=nNode;i++)     if(!HT[i].parent){     s1=i;     break; } for(j=i+1;j<=nNode;j++) if(!HT[j].parent){ s2=j; break; } for(i=1;i<=nNode;i++) if((HT[i].weight<HT[s1].weight)&&(!HT[i].parent)&&s2!=i) s1=i; for(i=1;j<=nNode;j++) if((HT[j].weight<HT[s2].weight)&&(!HT[j].parent)&&s1!=j) s2=j; if(HT[s1].weight>HT[s2].weight){ int temp=s1; s1=s2; s2=temp; } } void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int nNode){ int i,s1,s2,start,c,f; char *cd; if(nNode<=1) return; int m=2*nNode-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(i=1;i<=nNode;i++) { HT[i].parent=0; HT[i].weight=w[i-1]; HT[i].lchild=0; HT[i].rchild=0; } for(i=nNode+1;i<=m;i++) { HT[i].parent=0; HT[i].weight=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=nNode+1;i<=m;i++){//建立哈夫曼树 SelectMin(HT,nNode,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } //- - - -从叶子到根逆向求每个字符的哈夫曼编码- - - -// HC=(HuffmanCode)malloc((nNode+1)*sizeof(char *)); cd=(char *)malloc(nNode*sizeof(char)); cd[nNode-1]='0'; for(i=1;i<=nNode;i++){ start=nNode-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char *)malloc((nNode-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); }//HuffmanCoding int main(){ HuffmanTree HT; HuffmanCode HC;     int i,nNode,*w; char Code[20]={0}; printf("请输入结点个数:"); scanf("%d",&nNode); HC=(HuffmanCode)malloc(nNode*sizeof(HuffmanCode)); w=(int *)malloc(nNode*sizeof(int)); printf("请输入各结点的权值\n"); for(i=0;i<nNode;i++) scanf("%d",&w[i]);  HuffmanCoding(HT,HC,w,nNode);  printf("各点的哈夫曼编码为:\n");  for(i=0;i<=nNode;i++){  printf("%3d:%s\n",i,HC[i]);  }  return OK; }
查看完整描述

目前暂无任何回答

  • 0 回答
  • 1 关注
  • 1222 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信