.net C#单链表实现

xriantvc  于 2023-05-23  发布在  .NET
关注(0)|答案(4)|浏览(264)

在试图理解如何在C#中实现单列表时,我遇到了下面的链接:
Creating a very simple linked list
然而,由于我是C#的新手,我被上面讨论的第一部分中列出的语法弄糊涂了。声明了一个名为Node的类,并且该类中有另一个声明为“public Node next”的语句。这个语句叫做构造函数吗?请帮帮我

public class Node {
    public Node next;
    public Object data;
 }
oxiaedzo

oxiaedzo1#

在一个简单的单链表实现中,Node类型包含对列表中下一项的引用,这就是您发布的Node类型中的next字段所做的。此引用用于允许列表的迭代。
封闭的LinkedList类(或者你想叫它什么)将包含对列表中第一项的单个Node引用。从第一个节点开始,您可以通过获取next字段来遍历列表。当next为null时,您已经到达列表的末尾。
以下面的代码为例:

public class LinkedList
{
    public class Node
    {
        // link to next Node in list
        public Node next = null;
        // value of this Node
        public object data;
    }

    private Node root = null;

    public Node First { get { return root; } }

    public Node Last 
    {
        get
        {
            Node curr = root;
            if (curr == null)
                return null;
            while (curr.next != null)
                curr = curr.next;
            return curr;
        }
    }
}

First属性只返回根节点,即列表中的第一个节点。Last属性从根节点开始,遍历列表,直到找到next属性为null的节点,表示列表结束。
这使得向列表中添加项目变得简单:

public void Append(object value)
{
    Node n = new Node { data = value };
    if (root == null)
        root = n;
    else
        Last.next = n;
}

要删除一个节点,你必须找到列表中它前面的节点,然后更新next链接,从 that 节点指向要删除的节点后面的节点:

public void Delete(Node n)
{
    if (root == node) 
    {
        root = n.next;
        n.next = null;
    }
    else
    {
        Node curr = root;
        while (curr.next != null)
        {
            if (curr.next == n)
            {
                curr.next = n.next;
                n.next = null;
                break;
            }
            curr = curr.next;
        }
    }
}

还有一些其他的操作可以执行,比如在列表中的位置插入值,交换节点等。在节点之后插入是快速的,在节点之前插入是缓慢的,因为您必须定位先前的节点。如果你真的想要快速的'insert-before',你需要使用一个双向链表,其中Node类型同时具有nextprevious链接。
为了在评论中扩展您的问题...
在C#中,所有类型都分为两种基本分类:值类型和引用类型。这些名称反映了它们在代码块之间传递的方式:值类型通过值传递(值被复制到新变量),而引用类型通过引用传递(引用/指针被复制到新变量)。不同之处在于,对值类型参数的更改不会影响调用方的值副本,而对引用类型参数的更改将反映在调用方的引用副本中。
为变量赋值和引用也是如此。在下文中,当b改变时,a的值不改变:

int a = 0;
int b = a;
b = 1;

这是相当直观的。在C#中,struct也是一种值类型:

public struct test
{
    public string value;
}

static void Main()
{
    test a;
    a.value = "a";
    test b = a;
    b.value = "b";

    Console.WriteLine("{0} {1}", a.value, b.value);
}

上面的代码将给予a b的输出,因为当你将a赋值给b时,就产生了一个副本。但是如果我们改变一个类的结构:

public class test
{
    public string value;
}

static void Main()
{
    test a = new test(); // Note the 'new' keyword to create a reference type instance
    a.value = "a";
    test b = a;
    b.value = "b";
    Console.WriteLine("{0} {1}", a.value, b.value);
}

因为变量b引用的对象与变量a引用的对象 * 相同 *,所以这里的输出将是b b。这两个变量引用同一个 object
如果你来自C/C或其他类似的语言,你可以把引用类型变量看作指针。这并不完全相同,C#实际上也有指针(它们对正常的托管代码是隐藏的),但它足够接近。除非你将它指向该类型的一个 * 示例 *,否则它是不能完全使用的。就像C/C中的char*一样,除非你把它指向某个地方,否则它并不是特别有用。
Joseph Albahari(写了一篇关于值和引用类型的文章:这本书很值得一读,他写的很多东西也是如此。我也强烈推荐你考虑买一本他的C# in a Nutshell的书。

2jcobegt

2jcobegt2#

有一个简单的方法来创建单链表。让我们试着理解这个概念。如果概念清晰,那么你就可以理解逻辑本身。单链表有两个部分的节点。其中一个包含数据值,另一个包含下一个节点的引用地址。看看下面的代码:
首先我们需要创建链表节点类

/// <summary>
/// Creating the Real World Entity of Linked List Node
/// </summary>
public class LinkedListNode
{
    public Object Value { get; set; }

    public LinkedListNode Next { get; set; }

}

这里类有Value和保持器来保存序列中下一个Node的引用。接下来我们需要创建链表本身

/// <summary>
/// Creating the Linked List Class Itself. It defines the First and Last Nodes of Linked List
/// </summary>
public class LinkedList
{
    public LinkedListNode First { get; set; }
    public LinkedListNode Last { get; set; }

    /// <summary>
    /// Method to Add items into the Linked List
    /// </summary>
    /// <param name="_value"></param>
    public void AddToLinkedList(object _value)
    {
        LinkedListNode node = new LinkedListNode();
        node.Value = _value;

        if (First == null)
        {
            First = node;
            Last = node;
        }
        else
        {
            Last.Next = node;
            Last = node;
        }
    }

    /// <summary>
    /// Method to display all items. We can further implement the IEnumerable interface
    /// to Yield IEnumerator Interface.
    /// </summary>
    public void DisplayAllItems()
    {
        LinkedListNode current = First;
        while (current != null)
        {
            Console.WriteLine(current.Value);
            current = current.Next;
        }
    }
}

在这里,关键是将项目添加到链表中。首先,我们需要检查链表是否存在。我们检查链表中的第一个或头节点。如果为空,则将该节点指定为第一个入口点。在这个阶段,最后一项本身就是第一项。
现在这是我们如何添加和显示项目

class Program
{
    static void Main(string[] args)
    {
        LinkedList singlyLinkedList = new LinkedList();
        singlyLinkedList.AddToLinkedList(4);
        singlyLinkedList.AddToLinkedList(5);
        singlyLinkedList.AddToLinkedList(7);
        singlyLinkedList.AddToLinkedList(2);
        singlyLinkedList.AddToLinkedList(1);
        singlyLinkedList.AddToLinkedList(10);

        singlyLinkedList.DisplayAllItems();
        Console.ReadLine();
    }
}

让我知道它是否有意义:)

svujldwt

svujldwt4#

记住,链表不仅保存数据,还保存指向列表中下一个节点的引用/指针。因为类在C#中是引用类型,所以你不会看到任何特殊的语法,否则你会在C或C++中看到。

struct Node
{
    int Number;
    struct Node* next; /* this points to the next node in the linked list */
};

相关问题