uniqu.cpp

通过编程

//////////////////////////////////////////////////
//                                              //
//程序名：唯一可译码判断程序                    //  
//使用方法：1。输入信源符号个数（即码的个数）   // 
//          2。逐个输入码字                     //
//          3。输出判断结果                     //
//                                              //
//////////////////////////////////////////////////

//////////////////////////////////////////////////
//制作人：05105班  周吉超  23号               //
//////////////////////////////////////////////////

#include <iostream.h>
#include <string.h>
#include<stdio.h>


//////////////////////////////////////////////////
//                                              //  
//定义使用数据类型及全局变量                    //
//                                              // 
//////////////////////////////////////////////////
const int maxSize=99;        //定义码字最大长度
typedef  char*  string;		   //定义string(字符串)类型
string * words;                //定义存放码的数组指针
string *suffix1;               //定义存放后缀的数组指针1
string *suffix2;               //定义存放后缀的数组指针2  
string *collection;            //定义存放后缀集合数组指针
int numWords;                  //定义码字数组的长度
int length1;                   //定义后缀数组1的长度
int length2;   //定义后缀数组2的长度
                   
int numColle;                  //定义后缀集合数组的长度


///////////////////////////////////////////////////
//子函数：input()                                // 
//入口参数：无                                   //  
//出口参数：无                                   //
//功能：输入信源符号数（即码的总个数）           //
//      输入各个码                               //
//      将输入存到相应的单元                     //
/////////////////////////////////////////////////// 

void input()                   
{
	char line[maxSize];
	int i,len;
	cout<<"please input the number of words:"<<endl;
	cin>>numWords;
	cout<<"please input the words:"<<endl;
	words=new string [numWords];
	for(i=0;i<=numWords-1;i++)
	{
		gets(line);
		len=strlen(line);	
		words[i]=new char [len+1];//words[i]=new char [len];
		strcpy(words[i],line);
	}
	cout<<endl;
	return ;
}


////////////////////////////////////////////////////////
//子函数:findSuffix(char*strA,char*strB,string&suffix)//
//入口参数：需查找后缀的两个字符串strA和strB          //
//          及返回后缀的存储单元                      //    
//出口参数：无                                        //    
//功能：比较输入的两个字符串，将找到的后缀返回指定单元// 
////////////////////////////////////////////////////////
void findSuffix(char*strA,char* strB,string &suffix)
{

	int result,len1,len2;//len2>len1
	string str1,str2;
	if(strlen(strA)>strlen(strB))
	{
		len1=strlen(strB);
		len2=strlen(strA);
		str1=strB;
		str2=strA;
	}
	else
	{
		if(strlen(strB)>strlen(strA))
		{
			len1=strlen(strA);
			len2=strlen(strB);
			str1=strA;
			str2=strB;
		}
		else
		{
			suffix=new char [2];//suffix=new char [1];
			strcpy(suffix,"");
			return;
		}
	}
	result=strncmp(str1,str2,len1);
	if(result!=0)
	{
		suffix=new char [2];//suffix=new char [1];
		strcpy(suffix,"");
		return;
	}	
	suffix=new char [len2-len1+1];
	for(int i=0;i<=len2-len1-1;i++)
	{
		suffix[i]=str2[len1+i];
	}
	suffix[len2-len1]='\0';
	return;
}



/////////////////////////////////////////////////
//子函数：add(int addType,string str1)		   //
//入口参数：添加类型 addType 字符串str1        //                          
//出口参数：无                                 //
//功能：    addType==0 将str1添加到suffix2中； //
//			addType==1 将str1添加到collection中//                                      
/////////////////////////////////////////////////
void add(int addType,string str1)
{
	string* newArr,*oldArr;
	int newLen,oldLen;
	int len;
	if(addType==0)
	{
		oldArr=suffix2;
		oldLen=length2;
	}
	else
	{
		oldArr=collection;
		oldLen=numColle;
	}
	newLen=oldLen+1;
	newArr=new string [newLen];
	for(int i=0;i<=oldLen-1;i++)
	{
		len=strlen(oldArr[i]);
		newArr[i]=new char [len+1];
		strcpy(newArr[i],oldArr[i]);
	}
	len=strlen(str1);
	newArr[newLen-1]=new char [len+1];
	strcpy(newArr[newLen-1],str1);
	if(addType==0)
	{   suffix2=newArr;
		length2=newLen;
	}
	else
	{
		collection=newArr;
		numColle=newLen;
	}
	return;
}
	

