Динамические структуры данных: различия между версиями
Нет описания правки |
|||
Строка 63: | Строка 63: | ||
===Push=== |
===Push=== |
||
Пусть '''TNode<T>''' node - новый узел стека self, тогда: |
Пусть '''TNode<T>''' node - новый узел стека self, тогда: |
||
var node = new TNode<'''T'''>(value, self.'''Head''') |
var node = new TNode<'''T'''>(value, <span style="color:blue">self</span>.'''Head''') |
||
self.'''Head''' = node |
<span style="color:blue">self</span>.'''Head''' = node |
||
self.'''Count''' += 1 |
<span style="color:blue">self</span>.'''Count''' += 1 |
||
===Pop=== |
===Pop=== |
||
Пусть '''T''' result - значение удаляемого узла стека self, тогда: |
Пусть '''T''' result - значение удаляемого узла стека self, тогда: |
||
if (self.'''Count''' == 0) then ''# Гарантия наличия хотя бы одного элемента.'' |
if (<span style="color:blue">self</span>.'''Count''' == 0) then ''# Гарантия наличия хотя бы одного элемента.'' |
||
error |
error |
||
self.'''Head''' = self.Head.'''Next''' |
<span style="color:blue">self</span>.'''Head''' = <span style="color:blue">self</span>.Head.'''Next''' |
||
self.'''Count''' -= 1 |
<span style="color:blue">self</span>.'''Count''' -= 1 |
||
==Операции над односвязным списком - общий случай== |
==Операции над односвязным списком - общий случай== |
||
===Добавление в начало - AddFirst=== |
===Добавление в начало - AddFirst=== |
||
Пусть '''TNode<T>''' node - новый узел списка self, тогда: |
Пусть '''TNode<T>''' node - новый узел списка self, тогда: |
||
var node = new TNode<'''T'''>(value, self.'''Head''') |
var node = new TNode<'''T'''>(value, <span style="color:blue">self</span>.'''Head''') |
||
self.'''Head''' = node |
<span style="color:blue">self</span>.'''Head''' = node |
||
self.'''Count''' += 1 |
<span style="color:blue">self</span>.'''Count''' += 1 |
||
[[File:AddFirstMethod.jpg|frameless|400px]] |
[[File:AddFirstMethod.jpg|frameless|400px]] |
||
Строка 85: | Строка 85: | ||
Пусть '''TNode<T>''' node - новый узел списка self, а '''TNode<T>''' last - последний узел списка self тогда: |
Пусть '''TNode<T>''' node - новый узел списка self, а '''TNode<T>''' last - последний узел списка self тогда: |
||
var node = new TNode<'''T'''>(value) |
var node = new TNode<'''T'''>(value) |
||
if (self.'''Count''' == 0) then ''# Добавление в конец в пустой список эквивалентно добавлению в начало.'' |
if (<span style="color:blue">self</span>.'''Count''' == 0) then ''# Добавление в конец в пустой список эквивалентно добавлению в начало.'' |
||
self.'''Head''' = node |
<span style="color:blue">self</span>.'''Head''' = node |
||
else |
else |
||
self.last.'''Next''' = node |
<span style="color:blue">self</span>.last.'''Next''' = node |
||
self.'''Count''' += 1 |
self.'''Count''' += 1 |
||
Общий случай (множество узлов перед last не является пустым): |
Общий случай (множество узлов перед last не является пустым): |
||
Строка 104: | Строка 104: | ||
===Вставка после целевого узла - InsertAfter=== |
===Вставка после целевого узла - InsertAfter=== |
||
Пусть '''TNode<T>''' node - новый узел списка self, а '''TNode<T>''' target - узел списка self (target.Value == targetValue), после которого будет добавлен node, тогда: |
Пусть '''TNode<T>''' node - новый узел списка self, а '''TNode<T>''' target - узел списка self (target.Value == targetValue), после которого будет добавлен node, тогда: |
||
if (self.'''Count''' == 0) then |
if (<span style="color:blue">self</span>.'''Count''' == 0) then |
||
error |
error |
||
var node = new TNode<'''T'''>(value, target.'''Next''') |
var node = new TNode<'''T'''>(value, target.'''Next''') |
||
target.'''Next''' = node |
target.'''Next''' = node |
||
self.'''Count''' += 1 |
<span style="color:blue">self</span>.'''Count''' += 1 |
||
Предполагается, что target существует, иначе - ошибка. |
Предполагается, что target существует, иначе - ошибка. |
||
Строка 117: | Строка 117: | ||
===Вставка перед целевым узлом - InsertBefor=== |
===Вставка перед целевым узлом - InsertBefor=== |
||
Пусть '''TNode<T>''' node - новый узел списка self, '''TNode<T>''' target - узел списка self (target.Value == targetValue), перед которым будет добавлен node, а '''TNode<T>''' ancillary - узел списка self (ancillary.Next == target), который может ссылаться на node, тогда: |
Пусть '''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 |
if (<span style="color:blue">self</span>.'''Count''' == 0) then |
||
error |
error |
||
var node = new TNode<'''T'''>(value, self.'''Head''') |
var node = new TNode<'''T'''>(value, <span style="color:blue">self</span>.'''Head''') |
||
if (self.Head.'''Value''' == target.'''Value''') then |
if (<span style="color:blue">self</span>.Head.'''Value''' == target.'''Value''') then |
||
self.'''Head''' = node |
<span style="color:blue">self</span>.'''Head''' = node |
||
else |
else |
||
{ |
{ |
||
Строка 127: | Строка 127: | ||
ancillary.'''Next''' = node |
ancillary.'''Next''' = node |
||
} |
} |
||
self.'''Count''' += 1 |
<span style="color:blue">self</span>.'''Count''' += 1 |
||
Предполагается, что target существует, иначе - ошибка. |
Предполагается, что target существует, иначе - ошибка. |
||
Строка 144: | Строка 144: | ||
===Удаление первого узла - RemoveFirst=== |
===Удаление первого узла - RemoveFirst=== |
||
if (self.'''Count''' == 0) then |
if (<span style="color:blue">self</span>.'''Count''' == 0) then |
||
error |
error |
||
self.'''Head''' = self.Head.'''Next''' |
<span style="color:blue">self</span>.'''Head''' = <span style="color:blue">self</span>.Head.'''Next''' |
||
self.'''Count''' -= 1 |
<span style="color:blue">self</span>.'''Count''' -= 1 |
||
[[File:RemoveFirstMethod.jpg|frameless|400px]] |
[[File:RemoveFirstMethod.jpg|frameless|400px]] |
||
===Удаление последнего узла - RemoveLast=== |
===Удаление последнего узла - RemoveLast=== |
||
Пусть '''TNode<T>''' predLast - предпоследний узел списка self, тогда: |
Пусть '''TNode<T>''' predLast - предпоследний узел списка self, тогда: |
||
if (self.'''Count''' == 0) then |
if (<span style="color:blue">self</span>.'''Count''' == 0) then |
||
error |
error |
||
if (self.'''Count''' == 1) then |
if (<span style="color:blue">self</span>.'''Count''' == 1) then |
||
self.'''Head''' = null |
<span style="color:blue">self</span>.'''Head''' = null |
||
else |
else |
||
predLast.'''Next''' = null |
|||
self.'''Count''' -= 1 |
<span style="color:blue">self</span>.'''Count''' -= 1 |
||
Общий случай (множество узлов перед последним не является пустым): |
Общий случай (множество узлов перед последним не является пустым): |
||
Строка 173: | Строка 173: | ||
===Удаление после целевого узла - RemoveAfter=== |
===Удаление после целевого узла - RemoveAfter=== |
||
Пусть '''TNode<T>''' target - узел списка self (target.Value == value), после которого будет удален node, тогда: |
Пусть '''TNode<T>''' target - узел списка self (target.Value == value), после которого будет удален node, тогда: |
||
if (self.'''Count''' in set{0, 1}) then ''# Гарантия существования хотя бы двух узлом списка.'' |
if (<span style="color:blue">self</span>.'''Count''' in set{0, 1}) then ''# Гарантия существования хотя бы двух узлом списка.'' |
||
error |
error |
||
target.'''Next''' = target.Next.'''Next''' |
target.'''Next''' = target.Next.'''Next''' |
||
self.'''Count''' -= 1 |
<span style="color:blue">self</span>.'''Count''' -= 1 |
||
Предполагается, что target существует, иначе - ошибка. |
Предполагается, что target существует, иначе - ошибка. |
||
Строка 183: | Строка 183: | ||
===Удаление целевого узла - Remove=== |
===Удаление целевого узла - Remove=== |
||
Пусть '''TNode<T>''' target - узел списка self, после которого будет удален node, тогда: |
Пусть '''TNode<T>''' target - узел списка self, после которого будет удален node, тогда: |
||
if (self.'''Count''' == 0) then ''# Гарантия существования хотя бы одного узла списка.'' |
if (<span style="color:blue">self</span>.'''Count''' == 0) then ''# Гарантия существования хотя бы одного узла списка.'' |
||
error |
error |
||
if (node.'''Value''' == self.Head.'''Value''') then |
if (node.'''Value''' == <span style="color:blue">self</span>.Head.'''Value''') then |
||
self.'''Head''' = self.Head.'''Next''' |
<span style="color:blue">self</span>.'''Head''' = <span style="color:blue">self</span>.Head.'''Next''' |
||
else |
else |
||
target.'''Next''' = target.Next.'''Next''' |
target.'''Next''' = target.Next.'''Next''' |
||
self.'''Count''' -= 1 |
se<span style="color:blue">self</span>lf.'''Count''' -= 1 |
||
Предполагается, что node существует, иначе - ошибка. |
Предполагается, что node существует, иначе - ошибка. |
||
Версия от 12:35, 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 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 seselflf.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 }