信息论课程设计报告

1、xx大学信息论课程设计姓名：学号：学院：指导老师：完成日期：2015.01.04一、判定唯一可译码1．任务说明：输入：任意的一个码(即已知码字个数及每个具体的码字)输出：判决结果（是/不是）输入文件:in1.txt，含至少2组码，每组的结尾为”$”符输出文件:out1.txt，对每组码的判断结果说明：为了简化设计，可以假定码字为0，1串2．问题分析、实现原理判定唯一可译码根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据类型并利用指针进行编程来实现算法。算法：1、考察C中所有的码字，若Wi是Wj的前缀，则将对应的后缀作为一个尾随后缀码放入集合Fi+1中；2、考察C和Fi俩个集合，若Wi∈C是Wj∈F的前缀或Wi∈F是Wj∈C的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中；3、F=∪Fi即为码C的尾随后缀集合；4、若F中出现了C中的元素，算法终止，返回假（C不是唯一可译码）；否则若F中没有出现新的元素则返回真。3.源代码：#includeiostream#includestdlib.h#includestringusingnamespacestd;structst。

2、rings{char*string;structstrings*next;};structstringsFstr,*Fh,*FP;//输出当前集合voidoutputstr(strings*str){do{coutstr-stringendl;str=str-next;}while(str);coutendl;}inlineintMIN(inta,intb){returnab?b:a;}inlineintMAX(inta,intb){returnab?a:b;}#definelength_a(strlen(CP))#definelength_b(strlen(tempPtr))//判断一个码是否在一个码集合中，在则返回，不在返回intcomparing(strings*st_string,char*code){while(st_string-next){st_string=st_string-next;if(!strcmp(st_string-string,code))return0;}return1;}//判断两个码字是否一个是另一个的前缀，如果是则生成后缀码voidhouzhui(。

