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

Организация данных

Проблемы с организацией данных

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

а) Память выделена на этапе компиляции:

const int N = 5;

int x1[N];

б) Память выделена на этапе исполнения программы с помощью операции new:

int *x2;

int n;

do{

cout << "n=";

cin >> n;

}while(n <= 0);

x2 = new int[n];

Теперь массивы x1 и x2 можно использовать, например, задать значения элементам этих массивов.

Но в обоих случаях после того, как память под массивы выделена, мы не можем изменять размеры этих массивов по своему усмотрению. Если быть более точным, то это справедливо только для случая а). Для варианта б) проблему решить можно. Но какой ценой?! Приведём возможную программную реализацию изменения размера динамического массива:

//пусть k — новый размер массива

int k = n + 1;

// выделяем новый участок памяти необходимого размера

int *t = new int[k];

// переписываем в него содержимое исходного массива x2

for(int i = 0; i < k && i < n; i++)

t[i] = x2[i];

// освобождаем память, на которую указывал x2

delete []x2;

// настраиваем x2 на новый участок памяти

x2 = t;

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

Определение и классификация динамических структур данных

Для того чтобы в процессе выполнения программы произвольно добавлять и удалять данные, необходимо организовать наши данные не в массив, а в нечто другое. Если к элементу данных добавить ещё и указатель, в котором будет храниться адрес какого-то другого элемента, то это и будет кардинальным решением проблемы. Такая организация представления и хранения данных называется динамической структурой данных.

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

Кроме того, динамические структуры позволяют нам организовать данные так, чтобы их представление в программе было максимально приближено к тому, как эти данные выглядят в реальности. Так, для моделирования обслуживания очереди к кассе в магазине лучше всего подойдет динамическая структура данных под названием «очередь», а не пресловутый массив, а для представления сети автомобильных дорог массив вообще неприемлем. Здесь нужна именно «сеть».

Динамические структуры данных бывают линейные и нелинейные. В линейной динамической структуре данные связываются в цепочку. К линейным структурам относятся списки (односвязные, двухсвязные, кольцевые), стеки, очереди (односторонние, двухсторонние, очереди с приоритетами). Организация нелинейных структур более сложная. Нелинейные структуры представляются, как правило, в виде дерева (каждый элемент имеет некоторое количество связей, например, в бинарном дереве каждый элемент (узел) имеет ссылку на левый и правый элемент).

Рассмотрим более подробно хотя бы некоторые виды динамических структур. Начнём с линейных списков.

Списки

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

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

Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (next). Поле ссылки последнего элемента должно содержать пустой указатель (NULL).

Так как ссылка всего одна (только на следующий элемент), то такой список является односвязным.

Когда говорят о линейном списке, то, как правило, подразумевают именно односвязный список.

Пример. Сформировать список, содержащий целые числа 3, 5, 1, 9.

Решение. При работе с динамическими структурами данных можно рекомендовать следующий порядок действий.

а) Прежде всего необходимо определить две структуры:

1. структура, содержащая характеристики данных, то есть все те поля с данными, которые необходимы для решения поставленной задачи (в нашем случае имеется всего одно поле целого типа). Назовём эту структуру Data;

2. структура, содержащая поле типа Data и поле — адрес последующего элемента next. Вторую структуру назовём List.

Тексты этих структур необходимо расположить в начале программы (до main() и других функций). Вот возможная реализация структур:

struct Data

{

int a;

};

struct List

{

Data d;

List *next;

};

Такой подход позволит в дальнейшем изменять в широких пределах структуру с собственно данными, никак не затрагивая при этом основную структуру List.

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

б) В программе (обычно в функции main()) определяем указатель на начало будущего списка:

List *u = NULL;

Пока список пуст, и указатель явно задан равным константе NULL.

в) Выполняем первоначальное заполнение списка.

Создадим первый элемент:

u = new List; // Выделяем память под элемент списка

u->d.a = 3; // Заполняем поля с данными

// (здесь это всего одно поле)

u->next = NULL;// Указатель на следующий элемент пуст

После включения первого элемента список можно изобразить так:

Продолжим формирование списка, добавляя новые элементы в его конец. Для удобства заведём вспомогательную переменную-указатель, которая будет хранить адрес последнего элемента списка:

List *x;

x = u; // Сейчас последний элемент списка совпадает с его началом

Таким образом, к области памяти можно обратиться через два указателя.

Выделяем место в памяти для следующего элемента списка и перенаправляем указатель x на выделенную область памяти:

x->next = new List;

x = x->next;

Затем определяем значение этого элемента списка:

x->d.a = 5;

x->next = NULL;

Получилась такая схема:

Этот процесс продолжаем до тех пор, пока не будет сформирован весь список.