Huffman算法的程序
小弟不材，刚写出来的Huffman算法的程序。。请高手指点一下。。
#include "stdafx.h"
#include<iostream>
using namespace std;
#include<stdlib.h>
#include<conio.h>
#include<string.h>
typedef struct{
char name;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct{
char name;
unsigned int weight;
}character,*characterpointer;
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,characterpointer w,int n);
void Select(HuffmanTree HT,int i,int *p);
int main()
{
HuffmanTree HT;
HuffmanCode HC;
//int p[3]={0,0,0};
cout<<"请输入要求Huffman编码的个数n"<<endl;
int n;
cin>>n;
characterpointer w;
w=(characterpointer)malloc((n+1)*sizeof(character));
//HT=w;
for(int a=1;a<=n;a++)
{
cout<<"请输入第"<<a<<"个字符和权重"<<endl;
cin>>w[a].name;
cin>>w[a].weight;
}
HuffmanCoding(HT,HC,w,n);
getch();
return 0;
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,characterpointer w,int n)
{
if(n<=1)return;
int m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
HuffmanTree p;
p=HT;
for(int i=1;i<=n;++i)
{
p[i].name=w[i].name;
p[i].weight=w[i].weight;
p[i].parent=0;
p[i].lchild=0;
p[i].rchild=0;
}
for(;i<=m;++i)
{
p[i].name=0;
p[i].weight=0;
p[i].parent=0;
p[i].lchild=0;
p[i].rchild=0;
}
for(i=n+1;i<=m;++i)
{
int s1,s2;
int p[3];
Select(HT,i,p);
s1=p[1];s2=p[2];
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((n+1)*sizeof(char *));
char* cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
int start=0;
for(i=1;i<=n;++i)
{
start=n-1;
for(int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]=48;
else cd[--start]=49;
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
cout<<HT[i].name<<"的Huffman编码是"<<HC[i]<<endl;
}
free(cd);
}
void Select(HuffmanTree HT,int i,int *p)
{
int k,l;
for(int a=1;a<=i-1;a++)
{
if(HT[a].parent==0)
{
p[1]=HT[a].weight;
k=a;
break;
}
}
for(int j=1;j<=i-1;j++)
{
if((p[1]>HT[j].weight)&&(HT[j].parent==0)&&(j!=k))
{
p[1]=HT[j].weight;
k=j;
}
}
for(a=1;a<=i-1;a++)
{
if(HT[a].parent==0&&(a!=k))
{
p[2]=HT[a].weight;
l=a;
break;
}
}
for(j=1;j<=i-1;j++)
{
if((p[2]>HT[j].weight)&&(HT[j].parent==0)&&(j!=l)&&(j!=k))
{
p[2]=HT[j].weight;
l=j;
}
}
p[1]=k;
p[2]=l;
}
