LZW编码算法.doc

班级__ __学号__姓名__ ___ 评分__________ LZW 编码与解码算法 通过实验进一步掌握 LZW 编码的原理; 用C/C++ 等高级程序设计语言实现 LZW 编码。 (包括源程序或流程和说明等) 实验原理(1)在压缩过程中动态形成一个字符列表(字典)。(2)每当压缩扫描图像发现一个词典中没有的字符序列,就把该字符序列存到字典中,并用字典的地址(编码)作为这个字符序列的代码,替换原图像中的字符序列,下次再碰到相同的字符序列,就用字典的地址代替字符序列 实验步骤 LZW 编码算法的具体执行步骤如下: 步骤 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> using namespace std; const int N=200; class LZW{ private: string Dic[200]; //存放词典 int code[N]; //存放编码过的码字 public: LZW(){ //设置词典根 Dic[0]='a'; Dic[1]='b'; Dic[2]='c'; string *p=Dic; //定义指针指向词典中的字符} void Bianma(string cs[N]); //进行编码 int IsDic(string e); //判断是否在词典中 int codeDic(string f); void display(int g); //显示结果};void LZW::Bianma(string cs[N]){ string P,C,K; P=cs[0]; int l=0; for(int i=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); }int LZW::IsDic(string e){ //如果字符流中还有字符需要编码 for(int b=0; b<200; b++) {if(e==Dic[b]) return 1;} return 0; }int LZW::codeDic(string f){ int w=0; for(int y=0;y<200;y++) if(f==Dic[y