Динамические структуры данных: различия между версиями
Строка 296: | Строка 296: | ||
} |
} |
||
List.'''Count''' += 1 |
List.'''Count''' += 1 |
||
Предполагается, что target существует, иначе - ошибка. |
|||
<!-- |
|||
===Вставка перед целевым узлом - InsertBefor=== |
|||
Пусть '''TNode<T>''' node - новый узел списка List, а '''TNode<T>''' target - узел списка List (target.Value == targetValue), перед которым будет добавлен node, тогда: |
|||
if (List.'''Count''' == 0) then |
|||
error |
|||
var node = new TNode<'''T'''>(value, target, null) |
|||
target.'''Previous''' = node |
|||
if (target.'''Previous''' == null) then |
|||
List.'''Head''' = node |
|||
else |
|||
target.Previous.'''Next''' = node |
|||
node.Previous = target.Previous |
|||
target.'''Next''' = node |
|||
List.'''Count''' += 1--> |
|||
===Удаление первого узла - RemoveFirst=== |
===Удаление первого узла - RemoveFirst=== |
Версия от 12:07, 21 мая 2018
Замечания
- В данном контексте Stack и List являются аналогами self и this.
- Считаем, что элементы, на которые ничего не указывает, удаляются автоматически.
Односвязный список
Узел односвязного списка
type //Шаблонные параметры: // T - тип значения узла TNode<T> = class { public property T Value get-set; public property TNode<T> Next get-set; public constructor Create(T value; TNode<T> next) { Value = value; Next = next; } public constructor Create(T value) { Create(value, null) } }
Класс односвязного списка
type //Шаблонные параметры: // T - тип значения узлов списка TList<T> = class { public property TNode<T> Head get public property integer Count get constructor Create() { } [ # Stack: public void Push(T value) #быстрая операция public T Pop() #быстрая операция <---or---> # List: public void AddFirst(T value) #быстрая операция public void AddLast(T value) #требуется ссылка на хвост списка для того, чтобы операция была максимально быстрой public void InsertAfter(T targetValue; T value) public void InsertBefor(T targetValue; T value) public void RemoveFirst() #быстрая операция public void RemoveLast() public void RemoveAfter(T value) public void Remove(T value) ] operator+: TNode<T> node + TList<T> list // == AddFirst(node.Value) operator+: TList<T> list + TNode<T> node // == AddLast(node.Value) operator-: TList<T> list - TNode<T> node // == Remove(node.Value) }
Операции над стеком - частным случаем односвязного списка
Push
Пусть TNode<T> node - новый узел стека Stack, тогда:
var node = new TNode<T>(value, Stack.Head) Stack.Head = node Stack.Count += 1
Pop
Пусть T result - значение удаляемого узла стека Stack, тогда:
if (Stack.Count == 0) then # Гарантия наличия хотя бы одного элемента. error Stack.Head = Stack.Head.Next Stack.Count -= 1
Операции над односвязным списком - общий случай
Добавление в начало - AddFirst
Пусть TNode<T> node - новый узел списка List, тогда:
var node = new TNode<T>(value, List.Head) List.Head = node List.Count += 1
Добавление в конец - AddLast
Пусть TNode<T> node - новый узел списка List, а TNode<T> last - последний узел списка List тогда:
var node = new TNode<T>(value) if (List.Count == 0) then # Добавление в конец в пустой список эквивалентно добавлению в начало. List.Head = node else List.last.Next = node List.Count += 1
Общий случай (множество узлов перед last не является пустым):
Ситуация | Действие |
---|---|
Список пуст | Добавить элемент первым |
Список имеет хотя бы 1 элемент | Добавить элемент последним |
Вставка после целевого узла - InsertAfter
Пусть TNode<T> node - новый узел списка List, а TNode<T> target - узел списка List (target.Value == targetValue), после которого будет добавлен node, тогда:
if (List.Count == 0) then error var node = new TNode<T>(value, target.Next) target.Next = node List.Count += 1
Предполагается, что target существует, иначе - ошибка.
Множество узлов включает хотя бы один элемент:
Вставка перед целевым узлом - InsertBefor
Пусть TNode<T> node - новый узел списка List, TNode<T> target - узел списка List (target.Value == targetValue), перед которым будет добавлен node, а TNode<T> ancillary - узел списка List (ancillary.Next == target), который может ссылаться на node, тогда:
if (List.Count == 0) then error var node = new TNode<T>(value, List.Head) if (List.Head.Value == target.Value) then List.Head = node else { node.Next = target ancillary.Next = node } List.Count += 1
Предполагается, что target существует, иначе - ошибка.
Общий случай (вставка не перед головным элементом):
Ситуация | Действие |
---|---|
Добавление перед головой списка | Добавить элемент первым |
Добавление после головы списка | Добавить элемент после элемента, предшествующего целевому |
Удаление первого узла - RemoveFirst
if (List.Count == 0) then error List.Head = List.Head.Next List.Count -= 1
Удаление последнего узла - RemoveLast
Пусть TNode<T> predLast - предпоследний узел списка List, тогда:
if (List.Count == 0) then error if (List.Count == 1) then List.Head = null else List.predLast.Next = null List.Count -= 1
Общий случай (множество узлов перед последним не является пустым):
Ситуация | Действие |
---|---|
Удаление единственного элемента | Обнулить голову списка |
Удаление элемента, который не является головой списка | Убрать у предпоследнего элемента ссылку на последний |
Удаление после целевого узла - RemoveAfter
Пусть TNode<T> target - узел списка List (target.Value == value), после которого будет удален node, тогда:
if (List.Count in set{0, 1}) then # Гарантия существования хотя бы двух узлом списка. error target.Next = target.Next.Next List.Count -= 1
Предполагается, что target существует, иначе - ошибка.
Удаление целевого узла - Remove
Пусть TNode<T> target - узел списка List, после которого будет удален node, тогда:
if (List.Count == 0) then # Гарантия существования хотя бы одного узла списка. error if (node.Value == List.Head.Value) then List.Head = List.Head.Next else target.Next = target.Next.Next List.Count -= 1
Предполагается, что node существует, иначе - ошибка.
Ситуация | Действие |
---|---|
Удаление единственного элемента | Обнулить голову списка |
Удаление элемента, который не является головой списка | Переставить ссылку у элемента, предшествующего целевому на следующий элемент |
Двусвязный список
Узел двусвязного списка
type //Шаблонные параметры: // T - тип значения узла TNode<T> = class { public property T Value get-set public property TNode<T> Next get-set public property TNode<T> Previous get-set public constructor Create(T value; TNode<T> next; TNode<T> previous) { Value = value Next = next Previous = previous } public constructor Create(T value) { Create(value, null, null) } }
Класс двусвязного списка
type //Шаблонные параметры: // T - тип значения узлов списка TList<T> = class { public property TNode<T> Head get public property integer Count get constructor Create() { } public void AddFirst(T value) #быстрая операция public void AddLast(T value) #требуется ссылка на хвост списка для того, чтобы операция была максимально быстрой public void InsertAfter(T targetValue; T value) public void InsertBefor(T targetValue; T value) public void RemoveFirst() #быстрая операция public void RemoveLast() public void RemoveAfter(T value) public void Remove(T value) }
Операции над двусвязным списком - общий случай
Добавление в начало - AddFirst
Пусть TNode<T> node - новый узел списка List, тогда:
var node = new TNode<T>(value, List.Head, null) if (List.Count > 0) then List.Head.Previous = node List.Head = node List.Count += 1
Добавление в конец - AddLast
Пусть TNode<T> node - новый узел списка List, а TNode<T> last - последний узел списка List тогда:
var node = new TNode<T>(value) if (List.Count == 0) then List.Head = node else List.last.Next = node node.Previous = List.last List.Count += 1
Вставка после целевого узла - InsertAfter
Пусть TNode<T> node - новый узел списка List, а TNode<T> target - узел списка List (target.Value == targetValue), после которого будет добавлен node, тогда:
if (List.Count == 0) then error var node = new TNode<T>(value, target.Next, target) target.Next = node if (node.Next != null) then node.Next.Previous = node List.Count += 1
Предполагается, что target существует, иначе - ошибка.
Вставка перед целевым узлом - InsertBefor
Пусть TNode<T> node - новый узел списка List, TNode<T> target - узел списка List (target.Value == targetValue), перед которым будет добавлен node, а TNode<T> ancillary - узел списка List (ancillary.Next == target), который может ссылаться на node, тогда:
if (List.Count == 0) then error var node = new TNode<T>(value, List.Head, null) if (List.Head.Value == target.Value) then { List.Head.Previous = node List.Head = node else { node.Next = target node.Previous = ancillary ancillary.Next = node } List.Count += 1
Предполагается, что target существует, иначе - ошибка.
Удаление первого узла - RemoveFirst
if (List.Count == 0) then error List.Head = List.Head.Next if (List.Head != null) then List.Head.Previous = null List.Count -= 1
Удаление последнего узла - RemoveLast
Пусть TNode<T> predLast - предпоследний узел списка List, тогда:
if (List.Count == 0) then error if (List.Count == 1) then List.Head = null else List.predLast.Next = null List.Count -= 1
Удаление после целевого узла - RemoveAfter
Пусть TNode<T> target - узел списка List (target.Value == value), после которого будет удален node, тогда:
if (List.Count in set{0, 1}) then # Гарантия существования хотя бы двух узлом списка. error target.Next = target.Next.Next if (target.Next != null) then target.Next.Previous = target List.Count -= 1
Удаление целевого узла - Remove
Пусть TNode<T> target - узел списка List, после которого будет удален node, тогда:
if (List.Count == 0) then # Гарантия существования хотя бы одного узла списка. error if (node.Value == List.Head.Value) then List.Head = List.Head.Next if (List.Head != null) then List.Head.Previous = null else target.Next = target.Next.Next List.Count -= 1
Вывод списков
Вывод ациклического списка - Print
Пусть string delimiter - разделитель между выводимыми значениями списка List, тогда:
node = List.Head while (node != null) { print node.Value if (node.Next != null) then print delimiter node = node.Next }