编程实现lzw编码解码.docx
《编程实现lzw编码解码.docx》由会员分享，可在线阅读，更多相关《编程实现lzw编码解码.docx（10页珍藏版）》请在冰点文库上搜索。
编程实现lzw编码解码
江苏大学计算机与通信工程学院
实
验
报
告
实验：
编程实现lzw编码解码
学号：
姓名：
指导老师：
日期：
1．任务说明
对由{a,b,c,d}构成的字符进行LZW编码，然后译码。
2．问题分析、实现原理、流程图
由于时间有不多，不想用4叉树。
就用简单直接的单链表实现字典。
虽然效率极低，但长度小于100，所以没有太大问题。
1.字典初始化：
建立4个节点a,b,c,d;
2.动态数据初始化:
当发现字典中没有的，就把它加入字典。
3.结束判断
如果文件再无输入字符了，输出当前单词W的序号（即S的序号），编码结束。
3．实现源码
#include
#include
#defineMAXLEN10000
typedefstructNode{/*定义单链表结点类型*/
char*pstr;
unsignednum;
Node*next;
}Node;
intappendNode（Node*head,char*pstr）;
intgetNum（Node*head,char*pstr）;
intfreelist（Node*head）;
char*search（Node*head,intnum）;
Node*getLastNode（Node*head）;
intmain（）
{
charbuffer[MAXLEN];
FILE*fpin,*fpout;
inti=0,ch;
Node*header;
intslen,encodelen=0;
//readdata
fopen_s（&fpin,"in4.txt","r"）;
fopen_s（&fpout,"out4.txt","w+"）;
if（fpin==NULL）
{
printf（"openfileerror\n"）;
return0;
}
ch=fgetc（fpin）;
for（slen=0;（slen{
buffer[slen]=（char）ch;
ch=fgetc（fpin）;
}
buffer[slen]='\0';
printf（"%s\n",buffer）;
fclose（fpin）;
//编码
intencode[MAXLEN]={0};
//initlist
header=newNode;
header->next=NULL;
header->num=0;
header->pstr=NULL;
appendNode（header,"a"）;
appendNode（header,"b"）;
appendNode（header,"c"）;
appendNode（header,"d"）;
charx[2]={'\0'},I[MAXLEN]={'\0'};
intcurrentNum,temp;
I[0]=buffer[0];
while
（1）
{
staticinti=0;
temp=getNum（header,I）;
if（temp==0）
{
encode[encodelen++]=currentNum;
intret=appendNode（header,I）;
printf（"%d%s\n",ret,I）;
memset（I,'\0',4*sizeof（char））;
I[0]=x[0];
}
else
{
currentNum=temp;
x[0]=buffer[++i];
if（x[0]<'a'||x[0]>'d'）//到达末尾
{
printf（"%7d\n",currentNum）;
encode[encodelen++]=currentNum;
break;
}
strcat（I,x）;
}
}
freelist（header）;
printf_s（"encode:
\n"）;
fprintf_s（fpout,"\n编码为：
\n"）;
for（inti=0;;i++）//输出编码
{
if（encode[i]==0）break;
printf_s（"%d",encode[i]）;
fprintf_s（fpout,"%d",encode[i]）;
}
printf（"\n"）;
fprintf_s（fpout,"\n原文：
%s\n",buffer）;
//译码
fprintf_s（fpout,"\n还原为：
"）;
header=newNode;
header->next=NULL;
header->num=0;
header->pstr=NULL;
appendNode（header,"a"）;
appendNode（header,"b"）;
appendNode（header,"c"）;
appendNode（header,"d"）;
memset（I,'\0',16）;
char*pword;
Node*tempNode;
for（inti=0;i{
if（0==encode[i]）break;
pword=search（header,encode[i]）;//查字典
if（i>0）
{
//setx
x[0]=pword[0];
tempNode=getLastNode（header）;
strcat（tempNode->pstr,x）;
}
printf（pword）;
fprintf_s（fpout,"%s",pword）;
appendNode（header,pword）;//存字典
}
printf_s（"\n原始码长：
%d,编码长：
%d\n压缩率为:
%f",slen,encodelen,encodelen/（float）slen）;
fprintf_s（fpout,"\n原始码长：
%d,编码长：
%d\n%d/%d=%f",slen,encodelen,encodelen,slen,encodelen/（float）slen）;
fclose（fpout）;
getchar（）;
return0;
}
intappendNode（Node*head,char*pstr）
{
inti=1;
Node*p=head,*temp;
while（p->next）
{
i++;
p=p->next;
}
temp=newNode;
temp->next=NULL;
temp->num=i;
temp->pstr=newchar[strlen（pstr）+1];
strcpy_s（temp->pstr,strlen（pstr）+1,pstr）;
p->next=temp;
returni;
}
intgetNum（Node*head,char*pstr）
{
inti=0,flag=0;
Node*p=head;
while（p->next）
{
p=p->next;
i++;
if（0==strcmp（p->pstr,pstr））
{
flag=1;
break;
}
}
if（flag==1）
returni;//nothisnode
return0;
}
intfreelist（Node*head）
{
Node*temp;
while（head）
{
temp=head;
head=head->next;
delete[]temp->pstr;
deletetemp;
}
return0;
}
char*search（Node*header,intnum）
{
Node*p=header;
inti=0;
while（（i!
=num）&&（p））
{
p=p->next;
i++;
}
returnp->pstr;
}
Node*getLastNode（Node*head）
{
Node*p=head;
while（p->next）
{
p=p->next;
}
returnp;
}
4．运行结果：
输入、输出及结果分析
待编码（int4.txt）：
abdcacadcadbdadcdadbcbcabdacbdcadbcabdcabdcaddabcbadbacdcadbacdbacdcadacdacdacdddcadbadbcbdacbdadadadcbdabcdacadcdacddbcdbcadbcdbcdbacbdacbdacbddabdcbdabcdabcdabcdbcdabcdabcdacbdacbdadacdcdbacdbcabdacbdadcdacdabdaabdcacdbcadacdacdcdababddabdaddcdadcabadcbddcdbadcdadbaccadacabcadb
输出（out4.txt）：
编码为：
124318714612341223195172011138627251719218925331637253541164361824914175047192315234453212660371447243171453516706072746449353835216349717114228381042731226612921551569233971399027102
原文：
abdcacadcadbdadcdadbcbcabdacbdcadbcabdcabdcaddabcbadbacdcadbacdbacdcadacdacdacdddcadbadbcbdacbdadadadcbdabcdacadcdacddbcdbcadbcdbcdbacbdacbdacbddabdcbdabcdabcdabcdbcdabcdabcdacbdacbdadacdcdbacdbcabdacbdadcdacdabdaabdcacdbcadacdacdcdababddabdaddcdadcabadcbddcdbadcdadbaccadacabcadb
还原为：
abdcacadcadbdadcdadbcbcabdacbdcadbcabdcabdcaddabcbadbacdcadbacdbacdcadacdacdacdddcadbadbcbdacbdadadadcbdabcdacadcdacddbcdbcadbcdbcdbacbdacbdacbddabdcbdabcdabcdabcdbcdabcdabcdacbdacbdadacdcdbacdbcabdacbdadcdacdabdaabdcacdbcadacdacdcdababddabdaddcdadcabadcbddcdbadcdadbaccadacabcadb
原始码长：
280,编码长：
106
106/280=0.378571
5．设计体会
虽然没用4叉树，后来思考了下，用4叉树可能更简单，但通过实验对lzw编码方法有了基本了解。
lzw设计的很巧妙。
升级会员 