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