实验四LZW编码方案程序设计模板.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
实验四LZW编码方案程序设计
1、 实验目的
( 1) 进一步熟悉通用编码算法;
( 2) 掌握C语言程序设计和调试过程中数值的进制转换、 数值与字符串之间的转换等技术。
2、 实验要求
( 1) 输入: 本程序将从标准输入中读入待压缩的数据流;
( 2) 输出: 将压缩结果输出到标准输出上去。
3、 LZW算法描述

1: procedureLZW
2: 字典初始化: 将压缩文件中所有使用到的单字节字符放入字典中, 为了压缩任何类型的文件, 能够将字典的前256个位置( 0x000到0x0FF) 一次分配给0x00到0xFF的256个单字节字符。
3: 动态数据初始化: 初始化新单词存放位置指针P。将它指向字典的第一个空位置。例如P=256( 即0x100) , 读入被压缩文件的第一个字符cha, 作为待处理单词W。单词的前缀Q为空, 即Q=4095, 尾字符就是cha, 序号( 码字) 就是cha的序号。
4: 如果文件再没有字符了, 输出当前单词的序号。编码结束。如果文件中还有字符, 把当前单词W作为前缀, 再从被压缩文件中读入一个字符CH, 把CH作为尾字符, 得到一个单词W。
5: 如果字典中已有W, 则将W看做当前单词W, 返回第三步。如果字典中没有W( 发现一个新单词) , 先将原单词W的序号输出, 再加新单词W, 增加到字典中, 然后把刚刚读入的字符CH作为当前单词W, 返回第三步。
6:endprocedure
*******************************************************************************
实验流程图:

*******************************************************************************
4、 参考代码
/********************************************************************
*Author:
*Date:
*Copyright:
*Purpose: UseLZWalgorithmtocodethesourcesymbols***********************************************************
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
structword{
unsignedintn;
unsignedcharc;
}w,wd[4096];//Dictionary
unsignedintp,n;
unsignedcharh,m,l,f;
/*Outputthecode*/
voidout(intn)
{
if(f==0){
h=n/16;
m=(n<<4)&0xf0;
f=1;
}
else{
m+=n/256;
l=n&0xff;
fputc(h,stdout);
fputc(m,stdout);
fputc(l,stdout);
h=m=l=f=0;
}
}
/*Maincopressprogram*/
voidlzw()
{
intc,i;
unsignedcharch;
fprintf(stderr,"\n\nbegincompress,pleasewait!\n");
for(i=0;i<256;i++){//Initializefirst256word
wd[i].n=4095;//indictionary
wd[i].c=i;
}
p=256;
w.n=4095;
w.c=n=fgetc(stdin);
h=m=l=f=0
for(;;){
c=fgect(stdin);
if(c==-1){
out(n);
if(f)
out(4095);
fprintf(stderr,"\n\ncompressionisover!\n");
return;
}
ch=c;
for(i=n+1;i<p;i++){
if(wd[i].n!=n)
continue;
if(wd[i].c==ch)
break;
}
if(i!=p){
w.n=n;
w.c=ch;
n=i;
}
else{
out(n);
if(p<4095){
wd[p].n=n;
wd[p].c;
p++;
}
w.n=4095;
n=w.c=ch;
}
}
}
voidmain(void)
{
lzw();
}
5改动后代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
usingnamespacestd;
charwd[4096][20];//设定一个字典wd
charstr[20],w[20],w1[20],c[20];
chartext[1000];//输入的文本text
intN[1000];
intnum;
intM;
intout(chars[])//得到一个短语是否在字典中, 在时输出它的码字
{
inti;
for(i=0;i<M;i++)
if(!strcmp(s,wd[i]))returni;//短语在字典中则返回i
return-1;
}
voidadd(chars[])//将一个短语加入字典中
{
strcpy(wd[M++],s);将得到的短语加入词典
}
intmain()
{
inti,j,k;
for(i=0;i<256;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';//得到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
{
N[num++]=out(w);
add(w1);
strcpy(w,c);
}
}
printf("编码后的LZW码字:\n");
for(i=0;i<num;i++)//输出编码后的LZW码字
printf("%d",N[i]);
printf("\n\n");
printf("加入字典中的短语:\n");
for(i=256;i<M;i++)//输出新加入字典中的短语
printf("%s\n",wd[i]);
//system("CLS");
printf("请继续输入, 停止输入请按Esc键\n\n");
}
return0;
}
实验结果

输入数据: ababdabdcef
查找asic码表得到, a—97b—98c—99d—100e—101f—102
增加的新词有ab—256ba—257abd—258da—259abdc—260ce—261ef—262
实验总结:
经过lzw的实验了解lzw算法的具体工作原理, 了解的lzw编码的具体编码方式和与其它编码的不同, 利用字典的方式对每一个字符和短语进行编码, 在对于较长字符, 较多重复字符串的文本中有较高的编码效率