3、char*CP,char*tempPtr){if(!strcmp(CP,tempPtr)){cout集合C和集合F中有相同码字:endlCPendl不是唯一可译码码组!endl;exit(1);}if(!strncmp(CP,tempPtr,MIN(length_a,length_b))){structstrings*cp_temp;cp_temp=new(structstrings);cp_temp-next=NULL;cp_temp-string=newchar[abs(length_a-length_b)+1];char*longstr;longstr=(length_alength_b?CP:tempPtr);//将长度长的码赋给longstr//取出后缀for(intk=MIN(length_a,length_b);kMAX(length_a,length_b);k++)cp_temp-string[k-MIN(length_a,length_b)]=longstr[k];cp_temp-string[abs(length_a-length_b)]=NULL;//判断新生成的。

4、后缀码是否已在集合F里，不在则加入F集合if(comparing(Fh,cp_temp-string)){FP-next=cp_temp;FP=FP-next;}}}voidmain(){//功能提示和程序初始化准备cout\t\t\t判定唯一可译码\nendl;structstringsCstr,*Ch,*CP,*tempPtr;Ch=&Cstr;CP=Ch;Fh=&Fstr;FP=Fh;charc[]=码字集合C:;Ch-string=newchar[strlen(c)];strcpy(Ch-string,c);Ch-next=NULL;charf[]=后缀集合F:;Fh-string=newchar[strlen(f)];strcpy(Fh-string,f);Fh-next=NULL;intCnum;//待检测码的个数cout输入待检测码字的个数:;cinCnum;cout输入待检测码，每输入一个都按回车键结束：endl;for(inti=0;iCnum;i++){cout第i+1个码字是：;chartempstr[10];cintempstr;CP-next=new(stru。

5、ctstrings);CP=CP-next;CP-string=newchar[strlen(tempstr)];strcpy(CP-string,tempstr);CP-next=NULL;}outputstr(Ch);CP=Ch;while(CP-next-next){CP=CP-next;tempPtr=CP;do{tempPtr=tempPtr-next;houzhui(CP-string,tempPtr-string);}while(tempPtr-next);}outputstr(Fh);structstrings*Fbegin,*Fend;Fend=Fh;while(1){if(Fend==FP){cout是唯一可译码码组!endl;exit(1);}Fbegin=Fend;Fend=FP;CP=Ch;while(CP-next){CP=CP-next;tempPtr=Fbegin;for(;;){tempPtr=tempPtr-next;houzhui(CP-string,tempPtr-string);if(tempPtr==Fend)break;}}outputst。

6、r(Fh);//输出F集合中全部元素}}4.程序结果截图：二、LZW编码与译码1．任务说明：输入：由集合{a,b,c,d}内字符构成的输入串，输入序列长度L=100处理：先编码，再对编码结果译码输出：编码结果，译码结果输入文件:in4.txt，含至少两组输入，每组包含满足要求的串输出文件:out4.txt，对每组输入的编码和译码结果2.问题分析、实现原理（1）.编码程序：步骤一：开始时的词典包含所有可能的根，而当前前缀P是空的。步骤二：当前字符C：=字符流中的下一个字符。步骤三：判断P+C是否在词典中：（1）如果“是”，P:=P+C。（2）如果“否”，则：①把代表当前前缀P的码字输出到码字流。②把缀-符串P+C添加到词典中。③令P：=C。（3）判断字符流中是否还有字符需要编码：①如果“是”，返回到步骤二。②如果“否”：输出相应于当前前缀P的码字。结束编码。（2）.译码程序：步骤一：在开始译码时，词典包含所有可能的前缀根。步骤二：当前码字cW：=码字流中的第一个码字。步骤三：输出当前缀-符串string.cW到字符流。步骤四：先前码字pW：=当前码字cW。步骤五：当前码字cW:=码字流中。

7、的下一个码字。步骤六：判断当前缀-符串string.cW是否在词典中：（1）如果“是”，则：①当前缀-符串string.cW输出到字符流。②当前前缀P：=先前缀-符串string.pW。③当前字符C：=当前前缀-符串string.cW的第一个字符。④把缀-符串P+C添加到词典。（2）如果“否”，则：①当前前缀P：=先前缀-符串string.pW。②当前字符C：=当前缀-符串string.pW的第一个字符。③输出缀-符串P+C到字符流，然后把它添加到词典中。步骤七：判断码字流中是否还有码字要译：（1）如果“是”，就返回到步骤四。（2）如果“否”，结束。3.源代码：#includeiostream#includestring#includeiomanipusingnamespacestd;stringdic[30];intn;intfind(strings)//字典中寻找,返回序号{inttemp=-1;for(inti=0;i30;i++){if(dic[i]==s)temp=i+1;}returntemp;}voidinit()//字典初始{dic[0]=a;//开始时词典包含所有可能。

8、的根dic[1]=b;dic[2]=c;dic[3]=d;for(inti=4;i30;i++)//其余为空{dic[i]=;}}voidcode(stringstr){init();//初始化chartemp[2];temp[0]=str[0];//取第一个字符temp[1]='\0';stringP=temp;//P为前缀inti=1;intj=4;//目前字典存储的最后一个位置cout编码后的码字为：;while(1){chart[2];t[0]=str[i];//取下一字符t[1]='\0';stringC=t;//C为字符流中下一个字符if(C==)//无码字要译，结束{coutfind(P);//输出代表当前前缀的码字break;}//退出循环,编码结束if(find(P+C)-1)//有码字要译，如果P+C在词典中，则用C扩展P，进行下一步：{P=P+C;i++;}else//如果P+C不在词典中，则将P+C添加到词典中，令P:=C{coutfind(P);stringPC=P+C;dic[j++]=PC;P=C;i++;}}coutendl;cout生成的词典为：end。

9、l;for(i=0;ij;i++)//输出词典中的内容,j为词典的长度{coutsetw(12)i+1setw(12)dic[i]endl;}coutendl;}voiddecode(intc[]){init();//译码词典与编码词典相同，将a,b,c设为初始的前缀intpw,cw;//pw：先前码字，cw：当前码字cw=c[0];//输入码字流的第一个码字，赋给当前码字intj=3,i;cout译码为：;coutdic[cw-1];//输出当前字符串到字符流for(intm=0;mn-1;m++){pw=cw;//当前码字赋给先前码字cw=c[m+1];if(cw=j+1)//若当前码字在词典中{coutdic[cw-1];//输出当前码字锁代表的字符串chart[2];t[0]=dic[cw-1][0];t[1]='\0';stringk=t;j++;dic[j]=dic[pw-1]+k;//将先前码字与当前码字所代表的字符串的首字符连接而成的//字符串添加到词典中}else//若当前码字不在词典中{chart[2];t[0]=dic[pw-1][0];t[1]='\0';str。

10、ingk=t;j++;dic[j]=dic[pw-1]+k;//将先前码字与当前码字所代表的字符串的首字符连接而//成的字符串添加到词典中coutdic[cw-1];//输出该字符串}}coutendl;cout生成的词典为：endl;for(i=0;ij;i++)//输出词典中的内容,j为词典的长度{coutsetw(12)i+1setw(12)dic[i]endl;}coutendl;}intmain()//主程序{stringstr;charchoice;while(1){cout\n\n\t\t1.编码\t\t2.译码\n\n;cout请选择功能对应的编号：;cinchoice;if(choice=='1')//若选择1则编码{cout\n输入要。