信息论课程设计报告..docx

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#includestring using namespace std;struct strings { char *string; struct strings *next; }; struct strings Fstr, *Fh, *FP; //输出当前集合void outputstr(strings *str) { do { coutstr-stringendl; str = str-next; }while(str); coutendl; } inline int MIN(int a, int b) {return ab?b:a; } inline int MAX(int a, int b) {return ab?a:b; } #define length_a (strlen(CP)) #define length_b (strlen(tempPtr)) //判断一个码是否在一个码集合中，在则返回，不在返回int comparing(strings *st_string,char *code) { while(st_string-next) { st_string=st_string-next; if(!strcmp(st_string-string,code)) return 0; }return 1; } //判断两个码字是否一个是另一个的前缀，如果是则生成后缀码void houzhui(char *CP,char *tempPtr) { if (!strcmp(CP,tempPtr)) { cout集合C和集合F中有相同码字:endl CPendl 不是唯一可译码码组!endl; exit(1); } if (!strncmp(CP, tempPtr, MIN(length_a,length_b))) { struct strings *cp_temp; cp_temp=new (struct strings); cp_temp-next=NULL; cp_temp-string=new char[abs(length_a-length_b)+1]; char *longstr; longstr=(length_alength_b ? CP : tempPtr);//将长度长的码赋给longstr //取出后缀 for (int k=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; //判断新生成的后缀码是否已在集合F里，不在则加入F集合 if(comparing(Fh,cp_temp-string)) { FP-next=cp_temp; FP=FP-next; } } } void main() { //功能提示和程序初始化准备 cout\t\t\t判定唯一可译码\nendl; struct strings Cstr,*Ch, *CP,*tempPtr; Ch=Cstr; CP=Ch; Fh=Fstr; FP=Fh; char c[]=码字集合C :; Ch-string=new char[strlen(c)]; strcpy(Ch-stri