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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Строка 1: Строка 1:
[[Энциклопедия псевдокода|Обратно]]
[[Энциклопедия псевдокода|Обратно]]
=Замечания=
=Замечания=
В данном контексте Stack и List являются аналогами self или this.
В данном контексте Stack и List являются аналогами self и this.

=Односвязный список=
=Односвязный список=
==Узел односвязного списка==
==Узел односвязного списка==

Версия от 12:40, 20 мая 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()
    {
    }
    
    [
      public void Push(T value) # Stack
      public T Pop()
      <---or--->
      public void AddFirst(T value) # List
      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)
    ]
  }

Операции над стеком - частным случаем односвязного списка

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

Множество узлов включает хотя бы один элемент:

Вставка перед целевым узлом - 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

Общий случай (вставка не перед головным элементом):

Ситуация Действие
Добавление перед головой списка Добавить элемент первым
Добавление после головы списка Добавить элемент после элемента, предшествующего целевому

Удаление первого узла - 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

Удаление целевого узла - 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
Ситуация Действие
Удаление единственного элемента Обнулить голову списка
Удаление элемента, который не является головой списка Переставить ссылку у элемента, предшествующего целевому на следующий элемент

Вывод списка - Print

Пусть string delimiter - разделитель между выводимыми значениями списка List, тогда:

node = List.Head
while (node != null)
{
  print node.Value
  if (node.Next != null) then
    print delimiter
  node = node.Next
}

Двусвязный список

Узел двусвязного списка

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