Викиучебник

Динамические структуры данных: различия между версиями

Динамические структуры данных (править)

Версия 12:29, 21 мая 2018

10 байт убрано ,  2 года назад
Нет описания правки
[
''# Stackself:''
public void Push('''T''' value) <span style="color:red">#быстрая операция</span>
public '''T''' Pop() <span style="color:red">#быстрая операция</span>
<---or--->
''# Listself:''
public void AddFirst('''T''' value) <span style="color:red">#быстрая операция</span>
public void AddLast('''T''' value) <span style="color:red">#требуется ссылка на хвост списка для того, чтобы операция была максимально быстрой</span>
==Операции над стеком - частным случаем односвязного списка==
===Push===
Пусть '''TNode<T>''' node - новый узел стека Stackself, тогда:
var node = new TNode<'''T'''>(value, Stackself.'''Head''')
Stackself.'''Head''' = node
Stackself.'''Count''' += 1
 
===Pop===
Пусть '''T''' result - значение удаляемого узла стека Stackself, тогда:
if (Stackself.'''Count''' == 0) then ''# Гарантия наличия хотя бы одного элемента.''
error
Stackself.'''Head''' = Stackself.Head.'''Next'''
Stackself.'''Count''' -= 1
 
==Операции над односвязным списком - общий случай==
===Добавление в начало - AddFirst===
Пусть '''TNode<T>''' node - новый узел списка Listself, тогда:
var node = new TNode<'''T'''>(value, Listself.'''Head''')
Listself.'''Head''' = node
Listself.'''Count''' += 1
[[File:AddFirstMethod.jpg|frameless|400px]]
 
===Добавление в конец - AddLast===
Пусть '''TNode<T>''' node - новый узел списка Listself, а '''TNode<T>''' last - последний узел списка Listself тогда:
var node = new TNode<'''T'''>(value)
if (Listself.'''Count''' == 0) then ''# Добавление в конец в пустой список эквивалентно добавлению в начало.''
Listself.'''Head''' = node
else
Listself.last.'''Next''' = node
Listself.'''Count''' += 1
Общий случай (множество узлов перед last не является пустым):
[[File:AddLastMethod.jpg|frameless|400px]]
 
===Вставка после целевого узла - InsertAfter===
Пусть '''TNode<T>''' node - новый узел списка Listself, а '''TNode<T>''' target - узел списка Listself (target.Value == targetValue), после которого будет добавлен node, тогда:
if (Listself.'''Count''' == 0) then
error
var node = new TNode<'''T'''>(value, target.'''Next''')
target.'''Next''' = node
Listself.'''Count''' += 1
Предполагается, что target существует, иначе - ошибка.
 
 
===Вставка перед целевым узлом - InsertBefor===
Пусть '''TNode<T>''' node - новый узел списка Listself, '''TNode<T>''' target - узел списка Listself (target.Value == targetValue), перед которым будет добавлен node, а '''TNode<T>''' ancillary - узел списка Listself (ancillary.Next == target), который может ссылаться на node, тогда:
if (Listself.'''Count''' == 0) then
error
var node = new TNode<'''T'''>(value, Listself.'''Head''')
if (Listself.Head.'''Value''' == target.'''Value''') then
Listself.'''Head''' = node
else
{
ancillary.'''Next''' = node
}
Listself.'''Count''' += 1
Предполагается, что target существует, иначе - ошибка.
 
 
===Удаление первого узла - RemoveFirst===
if (Listself.'''Count''' == 0) then
error
Listself.'''Head''' = Listself.Head.'''Next'''
Listself.'''Count''' -= 1
[[File:RemoveFirstMethod.jpg|frameless|400px]]
 
===Удаление последнего узла - RemoveLast===
Пусть '''TNode<T>''' predLast - предпоследний узел списка Listself, тогда:
if (Listself.'''Count''' == 0) then
error
if (Listself.'''Count''' == 1) then
Listself.'''Head''' = null
else
Listself.predLast.'''Next''' = null
Listself.'''Count''' -= 1
Общий случай (множество узлов перед последним не является пустым):
 
 
===Удаление после целевого узла - RemoveAfter===
Пусть '''TNode<T>''' target - узел списка Listself (target.Value == value), после которого будет удален node, тогда:
if (Listself.'''Count''' in set{0, 1}) then ''# Гарантия существования хотя бы двух узлом списка.''
error
target.'''Next''' = target.Next.'''Next'''
Listself.'''Count''' -= 1
Предполагается, что target существует, иначе - ошибка.
 
 
===Удаление целевого узла - Remove===
Пусть '''TNode<T>''' target - узел списка Listself, после которого будет удален node, тогда:
if (Listself.'''Count''' == 0) then ''# Гарантия существования хотя бы одного узла списка.''
error
if (node.'''Value''' == Listself.Head.'''Value''') then
Listself.'''Head''' = Listself.Head.'''Next'''
else
target.'''Next''' = target.Next.'''Next'''
Listself.'''Count''' -= 1
Предполагается, что node существует, иначе - ошибка.
 
==Операции над двусвязным списком - общий случай==
===Добавление в начало - AddFirst===
Пусть '''TNode<T>''' node - новый узел списка Listself, тогда:
var node = new TNode<'''T'''>(value, Listself.'''Head''', null)
if (Listself.'''Count''' > 0) then
Listself.Head.'''Previous''' = node
Listself.'''Head''' = node
Listself.'''Count''' += 1
[[File:AddFirstMethod2.jpg|frameless|400px]]
 
===Добавление в конец - AddLast===
Пусть '''TNode<T>''' node - новый узел списка Listself, а '''TNode<T>''' last - последний узел списка Listself тогда:
var node = new TNode<'''T'''>(value)
if (Listself.'''Count''' == 0) then
Listself.'''Head''' = node
else
Listself.last.'''Next''' = node
node.'''Previous''' = Listself.'''last'''
Listself.'''Count''' += 1
 
===Вставка после целевого узла - InsertAfter===
Пусть '''TNode<T>''' node - новый узел списка Listself, а '''TNode<T>''' target - узел списка Listself (target.Value == targetValue), после которого будет добавлен node, тогда:
if (Listself.'''Count''' == 0) then
error
var node = new TNode<'''T'''>(value, target.'''Next''', target)
if (node.'''Next''' != null) then
node.Next.'''Previous''' = node
Listself.'''Count''' += 1
Предполагается, что target существует, иначе - ошибка.
 
===Вставка перед целевым узлом - InsertBefor===
Пусть '''TNode<T>''' node - новый узел списка Listself, '''TNode<T>''' target - узел списка Listself (target.Value == targetValue), перед которым будет добавлен node, а '''TNode<T>''' ancillary - узел списка Listself (ancillary.Next == target), который может ссылаться на node, тогда:
if (Listself.'''Count''' == 0) then
error
var node = new TNode<'''T'''>(value, Listself.'''Head''', null)
if (Listself.Head.'''Value''' == target.'''Value''') then
{
Listself.Head.'''Previous''' = node
Listself.'''Head''' = node
else
{
target.'''Previous''' = node
}
Listself.'''Count''' += 1
Предполагается, что target существует, иначе - ошибка.
 
 
===Удаление первого узла - RemoveFirst===
if (Listself.'''Count''' == 0) then
error
Listself.'''Head''' = Listself.Head.'''Next'''
if (Listself.'''Head''' != null) then
Listself.Head.'''Previous''' = null
Listself.'''Count''' -= 1
 
===Удаление последнего узла - RemoveLast===
Пусть '''TNode<T>''' predLast - предпоследний узел списка Listself, тогда:
if (Listself.'''Count''' == 0) then
error
if (Listself.'''Count''' == 1) then
Listself.'''Head''' = null
else
Listself.predLast.'''Next''' = null
Listself.'''Count''' -= 1
 
===Удаление после целевого узла - RemoveAfter===
Пусть '''TNode<T>''' target - узел списка Listself (target.Value == value), после которого будет удален node, тогда:
if (Listself.'''Count''' in set{0, 1}) then ''# Гарантия существования хотя бы двух узлом списка.''
error
target.'''Next''' = target.Next.'''Next'''
if (target.'''Next''' != null) then
target.Next.'''Previous''' = target
Listself.'''Count''' -= 1
 
===Удаление целевого узла - Remove===
Пусть '''TNode<T>''' target - узел списка Listself, после которого будет удален node, тогда:
if (Listself.'''Count''' == 0) then ''# Гарантия существования хотя бы одного узла списка.''
error
if (node.'''Value''' == Listself.Head.'''Value''') then
Listself.'''Head''' = Listself.Head.'''Next'''
if (Listself.'''Head''' != null) then
Listself.Head.'''Previous''' = null
else
target.'''Next''' = target.Next.'''Next'''
if (target.'''Next''' != null) then
target.Next.'''Previous''' = target
Listself.'''Count''' -= 1
''Пояснение: если удаляемый элемент - это голова списка, то переместить голову списка на один узел вперёд; если список еще содержит элементы, то убрать ссылку на предыдущий элемент для текущей головы списка; если удаляемый узел - не голова, то убрать связь с удаляемым элементом; если удаляемый элемент не был последним, то установить ссылку Previous на предыдущий узел предыдущего узла.''
 
=Вывод списков=
==Вывод ациклического списка - Print==
Пусть '''string''' delimiter - разделитель между выводимыми значениями списка Listself, тогда:
node = Listself.'''Head'''
while (node != null)
{
Источник — https://ru.wikibooks.org/wiki/Служебная:Сравнение_версий/146483