LZW编码算法.doc

 通过实验进一步掌握LZW编码的原理; 用C/C++等高级程序设计语言实现LZW编码。实验内容步骤或记录(包括源程序或流程和说明等)(1)在压缩过程中动态形成一个字符列表(字典)。(2)每当压缩扫描图像发现一个词典中没有的字符序列,就把该字符序列存到字典中,并用字典的地址(编码)作为这个字符序列的代码,替换原图像中的字符序列,下次再碰到相同的字符序列,:步骤1: 开始时的词典包含所有可能的根(Root),而当前前缀P是空的;步骤2: 当前字符(C) :=字符流中的下一个字符;步骤3: 判断缀-符串P+C是否在词典中(1) 如果“是”:P := P+C // (用C扩展P) ;(2) 如果“否”① 把代表当前前缀P的码字输出到码字流;② 把缀-符串P+C添加到词典;③ 令P := C //(现在的P仅包含一个字符C);步骤4: 判断码字流中是否还有码字要译(1) 如果“是”,就返回到步骤2;(2) 如果“否”① 把代表当前前缀P的码字输出到码字流;② 结束。#include<iostream>#include<string>usingnamespacestd;constintN=200;classLZW{private:stringDic[200];//存放词典 intcode[N];//存放编码过的码字public:LZW(){//设置词典根 Dic[0]='a'; Dic[1]='b'; Dic[2]='c'; string*p=Dic;//定义指针指向词典中的字符} voidBianma(stringcs[N]);//进行编码 intIsDic(stringe);//判断是否在词典中 intcodeDic(stringf); voiddisplay(intg);//显示结果};voidLZW::Bianma(stringcs[N]){ stringP,C,K; P=cs[0]; intl=0; for(inti=1;i<N;i++){ C=cs[i];//当前字符(C) :=字符流中的下一个字符 K=P+C; if(IsDic(K))P=K;//P+C在词典中,用C扩展P else{//P+C不在词典中 code[l]=codeDic(P); Dic[3+l]=K;//将P+C加入词典 P=C; l++; } if(N-1==i)//如果字符流中没有字符需要编码 code[l]=codeDic(P); }display(l);}intLZW::IsDic(stringe){//如果字符流中还有字符需要编码 for(intb=0;b<200;b++) {if(e==Dic[b])return1; } return0;}intLZW::codeDic(stringf){ intw=0; for(inty=0;y<200;y++) if(f==Dic[y]){ w=y+1; break; }returnw;}voidLZW::display(intg){ cout<<"经过LZW编码后的码字如下:"<<endl; for(inti=0;i<=g;i++