Основные структуры данных: Связанные списки

-
Связный список является простейшим типом данных динамической структуры, состоящей из элементов (узлов). Каждый узел включает в себя в классическом варианте два поля:

  • данные (в качестве данных может выступать переменная, объект класса или структуры и т. д.)
  • указатель на следующий узел в списке.



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


Классификация списков

По количеству полей указателей различают однонаправленный (односвязный) и двунаправленный (двусвязный) списки.


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

По способу связи элементов различают линейные и циклические списки.
Связный список, в котором, последний элемент указывает на NULL, называется линейным.
Связный список, в котором последний элемент связан с первым, называется циклическим.

 

Виды списков

Таким образом, различают 4 основных вида списков.
  • Односвязный линейный список (ОЛС).
    Каждый узел ОЛС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).
  • Односвязный циклический список (ОЦС).
    Каждый узел ОЦС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит адрес первого узла (корня списка).
  • Двусвязный линейный список (ДЛС).
    Каждый узел ДЛС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит нулевое значение (указывает на NULL). Поле указателя на предыдущий узел первого узла (корня списка) также содержит нулевое значение (указывает на NULL).
  • Двусвязный циклический список (ДЦС).
    Каждый узел ДЦС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит адрес первого узла (корня списка). Поле указателя на предыдущий узел первого узла (корня списка) содержит адрес последнего узла.

    Сравнение массивов и связных списков



Популярные сообщения из этого блога

Аппроксимация функций рядом Тейлора

-
Изображение
Ряды Тейлора помогают аппроксимировать функции с помощью ряда  полиномов  .  Другими словами, вы создаете функцию с множеством других меньших функций.  В качестве простого примера вы можете создать число 10 из меньших чисел: 1 + 2 + 3 + 4. Таким же образом вы можете объединить простые многочлены для создания более сложной функции. Зачем вам это делать?  1.  Во многих случаях вы знаете, как выглядит функция на графике; но вы не знаете этого уравнения. 2. Если сложную функцию представить как суперпозицию простых (то есть разложить в ряд), - то поведение сложной функции можно будет предсказать по анализу поведения простых. 3. Используя лишь стандартные операции сложения, умножения, вычитания, деления находит с заданной точностью результат. Точность зависит от того, сколько членов ряда взято в расчет. 4. Так как вычисления приближенные, то это уменьшает общее время расчета. Все зависит от заданной точности. Ряд Тейлора Многочле...
Далее...

Алгоритмы: Алгоритм Флойда-Уоршелла

-
Изображение
       Алгоритм Флойда — Уоршелла  —  динамический  алгоритм для нахождения кратчайших расстояний между всеми вершинами  взвешенного ориентированного графа .  Сложность алгоритма Три вложенных цикла содержат операцию, исполняемую за константное время.                                                                   то есть алгоритм имеет кубическую сложность, при этом простым расширением можно получить также информацию о кратчайших путях — помимо расстояния между двумя узлами записывать в матрицу идентификатор первого узла в пути. Сравнение с другими алгоритмами Алгоритм Флойда — Уоршелла является эффективным для расчёта всех кратчайших путей в  плотных графах , когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных ...
Далее...

Основные структуры данных: Множества

-
Изображение
Множество (set) — это структура данных, представляющая собой не организованный набор уникальных элементов одного типа. Данная структура  очень тесно связано с математическим понятием теории множеств. В наиболее упрощенном понимании, множество — это набор уникальных однотипных данных, рассматриваемых как единое целое. Давайте рассмотрим пример реализации множества и основных операций выполняемых с множествами на языке C#. На рисунке ниже схематически представлены два множества A и B, а также основные операции: объединение, пересечение, разность. Set Давайте подробнее рассмотрим все наиболее часто встречающиеся операции над множествами:                       Add — добавление элемента. Если такой элемент уже присутствует, то он не будет добавлен. Remove — удаление элемента из множества. Union — объединение множеств. Создается новое множество, включающее в себя все элементы из множества А и множества В. Если эле...
Далее...