实验1：唯一可译码的判定

实验1：唯一可译码的判定学生姓名：学号：一、实验室名称：信息论基础课程组二、实验项目名称：唯一可译码的判定三、实验原理：给定一个已知的码C，利用A.A.Sardinass和G.W.Patterson于1957年提出的算法判定码C是否为唯一可译码。四、实验目的：(1)进一步熟悉唯一可译码判决准则；(2)掌握C语言字符串处理程序的设计和调试技术。五、实验内容：给定一个已知的码C，判定码C是否为唯一可译码。六、实验器材（设备、元器件）：PC机一台，装有VC++6.0或其它C语言集成开发环境。七、实验步骤及操作：1．考查码C中所有的码子，若iW是jW的前缀，则将相应的后缀作为一个尾随后缀码放入集合1F中；2．考查C和kF两个集合，若CWi是kjFW的前缀或kiFW是CWj的前缀，则将相应的后缀作为尾随码放入集合1kF中；3．kkFF即为码C的尾随集合；4．若F中出现了C中的元素，则算法终止，返回假（C不是唯一可译码），否则若F中没有出现新的元素，则返回真。八、实验数据及结果分析：题目：教材P103例5.4的内容。#includeiostream#includevector#includestring#includecassertusingnamespacestd;#defineISSAME0#defineISPREFIX1#defineNOTPREFIX2#defineISUDC0//唯一可译码#defineISRTC1//即时码#defineNOTUDC2//非唯一可译码typedefvectorchar*pCharVector;/**************************************************************************//*判断chPrefix是否为chWord的前缀.*//**************************************************************************/intIsPrefix(constchar*chPrefix,constchar*chWord);/**************************************************************************//*往后缀码集合中插入不重复的键,*//*************************************************************************/boolPushBackUniqueValue(pCharVector&pCode,char*pValue);/**************************************************************************//*判断码字序列的类型,非回溯法*//**************************************************************************/intIsUDC(constpCharVector&pCode);/**************************************************************************//*回溯计算,如果不是唯一可译码则可以得到一串有歧义的码字序列(即有多种译法的/*序列),该序列用参数中的pInvalidSeqBuf返回,调用者需记得释放内存/*该方法的缺点是没有检测码字序列中是否有重复码字*//**************************************************************************/intIsUDC_Backtrace(constpCharVector&pCode,char**pInvalidSeqBuf);//#defineTEST_BY_FILEintmain(){#ifdefTEST_BY_FILEfreopen(in,r,stdin);#endifpCharVectorVCode;intnCodeNum;inti;charchContinue;do{cout请输入信源编码个数:;cinnCodeNum;cout请输入依次nCodeNum组码字(以回车表示码字的结束):;for(i=0;inCodeNum;i++){//将输入读取到缓冲区stringstrBuffer;cinstrBuffer;//copy字符到动态数组中已进行比较char*pTemp=newchar[strBuffer.size()+1];memcpy(pTemp,strBuffer.c_str(),sizeof(char)*(strBuffer.size()+1));VCode.push_back(pTemp);}char*pRetn=NULL;intnRetn=IsUDC_Backtrace(VCode,&pRetn);if(NOTUDC!=nRetn){cout该码字序列/集合是唯一可译码码组!;}else{cout该码字序列/集合不是唯一可译码码组!;cout有歧义序列为:pRetn;}if(ISRTC==nRetn){cout该码字序列/集合是即时码!;}else{cout该码字序列/集合不是即时码!;}//清除内存delete[]pRetn;for(i=0;iVCode.size();i++){delete[]VCode.at(i);}VCode.clear();cout继续吗?(Y/N):;cinchContinue;}while(toupper(chContinue)=='Y');#ifdefTEST_BY_FILEfclose(stdin);#endifreturn0;}intIsPrefix(constchar*chPrefix,constchar*chWord){assert(chPrefix!=NULL&&chWord!=NULL);intnLenPrefix,nLenWord;nLenPrefix=strlen(chPrefix);nLenWord=strlen(chWord);//前缀长度大于整个词的长度,返回falseif(nLenPrefixnLenWord){returnNOTPREFIX;}intnRetn=memcmp(chPrefix,chWord,sizeof(char)*strlen(chPrefix));if(0==nRetn&&nLenPrefix==nLenWord)returnISSAME;if(0==nRetn)returnISPREFIX;returnNOTPREFIX;}boolPushBackUniqueValue(pCharVector&pCode,char*pValue){assert(pValue!=NULL);for(inti=0;ipCode.size();i++){if(0==strcmp(pValue,pCode[i]))//有重复,直接返回returnfalse;}pCode.push_back(pValue);returntrue;}intIsUDC(constpCharVector&pCode){assert(pCode.size()!=0);//用于存放后缀码pCharVectorCodePostfix;//第一轮比较,码字内部比较,得到第一个后缀码集合char*iter1,*iter2;inti,j;for(i=0;ipCode.size();i++){iter1=pCode.at(i);for(j=0;jpCode.size();j++){//不比较自身if(i==j)continue;iter2=pCode.at(j);intnRetn=IsPrefix(iter1,iter2);if(ISSAME==nRetn)returnNOTUDC;if(ISPREFIX==nRetn){//将iter2的后缀填入CodePostfixPushBackUniqueValue(CodePostfix,iter2+strlen(iter1));}}}if(CodePostfix.size()==0)returnISRTC;//第二轮比较,比较后缀码集合中是否含有码字集合中的元素//有则返回NOTUDC,如果后缀码集合中没有再出现新元素了表明该码字是//UDC//指向当前集合在整个后缀码集合中的位置,也即是//前面所有后缀码的个数intnPointer=CodePostfix.size();//指向当前集合的大小intnNewAssembleSize=nPointer;do{nPointer=CodePostfix.size();for(i=0;ipCode.size();i++){iter1=pCode.at(i);for(j=nPointer-nNewAssembleSize;jnPointer;j++){iter2=CodePostfix.at(j);intnRetn=IsPrefix(iter1,iter2);if(nRetn==ISSAME){cout码字iter1无法解析!;//两个码字相同,返回falsereturnNOTUDC;}if(ISPREFIX==nRetn){//将iter2的后缀填入CodePostfixTempPushBackUniqueValue(CodePostfix,iter2+strlen(iter1));}if(ISPREFIX==IsPrefix(iter2,iter1)){//将iter1的后缀填入CodePostfixTempPushBackUniqueValue(CodePostfix,iter1+strlen(iter2));}}}nNewAssembleSize=CodePostfix.size()-nPointer;}while(nNewAssembleSize!=0);CodePostfix.clear();returnISUDC;}/************************************************************************//*该函数是用来对每个pPostfix和原码字序列进行比较,如果重复了则在pRetnBuf中/*返回本身.并返回1.否则如果没有得到新的后缀码的话返回0表示无重复*//*Stack用来存储递归中产生的后缀码集合,这样确保每次得到的后缀码不会重复/*防止进去死循环/************************************************************************/intGetBacktraceSeq(constpCharVector&pCode,char*pPostfix,pCharVector&Stack,char**pRetnBuf){char*iter1;for(inti=0;ipCode.size();i++){iter1=pCode.at(i);intnRetn=IsPrefix(iter1,pPostfix);if(nRetn==ISSAME){//第一次进来的话由于是码字序列内部的比较,所以//肯定会遇到自己跟自己比较然后相等的情况,对该情况不允考虑if(Stack.size()==0)continue;*pRetnBuf=newchar[strlen(pPostfix)+1];strcpy(*pRetnBuf,pPostfix);return1;}if(ISPREFIX==nRetn){//新得到的后缀码已经重复了,跳过对他的处理if(PushBackUniqueValue(Stack,iter1)==false)cont