信息論與編碼實驗報告學(xué)院：計算機與通信工程學(xué)院專業(yè)：計算機科學(xué)與技術(shù)班級：計1203班學(xué)號：姓名：2014年12月29日實驗一唯一可譯碼判別準(zhǔn)則實驗?zāi)康模?.進一步熟悉唯一可譯碼判別準(zhǔn)則；2.掌握C語言字符串處理程序的設(shè)計和調(diào)試技術(shù)。實驗內(nèi)容：已知：信源符號數(shù)和碼字集合C；輸入：任意的一個碼，碼字的個數(shù)和每個具體的碼字在運行時從鍵盤輸入；輸出：判決（是唯一可譯碼/不是唯一可譯碼）；循環(huán)（若繼續(xù)判決則輸入1循環(huán)判決，否則輸入0結(jié)束運行）。實驗原理：根據(jù)唯一可譯碼的判別方法，利用數(shù)據(jù)結(jié)構(gòu)所學(xué)的知識，定義字符串?dāng)?shù)據(jù)類型并利用指針進行編程來實現(xiàn)算法。算法：1、考察C中所有的碼字，若Wi是Wj的前綴，則將對應(yīng)的后綴作為一個尾隨后綴碼放入集合Fi+1中；2、考察C和Fi倆個集合，若Wi∈C是Wj∈F的前綴或Wi∈F是Wj∈C的前綴，則將相應(yīng)的后綴作為尾隨后綴碼放入集合Fi+1中；3、F=∪Fi即為碼C的尾隨后綴集合；4、若F中出現(xiàn)了C中的元素，算法終止，返回假（C不是唯一可譯碼）；否則若F中沒有出現(xiàn)新的元素，則返回真。實驗環(huán)境及實驗文件存檔名：1.實驗環(huán)境：visualC++6.02.文件名：weiyikeyi.cpp實驗結(jié)果及分析：1.源代碼：#include<stdio.h>#include<string.h>charc[100][50];charf[300][50];intN,sum=0;//N為輸入碼字的個數(shù)，sum為尾隨后綴集合中碼字的個數(shù)intflag;//判斷是否唯一可譯標(biāo)志位voidpatterson(charc[],chard[])//檢測尾隨后綴{ inti,j,k;for(i=0;;i++) { if(c[i]=='\0'&&d[i]=='\0')//2字符串一樣，跳出 if(strcmp(f[i],c[j])==0) { flag=1; break; } } } if(flag==1) { printf("這不是唯一可譯碼！\n"); } else printf("這是唯一可譯碼！\n"); }}voidmain(){ intflag=1; while(flag){ yima(); printf("是否繼續(xù)判別？1/0\n"); scanf("%d",&flag); }}運行結(jié)果輸入0,01,001時：繼續(xù)執(zhí)行，輸入1,01,10,1010結(jié)束執(zhí)行實驗二霍夫曼編碼實驗?zāi)康模哼M一步熟悉Huffman編碼過程；掌握C語言遞歸程序的設(shè)計和調(diào)試技術(shù)。實驗內(nèi)容：輸入：信源符號個數(shù)r、信源的概率分布P；輸出：每個信源符號對應(yīng)的Huffman編碼的碼字。實驗原理：將q個信源符合按概率大小遞減排列;用“0,1”碼符號分別代表概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個，從而得到只包含q-1個符號的新信源，稱為縮減信源；把縮減信源的符號仍按概率大小遞減次序排列，再將其最后兩個概率最小的信源符號分別用“0”和“1”碼符號表示，并且合并成一個符號，這樣又形成了q-2個信源符號的縮減信源；依次繼續(xù)下去，直至信源符號最后只剩下兩個信源符號為止，將這最后兩個信源符號分別用二元碼符號“0”和“1”表示；然后從最后一級縮減信源開始，進行回溯，就得到各信源符號所對應(yīng)的碼符號序列，即對應(yīng)的碼字。實驗環(huán)境及實驗文件存檔名：1.實驗環(huán)境：visualC++6.02.文件名：Huffman.cpp實驗結(jié)果及分析：程序源代碼：#include<stdio.h>#defineN50#definemaxval10000.0#definemaxsize100typedefstruct{charch;floatweight;intlchild,rchild,parent;}hufmtree;typedefstruct{charbits[N];//位串intstart;//編碼在位串中的起始位置charch;//字符}codetype;voidhuffman(hufmtreetree[]);//建立哈夫曼樹voidhuffmancode(codetypecode[],hufmtreetree[]);//根據(jù)哈夫曼樹求出哈夫曼編碼intn;intm;voidmain(){ printf("輸入信源符號個數(shù)\n"); scanf("%d",&n); getchar(); m=2*n-1;printf("*****霍夫曼哈夫曼編碼*****\n");printf("總共有%d個字符\n",n);hufmtreetree[2*N-1];codetypecode[N];inti,j;//循環(huán)變量huffman(tree);//建立哈夫曼樹huffmancode(code,tree);//根據(jù)哈夫曼樹求出哈夫曼編碼printf("輸出每個字符的哈夫曼編碼\n");for(i=0;i<n;i++){printf("%c:",code[i].ch);for(j=code[i].start;j<n;j++)printf("%c",code[i].bits[j]);printf("\n");}}voidhuffman(hufmtreetree[])//建立哈夫曼樹{inti,j,p1,p2;//p1,p2分別記住每次合并時權(quán)值最小和次小的兩個根結(jié)點的下標(biāo)floatsmall1,small2,f;charc;for(i=0;i<m;i++)//初始化{tree[i].parent=0;tree[i].lchild=-1;tree[i].rchild=-1;tree[i].weight=0.0;}printf("依次讀入前%d個結(jié)點的字符及權(quán)值(中間用空格隔開)\n",n);for(i=0;i<n;i++)//讀入前n個結(jié)點的字符及權(quán)值{printf("輸入第%d個字符為和權(quán)值",i+1);scanf("%c%f",&c,&f);getchar();tree[i].ch=c;tree[i].weight=f;}for(i=n;i<m;i++)//進行n-1次合并，產(chǎn)生n-1個新結(jié)點{p1=0;p2=0;small1=maxval;small2=maxval;//maxval是float類型的最大值for(j=0;j<i;j++)//選出兩個權(quán)值最小的根結(jié)點if(tree[j].parent==0)if(tree[j].weight<small1){small2=small1;//改變最小權(quán)、次小權(quán)及對應(yīng)的位置small1=tree[j].weight;p2=p1;p1=j;}elseif(tree[j].weight<small2){small2=tree[j].weight;//改變次小權(quán)及位置p2=j;}tree[p1].parent=i;tree[p2].parent=i;tree[i].lchild=p1;//最小權(quán)根結(jié)點是新結(jié)點的左孩子tree[i].rchild=p2;//次小權(quán)根結(jié)點是新結(jié)點的右孩子tree[i].weight=tree[p1].weight+tree[p2].weight;}}//huffmanvoidhuffmancode(codetypecode[],hufmtreetree[])//根據(jù)哈夫曼樹求出哈夫曼編碼//codetypecode[]為求出的哈夫曼編碼//hufmtreetree[]為已知的哈夫曼樹{inti,c,p;codetypecd;//緩沖變量for(i=0;i<n;i++){cd.start=n;cd.ch=tree[i].ch;c=i;//從葉結(jié)點出發(fā)向上回溯p=tree[i].parent;//tree[p]是tree[i]的雙親while(p!=0){cd.start--;if(tree[p].l