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

1、实验四 LZW编码方案程序设计一、实验目的 （1）进一步熟悉通用编码算法； （2）掌握C语言程序设计和调试过程中数值进制转换、数值与字符串之间的转换等技术。二、实验要求 （1）输入：本程序将从标准输入中读入待压缩的数据流； （2）输出：将压缩结果输出到标准输出上去。三、LZW算法描述 1：procedure LZW 2：字典初始化：将压缩文件中所有使用到的单字节字符放入字典中，为了压缩任何类型的文件，可以将字典的前256个位置（0x000到0x0FF）一次分配给0x00到0xFF的256个单字节字符。 3：动态数据初始化：初始化新单词存放位置指针P。将它指向字典的第一个空位置。例如P=256（

2、即0x100），读入被压缩文件的第一个字符cha，作为待处理单词W。单词的前缀Q为空，即Q=4095，尾字符就是cha，序号（码字）就是cha的序号。 4：如果文件再没有字符了，输出当前单词的序号。编码结束。如果文件中还有字符，把当前单词W作为前缀，再从被压缩文件中读入一个字符CH，把CH作为尾字符，得到一个单词W。 5：如果字典中已有W，则将W看做当前单词W，返回第三步。如果字典中没有W（发现一个新单词），先将原单词W的序号输出，再加新单词W，增加到字典中，然后把刚刚读入的字符CH作为当前单词W，返回第三步。 6:end procedure-四、实验代码/* 程序说明： 对输入的任意字符串，

3、实现字典编码 */#include#include#include #include using namespace std; char wd409620; char str20,w20,w120,c20; char text1000; int N1000; int num; int M; int out( char s) /得到一个短语是否在字典中，在时输出它的码字 int i; for(i=0;iM;i+) if(!strcmp(s,wdi) return i; return -1; void add( char s ) /将一个短语加入字典中 strcpy(wdM+,s); int ma

4、in() int i,j,k; for(i=0;i256;i+) /将所有单个字符加入字典中，初始化字典 wdi0=i; wdi1=0; printf(请输入任意字符串，以回车键结束：nn); while( scanf(%s,text)!=EOF) /读入字符串 w0=0; num=0; M=256; for(i=0;i+) if(texti=0) /字符串结尾处的处理 if(out(w)=-1) add(w); Nnum+=out(w); break; c0=texti; c1=0; /得到C strcpy(w1,w); strcat(w1,c); /W1=W+C k=out(w1); if(k!=-1) /如果W1在字典中，W=W+C strcpy(w,w1); continue; else /如果W1不在字典中，W的编码加入编码码字中，将W+C加入字典中，W=C Nnum+=out(w); add(w1); strcpy(w,c); printf(编码后的LZW码字:n); for(i=0;inum;i+) /输出编码后的LZW码字 printf(%d ,Ni); printf(nn); printf(加入字典中的短语:n); for(i=256;iM;i+) /输出新加入字典中的短语