如何正确地制作一个带有cursom链接的链接列表

Question

在C#中创建LinkedList时，可以通过模板LinkedList<T>指定其节点的类型，但不能指定其链接的类型。它总是LinkedListNode。这很奇怪，因为从数学上讲，图节点可以携带数据(边的宽度等(。这甚至不是不可能实现的，但他们选择了不实现。我的问题是：如何用自定义节点和链接表示链表？我一定要写我自己的链表实现吗？

Answer 1

您可以构建自己的链表类型，但也可以将与边缘相关的数据放入存储的对象中。

一个简单的版本是：

public class NodeInfo 
{
public NodeInfo(string data, double prevWeight = 1.0, double nextWeight = 1.0)
{
Data = data;
PrevLinkWeight = prevWeight;
NextLinkWeight = nextWeight;
}
public string Data { get; set; }
public double PrevLinkWeight { get; set; }
public double NextLinkWeight { get; set; }
}

然后添加如下节点：

var list = new LinkedList<NodeInfo>();
list.AddLast(new NodeInfo("Node1", nextWeight: 0.5));
list.AddLast(new NodeInfo("Node2", prevWeight: 0.5, nextWeight: 1.0));
list.AddLast(new NodeInfo("Node3", prevWeight: 2.0));

并且，给定LinkedListNode<NodeInfo>，您可以通过以下方式访问节点/边缘数据：

node.Value.Data
node.Value.NextLinkWeight

更为复杂的方法：

你也可以做一些稍微复杂一点的事情——例如，为节点和边缘分别设置不同的类型：

// Container class
public class NodeInfo<TValue>
{
public NodeInfo(
TValue value, 
LabeledWeightedLink prevLink = null, 
LabeledWeightedLink nextLink = null)
{
Data = value;
PrevLink = prevLink ?? new LabeledWeightedLink();
NextLink = nextLink ?? new LabeledWeightedLink();
}
public TValue Data { get; set; }
public LabeledWeightedLink PrevLink { get; set; }
public LabeledWeightedLink NextLink { get; set; }
}
// Edge-related data
public class LabeledWeightedLink 
{
public LabeledWeightedLink()
: this(string.Empty, 1.0)
{}
public LabeledWeightedLink(string label, double weight = 1.0)
{
Label = label;
Weight = weight;
}
public string Label {get; set; }
public double Weight { get; set; }
public override string ToString() => $"lnk("{Label}"; {Weight})";
}

然后你可以添加这样的节点：

var list = new LinkedList<NodeInfo<string>>(); 
list.AddLast(new NodeInfo<string>(
"node1",
nextLink: new LabeledWeightedLink("1 to 2", 2.0)));
list.AddLast(new NodeInfo<string>(
"node2", 
prevLink: new LabeledWeightedLink("2 to 1", 1.0),
nextLink: new LabeledWeightedLink("2 to 3", 2.0)));
list.AddLast(new NodeInfo<string>(
"node3",
prevLink: new LabeledWeightedLink("3 to 2", 2.5),
nextLink: new LabeledWeightedLink("3 to 4", 1.5)));
list.AddLast(new NodeInfo<string>(
"node4",
prevLink: new LabeledWeightedLink("4 to 3", 1.5)));

同样，给定一个节点，您可以通过NodeInfo类访问各种感兴趣的属性：

node.Value.Data
node.Value.NextLink.Label
node.Value.NextLink.Weight

例如：

var current = list.First;
do {
string nodeData = current.Value.Data;
string prevLink = current.Value.PrevLink.ToString();
string nextLink = current.Value.NextLink.ToString();
Console.WriteLine($"{prevLink}<---[{nodeData}]--->{nextLink}");
current = current.Next;
} while (current != null);

打印出来：

lnk(""; 1)<---[node1]--->lnk("1 to 2"; 2)
lnk("2 to 1"; 1)<---[node2]--->lnk("2 to 3"; 2)
lnk("3 to 2"; 2.5)<---[node3]--->lnk("3 to 4"; 1.5)
lnk("4 to 3"; 1.5)<---[node4]--->lnk(""; 1)

Answer 2

是的，你必须自己写。您可以使用参考源作为启动程序https://referencesource.microsoft.com/#System/compmod/system/collections/generic/linkedlist.cs

听起来像是一个有趣的项目，如果你在这里遇到问题(带代码(