Викиучебник

Динамические структуры данных

Обратно

Замечания

править

Считаем, что элементы, на которые ничего не указывает, удаляются автоматически.

Односвязный список

править

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

править 
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
  { 
    private TNode<T> last
    
    public property TNode<T> Head get
    public property integer Count get
    
    public 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)
    ]
  }

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

править

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
self.Count -= 1

Предполагается, что node существует, иначе - ошибка.

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

Операции над кольцевым односвязным списком - общий случай

править

Добавление в начало - AddFirst

править

Пусть TNode<T> node - новый узел списка self, а TNode<T> last - последний узел списка, тогда: 

var node = new TNode<T>(value, self.Head)
if (self.Count == 0) then
{
  self.Next = node
  self.last = node
}
else
  self.last.Next = node
self.Head = node
self.Count += 1
Ситуация Действие
Список пуст Добавить элемент первым, замкнув цепь узлов
Список имеет хотя бы 1 элемент Добавить элемент последним, замкнув цепь узлов

Добавление в конец - AddLast

править

Пусть TNode<T> node - новый узел списка self, а TNode<T> last - последний узел списка self тогда: 

var node = new TNode<T>(value, self.Head)
if (self.Count == 0) then # Добавление в конец в пустой список эквивалентно добавлению в начало.
{
  self.Head = node
  self.last = node
  node.Next = node
}
else
{
  self.last.Next = node
  self.last = node
}
self.Count += 1

Общий случай (множество узлов перед last не является пустым):

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

править

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

править 
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 TNode<T> Last get
    public property integer Count get
    
    public 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.Last = node
else
  self.Head.Previous = node
self.Head = node
self.Count += 1

 

Добавление в конец - AddLast

править

Пусть TNode<T> node - новый узел списка self, тогда: 

var node = new TNode<T>(value, null, self.Last)
if (self.Count == 0) then
  self.Head = node
else
  self.Last.Next = node
self.Last = node
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
  self.Last = 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
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
}

Рекурсивный вариант: 

if (node != null) then
{
  print node.Value
  PrintFunction(node.Next)
}
Источник — https://ru.wikibooks.org/w/index.php?title=Динамические_структуры_данных&oldid=163494