主题:[原创]哈夫曼编码的翻译?加分!
各位请帮忙看一下这个程序:
它是一道哈夫曼编码问题,就是要求用户首先输入字符对及应的权值(从大到小输),本题字符串中最多包含4个字符,不过可以通过修改N来修改,可以包含的最多字符个数。(注意:左子树为权值小的)
它能正常编码,在传送过程中的传递(即转化为0,1代码传递),但是在对方接到字符串时,它的0,1代码都在yi这个数组中,但是如果传一个字符能正常翻译过来,可是如果有2个以上就不正确了,请教一下,这个翻译过程,哪里出错了,你可以贴下去,运行一下,谢了!
#include<string.h>
#include<conio.h>
#include<iostream.h>
#include<malloc.h>
#include<stdlib.h>
const int n=4;
typedef struct node
{int data;
int r,l,p;
char ch;
char stf[n+1];
}node;
node * init();
void creattree(node *T);
void getrule(node *T);
void deal(node *p);
int main()
{node *p;
p=init();
creattree(p);
getrule(p);
deal(p);
return 0;
}
node * init()
{int i;
node *T;
T=(node *)malloc((2*n-1)*sizeof(node));
if(!T){cout<<"开辟失败"<<endl;
getch();exit(0);}
cout<<"本题只给出4个叶子结点,可以令常量n取其他它值,增加或者减少叶子结点个数即传送字符串可以包含的字符个数.注意:请按权值从大到小输入"<<endl;
for(i=0;i<n;i++)
{cout<<"请输入权值:";
cin>>(T+i)->data;
cout<<"代表字符:";
cin>>(T+i)->ch;
}
for(i=0;i<2*n-1;i++)
(T+i)->l=(T+i)->r=(T+i)->p=-1;
cout<<"初始化结束,请按任意键继续"<<endl;
getch();
return T;
}
void getrule(node *T)
{int w=0,i,m,k=0,j,t;
char temp[n]={'\0'};
for(i=0;i<n;i++)
{j=i;
m=(T+i)->p;
while(m!=-1)
{if((T+m)->l==j)temp[w++]='0';
else temp[w++]='1';
j=m;
m=(T+m)->p;
}
for(t=w-1;t>=0;t--)
(T+i)->stf[w-1-t]=temp[t];
(T+i)->stf[w]='\0';
w=0;
for(k=0;k<n;k++)
temp[k]='\0';
}
for(i=0;i<n;i++)
cout<<(T+i)->ch<<"对应的代码:"<<(T+i)->stf<<endl;
}
void deal(node *p)
{char temp[100],yi[250]={'\0'},opyi[100]={'\0'},arr[n+1];
int i=0,v=0,j,k=0,t=0,m=0,flag=0;
cout<<"输入要表达的字符串"<<endl;
cin>>temp;
while(1)
{
for(t=0;t<n;t++)
if(temp[i]==(p+t)->ch)strcat(yi,(p+t)->stf);
i++;
if(temp[i]=='\0')break;
}
cout<<"发送字符串 :"<<yi<<endl;
cout<<"对方接收字符串:"<<yi<<endl;
i=k=m=v=0;
while(1)
{
for(i=k;i<n+k;i++)
{arr[m]=yi[i];
m++;
for(j=0;j<n;j++)
if(!strcmp(arr,(p+j)->stf))
{flag=1;opyi[v]=(p+j)->ch;break;}
if(flag==1){flag=0;break;}
}
cout<<i<<endl;
k=i+1;
m=0;
while(1)
{arr[m++]='\0';
if(arr[m]=='\0')break;
}
m=0;
if(yi[k]=='\0')break;
}
cout<<"经过事先约定的规则译后得到的字符串如下:"<<opyi<<endl;
}
void creattree(node *T)
{int t=n,s,m1,m2,s1,s2,w,x;
m1=T->data;
m2=m1;
s1=0;
s2=s1;
while(1)
{for(w=0;w<t;w++)
{if((T+w)->p!=-1)continue;
if((T+w)->data<m1){m1=(T+w)->data;s1=w;}
}
if(s1==t-1)x=t-1;
else x=t;
for(w=0;w<x;w++)
{if(((T+w)->p!=-1)||((T+w)->data==m1&&w==s1))continue;
if((T+w)->data<m2){m2=(T+w)->data;s2=w;}
}
(T+t)->data=m1+m2;
(T+t)->l=s1;
(T+t)->r=s2;
(T+t)->p=-1;
(T+s1)->p=(T+s2)->p=t;
t++;
if(t==2*n-1)break;
m1=0xffff;
m2=m1;
s1=0;
s2=s1;
}
}
它是一道哈夫曼编码问题,就是要求用户首先输入字符对及应的权值(从大到小输),本题字符串中最多包含4个字符,不过可以通过修改N来修改,可以包含的最多字符个数。(注意:左子树为权值小的)
它能正常编码,在传送过程中的传递(即转化为0,1代码传递),但是在对方接到字符串时,它的0,1代码都在yi这个数组中,但是如果传一个字符能正常翻译过来,可是如果有2个以上就不正确了,请教一下,这个翻译过程,哪里出错了,你可以贴下去,运行一下,谢了!
#include<string.h>
#include<conio.h>
#include<iostream.h>
#include<malloc.h>
#include<stdlib.h>
const int n=4;
typedef struct node
{int data;
int r,l,p;
char ch;
char stf[n+1];
}node;
node * init();
void creattree(node *T);
void getrule(node *T);
void deal(node *p);
int main()
{node *p;
p=init();
creattree(p);
getrule(p);
deal(p);
return 0;
}
node * init()
{int i;
node *T;
T=(node *)malloc((2*n-1)*sizeof(node));
if(!T){cout<<"开辟失败"<<endl;
getch();exit(0);}
cout<<"本题只给出4个叶子结点,可以令常量n取其他它值,增加或者减少叶子结点个数即传送字符串可以包含的字符个数.注意:请按权值从大到小输入"<<endl;
for(i=0;i<n;i++)
{cout<<"请输入权值:";
cin>>(T+i)->data;
cout<<"代表字符:";
cin>>(T+i)->ch;
}
for(i=0;i<2*n-1;i++)
(T+i)->l=(T+i)->r=(T+i)->p=-1;
cout<<"初始化结束,请按任意键继续"<<endl;
getch();
return T;
}
void getrule(node *T)
{int w=0,i,m,k=0,j,t;
char temp[n]={'\0'};
for(i=0;i<n;i++)
{j=i;
m=(T+i)->p;
while(m!=-1)
{if((T+m)->l==j)temp[w++]='0';
else temp[w++]='1';
j=m;
m=(T+m)->p;
}
for(t=w-1;t>=0;t--)
(T+i)->stf[w-1-t]=temp[t];
(T+i)->stf[w]='\0';
w=0;
for(k=0;k<n;k++)
temp[k]='\0';
}
for(i=0;i<n;i++)
cout<<(T+i)->ch<<"对应的代码:"<<(T+i)->stf<<endl;
}
void deal(node *p)
{char temp[100],yi[250]={'\0'},opyi[100]={'\0'},arr[n+1];
int i=0,v=0,j,k=0,t=0,m=0,flag=0;
cout<<"输入要表达的字符串"<<endl;
cin>>temp;
while(1)
{
for(t=0;t<n;t++)
if(temp[i]==(p+t)->ch)strcat(yi,(p+t)->stf);
i++;
if(temp[i]=='\0')break;
}
cout<<"发送字符串 :"<<yi<<endl;
cout<<"对方接收字符串:"<<yi<<endl;
i=k=m=v=0;
while(1)
{
for(i=k;i<n+k;i++)
{arr[m]=yi[i];
m++;
for(j=0;j<n;j++)
if(!strcmp(arr,(p+j)->stf))
{flag=1;opyi[v]=(p+j)->ch;break;}
if(flag==1){flag=0;break;}
}
cout<<i<<endl;
k=i+1;
m=0;
while(1)
{arr[m++]='\0';
if(arr[m]=='\0')break;
}
m=0;
if(yi[k]=='\0')break;
}
cout<<"经过事先约定的规则译后得到的字符串如下:"<<opyi<<endl;
}
void creattree(node *T)
{int t=n,s,m1,m2,s1,s2,w,x;
m1=T->data;
m2=m1;
s1=0;
s2=s1;
while(1)
{for(w=0;w<t;w++)
{if((T+w)->p!=-1)continue;
if((T+w)->data<m1){m1=(T+w)->data;s1=w;}
}
if(s1==t-1)x=t-1;
else x=t;
for(w=0;w<x;w++)
{if(((T+w)->p!=-1)||((T+w)->data==m1&&w==s1))continue;
if((T+w)->data<m2){m2=(T+w)->data;s2=w;}
}
(T+t)->data=m1+m2;
(T+t)->l=s1;
(T+t)->r=s2;
(T+t)->p=-1;
(T+s1)->p=(T+s2)->p=t;
t++;
if(t==2*n-1)break;
m1=0xffff;
m2=m1;
s1=0;
s2=s1;
}
}