the unique code.cpp

用分支界限法实现了树的数据结构。本内容提供了完整的算法

//输入一个码字集key,判断是否为唯一可译码
#include<iostream.h>
#include<string.h>
#define N 20
#define M 10
static char key[N][M],back[N][M],back1[N][M],allback[N*N][M];
static int kk=0,kb=10,number=0;//allback数组中存储所有的后缀
int distinguish(char xx[],char yy[]);//判断前一个字符串是否为后一个字符串的前缀
void seekback(char xx[],char yy[]);//将两个字符串相差的后缀提取出来
int distinguish(char xx[],char yy[])
{
	int lon,len;lon=strlen(xx);len=strlen(yy);//cout<<lon<<endl<<len;
	if(lon>len) return 0;
	for(int i=0;i<lon;i++)
	{
		if(xx[i]!=yy[i]) return 0;
	}
	if(i>=lon)  
	{
		if(lon==len) {cout<<"此编码不是唯一可译码!!!!!"<<endl;kb=0;}
		return 1;
	}
	return 1;
}
void seekback(char xx[],char yy[])
{ 
	//cout<<"wo shi "<<xx<<"   "<<yy<<endl<<back[kk][1];
	int log,len; log=strlen(xx);len=strlen(yy);
	for(int i=log;i<len;i++)
	{back[kk][i-log]=yy[i];allback[number][i-log]=yy[i];}//cout<<back[kk];
//	back[kk][i-log]='\0';
	for(i=0;i<kk;i++)
	{
		if(strcmp(back[i],back[kk])==0)
		{
			for(i=0;i<len-log;i++)
				back[kk][i]='\0';
			kk--;break;
		}
	}
	kk++;number++;
}
void main()
{
	int n,num;cout<<"请输入码字集的个数  ";cin>>n;
	for(int i=0;i<n;i++)
	{
		cout<<"please input the "<<i+1<<"  string"<<endl;
		cin>>key[i];
	}
	for(int j=0;j<n;j++)
	{
		for(int jj=j+1;jj<n;jj++)
		{
		    if(distinguish(key[j],key[jj]))
				seekback(key[j],key[jj]);
		}

	}
	while(kb)
	{
		cout<<"后缀集合--------"<<endl; num=0;
			for(int k=0;k<kk;k++)
			{
				//num=0;
		        cout<<back[k]<<endl;cout<<endl;//////////////
				for(int i=0;i<number-kk;i++)// number-kk!!!!!!!!!
					if(strcmp(allback[i],back[k])==0)
					{num++;	break;}//num用来控制back中是否所有的都已经出现过
								
			}
			if(num>=kk)
				{cout<<"此编码是唯一可译码!!!!!"<<endl;kb=0;}
//////////////////////////////////////////////////////////////////////////////
		for(i=0;i<kk;i++)//初始化
		{
			strcpy(back1[i],back[i]);
			for(j=0;j<M;j++)
		    back[i][j]='\0';
		}
		for(i=kk;i<20;i++)
		{
			for(j=0;j<M;j++)
		    back1[i][j]='\0';
		}
//////////////////////////////////////////////////////////////////////
		int ky=kk; kk=0;
		for( j=0;j<n;j++)
		{
	    	for(int jj=0;jj<ky;jj++)
			{
		        if(distinguish(key[j],back1[jj]))
				   seekback(key[j],back1[jj]);
				if(distinguish(back1[jj],key[j]))
					seekback(back1[jj],key[j]);
			}
		}
	}
}