Структуры данных и алгоритмы, страница 13

Но такая ситуация невозможна, так как между очередными проверками q <> END(L) в строке (4) может выполниться или строка (6), или строка (7), но не обе сразу.2.2. Реализация списковВ этом разделе речь пойдет о нескольких структурах данных, которые можно использовать для представления списков. Мы рассмотрим реализации списков с помощью массивов, указателей и курсоров. Каждая их этих реализаций осуществляет определенные операторы, выполняемые над списками, более эффективно, чем другая.Реализация списков посредством массивовПри реализации списков с помощью массивов элементы списка располагаются всмежных ячейках массива. Это представление позволяет легко просматривать содержимое списка и вставлять новые элементы в его конец.

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

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

Как видно из рис. 2.1, i-й элемент списка, если 1 < i < last, находится в i-й ячейке массива. Позиции элементов всписке представимы в виде целых чисел, таким образом, t-я позиция — это простоцелое число i. Функция END(L) возвращает значение last + 1. Приведем необходимые объявления (константа maxlength определяет максимальный размер массива):constmaxlength = 100 { или другое подходящее число };type48ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХLIST = recordelements: array[1..maxlength} of elementtype;last: integerend;•••position = integer;'function END ( var L: LIST ) : position;beginreturn(L.last + 1)end; { END }В листинге 2.2 показано, как можно реализовать операторы INSERT, DELETE иLOCATE при представлении списков с помощью массивов. Оператор INSERT перемещает элементы из позиций р, р + 1, ....

last в позиции р + 1, р + 2, ..., last + 1 ипомещает новый элемент в позицию р. Если в массиве уже нет места для нового элемента, то инициализируется подпрограмма error (ошибка), распечатывающая соответствующее сообщение, затем выполнение программы прекращается. ОператорDELETE удаляет элемент в позиции р, перемещая элементы из позицийр + 1, р + 2, ..., last в позиции р, р + 1, ..., last — 1. Функция LOCATE последовательно просматривает элементы массива для поиска заданного элемента.

Если этотэлемент не найден, то возвращается last + 1.Листинг 2.2. Реализация операторов списка:::•'-. : • ... •.•-. • ' лу,' '••:,'..'• ;•-":• V'- .•:•.'•'• . • . ' . . • • ' : -••'••':•.• ', -'. ,"Кprocedure INSERT (x: elementtype; р: position; var L: LIST );{ INSERT вставляет элемент x в позицию p в списке L },varg: position;beginif L.last >= maxlength thenerror('Список полон')else if (p > L.last +• 1) or (p < 1) thenerror С Такой позиции не существует')else beginfor q:= L.last downto p do{ перемещение элементов из позиций р, р+1, ... наодну позицию к концу списка }L.elements[g+1]:= L.elements[q];L.last:= L.last + 1;L.elements[p]:= xendend; { INSERT }procedure DELETE ( p: position; var L: LIST );{ DELETE удаляет элемент в позиции р списка L }varq: position;beginif (p > L.last) or (p < 1) thenerror('Такой позиции не существует')else beginL.last:= L.last - 1;for q:= p to L.last do{ перемещение элементов из позиций р+1, р+2, .;.на одну позицию к началу списка }L.elements[q] := L.elements[q+i]2.2.

РЕАЛИЗАЦИЯ СПИСКОВ49endend; { DELETE }'procedure LOCATE ( x: elementtype; i: LIST ): position;{ LOCATE возвращает позицию элемента х в списке L }varg: position;beginfor q:= 1 to L.last doif L.elements[q] = x thenreturn(g);return(L.last + 1) { элемент x не найден }end; { LOCATE }Легко видеть, как можно записать другие операторы списка, используя даннуюреализацию списков. Например, функция FIRST всегда возвращает 1, функцияNEXT возвращает значение, на единицу большее аргумента, а функция PREVIOUSвозвращает значение, на единицу меньшее аргумента. Конечно, последние функциидолжны делать проверку корректности результата.

Оператор MAKENULL(L) устанавливает L.last в 0.Итак, если выполнению процедуры PURGE (листинг 2.1) предшествуют определения типа elementtype и функции same, объявления типов LIST и position и заданиефункции END (как показано выше), написание процедуры DELETE (листинг 2.2),подходящая реализация простых процедур FIRST, NEXT и RETRIEVE, то процедураPURGE станет вполне работоспособной программой.Вначале написание всех этих процедур для управления доступом к основополагающим структурам может показаться трудоемким делом. Но если мы все же подвигнем себя на написание программ в терминах операторов управления абстрактными типами данными, не задерживаясь при этом на частных деталях их реализаций,то сможем изменять программы, изменяя реализацию этих операторов, не выполняяутомительного поиска тех мест в программах, где необходимо внести изменения вформу или способ доступа к основополагающим структурам данных.

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

Эта реализация освобождаетнас от использования непрерывной области памяти для хранения списка и, следовательно, от необходимости перемещения элементов списка при вставке или удаленииэлементов. Однако ценой за это удобство становится дополнительная память дляхранения указателей.В этой реализации список состоит из ячеек, каждая из которых содержит элементсписка и указатель на следующую ячейку списка. Если список состоит из элементовdi, а2, .... ап, то для i = 1, 2, ..., л-1 ячейка, содержащая элемент а,-, имеет такжеуказатель на ячейку, содержащую элемент ai+1. Ячейка, содержащая элемент а„,имеет указатель nil (нуль).

Имеется также ячейка header (заголовок), которая указывает на ячейку, содержащую а^. Ячейка header не содержит элементов списка1. Вслучае пустого списка заголовок имеет указатель nil, не указывающий ни на какуюячейку. На рис. 2.2 показан связанный список описанного вида.1Объявление ячейки заголовка "полноценной" ячейкой (хотя и не содержащей элементовсписка) упрощает реализацию операторов списка на языке Pascal.

Можете использовать указатели на заголовки, если хотите каким-либо специальным способом реализовать операторывставки и удаления в самом начале списка.50ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХ1header^23ГL-^*СПИСОКРис. 2.2. Связанный списокДля однонаправленных списков удобно использовать определение позицийэлементов, отличное от того определения позиций, которое применялось в реализации списков с помощью массивов. Здесь для i = 2, 3п позиция i определяется как указатель на ячейку, содержащую указатель на элемент а<.

Позиция 1 — это указатель в ячейке заголовка, а позиция END(L) — указатель впоследней ячейке списка L.Бывает, что тип списка совпадает с типом позиций, т.е. является указателем наячейку, реже на заголовок. Формально определить структуру связанного спискаможно следующим образом:typecelltype = recordelevent: elementtype;next: t celltypeend;LIST = t celltype;position = T celltype;В листинге 2.3 показан код функции END(L).

Результат функции получаем путемперемещения указателя q от начала списка к его концу, пока не будет достигнут конец списка, который определяется тем, что q становится указателем на ячейку с указателем nill. Отметим, что эта реализация функции END неэффективна, так как требует просмотра всего списка при каждом вычислении этой функции. Если необходимо частое использование данной функции, как в программе PURGE (листинг 2.1), томожно сделать на выбор следующее.1. Применить представление списков, которое не использует указатели на ячейки.2.