本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 前移编码

题目

1.3.40 前移编码。从标准输入读取一串字符，使用链表保存这些字符并删除重复字符。当你读取了一个从未见过的字符时，将它插入表头。当你读取了一个重复的字符时，将它从链表中删去并再次插入表头。将你的程序命名为 MoveToFront：它实现了著名的前移编码策略，这种策略假设最近访问过的元素很可能会再次访问，因此可以用于缓存、数据压缩等许多场景。

1.3.40 Move-to-front. Read in a sequence of characters from standard input and maintain the characters in a linked list with no duplicates. When you read in a previ- ously unseen character, insert it at the front of the list. When you read in a duplicate character, delete it from the list and reinsert it at the beginning. Name your program MoveToFront: it implements the well-known move-to-front strategy, which is useful for caching, data compression, and many other applications where items that have been recently accessed are more likely to be reaccessed.

分析

本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅

答案

private static class Node {
    char item;
    Node next;
}

public static class MoveToFront {

    private Node first;
    private int N=0;

    public void Judge(char c)
    {
        Node current = first;
        for(int i=0;i < N;i++)
        {
            if(current.item == c)
            {
                current = current.next;
                return ;
            }
            current=current.next;
        }
        this.push(c);
    }

    public void push(char item)
    {
        Node oldfirst= first;
        first = new Node();
        first.item=item;
        first.next=oldfirst;
        N++;
    }

    public void print()
    {
        for(Node current=first;current!=null;current=current.next) {
            System.out.print(current.item+" ");
        }
    }

}

public static void main(String[] args){
    MoveToFront mtf = new MoveToFront();
    while(!StdIn.isEmpty())
    {
        mtf.Judge(StdIn.readChar());
    }
    mtf.print();

}

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。

壁纸宝贝