Алгоритмическое мышление при решении задач (на примере языка C#). Шамшев А.Б - 77 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

77
Задача 17. Работа с односвязанным списком
Для начала дадим определение односвязанного списка.
Односвязанный список – связанный, ориентированный, ациклический
граф, в каждую вершину которого входит не более одной связи и выходит не
более одной связи. Количество вершин в односвязанном списке на единицу
больше количества ребер (исключение составляет пустой граф (список) – в нем
количество ребер
и количество вершин равно нулю).
Исходя из этого определения, можно понять, что в элементе
односвязанного списка можно объединить данное и указатель на следующую
вершину. При этом следующая вершина имеет такой же тип, что и текущая.
Поэтому первый шаг в объявлении узла односвязанного списка будет
следующий:
public class ListNode {
public int data;
public ListNode next;
}
Однако по логике элемент данных не может не содержать данных.
Поэтому следующий шаг заключается во введении конструктора (в список его
параметров для удобства сразу добавим ссылку на следующий элемент).
public class ListNode {
public int data;
public ListNode next;
public ListNode(int _data, ListNode _next) {
data = _data;
next = _next;
}
}
Если ссылка next равна null, то это означает, что следующего элемента за
текущим элементом нет.
Для конкретики изобразим пример односвязанного списка.
При этом условимся, что означает ссылку на null. Следует отметить,
что формально этой связи нет (с точки зрения определения из теории графов),
она изображается для удобства.
Из этого рисунка вытекает важное следствие: в последнем элементе
односвязанного списка ссылка на next равна null.
Как правило, односвязанный список характеризуют через голову (head).
Отличительной особенностью головы является
то, что в нее нет входящих
связей. Поэтому детализируем рисунок.

Страницы