Algorithm 版 (精华区)

发信人: lofe ()感激生活(), 信区: Algorithm
标  题: 原代码_1
发信站: 哈工大紫丁香 (Sun Sep  3 08:29:18 2000), 转信

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dir.h>
#include <dos.h>
#include <direct.h>
#include <bios.h>
#include <conio.h>
#include <time.h>
#define EXIT_OK 0
#define EXIT_FAILED -1
//////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////////////////
FILE  *infile, *outfile;
unsigned long int  textsize = 0, codesize = 0, printcount = 0;

void Error(char *message)
{
        printf("\n%s\n", message);
        exit(-1);
}

/* LZSS Parameters */

#define N               4096    /* Size of string buffer */
#define F               60      //* Size of look-ahead buffer 60
#define THRESHOLD       2
#define NIL             N       /* End of tree's node  */

unsigned char
                text_buf[N + F -1];//-1
int             match_position, match_length,
                lson[N + 1], rson[N + 257], dad[N + 1];

void InitTree(void)  /* Initializing tree */
{
        int  i;

        for (i = N + 1; i <= N + 256; i++)
                rson[i] = NIL;                  /* root */
        for (i = 0; i < N; i++)
                dad[i] = NIL;                   /* node */
}

void InsertNode(int r)  /* Inserting node to the tree */
{
        int  i, p, cmp;
        unsigned char  *key;
        unsigned c;

        cmp = 1;
        key = &text_buf[r];
        p = N + 1 + key[0];
        rson[r] = lson[r] = NIL;
        match_length = 0;
        for ( ; ; ) {
                if (cmp >= 0) {
                        if (rson[p] != NIL)
                                p = rson[p];
                        else {
                                rson[p] = r;
                                dad[r] = p;
                                return;
                        }
                } else {
                        if (lson[p] != NIL)
                                p = lson[p];
                        else {
                                lson[p] = r;
                                dad[r] = p;
                                return;
                        }
                }
                for (i = 1; i < F; i++)
                        if ((cmp = key[i] - text_buf[p + i]) != 0)
                                break;
                if (i > THRESHOLD) {
                        if (i > match_length) {
                                match_position = ((r - p) & (N - 1)) - 1;
                                if ((match_length = i) >= F)
                                        break;
                        }
                        if (i == match_length) {
                                if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
                                        match_position = c;
                                }
                        }
                }
        }
        dad[r] = dad[p];
        lson[r] = lson[p];
        rson[r] = rson[p];
        dad[lson[p]] = r;
        dad[rson[p]] = r;
        if (rson[dad[p]] == p)
                rson[dad[p]] = r;
        else
                lson[dad[p]] = r;
        dad[p] = NIL;  /* remove p */
}

--
    _______     __        ____ ________ __     __    ____     _   __
   /  _____)   / /       / _ ]  \ __ /  [ ^\_/^ ]   / _ ]    / \  /
  (  (_____   / (____   / _  ]   \  /   [  ] [  ]  / _  ]   /\  \/
   \_______) /_______) /_/ (_)   [__]   [  ] [  ] /_/ (_)  /  \_/
  ________________________________________________________/
※ 修改:．haojs 于 Sep  3 08:26:54 修改本文．[FROM: bbs.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: bbs.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: haojs.bbs@bbs.whnet.]