实验四LZW编码方案程序设计

实验四LZW编码方案程序设计一、实验目的（1）进一步熟悉通用编码算法；（2）掌握C语言程序设计和调试过程中数值进制转换、数值与字符串之间的转换等技术。二、实验要求（1）输入：本程序将从标准输入中读入待压缩的数据流；（2）输出：将压缩结果输出到标准输出上去。三、LZW算法描述1：procedureLZW2：字典初始化：将压缩文件中所有使用到的单字节字符放入字典中，为了压缩任何类型的文件，可以将字典的前256个位置（0x000到0x0FF）一次分配给0x00到0xFF的256个单字节字符。3：动态数据初始化：初始化新单词存放位置指针P。将它指向字典的第一个空位置。例如P=256（即0x100），读入被压缩文件的第一个字符cha，作为待处理单词W。单词的前缀Q为空，即Q=4095，尾字符就是cha，序号（码字）就是cha的序号。4：如果文件再没有字符了，输出当前单词的序号。编码结束。如果文件中还有字符，把当前单词W作为前缀，再从被压缩文件中读入一个字符CH，把CH作为尾字符，得到一个单词W1。5：如果字典中已有W1，则将W1看做当前单词W，返回第三步。如果字典中没有W1（发现一个新单词），先将原单词W的序号输出，再加新单词W1，增加到字典中，然后把刚刚读入的字符CH作为当前单词W，返回第三步。6:endprocedure--------------------------------------------------------------------------------------------------------------------四、实验代码/*程序说明：对输入的任意字符串，实现字典编码*/#includestdio.h#includestring.h#includestdlib.h#includeiostreamusingnamespacestd;charwd[4096][20];charstr[20],w[20],w1[20],c[20];chartext[1000];intN[1000];intnum;intM;intout(chars[])//得到一个短语是否在字典中，在时输出它的码字{inti;for(i=0;iM;i++)if(!strcmp(s,wd[i]))returni;return-1;}voidadd(chars[])//将一个短语加入字典中{strcpy(wd[M++],s);}intmain(){inti,j,k;for(i=0;i256;i++)//将所有单个字符加入字典中，初始化字典{wd[i][0]=i;wd[i][1]='\0';}printf(请输入任意字符串，以回车键结束：\n\n);while(scanf(%s,text)!=EOF)//读入字符串{w[0]='\0';num=0;M=256;for(i=0;;i++){if(text[i]=='\0')//字符串结尾处的处理{if(out(w)==-1)add(w);N[num++]=out(w);break;}c[0]=text[i];c[1]='\0';//得到Cstrcpy(w1,w);strcat(w1,c);//W1=W+Ck=out(w1);if(k!=-1)//如果W1在字典中，W=W+C{strcpy(w,w1);continue;}else//如果W1不在字典中，W的编码加入编码码字中，将W+C加入字典中，W=C{N[num++]=out(w);add(w1);strcpy(w,c);}}printf(编码后的LZW码字:\n);for(i=0;inum;i++)//输出编码后的LZW码字printf(%d,N[i]);printf(\n\n);printf(加入字典中的短语:\n);for(i=256;iM;i++)//输出新加入字典中的短语printf(%s\n,wd[i]);//system(CLS);printf(请继续输入，停止输入请按Esc键\n\n);}return0;}五、实验结果