1、实验二 唯一可译码判决准则一、实验目的（1）进一步熟悉唯一可译码判决准则；（2）掌握 C 语言字符串处理程序的设计和调试技术。二、实验要求（1）已知：信源符号个数 q、码字集合 C。（2）输入：任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。（3）输出：判决（是唯一可译码/不是唯一可译码） 。三、算法1.考察 C 中所有的字码，若 是 的前缀，则将相应的后缀作为一iWj个尾随后缀码放入集合 中；0F2.考察 C 和 两个集合，若 是 的前缀或 是 的i icjiFiiWFjC前缀，则将相应的后缀作为尾随后码放入集合 1i3. 即为码 C 的尾随后缀集合；iF4.若 中出现了 中的元素
2、，则算法终止，返回假（ 不是唯一可译C码） ；否则，若 中没有出现新的元素，则返回真。四、代码#include #include #include #include using namespace std;#define ISSAME 0 #define ISPREFIX 1#define NOTPREFIX 2#define ISUDC 0 /唯一可译码#define ISRTC 1 /即时码#define NOTUDC 2 /非唯一可译码typedef vector pCharVector;/*/* 判断 chPrefix 是否为 chWord 的前缀.*/int IsPrefix(con
3、st char* chPrefix,const char* chWord);/*/* 往后缀码集合中插入不重复的键,*/bool PushBackUniqueValue(pCharVector/*/* 判断码字序列的类型,非回溯法*/int IsUDC(const pCharVector/*/* 回溯计算,如果不是唯一可译码则可以得到一串有歧义的码字序列( 即有多种译法的/* 序列),该序列用参数中的 pInvalidSeqBuf 返回,调用者需记得释放内存/* 该方法的缺点是没有检测码字序列中是否有重复码字 */int IsUDC_Backtrace(const pCharVector/#d
4、efine TEST_BY_FILEint main()#ifdef TEST_BY_FILEfreopen(“in“,“r“,stdin);/文件重定向 freopen 函数,文本多行读入 *freopen(char *filename, char *type, FILE *stream)#endifpCharVector VCode;int nCodeNum;int i;char chContinue;do coutnCodeNum;coutstrBuffer;/copy 字符到动态数组中已进行比较char* pTemp = new charstrBuffer.size() + 1;/*m
5、emcpy(void *dest, void *src, unsigned int count),功能：由 src 所指内存区域复制 count 个字节到 dest 所指内存区域/src 和 dest 所指内存区域不能重叠，函数返回指向 dest 的指针memcpy(pTemp,strBuffer.c_str(),sizeof(char) * (strBuffer.size() + 1);/c_str() 是把 string 转化为 char*型VCode.push_back(pTemp); /push_back()函数会在 vector 对象 VCode 后面添加元素 char * pRet
6、n = NULL;int nRetn = IsUDC_Backtrace(VCode,if (NOTUDC != nRetn)coutchContinue; while(toupper(chContinue) = Y);/toupper（将小写字母转换成大写字母）#ifdef TEST_BY_FILEfclose(stdin);/fclose 是关闭 freopen()的指针#endifreturn 0;int IsPrefix(const char* chPrefix,const char* chWord)assert(chPrefix != NULL int nLenPrefix,nLen
7、Word;nLenPrefix = strlen(chPrefix);nLenWord = strlen(chWord);/前缀长度大于整个词的长度,返回 falseif (nLenPrefix nLenWord)return NOTPREFIX;int nRetn = memcmp(chPrefix,chWord,sizeof(char) * strlen(chPrefix);if(0 = nRetn if(0 = nRetn) return ISPREFIX;return NOTPREFIX;bool PushBackUniqueValue(pCharVectorfor (int i =
8、0; i pCode.size(); i+)if (0 = strcmp(pValue,pCodei) /有重复,直接返回return false;pCode.push_back(pValue);return true;int IsUDC(const pCharVector/用于存放后缀码 pCharVector CodePostfix;/第一轮比较,码字内部比较,得到第一个后缀码集合char *iter1,*iter2;int i,j;for (i = 0; i pCode.size(); i+)iter1 = pCode.at(i);for (j = 0; j pCode.size();
9、j+)/不比较自身if(i = j) continue;iter2 = pCode.at(j);int nRetn = IsPrefix(iter1,iter2);if(ISSAME = nRetn) return NOTUDC;if (ISPREFIX = nRetn)/将 iter2 的后缀填入 CodePostfixPushBackUniqueValue(CodePostfix,iter2+strlen(iter1);if(CodePostfix.size() = 0) return ISRTC;/第二轮比较,比较后缀码集合中是否含有码字集合中的元素/有则返回 NOTUDC,如果后缀码集
10、合中没有再出现新元素了表明该码字是/UDC/指向当前集合在整个后缀码集合中的位置,也即是/前面所有后缀码的个数int nPointer = CodePostfix.size(); /指向当前集合的大小int nNewAssembleSize = nPointer;do nPointer = CodePostfix.size();for (i = 0; i pCode.size(); i+)iter1 = pCode.at(i);for (j = nPointer - nNewAssembleSize; j nPointer; j+)iter2 = CodePostfix.at(j);int n
11、Retn = IsPrefix(iter1,iter2);if (nRetn = ISSAME)cout“码字“iter1“无法解析! “;/两个码字相同,返回 falsereturn NOTUDC;if (ISPREFIX = nRetn)/将 iter2 的后缀填入 CodePostfixTempPushBackUniqueValue(CodePostfix,iter2+strlen(iter1);if (ISPREFIX = IsPrefix(iter2,iter1)/将 iter1 的后缀填入 CodePostfixTempPushBackUniqueValue(CodePostfix
12、,iter1+strlen(iter2);nNewAssembleSize = CodePostfix.size() - nPointer; while(nNewAssembleSize != 0);CodePostfix.clear();return ISUDC;/*/* 该函数是用来对每个 pPostfix 和原码字序列进行比较, 如果重复了则在 pRetnBuf 中/* 返回本身.并返回 1.否则如果没有得到新的后缀码的话返回 0 表示无重复*/*/* Stack 用来存储递归中产生的后缀码集合,这样确保每次得到的后缀码不会重复/* 防止进去死循环*/int GetBacktraceSe
13、q(const pCharVectorfor (int i = 0; i pCode.size(); i+)iter1 = pCode.at(i); int nRetn = IsPrefix(iter1,pPostfix);if (nRetn = ISSAME)/第一次进来的话由于是码字序列内部的比较 ,所以/肯定会遇到自己跟自己比较然后相等的情况 ,对该情况不允考虑if(Stack.size() = 0) continue; *pRetnBuf = new charstrlen(pPostfix) + 1;strcpy(*pRetnBuf,pPostfix);return 1; if (IS
14、PREFIX = nRetn) /新得到的后缀码已经重复了,跳过对他的处理if(PushBackUniqueValue(Stack,iter1) = false) continue;char* pTemp = NULL;/递归处理下一个后缀码if(GetBacktraceSeq(pCode,pPostfix+strlen(iter1),Stack,Stack.pop_back();continue;Stack.pop_back();/递归过程中遇到重复码字,算法应立即返回 ./将自身和递归得到的后面的后缀码组合成一个歧义序列返回char* pNewTraceSeq = new charstrl
15、en(iter1) + strlen(pTemp) + 1;pNewTraceSeq0 = 0;strcat(pNewTraceSeq,iter1);strcat(pNewTraceSeq + strlen(iter1),pTemp);delete pTemp;*pRetnBuf = pNewTraceSeq; return 1;if (ISPREFIX = IsPrefix(pPostfix,iter1) if(PushBackUniqueValue(Stack,pPostfix) = false) continue;char* pTemp = NULL;if(GetBacktraceSeq
16、(pCode,iter1+strlen(pPostfix),Stack,Stack.pop_back();continue;Stack.pop_back();char* pNewTraceSeq = new charstrlen(pPostfix) + strlen(pTemp) + 1;pNewTraceSeq0 = 0;strcat(pNewTraceSeq,pPostfix);strcat(pNewTraceSeq + strlen(pPostfix),pTemp);delete pTemp;*pRetnBuf = pNewTraceSeq; return 1;return 0;/*/*
17、 用递归的方法实现唯一可译码的判决,当码字序列不是唯一可译码时,输出有歧义的/* 码字序列*/int IsUDC_Backtrace(const pCharVector/用于存放后缀码 pCharVector CodePostfix;/第一轮比较,码字内部比较,得到第一个后缀码集合char *iter1;int i,j;pCharVector Stack;for (i = 0; i pCode.size(); i+)iter1 = pCode.at(i);/AT( ) 函数：返回一个字符表达式或备注字段在另一个字符表达或备注字段中首次出现的位置，/从最左边开始计数。 char* pTemp =
18、 NULL;int nRetn = GetBacktraceSeq(pCode,iter1,Stack,if(nRetn = 1) *pInvalidSeqBuf = pTemp;return NOTUDC;*pInvalidSeqBuf = NULL;return ISUDC;五、运行结果1、为唯一可译码时：（1）已知：信源符号个数 6、码字集合aba ae de acd bbs dnf（2）输入：任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。（3）输出：判决（是唯一可译码） 。2、不是唯一可译码时：（1）已知：信源符号个数 6、码字集合a c ad abb ba dad（2）输入：任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。（3）输出：判决（不是是唯一可译码） 。歧义序列为：adad六、实验总结本实验使用 C+编写，使用了递归方法比较出了惟一可译码和不是唯一可译码，感觉这个实验比较复杂，对于信息论与编码也是一个很好的复习，也是对 C+语言的一个回顾与熟悉，便于后面的实验。
