實驗1：唯一可譯碼的判定(共9頁)

1、實驗1：唯一可譯碼的判定學(xué)生姓名： 學(xué) 號：一、實驗室名稱：信息論基礎(chǔ)課程組二、實驗項目名稱：唯一可譯碼的判定三、實驗原理：給定一個已知的碼C，利用A . A .Sardinass和G .W .Patterson于1957年提出的算法判定碼C是否為唯一可譯碼。四、實驗?zāi)康模?1)進一步熟悉唯一可譯碼判決準則；(2)掌握C語言字符串處理程序的設(shè)計和調(diào)試技術(shù)。五、實驗內(nèi)容： 給定一個已知的碼C，判定碼C是否為唯一可譯碼。六、實驗器材（設(shè)備、元器件）：PC機一臺，裝有VC+6.0或其它C語言集成開發(fā)環(huán)境。七、實驗步驟及操作：1 考查碼C中所有的碼子，若是的前綴，則將相應(yīng)的后綴作為一個尾隨后綴碼放入集

2、合中；2 考查C和兩個集合，若是的前綴或是的前綴，則將相應(yīng)的后綴作為尾隨碼放入集合中；3 即為碼C的尾隨集合；4 若F中出現(xiàn)了C中的元素，則算法終止，返回假（C不是唯一可譯碼），否則若F中沒有出現(xiàn)新的元素，則返回真。八、實驗數(shù)據(jù)及結(jié)果分析： 題目：教材P103 例5.4的內(nèi)容。#include <iostream>#include <vector>#include <string>#include <cassert>using namespace std;#define ISSAME 0 #define ISPREFIX 1#define NOT

3、PREFIX 2#define ISUDC 0 /唯一可譯碼#define ISRTC 1 /即時碼#define NOTUDC 2 /非唯一可譯碼typedef vector<char*> pCharVector;/*/* 判斷chPrefix是否為chWord的前綴.*/*/int IsPrefix(const char* chPrefix,const char* chWord);/*/* 往后綴碼集合中插入不重復(fù)的鍵,*/*/bool PushBackUniqueValue(pCharVector& pCode,char* pValue);/*/* 判斷碼字序列的類型

