Contents

Структуры данных

Логические структуры данных – это абстракции объектов реального мира.

Физические структуры данных – это программные объекты. (массивы, ссылочные типы, файлы и др.)

Структуры данных:

• линейные (последовательные) списки
  – стек (stack)
  – очередь (queue)
  – дек (deque)
• связные списки (linked lists)
  – односвязный список (singly linked list)
  – двусвязный список (doubly linked list)
  – циклический список (circular list)
• хеш-таблицы (hash tables)
• деревья (trees)
  – бинарные деревья (binary trees)

Линейные списки

Стек

Стек – линейный список, доступ к элементам которого осуществляется по принципу LIFO (Last In First Out).

Основные операции:
– инициализация (Init)
– деструктизация (Destroy)
– помещение элемента в стек (Push)
– удаление элемента из стека (Pop)
– значение верхнего элемента (Top)
– проверка на пустоту (isEmpty)
– проверка на полноту (isFull)

Очередь

Очередь – линейный список, доступ к элементам которого осуществляется по принципу FIFO (First In First Out).

Основные операции:
– инициализация (Init)
– деструктизация (Destroy)
– помещение элемента в очередь (Insert)
– удаление элемента из очереди (Remove)
– значение первого элемента (Head)
– значение последнего элемента (Tail)
– проверка на пустоту (isEmpty)
– проверка на полноту (isFull)

Дек

Дек – линейный список, доступ к элементам которого как с начала, так и с конца списка.

Основные операции:
– инициализация (Init)
– деструктизация (Destroy)
– помещение элемента в начало дека (InsertHead)
– помещение элемента в конец дека (InsertTail)
– удаление элемента из начала дека (RemoveHead)
– удаление элемента из конца дека (RemoveTail)
– значение первого элемента (Head)
– значение последнего элемента (Tail)
– проверка на пустоту (isEmpty)
– проверка на полноту (isFull)

Связные списки

Связный список – структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и ссылки на следующий и/или предыдущий узел списка.

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

В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего элемента невозможно.

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

По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.

Циклический список

Циклический список тоже может быть односвязным или двусвязным. Последний элемент циклического списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний. Реализация такой структуры происходит на базе линейного списка.