根据萨德纳斯和彼特森设计判断唯一可以码的算法思想，设计算法，判断一个码是否为唯一可译码

 

判断标准：

    将码所有可能的未遂后缀组成一个集合，当且仅当集合中没有包含任意码字时，码为唯一可译码。

 

程序代码：

 

#include <iostream.h>

#include <stdlib.h>

#include <string.h>

struct strings

{

    char *string;

    struct strings *next;

};

struct strings  Fstr, *Fh, *FP;

void outputstr(strings *str)

{                

         do

         {

                   cout<<str->string<<endl;

                   str = str->next;

         }while(str);

         cout<<endl;

}

inline int MIN(int a, int b)

{    return a>b?b:a;     }

inline int MAX(int a, int b)

{    return a>b?a:b;     }

#define length_a (strlen(CP))

#define length_b (strlen(tempPtr))

//判断一个码是否在一个码集合中，在则返回0，不在返回1

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 houzhui(char *CP,char *tempPtr)

{

         if (!strcmp(CP,tempPtr))

         {

                   cout<<"集合C和集合F中有相同码字:"<<endl

                            <<CP<<endl

                            <<"不是唯一可译码码组!"<<endl;

                   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;

                   }

         }

}

void main()

{

         cout<<"\t\t唯一可译码的判断!\n"<<endl;

         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;

//输入待检测码的个数

         int Cnum;

         cout<<"输入待检测码的个数:";

         cin>>Cnum;

         cout<<"输入待检测码"<<endl;

         for(int i=0; i<Cnum; i++)

    {

                   cout<<i+1<<" ：";

                   char tempstr[10];

                   cin>>tempstr;  

                   CP->next=new (struct strings);

                   CP=CP->next;

                   CP->string=new char[strlen(tempstr)] ;

                   strcpy(CP->string, tempstr);

                   CP->next = NULL;

    }

         outputstr(Ch);

    CP=Ch;

    while(CP->next->next)

    {

                   CP=CP->next; 

                   tempPtr=CP;            

                   do

                   {

                            tempPtr=tempPtr->next;

                            houzhui(CP->string,tempPtr->string);

                   }while(tempPtr->next);

    }

    outputstr(Fh);

         struct strings *Fbegin,*Fend;

    Fend=Fh;

    while(1)

    {

                   if(Fend == FP)

                   {

               cout<<"是唯一可译码码组!"<<endl;

                            exit(1);

                   }

                   Fbegin=Fend;

                   Fend=FP;

                   CP=Ch;             

                   while(CP->next)

                   {

            CP=CP->next;

                            tempPtr=Fbegin;

                            for(;;)

                            {

                                     tempPtr=tempPtr->next;

                                     houzhui(CP->string,tempPtr->string);

                                     if(tempPtr == Fend)

                                               break;

                            }

                   }       

                   outputstr(Fh);//输出F集合中全部元素

    }

}