main.cpp

用以判决输入码字是否唯一可译码 先输入总的码字个数 再输入各个码字 程序会判断出该码字集合是否为唯一可译码

#include <iostream> 
#include <string> 
using namespace std; 

int iniF(char *p1,char *p2,char *ch,char *f1,char *&rear,int r,int &num);
void compara(bool &resault,int &flag,char *p2,char *f2,char *f3,int &num,int n,int r,char *change,char *&rear);
void  main() 
{ 	char quit='C';	//用于判断是否退出
	string s;		//s存输入的码字

	while(quit!='n')
	{
	cin.sync();		//清空输入缓存
	//将输入数据读入
	int r;//码字个数
	int n=0;
	int num=0;//记录集合F中尾缀的个数
	cout<<"请输入码字个数"<<endl;
	cin>>r;
	
	cout<<"请输入各码字（以空格或“,”作为各码字间隔,以“$”作为结束标志）"<<endl;
	
	cin.sync();		//清空输入缓存
	getline(cin,s,'$'); //读入输入码字
	char *ch=new char[s.length()+1]; //动态申请堆栈存储码字

	//利用strtok()函数 将读进来的含有码字的字符串中的间隔字符置“'\0'”
	char *p;
	char dd[]={' ',',','\0'};	//dd存储可用于表示间隔的符号' '或','
	char *d=dd;
	int count=0;
	strcpy(ch,s.c_str()); 
	p=strtok(ch,d);
	while(p)
	{
	  p=strtok(NULL,d);//用'\0'替换' '或','
	  count++;
	}
	
	
	if(r!=count)
	{
		cout<<"码字个数不符请重新输入"<<endl;//输入码字个数不一致
	}
	else
	{//输入码字个数一致 
	char *f1,*rear,*f3,*f2,*f4;//f1始终指向F的首地址，rear为F的最后字符串位置，f4存储前一次rear的位置，f2，f3用于C和F的比较
	f1=rear=f3=new char[50*s.length()];//动态申请集合F
	f1[0]='\0';//F的初始状态
	//建立集合F0
	char *p1=ch,*p2=ch,*change=ch;
	int flag=0;
	bool resault=1;//是否可译码标志，1-真,0-假
	flag=iniF(p1,p2,ch,f1,rear,r,num);//建立F0
	p1=p2=ch;
	n=num;
	f2=f3=f1;
	//集合C和集合F间的比较
	while(resault==1 )
	{	f4=rear;//记录比较前rear的位置
		if(flag==0)		//表示上次比较后没有新的尾缀，即唯一可译码
		{	cout<<"是唯一可译码"<<endl;
			break;		//跳出循环
		}
		flag=0;
	
		p2=p1;
		compara(resault,flag,p2,f2,f3,num,n,r,change,rear);//C和F间比较
		n=num;		//修改尾缀的个数
		f3=f2=f4;//f2，f3指向上一次比较完的位置，并开始新的比较
		
	}
	//根据上一步的结果判断
	if(resault ==0)
	cout<<"不是唯一可译码"<<endl;
	//释放堆栈
	rear=f1;
	f3=f1;
	p1=p2=ch;
	delete[]f1;
	}
	
	delete[]ch;
	
	cout<<"是否继续？y/n"<<endl;
	cin>>quit;
	}

} 


int iniF(char *p1,char *p2,char *ch,char *f1,char *&rear,int r,int &num)
//初始化F集合
{
	while(*p2)	//找到p1指向的码字的下一个码字首字符
	{
		p2++;
	}
	p2++;


	char *change=ch;
	int fl=0;	//标志，0-无新的尾缀，1-有新的尾缀

	for(int i=1;i<r;i++)	//将码字集合C的所有码字比较一遍
	{
		for(int j=i+1;j<=r;j++)	//将p1指向的码字与其后所有码字比较一遍
		{
			//取码字长度
			int m=strlen(p1);
			int k=strlen(p2);
			int x=m>=k?k:m;
			int a=strncmp(p1,p2,x);//比较前x位是否相同
			if (a==0)	
			{	//前x位相同
				num++ ;	//修改尾缀个数
				if(m!=k)
					fl=1;	//表示有新的尾缀要添加
				if(m>k)
				{	//p1指向的字符串的长度>p2指向的字符串的长度
					change=p1;
					//找到p1的尾缀
					for(int jj=0;jj<x;jj++)
					{
						change++;
					}
					//将尾缀添加到尾缀集合F的最后面
					while(*change)
					{
						*rear=*change;
						*(++rear)=NULL;
						change++;
					}
					rear++;
				}
				else if(m<k)
				{	//p2指向的字符串的长度>p1指向的字符串的长度
					change=p2;
					//找到p2的尾缀
					for(int jj=0;jj<x;jj++)
					{
						change++;
					}
					//将尾缀添加到尾缀集合F的最后面
					while(*change)
					{
						*rear=*change;
						*(++rear)=NULL;
						change++;
					}
					rear++;
				}
			}
			//p2移向下一个码字
			while(*p2)
			{
				p2++;
			}
			p2++;

		}
		//p1移向下一个码字
		while(*p1)
		{
			p1++;
		}
		p1++;
		//p2移向p1的下一个码字
		p2=p1;
		while(*p2)
		{
			p2++;
		}
		p2++;
	}
	
	return fl;
}

void compara(bool &resault,int &flag,char *p2,char *f2,char *f3,int &num,int n,int r,char *change,char *&rear)
//将F集合与码字集合C比较
{	num=0;
	
	for(int i=1;i<=r;i++)	//将F集合与码字集合C的所有字符串比较
	{
		for(int j=1;j<=n;j++)	//将集合F中的所有字符串与码字集合C中的一个码字比较
		{
			//取长度
			int m=strlen(p2);
			int k=strlen(f3);
			int x=m>=k?k:m;
			int a=strncmp(p2,f3,x);//判断前x位是否相同
			if (a==0)
			{	//前x位相同
				num++; 
				flag=1;
				if(m==k)
				{	//码字与尾缀相同，不唯一可以，跳出
					resault=0;
					break;
				}
				else if(m>k)
				{	//找到p2的尾缀
					change=p2;
					for(int jj=0;jj<x;jj++)
					{
						change++;
					}
					//将p2的尾缀添加到尾缀集合F的最后
					while(*change)
					{
						*rear=*change;
						*(++rear)=NULL;
						change++;
					}
					rear++;
				}
				else
				{	//找到f3所指向的尾缀的尾缀
					change=f3;
					for(int jj=0;jj<x;jj++)
					{
						change++;
					}
					//将该尾缀添加到尾缀集合F的最后
					while(*change)
					{
						*rear=*change;
						*(++rear)=NULL;
						change++;
					}
					rear++;
				}
			}
			if(resault==0)
				break;
			//f3移向下一个尾缀
			while(*f3)
			{
				f3++;
			}
			f3++;

		}
		f3=f2;	//复原f3
		if(resault==0)
			break;
		//p2移向下一个码字
		while(*p2)
		{
			p2++;
		}
		p2++;
	}

}