#include <iostream>
#include <string>
using namespace std;
main()
{
void lzw(string a[],string d[],int n,int k);
string a[100],d[100],c;
string b[100];
int i,j,n,k,r;
cout<<"请输入信源序列（以“*”结束）："<<endl;
n=0;
for(i=0; i<100; i++)//输入信源序列并保存到string类数组a中
{
cin>>c;
if(c.compare("*")==0)
{
break;
}
else
{
a[i]=c;
n++;
}
}
d[0]=a[0];
k=1;
for(i=1;i<n;i++)//找出信源序列的基本元素并存在d数组中
{
for(j=0;j<k;j++)
{
if(a[i]==d[j])
{
r=0;
break;
}
else
{
r=1;
}
}
if(r==1)
{
d[k]=a[i];
k++;
}
}
cout<<"信源序列为："<<endl;
for(i=0;i<n;i++)
{
cout<<" "<<a[i];
}
cout<<endl;
cout<<"信源基本元素为："<<endl;
for(i=0;i<k;i++)
{
cout<<" "<<d[i];
}
cout<<endl;
cout<<"编码输出为： ";
lzw(a,d,n,k);//a为信源数组，d为基本元素数组，n为信源数组元素个数，k为基本元素数组元素个数
}
void lzw(string a[],string d[],int n,int k)
{
int i,j,r,w,v,q,z;
string p,s,h;
p=a[0];
s=a[1];
v=1;
z=0;
while(z<n+1)//从头循环到尾
{
h=p+s;//h表示p+s，并与基本元素数组做比较
for(i=0;i<k;i++)
{
if(h.compare(d[i])==0)
{
r=0;
break;
}
else
{
r=1;
}
}
if(r==0)
{
p=h;
s=a[++v];
}
else if(r==1)
{
for(i=0;i<k;i++)
{
if(p.compare(d[i])==0)
{
cout<<" "<<i+1;//输出编码
break;
}
}
d[k++]=h;
p=s;
s=a[++v];
}
z++;
}
for(i=0;i<k;i++)
{
if(p.compare(d[i])==0)
{
cout<<" "<<i+1;//输出最后一个元素的编码
break;
}
}
cout<<endl;
}
