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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Нет описания правки
Строка 39: Строка 39:
[
[
''# self:''
''# 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--->
''# self:''
''# 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
}