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

LZW编码的编程和实现 实验目的 编写源程序,实现LZW的编码和解码 实验要求 1.编码 输入若干字母(如abbababac),输出相应的编码 2.解码 输入若干数字(如122473),输出相应的字母 编程思想 1.编码 根缀表已知 1 A 2 B 3 C 编码 分析字符串流，从词典中寻找最长匹配串，即字符串P在词典中，而字符串P+后一个字符C不在词典中 此时，输出P对应的码字，将P+C放入词典中。 如第一步： 输入A 此时，A在表中，而AB不在表中，则输出A对应的码字1,同时将AB写入表中，此时表为 1 A 2 B 3 C 4 AB 编码输出为1 (A已编码) 第二步,输入B,B在词典中，而BB不在词典中，则输出2，将BB写入表中，此时表为 1 A 2 B 3 C 4 AB 5 BB 编码输出为12 (AB已经编码) .... 2.解码 根缀表为 1 A 2 B 3 C 定义如下变量 StringP :前一步码字流 pW : StringP的第一个字符 StringC :当前的码字流 cW : StringC的第一个字符 第一步 输出StringC 并StringP = StringC 如: 1解码为A,则StringC = A 那么 输出A,并令StringP = A --------------------------------------------------------------------------- 第二步 1.解码得到StringC,并输出StringC 2.将StringP + cW放入词典(如果当前码字不在词典中,则将StringP + cP放入词典中) 3.StringP = StringC 如: 第二步要解码为2,解码为B,则StringC=B,输出B (此时StringP = A) 将StringP+cW放入表中,即将AB放入表中,此时表为 1 A 2 B 3 C 4 AB 实验情况及分析 编码 解码 错误提示 附:源代码 #includeiostream #includestring #includeiomanip using namespace std; string dic[30]; int n; int find(string s)//字典中寻找,返回序号 { int temp=-1; for(int i=0;i30;i++) { if(dic[i]==s) temp=i+1; } return temp; } void init()//字典初始化 { dic[0]=a; dic[1]=b; dic[2]=c;//字根为a,b,c for(int i=3;i30;i++)//其余为空 { dic[i]=; } } void code(string str) { init();//初始化 char temp[2]; temp[0]=str[0];//取第一个字符 temp[1]=\0; string w=temp; int i=1; int j=3;//目前字典存储的最后一个位置 cout\n 编码为：; for(;;) { char t[2]; t[0]=str[i];//取下一字符 t[1]=\0; string k=t; if(k==) //为空，字符串结束 { cout find(w); break;//退出for循环,编码结束 } if(find(w+k)-1) { w=w+k; i++; } else { cout find(w); string wk=w+k; dic[j++]=wk; w=k; i++; } } coutendl; for(i=0;ij;i++) { coutsetw(45)i+1setw(12)dic[i]endl; } coutendl; } void decode(int c[]) { init(); int pw,cw; cw=c[0]; int j=2; cout\n 译码为：; coutdic[cw-1]; for(int i=0;in-1;i++) { pw=cw; cw=c[i+1]; if(cw=j+1) { coutdic[cw-1]; char t[2]; t[0]=dic[cw-1][0]; t[1]=\0; string k=t; j++; dic[j]=dic[pw-1]+k; } else { char t[2]; t[0]=dic[pw-1][0]; t[1]=\0; string k=t; j++; dic[j]=dic[pw-1]+k; coutdic[cw-1]; } } coutendl; for(i=0;ij+1;i++) { co