Динамические структуры данных: различия между версиями
Нет описания правки |
|||
Строка 39: | Строка 39: | ||
[ |
[ |
||
''# |
''# Stack:'' |
||
public void Push('''T''' value) <span style="color:red">#быстрая операция</span> |
public void Push('''T''' value) <span style="color:red">#быстрая операция</span> |
||
public '''T''' Pop() <span style="color:red">#быстрая операция</span> |
public '''T''' Pop() <span style="color:red">#быстрая операция</span> |
||
<---or---> |
<---or---> |
||
''# |
''# List:'' |
||
public void AddFirst('''T''' value) <span style="color:red">#быстрая операция</span> |
public void AddFirst('''T''' value) <span style="color:red">#быстрая операция</span> |
||
public void AddLast('''T''' value) <span style="color:red">#требуется ссылка на хвост списка для того, чтобы операция была максимально быстрой</span> |
public void AddLast('''T''' value) <span style="color:red">#требуется ссылка на хвост списка для того, чтобы операция была максимально быстрой</span> |
Версия от 12:29, 21 мая 2018
Замечания
Считаем, что элементы, на которые ничего не указывает, удаляются автоматически.
Односвязный список
Узел односвязного списка
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 - новый узел стека self, тогда:
var node = new TNode<T>(value, self.Head) self.Head = node self.Count += 1
Pop
Пусть T result - значение удаляемого узла стека self, тогда:
if (self.Count == 0) then # Гарантия наличия хотя бы одного элемента. error self.Head = self.Head.Next self.Count -= 1
Операции над односвязным списком - общий случай
Добавление в начало - AddFirst
Пусть TNode<T> node - новый узел списка self, тогда:
var node = new TNode<T>(value, self.Head) self.Head = node self.Count += 1
Добавление в конец - AddLast
Пусть TNode<T> node - новый узел списка self, а TNode<T> last - последний узел списка self тогда:
var node = new TNode<T>(value) if (self.Count == 0) then # Добавление в конец в пустой список эквивалентно добавлению в начало. self.Head = node else self.last.Next = node self.Count += 1
Общий случай (множество узлов перед last не является пустым):
Ситуация | Действие |
---|---|
Список пуст | Добавить элемент первым |
Список имеет хотя бы 1 элемент | Добавить элемент последним |
Вставка после целевого узла - InsertAfter
Пусть TNode<T> node - новый узел списка self, а TNode<T> target - узел списка self (target.Value == targetValue), после которого будет добавлен node, тогда:
if (self.Count == 0) then error var node = new TNode<T>(value, target.Next) target.Next = node self.Count += 1
Предполагается, что target существует, иначе - ошибка.
Множество узлов включает хотя бы один элемент:
Вставка перед целевым узлом - InsertBefor
Пусть TNode<T> node - новый узел списка self, TNode<T> target - узел списка self (target.Value == targetValue), перед которым будет добавлен node, а TNode<T> ancillary - узел списка self (ancillary.Next == target), который может ссылаться на node, тогда:
if (self.Count == 0) then error var node = new TNode<T>(value, self.Head) if (self.Head.Value == target.Value) then self.Head = node else { node.Next = target ancillary.Next = node } self.Count += 1
Предполагается, что target существует, иначе - ошибка.
Общий случай (вставка не перед головным элементом):
Ситуация | Действие |
---|---|
Добавление перед головой списка | Добавить элемент первым |
Добавление после головы списка | Добавить элемент после элемента, предшествующего целевому |
Удаление первого узла - RemoveFirst
if (self.Count == 0) then error self.Head = self.Head.Next self.Count -= 1
Удаление последнего узла - RemoveLast
Пусть TNode<T> predLast - предпоследний узел списка self, тогда:
if (self.Count == 0) then error if (self.Count == 1) then self.Head = null else self.predLast.Next = null self.Count -= 1
Общий случай (множество узлов перед последним не является пустым):
Ситуация | Действие |
---|---|
Удаление единственного элемента | Обнулить голову списка |
Удаление элемента, который не является головой списка | Убрать у предпоследнего элемента ссылку на последний |
Удаление после целевого узла - RemoveAfter
Пусть TNode<T> target - узел списка self (target.Value == value), после которого будет удален node, тогда:
if (self.Count in set{0, 1}) then # Гарантия существования хотя бы двух узлом списка. error target.Next = target.Next.Next self.Count -= 1
Предполагается, что target существует, иначе - ошибка.
Удаление целевого узла - Remove
Пусть TNode<T> target - узел списка self, после которого будет удален node, тогда:
if (self.Count == 0) then # Гарантия существования хотя бы одного узла списка. error if (node.Value == self.Head.Value) then self.Head = self.Head.Next else target.Next = target.Next.Next self.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 - новый узел списка self, тогда:
var node = new TNode<T>(value, self.Head, null) if (self.Count > 0) then self.Head.Previous = node self.Head = node self.Count += 1
Добавление в конец - AddLast
Пусть TNode<T> node - новый узел списка self, а TNode<T> last - последний узел списка self тогда:
var node = new TNode<T>(value) if (self.Count == 0) then self.Head = node else self.last.Next = node node.Previous = self.last self.Count += 1
Вставка после целевого узла - InsertAfter
Пусть TNode<T> node - новый узел списка self, а TNode<T> target - узел списка self (target.Value == targetValue), после которого будет добавлен node, тогда:
if (self.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 self.Count += 1
Предполагается, что target существует, иначе - ошибка.
Вставка перед целевым узлом - InsertBefor
Пусть TNode<T> node - новый узел списка self, TNode<T> target - узел списка self (target.Value == targetValue), перед которым будет добавлен node, а TNode<T> ancillary - узел списка self (ancillary.Next == target), который может ссылаться на node, тогда:
if (self.Count == 0) then error var node = new TNode<T>(value, self.Head, null) if (self.Head.Value == target.Value) then { self.Head.Previous = node self.Head = node else { node.Next = target node.Previous = ancillary ancillary.Next = node target.Previous = node } self.Count += 1
Предполагается, что target существует, иначе - ошибка.
Пояснение: предполагаем, что добавляемый узел вставляется перед головой списка, если это так, то предыдущим для головы списка делаем добавленный узел и переставляем голову списка на один элемент назад; если добавляемый узел вставляется не перед головой, то устанавливаем связи у него с соседними узлами.
Удаление первого узла - RemoveFirst
if (self.Count == 0) then error self.Head = self.Head.Next if (self.Head != null) then self.Head.Previous = null self.Count -= 1
Удаление последнего узла - RemoveLast
Пусть TNode<T> predLast - предпоследний узел списка self, тогда:
if (self.Count == 0) then error if (self.Count == 1) then self.Head = null else self.predLast.Next = null self.Count -= 1
Удаление после целевого узла - RemoveAfter
Пусть TNode<T> target - узел списка self (target.Value == value), после которого будет удален node, тогда:
if (self.Count in set{0, 1}) then # Гарантия существования хотя бы двух узлом списка. error target.Next = target.Next.Next if (target.Next != null) then target.Next.Previous = target self.Count -= 1
Удаление целевого узла - Remove
Пусть TNode<T> target - узел списка self, после которого будет удален node, тогда:
if (self.Count == 0) then # Гарантия существования хотя бы одного узла списка. error if (node.Value == self.Head.Value) then self.Head = self.Head.Next if (self.Head != null) then self.Head.Previous = null else target.Next = target.Next.Next if (target.Next != null) then target.Next.Previous = target self.Count -= 1
Пояснение: если удаляемый элемент - это голова списка, то переместить голову списка на один узел вперёд; если список еще содержит элементы, то убрать ссылку на предыдущий элемент для текущей головы списка; если удаляемый узел - не голова, то убрать связь с удаляемым элементом; если удаляемый элемент не был последним, то установить ссылку Previous на предыдущий узел предыдущего узла.
Вывод списков
Вывод ациклического списка - Print
Пусть string delimiter - разделитель между выводимыми значениями списка self, тогда:
node = self.Head while (node != null) { print node.Value if (node.Next != null) then print delimiter node = node.Next }