博客

此为本人多媒体课程上机题目中的一个程序，供大家参考！


一． 编程思路

LZ77算法的主要思路是构造一个三元组（off, len, c），其中off表示窗口中匹配的字符串相对于窗口右边界的位移，len表示可以进行匹配的字符串的长度，c表示需要下一个输出的字符。对一串已经储存在文本中的字符串（origin.txt）进行LZ77编码，将三元组输出到一个编码文件中（code.txt），最后只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c 输出（如果 off和 len 都为 0 则只输出后继字符c即可还原出原始数据，同样的，将解码后的字符串也输出到一个文本中。（decode.txt）

二. 源代码

#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>

#define window_length 100
#define max_length 10000

typedef struct{
    int off,len;
    char c;
}CODE; //lz77编码的结构体

CODE code_file[max_length]={0,0,0};//数据结构的初始化
char origin_array[max_length]={0};//待编码的字符数组
char decode_array[max_length]={0};//解码后的字符数组

int origin_file_in(char *array,int *pcount)  //从文件读入字符数组
{
    char c=0;
    FILE *fp;
    if((fp=fopen("origin.txt","r"))==NULL)
        return 0;
    while((c=fscanf(fp,"%c",array+*pcount))!=EOF)
    {
        ++(*pcount);
    }
    fclose(fp);
    return 1;
}

int code_file_out(CODE *code_file,int count)  //将字符数组的编码输出到文件
{
    int i=0;
    FILE *fp;
    if((fp=fopen("code.txt","w"))==NULL)
        return 0;
    while(i<count)
    {
        fprintf(fp,"%d %d %c\n",code_file[i].off,code_file[i].len,code_file[i].c);
        ++i;
    }
    fclose(fp);
    return 1;
}

int decode_file_out(char *array,int count)//将解码输出到文件中
{
    int i=0;
    FILE *fp;
    if((fp=fopen("decode.txt","w"))==NULL)
        return 0;
    while(i<count)
    {
        fprintf(fp,"%c",array[i]);
        ++i;
    }
    fclose(fp);
    return 1;
}

int match(char *s,int sn,char *t,int tn)//字符串的匹配
{
    int i=0,j=0,k;
    while(i<sn&&j<tn)
    {
        if(s[i]==t[j])
        {
            i++;
            j++;
        }
        else
        {
            i=i-j+1;
            j=0;
        }
    }
    if(j>=tn)
        k=i-tn;
    else k=-1;//k是可以匹配的字符串的位置
    return k;
}

void code(char *array,int count1,CODE *code_file,int *pcount2)
{
    int window_start=0,window_end=0;
    *pcount2=0;
    if(count1>0)
    {
        code_file[0].off=0;
        code_file[0].len=0;
        code_file[0].c=array[0];
        (*pcount2)++;//对字符串第一个字符进行编码输出
    }
    int i=1,j=1,k1=0,k2=0;
    for(;i<count1;i++)
    {
        if(i<window_length)
            window_end=i;//更新窗口右边界
        else window_end=window_length;
        for(j=1,k1=0,k2=0;;j++)
        {
            k1=k2;
            k2=match(array+i-window_end,window_end,array+i,j);//匹配结果返回
            if(k2<0)//没有匹配的
            {
                code_file[*pcount2].off=window_end-k1;//存在可以编码的情况的话，off值为当前字符相对于右窗口的位移
                if((code_file[*pcount2].len=j-1)==0)//在出现新字符的情况下，将off置为0
                    code_file[*pcount2].off=0;
                code_file[*pcount2].c=array[i+j-1];//输出需要输出的下一位不能匹配的字符
                (*pcount2)++;//指针移动
                i=i+j-1;//更新i
                break;
            }
        }
    }
}

void decode(CODE *code_file,int count2,char *array,int *pcount3)
{
    *pcount3=0;
    int i=0,j=0;
    for(;i<count2;++i)
    {
        if(code_file[i].len==0)
        {
            array[*pcount3]=code_file[i].c;
            ++(*pcount3);
        }
        else
        {
            for(j=0;j<code_file[i].len;++j)
            {
                array[*pcount3+j]=array[*pcount3-code_file[i].off+j];
            }
            array[*pcount3+j]=code_file[i].c;
            *pcount3=*pcount3+code_file[i].len+1;
        }
    }
}

int main()
{
    int count1=0,count2=0,count3=0;
    origin_file_in(origin_array,&count1);
    code(origin_array,count1,code_file,&count2);
    code_file_out(code_file,count2);
    decode(code_file,count2,decode_array,&count3);
    decode_file_out(decode_array,count3);

    printf("finish!\n");
    return 0;
}