Как правильно составить связанный список с краткими ссылками? - PullRequest
Новая
       20

Как правильно составить связанный список с краткими ссылками?

0 голосов
/ 25 апреля 2020

При создании LinkedList в C# вы можете указать тип его узла с помощью шаблонов LinkedList<T>, но вы не можете указать тип его ссылок. Это всегда LinkedListNode. И это странно, потому что математически узлы графа могут нести данные (ширина ребер и т. Д. c.). Это не невозможно реализовать даже, но они решили не делать этого. Мой вопрос: как мне представить связанный список с пользовательскими узлами и ссылками? Обязательно ли мне писать собственную реализацию связанного списка?

Ответы [ 2 ]

1 голос
/ 04 мая 2020

Вы можете создать свой собственный тип связанного списка, но вы также можете просто поместить данные, связанные с ребрами, в хранимый объект.

Простая версия этого была бы: 

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)
0 голосов
/ 30 апреля 2020

да, ты должен написать свой. Вы можете использовать справочный источник как стартовый. https://referencesource.microsoft.com/#System / compmod / system / collection / generic / connectedlist.cs

звучит как забавный проект, если вы застряли в постах ( код) здесь

...