LZW编码编程实现（C++版）.doc

LZW编码的编程和实现一、 实验目的编写源程序,实现LZW的编码和解码二、 实验要求1.编码 输入若干字母(如abbababac),输出相应的编码2.解码 输入若干数字(如122473),输出相应的字母三、 编程思想1.编码根缀表已知1 A2 B3 C编码分析字符串流，从词典中寻找最长匹配串，即字符串P在词典中，而字符串P+后一个字符C不在词典中此时，输出P对应的码字，将P+C放入词典中。如第一步：输入A此时，A在表中，而AB不在表中，则输出A对应的码字1,同时将AB写入表中，此时表为1 A2 B3 C4 AB编码输出为1 (A已编码)第二步,输入B,B在词典中，而BB不在词典中，则输出2，将BB写入表中，此时表为1 A2 B3 C4 AB5 BB编码输出为12 (AB已经编码).2.解码根缀表为1 A2 B3 C定义如下变量StringP :前一步码字流pW : StringP的第一个字符StringC :当前的码字流cW : StringC的第一个字符第一步输出StringC 并StringP = StringC如:1解码为A,则StringC = A那么输出A,并令StringP = A-第二步1.解码得到StringC,并输出StringC2.将StringP + cW放入词典(如果当前码字不在词典中,则将StringP + cP放入词典中)3.StringP = StringC如:第二步要解码为2,解码为B,则StringC=B,输出B (此时StringP = A)将StringP+cW放入表中,即将AB放入表中,此时表为1 A2 B3 C4 AB四、 实验情况及分析编码 解码错误提示附:源代码#include#include#includeusing namespace std;string dic30;int n;int find(string s)/字典中寻找,返回序号int temp=-1;for(int i=0;i30;i+)if(dici=s) temp=i+1;return temp;void init()/字典初始化dic0=a;dic1=b;dic2=c;/字根为a,b,cfor(int i=3;i30;i+)/其余为空dici=;void code(string str)init();/初始化char temp2;temp0=str0;/取第一个字符temp1=0;string w=temp;int i=1;int j=3;/目前字典存储的最后一个位置coutn 编码为：;for(;)char t2;t0=stri;/取下一字符t1=0;string k=t;if(k=) /为空，字符串结束cout -1)w=w+k;i+;elsecout find(w);string wk=w+k;dicj+=wk;w=k;i+;coutendl;for(i=0;ij;i+)coutsetw(45)i+1setw(12)diciendl;coutendl;void decode(int c)init();int pw,cw;cw=c0;int j=2;coutn 译码为：;coutdiccw-1;for(int i=0;in-1;i+)pw=cw;cw=ci+1;if(cw=j+1)coutdiccw-1;char t2;t0=diccw-10;t1=0;string k=t;j+;dicj=dicpw-1+k;elsechar t2;t0=dicpw-10;t1=0;string k=t;j+;dicj=dicpw-1+k;coutdiccw-1;coutendl;for(i=0;ij+1;i+)coutsetw(45)i+1setw(12)diciendl;coutendl;void main()string str;while(1)coutnnta.编码tb.译码nn;coutcha;if(cha=a)coutstr;code(str);i