c# - 使用链表创建基本的浏览器历史记录

Question

所以我正在做一个任务，我们用c#制作一个基本的浏览器历史。要求是我们需要使用单链表来执行此操作。我遇到的问题是，当我想在历史中倒退并打印它时，它需要从列表的开头而不是前面。（例如，如果我有一个包含 1、2、3、4 的列表并返回，那么 2、3、4 和 1 将被移至未来类别）。

public class UnderflowException : Exception
{
    public UnderflowException(string s) : base(s) { }
}

public class OverflowException : Exception
{
    public OverflowException(string s) : base(s) { }
}

class History
{
    protected class IntListNode
    {
        public string Data;
        public IntListNode Next;

        public IntListNode(string data)
        {
            Data = data;
        }

        public IntListNode(string data, IntListNode next)
        {
            Next = next;
        }
    }

    protected IntListNode first;

    private int i;

    public void PrintAll()
    {
        int j = 0;
        IntListNode node = first;
        Console.WriteLine("Privious things that you have viewed.");

        while (node != null)
        {
            if (counter <= j)
            {
                break;
            }

            Console.WriteLine(node.Data);
            node = node.Next;
            j++;
        }

        Console.WriteLine("Things to go forward to.");

        while (node != null)
        {
            Console.WriteLine(node.Data);
            node = node.Next;
        }
    }

    private int counter;

    public void MoveBackwards()
    {
        if (counter >= 0)
        {
            counter = counter - 1;
        }
        else
        {
            throw new UnderflowException("underflow");
        }
    }

    public void MoveForwards()
    {
        if (counter > i)
        {
            throw new OverflowException("overflow");
        }        
        else
        {
            counter++;
        }
    }

    public void VisitPage(string desc)
    {
        IntListNode n = new IntListNode(desc);
        n.Next = this.first;
        this.first = n;
        counter++;
        i = counter;
    }
}

当我已经在列表中有项目并要求它向后移动一个时，它需要第一个节点而不是列表中的最后一个节点。在前面的示例中，希望它从 1、2、3、4 开始使用 go backs 命令并让历史显示 1、2、3 和前向显示 4。

标签： c#

Answer 1

这是一个基于您的代码的示例，但略有更改。

counter而不是跟踪i我们的状态，我只跟踪两个节点：（head第一个）和current（用户现在所在的那个）。我还在current.Next节点而不是节点处插入新页面，head因为这就是我习惯使用链表的方式。

通过这样做，它使导航变得容易。要前进，我们只需设置current = current.Next，要后退，我们从 开始head并向前移动，直到找到Next指向的节点current。然后我们设置current到那个节点。

要打印历史记录，我们只需从 开始head并继续前进Next。当我们看到 时Next == current，我们知道我们在当前页面（我用不同的颜色打印它）。然后我们可以继续打印Next节点以显示未来的节点，直到Nextis null。

请注意，这实际上是导航历史记录，而不是浏览历史记录的完整记录，因为如果您返回然后访问新页面，则会丢失您返回的页面。

希望这可以帮助：

class History
{
    private class Node
    {
        public string Data { get; set; }
        public Node Next { get; set; }
        public Node(string data) { Data = data; }
    }

    private Node head;
    private Node current;

    public void VisitNewPage(string desc)
    {
        // Create a node for this page
        var node = new Node(desc);

        // If it's our first page, set the head
        if (head == null) head = node;

        // Update our current.Next pointer
        if (current != null) current.Next = node; 

        // Set this page as our current page
        current = node;
    }

    public void MoveBackwards()
    {
        // Can't move backwards from the head
        if (current == head) return;

        var previous = head;

        // Find the node that's behind (pointing to) the current node
        while (previous.Next != current)
        {
            previous = previous.Next;
        }

        // Make that node our new current
        current = previous;
    }

    public void MoveForwards()
    {
        // Just move to the next node
        if (current.Next != null) current = current.Next;
    }

    public void PrintCurrent()
    {
        Console.WriteLine($"You are on page: {current.Data}");
    }

    public void PrintHistory()
    {
        Console.WriteLine("\nBrowsing History");

        if (head == null)
        {
            Console.WriteLine("[Empty]");
            return;
        }

        var node = head;

        // Print previous pages
        while (node != current)
        {
            Console.WriteLine($" - {node.Data}");
            node = node.Next;
        }

        // Print current page in green
        Console.ForegroundColor = ConsoleColor.Green;
        Console.WriteLine($" - {node.Data}");
        Console.ResetColor();
        node = node.Next;

        // Print next pages
        while (node != null)
        {
            Console.WriteLine($" - {node.Data}");
            node = node.Next;
        }

        Console.WriteLine();
    }
}

示例使用

这是一个简单的无限循环，可让您访问新站点、前进、后退并打印历史记录：

private static void Main()
{
    var history = new History();

    while (true)
    {
        Console.Write("Enter new page to visit, [b]ack, [f]orward, or [p]rint: ");
        var input = Console.ReadLine();
        if (string.IsNullOrWhiteSpace(input)) continue;

        switch (input.ToLower())
        {
            case "b":
            case "back":
                history.MoveBackwards();
                break;
            case "f":
            case "forward":
                history.MoveForwards();
                break;
            case "p":
            case "print":
                history.PrintHistory();
                break;
            default:
                history.VisitNewPage(input);
                break;
        }
    }
}

输出