dnf杰伊:关于赫夫曼编码有一点问题,请高手指点

来源:百度文库 编辑:高校问答 时间:2024/05/03 01:12:30
这是个赫夫曼树编码的程序,好像是我写的select函数有点问题,反正输出的编码就不正确,请高手帮我指点一下(尽快啊,晚上就要交作业了,谢谢)
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; typedef char **HuffmanCode;

#include <malloc.h>
#include <iostream>
using namespace std;

void select(HuffmanTree HT,int n,int& s1, int& s2){
s1=s2=0;
for(int i=1;i<=n;i++)
if(HT[i].parent==0&&HT[i].weight<HT[s1].weight)
s1=i;
for(i=1;i<n;i++)
if(HT[i].parent==0&&i!=s1&&HT[i].weight<HT[s2].weight)
s2=i;
}

void strcpy(int* a,int b[]){
a=b;
}

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) {
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
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)
{
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;
}

*HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd=(char*)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-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((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]); }
free(cd);
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("输入权值个数(>1): ");
scanf("%d",&n);
w=(int*)malloc(n*sizeof(int));
printf("请依次输入这几个权值\n",n);
for(i=0;i<=n-1;i++)
scanf("%d",w+i);
HuffmanCoding(&HT,&HC,w,n);
for(i=1;i<=n;i++)
puts(HC[i]);
}

void select(HuffmanTree HT,int n,int& s1, int& s2){
int k;
for(k=1;k<=n;k++)
if(0==HT[k].parent)
{
s1=s2=k;
break;
}

for(int i=k+1;i<=n;i++)
if(HT[i].parent==0&&HT[i].weight<HT[s1].weight)
s1=i;

if(k==s1)
for(;k<=n;k++)
if(0==HT[k].parent)
{
s2 = k;
break;
}

for(i=k+1;i<=n;i++)
if(HT[i].parent==0&&i!=s1&&HT[i].weight<HT[s2].weight)
s2=i;
}