unique.cpp

信息论实验 唯一课译码的判断~。。。很好~

/************************************************************************/
//作用：判断输入码元序列是否唯一可译码；若不是，输出某一歧义序列
//作者：nancyxu
//时间：2008/06/12
/************************************************************************/
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
using namespace std;

#define SAME        0    
#define PRE      1
#define UNPRE     2

#define UNIQUE         0    //唯一可译码
#define NUNIQUE        1    //非唯一可译码

typedef vector<char*> CharVec;
int Pre(const char* a,const char* b);							//判断a是否为b的前缀
bool add(CharVec& pCode,char* pValue);							//判断后缀是否重复
int UNIQUE_CHECK(const CharVec& pCode,char** pInvalidSeqBuf);	//判断是否唯一可译码

int main()
{
    CharVec VCode;
    int N;
    int i;
    char chContinue;
    do 
    {    
        cout<<"请输入编码个数:";
        cin>>N;
        cout<<"请输入依次"<<N<<"组码字(回车结束输入): ";
        for (i = 0; i < N; i++)
        {
            string buffer;													//将输入读取到缓冲区    
            cin>>buffer;
            char* pTemp = new char[buffer.size() + 1];
            memcpy(pTemp,buffer.c_str(),sizeof(char) * (buffer.size() + 1));//拷贝字符到动态数组
            VCode.push_back(pTemp);        
        }
        char * pRetn = NULL;
        int nRetn = UNIQUE_CHECK(VCode,&pRetn);								//判断是否唯一可译
        if (NUNIQUE != nRetn)
        {
            cout<<"是唯一可译码码组! ";
        }
        else
        {            
            cout<<"不是唯一可译码码组! ";
            cout<<"有歧义序列为:"<<pRetn;
        }
        delete[] pRetn;														//释放内存
        for (i = 0; i < VCode.size(); i++)
        {
            delete[] VCode.at(i);
        }
        VCode.clear();    
        cout<<"是否继续?(Y/N):";    
        cin>>chContinue;
    } 
	while(toupper(chContinue) == 'Y');
    return 0;
}
/************************************************************************/
//作用：判断a是否为b的前缀
//输入：码组a、b
//输出：是前缀——PRE，相同——SAME，不是前缀——UNPRE
/************************************************************************/
int Pre(const char* a,const char* b)
{
    assert(a != NULL && b != NULL);
    int nLenPrefix,nLenWord;
    nLenPrefix = strlen(a);
    nLenWord = strlen(b);
    if (nLenPrefix > nLenWord)				//前缀长度大于所比码字的长度
        return UNPRE;
    int nRetn = memcmp(a,b,sizeof(char) * strlen(a));
    if(0 == nRetn && nLenPrefix == nLenWord) 
		return SAME;
    if(0 == nRetn) 
		return PRE;
	return UNPRE;
}
/************************************************************************/
//作用：判断后缀是否重复
//输入：pCode集合，pValue码字
//输出：重复——0，不重复——1
/************************************************************************/
bool add(CharVec& pCode,char* pValue)
{
    assert(pValue != NULL);
    for (int i = 0; i < pCode.size(); i++)
    {
        if (0 == strcmp(pValue,pCode[i]))    //重复,返回0
            return false;
    }
    pCode.push_back(pValue);                 //向后缀集合中插入不重复后缀
    return true;
}

/**************************************************************************/
//作用：对pCode集合中每个码字和原码字序列进行比较, 
//输入：pCode集合，pPostfix原后缀码集合，Stack原码字集合，pRetnBuf缓冲区
//输出：如重复返回1.否则返回0
//Stack用来存储递归中产生的后缀码集合
/**************************************************************************/
int GetBacktraceSeq(const CharVec& pCode,char* pPostfix,CharVec& Stack,char** pRetnBuf)
{
    char* iter;
    for (int i= 0; i < pCode.size(); i++)
    {
        iter= pCode.at(i);            
        int nRetn = Pre(iter,pPostfix);
        if (nRetn == SAME)									//遇到重复码字,立即返回.
        {
            if(Stack.size() == 0) continue;					//第一次比较        
            *pRetnBuf = new char[strlen(pPostfix) + 1];
            strcpy(*pRetnBuf,pPostfix);
            return 1;            
        }
        if (PRE == nRetn)
        {            
            if(add(Stack,iter) == false)					//若为新得到的后缀码,跳过
				continue;
            char* pTemp = NULL;
            if(GetBacktraceSeq(pCode,pPostfix+strlen(iter),Stack,&pTemp) == 0) //处理下一个后缀码
            {
                *pRetnBuf = NULL;
                Stack.pop_back();
                continue;
            }
            Stack.pop_back();
            char* pNewTraceSeq = new char[strlen(iter) + strlen(pTemp) + 1];
            pNewTraceSeq[0] = 0;
            strcat(pNewTraceSeq,iter);
            strcat(pNewTraceSeq + strlen(iter),pTemp);
            delete[] pTemp;
            *pRetnBuf = pNewTraceSeq;    
            return 1;
        }
        if (PRE == Pre(pPostfix,iter))
        {    
            if(add(Stack,pPostfix) == false) continue;		//若为新得到的后缀码,跳过
            char* pTemp = NULL;
            if(GetBacktraceSeq(pCode,iter+strlen(pPostfix),Stack,&pTemp) == 0) //处理下一个后缀码
            {
                *pRetnBuf = NULL;
                Stack.pop_back();
                continue;
            }
            Stack.pop_back();
			//将自身和后缀码组合成一个歧义序列返回
            char* pNewTraceSeq = new char[strlen(pPostfix) + strlen(pTemp) + 1];
            pNewTraceSeq[0] = 0;
            strcat(pNewTraceSeq,pPostfix);
            strcat(pNewTraceSeq + strlen(pPostfix),pTemp);
            delete[] pTemp;
            *pRetnBuf = pNewTraceSeq;						
            return 1;
        }
    }
    return 0;
}
/**************************************************************************/
//作用：判决是否为唯一可译码
//输入：原码元集合，有歧义序列存储地址。
//输出：唯一可译——UNIQUE。非唯一可译——NUNIQUE
/**************************************************************************/
int UNIQUE_CHECK(const CharVec& pCode, char** pInvalidSeqBuf)
{
    assert(pCode.size() != 0);    
    CharVec CodePostfix;                   //后缀码
    //码字内部比较,得到第一个后缀码集合
    char *iter;
    int i;
    CharVec Stack;
    for (i = 0; i < pCode.size(); i++)
    {
        iter= pCode.at(i);
        char* pTemp = NULL;
        int nRetn = GetBacktraceSeq(pCode,iter,Stack,&pTemp);
        if(nRetn == 1) 
        {            
            *pInvalidSeqBuf = pTemp;
            return NUNIQUE;
        }
    }
    *pInvalidSeqBuf = NULL;
    return UNIQUE;
}