4、,非回溯法*/*/int IsUDC(const pCharVector& pCode);/*/* 回溯計算,如果不是唯一可譯碼則可以得到一串有歧義的碼字序列(即有多種譯法的/* 序列),該序列用參數(shù)中的pInvalidSeqBuf返回,調(diào)用者需記得釋放內(nèi)存/* 該方法的缺點是沒有檢測碼字序列中是否有重復(fù)碼字*/*/int IsUDC_Backtrace(const pCharVector& pCode,char* pInvalidSeqBuf);/#define TEST_BY_FILEint main() #ifdef TEST_BY_FILE freopen("

5、in","r",stdin); #endif pCharVector VCode; int nCodeNum; int i; char chContinue; do cout<<"請輸入信源編碼個數(shù):" cin>>nCodeNum; cout<<"請輸入依次"<<nCodeNum<<"組碼字(以回車表示碼字的結(jié)束): " for (i = 0; i < nCodeNum; i+) /將輸入讀取到緩沖區(qū) string strBuffer; c

6、in>>strBuffer; /copy字符到動態(tài)數(shù)組中已進行比較 char* pTemp = new charstrBuffer.size() + 1; memcpy(pTemp,strBuffer.c_str(),sizeof(char) * (strBuffer.size() + 1); VCode.push_back(pTemp); char * pRetn = NULL; int nRetn = IsUDC_Backtrace(VCode,&pRetn); if (NOTUDC != nRetn) cout<<"該碼字序列/集合是唯一可譯碼碼

7、組! " else cout<<"該碼字序列/集合不是唯一可譯碼碼組! " cout<<"有歧義序列為:"<<pRetn; if (ISRTC = nRetn) cout<<"該碼字序列/集合是即時碼! " else cout<<"該碼字序列/集合不是即時碼! " /清除內(nèi)存 delete pRetn; for (i = 0; i < VCode.size(); i+) delete VCode.at(i); VCode.clear();

8、cout<<"繼續(xù)嗎?(Y/N):" cin>>chContinue; while(toupper(chContinue) = 'Y'); #ifdef TEST_BY_FILE fclose(stdin); #endif return 0;int IsPrefix(const char* chPrefix,const char* chWord) assert(chPrefix != NULL && chWord != NULL); int nLenPrefix,nLenWord; nLenPrefix = strle

9、n(chPrefix); nLenWord = strlen(chWord); /前綴長度大于整個詞的長度,返回false if (nLenPrefix > nLenWord) return NOTPREFIX; int nRetn = memcmp(chPrefix,chWord,sizeof(char) * strlen(chPrefix); if(0 = nRetn && nLenPrefix = nLenWord) return ISSAME; if(0 = nRetn) return ISPREFIX; return NOTPREFIX;bool PushBac

10、kUniqueValue(pCharVector& pCode,char* pValue) assert(pValue != NULL); for (int i = 0; i < pCode.size(); i+) if (0 = strcmp(pValue,pCodei) /有重復(fù),直接返回 return false; pCode.push_back(pValue); return true;int IsUDC(const pCharVector& pCode) assert(pCode.size() != 0); /用于存放后綴碼 pCharVector CodePo

11、stfix; /第一輪比較,碼字內(nèi)部比較,得到第一個后綴碼集合 char *iter1,*iter2; int i,j; for (i = 0; i < pCode.size(); i+) iter1 = pCode.at(i); for (j = 0; j < pCode.size(); j+) /不比較自身 if(i = j) continue; iter2 = pCode.at(j); int nRetn = IsPrefix(iter1,iter2); if(ISSAME = nRetn) return NOTUDC; if (ISPREFIX = nRetn) /將ite

12、r2的后綴填入CodePostfix PushBackUniqueValue(CodePostfix,iter2+strlen(iter1); if(CodePostfix.size() = 0) return ISRTC; /第二輪比較,比較后綴碼集合中是否含有碼字集合中的元素 /有則返回NOTUDC,如果后綴碼集合中沒有再出現(xiàn)新元素了表明該碼字是 /UDC /指向當前集合在整個后綴碼集合中的位置,也即是 /前面所有后綴碼的個數(shù) int nPointer = CodePostfix.size(); /指向當前集合的大小 int nNewAssembleSize = nPointer; do

13、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 nRetn = IsPrefix(iter1,iter2); if (nRetn = ISSAME) cout<<"碼字"<<iter1<<"無法解析! " /兩個碼

14、字相同,返回false return NOTUDC; if (ISPREFIX = nRetn) /將iter2的后綴填入CodePostfixTemp PushBackUniqueValue(CodePostfix,iter2+strlen(iter1); if (ISPREFIX = IsPrefix(iter2,iter1) /將iter1的后綴填入CodePostfixTemp PushBackUniqueValue(CodePostfix,iter1+strlen(iter2); nNewAssembleSize = CodePostfix.size() - nPointer; wh

15、ile(nNewAssembleSize != 0); CodePostfix.clear(); return ISUDC;/*/* 該函數(shù)是用來對每個pPostfix和原碼字序列進行比較, 如果重復(fù)了則在pRetnBuf中/* 返回本身.并返回1.否則如果沒有得到新的后綴碼的話返回0表示無重復(fù)*/* Stack用來存儲遞歸中產(chǎn)生的后綴碼集合,這樣確保每次得到的后綴碼不會重復(fù)/* 防止進去死循環(huán)/*/int GetBacktraceSeq(const pCharVector& pCode,char* pPostfix,pCharVector& Stack,char* pRetn

16、Buf) char* iter1; for (int i = 0; i < pCode.size(); i+) iter1 = pCode.at(i); int nRetn = IsPrefix(iter1,pPostfix); if (nRetn = ISSAME) /第一次進來的話由于是碼字序列內(nèi)部的比較,所以 /肯定會遇到自己跟自己比較然后相等的情況,對該情況不允考慮 if(Stack.size() = 0) continue; *pRetnBuf = new charstrlen(pPostfix) + 1; strcpy(*pRetnBuf,pPostfix); return

17、1; if (ISPREFIX = nRetn) /新得到的后綴碼已經(jīng)重復(fù)了,跳過對他的處理 if(PushBackUniqueValue(Stack,iter1) = false) continue; char* pTemp = NULL; /遞歸處理下一個后綴碼 if(GetBacktraceSeq(pCode,pPostfix+strlen(iter1),Stack,&pTemp) = 0) *pRetnBuf = NULL; Stack.pop_back(); continue; Stack.pop_back(); /遞歸過程中遇到重復(fù)碼字,算法應(yīng)立即返回. /將自身和遞歸得到

18、的后面的后綴碼組合成一個歧義序列返回 char* pNewTraceSeq = new charstrlen(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,pPostfi

19、x) = false) continue; char* pTemp = NULL; if(GetBacktraceSeq(pCode,iter1+strlen(pPostfix),Stack,&pTemp) = 0) *pRetnBuf = NULL; Stack.pop_back(); continue; Stack.pop_back(); char* pNewTraceSeq = new charstrlen(pPostfix) + strlen(pTemp) + 1; pNewTraceSeq0 = 0; strcat(pNewTraceSeq,pPostfix); strcat(pNewTraceSeq + strlen(pPostfix),pTe