信息论课程设计报告(唯一可译码 lzw编码 算数编码) (1).doc

一判定唯一可译码
任务说明
输入:任意的一个码(即已知码字个数及每个具体的码字)
输出:判决结果(是/不是)
输入文件:,含至少2组码,每组的结尾为”$”符
输出文件:,对每组码的判断结果
说明:为了简化设计,可以假定码字为0,1串
问题分析、实现原理、流程图
参考算法伪代码:
For all do
if 是的前缀 then
将相应的后缀作为一个尾随后缀放入集合中
End if
End for
Loop
For all do
For all do
if 是的前缀 then
将相应的后缀作为一个尾随后缀放入集合中
Else if 是的前缀 then
将相应的后缀作为一个尾随后缀放入集合中
End if
End for
End for
If then
Return false
Else if F 中未出现新的元素 then
Return true
End if
//能走到这里,说明F中有新的元素出现,需继续
End loop
实现源码
#include <iostream>
#include <string>
using namespace std;
struct strings
{
char *string;
struct strings *next;
};
struct strings Fstr, *Fh, *FP;
//输出当前集合
void outputstr(strings *str)
{
do
{
cout<<str->string<<endl;
str = str->next;
}while(str);
cout<<endl;
}
inline int MIN(int a, int b)
{ return a>b?b:a; }
inline int MAX(int a, int b)
{ return a>b?a:b; }
#define length_a (strlen(CP))
#define length_b (strlen(tempPtr))
//判断一个码是否在一个码集合中,在则返回0,不在返回1
paring(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
<<CP<<endl
<<"不是唯一可译码码组!"<<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_a>length_b ? CP : tempPtr);//将长度长的码赋给longstr
//取出后缀
for (int k=MIN(length_a,length_b); k<MAX(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集合
paring(Fh,cp_temp->string))
{
FP->next=cp_temp;
FP=FP->next;
}
}
}
void main()
{
//功能提示和程序初始化准备
cout<<"\t\t唯一可译码的判断!\n"<<endl;
struct strings Cstr,*Ch,