在 C# 中使用结构实现链表时获取垃圾值（不安全构造）

Question

我试图验证我的一个朋友报告的行为，所以我使用 struct 在 C# 中实现了单向链表。由于我必须使用指针，所以我使用了 C# 提供的不安全结构。我还在项目属性的构建选项卡中将属性设置为 Allow unsafe code 以使代码可编译。

这是我的完整代码实现：

public unsafe struct NodeList
{
    public Node* head;
    public Node* current;

    public  void AddNode(int d)
    {
        Node n = new Node();
        n.data = d;
        n.link = null;
        if (head == null)
        {
            head = current = &n;
        }
        else
        {
            (*current).link = &n;
            current = &n;
        }
        Console.WriteLine(head->data);
    }

    public void TraverseNodes()
    {
        Node* temp = head;
        while(temp != null)
        {
             Console.WriteLine(temp -> data);
             temp= temp -> link;                
        }
    }
}

public unsafe struct Node
{
    public int data;
    public Node* link;
}

class Program
{
    private static void UnsafeDSImplementation()
    {
        var myLinkedList = new NodeList();
        myLinkedList.AddNode(2);
        myLinkedList.AddNode(4);
        myLinkedList.TraverseNodes();
    }

    static void Main(string[] args)
    {
        UnsafeDSImplementation();
    }
}

错误的观察：

每次我进入 AddNode 方法并尝试打印节点数据值，然后第一次我得到 2，第二次我得到 4。我想知道当我分配时 head 是如何改变的添加第一个节点时只执行一次。
在遍历所有节点时 - 我得到第一个节点的数据值为 2243610（这在每个运行上不断变化，所以它是垃圾）和第二个节点迭代的 System.NullRefernceException 异常。两个节点都应该正确打印数据。

现在我得到的行为可能是由于我在代码中犯了一个错误，或者可能是显而易见的，因为我正在使用来自托管世界的指针。我需要你的帮助来解决这个问题。

Answer 1

使用本机分配内存Marshal.AllocHGlobal（类似于 C 中的 malloc）

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

namespace Linked_List
{

public unsafe class NodeList
{
    public static Node * head ;

    public void AddNode(int d)
    {

        Node* newNode = (Node*)Marshal.AllocHGlobal(sizeof(Node)).ToPointer();
        newNode->data = d;
        newNode->link = null;

        Node* temp;
        if (head == null)
        {
            head = newNode;
        }
        else
        {
            temp = head;
            head = newNode;
            newNode->link = temp;

        }
        Console.WriteLine(head->data);
    }

    public void TraverseNodes()
    {
        Node* temp = head;
        while (temp != null)
        {
            Console.WriteLine(temp->data);
            temp = temp->link;
        }
    }
}

public unsafe struct Node
{
    public int data;
    public Node* link;
}


unsafe class  Program
{
    private  static void UnsafeDSImplementation()
    {
        var myLinkedList = new NodeList();
        myLinkedList.AddNode(2);
        myLinkedList.AddNode(4);
        myLinkedList.TraverseNodes();
    }


    static void Main(string[] args)
    {
        UnsafeDSImplementation();
    }
 }
}

注意：您还需要使用Marshal.FreeHGlobal

释放内存

Answer 2

看起来当 head 为 null 时，head 和 current 都指向相同的内存位置。所以两者都变成指向相同内存地址的指针。添加第二个节点时，您正在更改当前指针指向的值，但由于 head 也指向相同的值，因此它也会随当前值而变化。

我是看了你的代码才得出这个结论的，所以我可能不正确。不过好像是这个原因。

在 C# 中使用结构实现链表时获取垃圾值（不安全构造）

Getting garbage values while implementing linked list using structs in C# (unsafe construct)

c#

struct

unsafe