Algorithm 版 (精华区)

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

/* reconstruct freq tree */

void reconst()
{
        int i, j, k;
        unsigned f, l;

        /* halven cumulative freq for leaf nodes */
        j = 0;
        for (i = 0; i < T; i++) {
                if (son[i] >= T) {
                        freq[j] = (freq[i] + 1) / 2;
                        son[j] = son[i];
                        j++;
                }
        }
        /* make a tree : first, connect children nodes */
        for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
                k = i + 1;
                f = freq[j] = freq[i] + freq[k];
                for (k = j - 1; f < freq[k]; k--);
                k++;
                l = (j - k) * 2;
                
                /* movmem() is Turbo-C dependent
                   rewritten to memmove() by Kenji */
                
                /* movmem(&freq[k], &freq[k + 1], l); */
                (void)memmove(&freq[k + 1], &freq[k], l);
                freq[k] = f;
                /* movmem(&son[k], &son[k + 1], l); */
                (void)memmove(&son[k + 1], &son[k], l);
                son[k] = i;
        }
        /* connect parent nodes */
        for (i = 0; i < T; i++) {
                if ((k = son[i]) >= T) {
                        prnt[k] = i;
                } else {
                        prnt[k] = prnt[k + 1] = i;
                }
        }
}


/* update freq tree */

void update(int c)
{
        int i, j, k, l;

        if (freq[R] == MAX_FREQ) {
                reconst();
        }
        c = prnt[c + T];
        do {
                k = ++freq[c];

                /* swap nodes to keep the tree freq-ordered */
                if (k > freq[l = c + 1]) {
                        while (k > freq[++l]);
                        l--;
                        freq[c] = freq[l];
                        freq[l] = k;

                        i = son[c];
                        prnt[i] = l;
                        if (i < T) prnt[i + 1] = l;

                        j = son[l];
                        son[l] = i;

                        prnt[j] = c;
                        if (j < T) prnt[j + 1] = c;
                        son[c] = j;

                        c = l;
                }
        } while ((c = prnt[c]) != 0);   /* do it until reaching the root */
}

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

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