哈弗曼树 译码存在问题
#include <iostream.h>#include <iomanip.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>
#define maxsize 100
typedef char **HuffmanCode;
//typedef int TElemType;
const int UINT_MAX = 1000;
typedef struct
{
int weight;
int parent, lchild, rchild;
} HTNode, *HuffmanTree;
HuffmanTree HT;
HuffmanCode HC;
int *w, i, j, n;
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].weight < k && t[j].parent == 0)
k = t[j].weight, flag = j;
t[flag].parent = 1;
return flag;
}
void Select(HuffmanTree t, int i, int &s1, int &s2)
{
// s1为最小的两个值中序号小的那个
int j;
s1 = min(t, i);
s2 = min(t, i);
if (s1 > s2)
{
j = s1;
s1 = s2;
s2 = j;
}
}
void CreateHuffmanTree(HuffmanTree &HT,int n)
{ char str[100];
int num[26]={0};
int m,i,s1,s2,len;
if(n<=1) return;
m=2*n-1;
HT=new HTNode[m+1];
for(i=1;i<=m;++i)
{HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}
cout << "输入若干个整形数据:" << endl;
scanf("%s",str);
len=strlen(str);
for(i=0;i<=len;i++)
{if(str[i]>='a'&&str[i]<='z')
num[str[i]-'a']++;}
for(i=0;i<26;i++)
printf("%c: %d ",i+'a',num[i]);
for(i=1;i<=n;i++)
HT[i].weight=num[i];
for(i=n+1;i<=m;++i)
{
Select(HT,i-1,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;
}
}
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC, int n)
{
int f,c,i,star;
char *cd;
HC=new char*[n+1];
cd=new char[n];
cd[n-1]='\0';
cout<<"字符串的密文是:";
for(i=1;i<=n;++i)
{
star=n-1;
c=i;f=HT[i].parent;
while(f!=0)
{--star;
if(HT[f].lchild==c) cd[star]='0';
else cd[star]='1';
c=f;
f=HT[f].parent;
}
HC[i]=new char[n-star];
strcpy(HC[i],&cd[star]);
cout<<HC[i];
}
delete cd;
}
void decode(HuffmanTree HT[])
{
int i,j=0,m;
char b[maxsize];
char endflag='2';
i=m-1;
printf("输入发送的编码(以'2'为结束标志)：");
gets(b);
printf("译码后的字符为");
while(b[j]!='2')
{
if(b[j]=='0')
i=HT[i].lchild;
else
i=HT[i].rchild;
if(HT[i].lchild==-1)
{
printf("%c",HT[i].ch);
i=m-1;
}
j++;
}
printf("\n");
if(HT[i].lchild!=-1&&b[j]!='2')
printf("\nERROR\n");
}
void main()
{ HuffmanTree HT;
HuffmanCode HC;
int n;
cout<<"你输入的数据个数是:";
cin>>n;
CreateHuffmanTree(HT,n);
CreatHuffmanCode(HT,HC,n);
}
