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

#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;
}


可可wrh
浏览 1236回答 0
0回答
打开App,查看更多内容
随时随地看视频慕课网APP