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

А теперь рассмотрим важную прикладную задачу.

1. Необходимо средство, которое могло бы представить неопределенное количество элементов.

2. Каждый элемент представляет из себя два целых числа и одно дробное (float).

3. Размер такого " массива" может очень сильно меняться в процессе работы.

Если бы не последнее условие, то нам идеально подошел бы динамический массив. Но тут он оказывается бессильным – если мы будем каждый раз при добавлении нового элемента делать realloc(), то очень скоро получим нехватку памяти – в результате копирования данных в новое место память может оказаться фрагментированной настолько, что в ней просто не найдется непрерывного блока требуемой длины. Так что динамические массивы отпадают. Что делать?

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

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

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

Что, если мы применим этот подход? Он как раз идеально подходит нашим условиям. Конструкции такого типа называют связными списками.

Итак, первым делом опишем структуру элемента:

struct TElem

{ int Int1, Int2;

float Float;

struct TElem *Next; };

Выделенное поле – это и есть указатель на следующий элемент нашего списка.

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

Все наши функции манипулируют связным списком.

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

Поэтому в качестве первого фактического входного параметра для всех функций используется

struct TElem **List.

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

Вместе с тем существуют и другие виды списков:

· Двунаправленный список – это список, в котором в каждом элементе наряду с указателем на следующий элемент присутствует указатель на предыдущий элемент. У него, конечно, есть недостаток – каждый элемент занимает в памяти на 4 байта больше, чем предыдущий. В связи с этим не стоит создавать список char 'ов. Но есть и достоинства – такой список можно читать в обоих направлениях (одинарный список хорошо читается в одном направлении и очень плохо в другом), для работы с ним достаточно одного указателя. Разумеется, с ним несколько сложнее обращаться, но вы как программист должны взять это на себя.

· Кольцевой список – разновидность однонаправленного списка, в котором последний элемент указывает не на NULL, а на первый элемент. Таким образом образуется кольцо из элементов. Находит применение, скажем, в списках элементов окна. Разумеется, манипуляции с ним проходят несколько по-другому.

· Очередь – является сильно упрощенной разновидностью связного списка – для нее разрешено только добавление элемента в самый конец (хвост) очереди и извлечение элемента из начала (головы) очереди. Извлечение элемента влечет за собой его удаление. В некоторых реализациях предусмотрен " просмотр" элемента (т.н. peek) – получение первого элемента очереди без его удаления. Очередь реализует принцип FIFO (First In First Out – первым пришел, первым ушел). Применяется, например, при организации списка событий – пришедшее первым нажатие клавиши должно быть обработано первым.

· Стек можно представить в виде запаянной с одного конца трубочки, в которую помещаются шарики (элементы стека). Понятно, что поместив такой шарик в стек, мы не сможем получить доступ к оствльным элементам, пока не вытащим его. Формализую: стек – это разновидность однонаправленного списка, для которого разрешено только добавление элемента в начало (голову) стека и удаление элемента из головы же. Для работы со стеком достаточно одного указателя на голову. Стек реализует принцип LIFO (Last In First Out – последним пришел, первым ушел).

· Дерево является очень специфическим видом списка – каждый элемент ссылается не на один, а на несколько следующих. Наибольшее распространение получили бинарные деревья, в которых каждый элемент (элементы дерева называются узлами) ссылается на два своих подузла. Добавление элементов в дерево разрешается лишь один из его многочисленных концов (листьев). Удаление – даже не знаю, никогда не сталкивался... Деревья хорошо обрабатываются рекурсивными алгоритмами (каждый узел дерева – сам по себе дерево).

Вывод: Вообще целесообразно иметь один хорошо написанный универсальный двунаправленный список и использовать его при необходимости. Что должно быть элементом такого списка? Разумеется, void*. Таким образом создавать элемент мы должны сами – соответствующие функции Insert и Remove будут лишь связывать его в список. Я предлагаю такой список функций:

struct TElem

{

void *Item;

struct TElem *Next, *Prev;

}

void InsertBefore (struct TElem *Elem, void *NewItem);

void InsertAfter (struct TElem *Elem, void *NewItem);

void RemoveElem (struct TElem *Elem);

struct TElem *Advance (struct TElem *Elem, int Count);

void *GetItem (struct TElem *Elem);

void DeleteList (struct TElem *Elem);

Теперь более подробно о каждой из функций.

· InsertBefore и InsertAfter – создают элемент со значением Item и помещают соответственно перед или после элемента Elem. Если Elem == NULL, то создается список из одного элемента – Item.

· RemoveElem – удаляет из списка элемент Elem.

· Advance – продвигается в списке на | Count | позиций от элемента Elem вперед, если Count > 0, и назад, если Count < 0. Если имеет место выход за границы списка, функция возвращает NULL, в противном случае – указатель на соответствующий элемент списка.

· GetItem – возвращает поле Item элемента Elem.

· DeleteList – удаляет весь список по любому его элементу.

Вы можете спросить, зачем нужна функция GetItem, ведь можно и самому прочитать поле Item. Отвечаю: читать поле Item нельзя. В нашем конкретном случае, конечно, этим можно пренебречь, но вообще-то правила написания программ требуют, чтобы все взаимодействия объекта с внешним миром должны осуществляться через функциональный интерфейс. А мы уже сделали полноценный объект – связный список. В противном случае, если кто угодно сможет изменять любые поля объекта, корректная работа может стать невозможной. Поэтому сразу приучайтесь писать хорошо. Когда мы начнем классы, это умение вам сильно понадобится.

Осталась одна маленькая деталь: написать реализацию всего вышеперечисленного.

Следует помнить, что связные списки – структура крайне неустойчивая, поэтому грамотно проектируйте их. 1) Попытка удаления элемента без исключения его из списка приведет к тому, что весь список окажется разрушенным. 2) Потерянный указатель – и вы не сможете больше получить доступ к списку, даже не сможете его удалить. Так что внимательно смотрите, и используйте отладчик.