唯一可译码.cpp

输入一组码组

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


struct strings
{
    char *string;
    struct strings *next;
};

struct strings  Fstr, *Fh, *FP;

int MIN(int a, int b)
{    return a>b?b:a;     }
int MAX(int a, int b)
{    return a>b?a:b;     }

#define length_a (strlen(CP))
#define length_b (strlen(tempPtr))

int comparing(strings *st_string,char *code)
{
	while(st_string->next)
	{
		st_string=st_string->next;
		if(!strcmp(st_string->string,code))
			return 0;
	}
	return 1;
}

void determine(char *CP,char *tempPtr)
{
	if (!strcmp(CP,tempPtr))
	{
		printf("C和F有相同的字符串.");
		
		printf("此码非唯一可译码 !");
		exit(1);
	}
	if (!strncmp(CP, tempPtr, MIN(length_a,length_b)))
	{					
		struct strings *cp_temp;
		cp_temp=new (struct strings);
		cp_temp->next=NULL;
		cp_temp->string=new char[abs(length_a-length_b)+1];		    
		char *longstr;
		longstr=(length_a>length_b ? CP : tempPtr);   //将长度长的码赋给longstr
		
		//取出后缀
		for (int k=MIN(length_a,length_b); k<MAX(length_a,length_b); k++)
			cp_temp->string[k - MIN(length_a,length_b)]=longstr[k];
		
		cp_temp->string[abs(length_a-length_b)]=NULL;
		
		//判断新生成的后缀码是否已在集合F里，不在则加入F集合
		if(comparing(Fh,cp_temp->string))
		{
			FP->next=cp_temp;
			FP=FP->next;
		}
	}
}



main()
{
	int n;
	struct strings  Cstr, *Ch, *CP,*tempPtr;
	Ch=&Cstr;
	CP=Ch;
    Fh=&Fstr;
	FP=Fh;
	
	char c[]="C :";
    Ch->string=new char[strlen(c)];
    strcpy(Ch->string, c);	
    Ch->next=NULL;
    char f[]="F :";
    Fh->string=new char[strlen(f)];
    strcpy(Fh->string, f);
    Fh->next=NULL;
	
	//输入待测码的个数
	printf("请输入待检测码的个数: \n");
	scanf("%d",&n);
	if(n<1)
	{
		printf("输入错误 !");
		printf("重新 ! ");
		
		exit(1);
	}
	
	//输入待检测码
	printf("输入码组 : ");
	for(int i=0; i<n; i++)
    {
		printf("%d : \n",i+1);
		char tempstr[10];
		scanf("%s",tempstr);   
		CP->next=new(struct strings);
		CP=CP->next;
		CP->string=new char[strlen(tempstr)] ;
		strcpy(CP->string, tempstr);
		CP->next = NULL;
    }
	
	CP=Ch;
	//将集合C中的码组进行比较，将尾缀加到集合F中
	while(CP->next->next)
    {
		CP=CP->next;	
		tempPtr=CP;		
		do
		{
			tempPtr=tempPtr->next;
			determine(CP->string,tempPtr->string);
		}while(tempPtr->next);
    }
	struct strings *Fbegin,*Fend;
    Fend=Fh;
    while(1)
    {
		if(Fend == FP)//若在不断的比较中，F中没有加入新的码组时，可判断出唯一
		{
			cout<<"此码是唯一可译码 ！"<<endl;
			exit(1);
		}
		
		Fbegin=Fend;
		Fend=FP;
		CP=Ch;		
		while(CP->next)//将F中的码组不断的和C中的码组比较，如果有相同的码组，则不是唯一的
		{
            CP=CP->next;//不断的比较使得F中不断加入新的码组，直到C码组完结
			tempPtr=Fbegin;
			for(;;)
			{
				tempPtr=tempPtr->next;
				determine(CP->string,tempPtr->string);
				if(tempPtr == Fend)
					break;
			}
	}	}
}