//////////////////////////////////////////////
//子函数：strSearch(string str1)            //
//入口参数：需查找的字符串str1              //     
//出口参数：整型数：0－－not found; 1--found//
//功能：寻找在collection是否已有了str1后缀	//
//////////////////////////////////////////////

int strSearch(string str1)//  return 0 --not find     return 1--- find
{
	int result=1,i=0;
	while(result!=0 && i<=numColle-1)
	{
		result=strcmp(str1,collection[i]);
		i++;
	}
	if(result!=0)
		return 0;
	else
		return 1;
}
	
///////////////////////////////////////////////////////////
//主函数：void main()									 //
//操作：首先输入码序列的总个数,(如序列"110","011"个数为2)//
//			以回车结束；								 //					
//		其次依次输入各码序列,每输入一个码序列用回车换行, //
//		    再输入下一个码序列。                         //
//功能：判断是否为唯一可以码；并给出原因。               //                                              
///////////////////////////////////////////////////////////
void main()
{
	cout<<" Help:"<<endl;
	cout<<"首先输入码序列的总个数,(如序列'110','011'个数为2),以回车结束"<<endl;
	cout<<"其次依次输入各码序列每输入一个码序列用回车换行,再输入下一个码."<<endl;
    cout<<"最后输入回车输出判断结果及理由"<<endl<<endl;	
	string temp;
	int i,j,k,m,len;
	int cmpResult,schResult;
	int flag=1;             
	int ii;
	char* pt;
	input();

	suffix1=new string[numWords];
	length1=numWords;
	for(i=0;i<=numWords-1;i++)
	{
		len=strlen(words[i]);
		suffix1[i]=new char [len+1];
		strcpy(suffix1[i],words[i]);
	}
	for(i=0;i<=length1-1;i++)                     //首先判断是否非奇异码
	{
		for(j=i+1;j<=length1-1;j++)
		{
			cmpResult=strcmp(suffix1[i],words[j]);
			if(cmpResult==0)
			{
				cout<<"It is NOT a uniqued decoding code."<<endl
				<<"for the word  "<<words[j]<<"  is found twice."<<endl;
				return;
			}
		}
	}
	while(flag==1)
	{
		flag=0;									//flag用来标识有无新元素的添加
		for(i=0;i<=length1-1;i++)
		{
			for(j=0;j<=numWords-1;j++)
			{
				findSuffix(suffix1[i],words[j],temp);
				cmpResult=strcmp(temp,"");		
				if(cmpResult!=0)
				{
					for( k=0;k<=numWords-1;k++)
					{
						cmpResult=strcmp(temp,words[k]);
						if(cmpResult==0)
						{
							cout<<"the collection of suffix is:"<<endl;
							for(m=0;m<=numColle-1;m++)
							cout<<collection[m]<<endl;
							cout<<temp<<endl;
							cout<<endl<<"So it is NOT an uniqued decoding code."<<endl;
							cout<<"Because the word "<<temp<<" is in the suffix collection."<<endl; 
							return;
						}//end if cmpResult
					}//end for k
					schResult=strSearch(temp);
					if(schResult==0)
					{
						flag=1;
						add(1,temp);//add collection
						add(0,temp);//add suffix2
					}//end if schResult
				}//end if cmpResult
			    delete []temp;
			}//end for j
		}//end for i
		if(length1>0)							//释放suffix1
		{
			for(ii=0;ii<=length1-1;ii++)
			{
				pt=suffix1[ii];
				delete []pt;
			}
			delete [] suffix1;
		}
		suffix1=suffix2;
		length1=length2;
		length2=0;
	}//end while
	
	cout<<"the collection of suffix is:"<<endl;
	for(k=0;k<=numColle-1;k++)
		cout<<collection[k]<<endl;
	cout<<endl<<"So it is  an uniqued decoding code."<<endl;
	for( ii=0;ii<=numWords-1;ii++)				//释放words
	{
		pt=words[ii];
		delete []pt;
	}
	delete []words;
	if(length2>0)								//释放suffix2
	{
		for(ii=0;ii<=length2-1;ii++)
		{
			pt=suffix2[ii];
			delete []pt;
		}
		delete []suffix2;
	}
}