Главная Промышленная автоматика.

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

Необходимо сделать замечание о внутреннем цикле, состоящем из строк (4) - (8) листинга 2.1. Нри удалении элемента в позиции q, строка (6), элементы в позициях q + \, q + 2, ... и т.д. переходят на одну позицию влево. Иногда может случиться, что q является последней позицией в списке, тогда после удаления элемента позиция q становится равной END(L). Если теперь мы выполним оператор в строке (7), NEXT(END(I/), L), то получим неопределенный результат. Но такая ситуация невозможна, так как между очередными проверками q <> END(Z,) в строке (4) может выполниться или строка (6), или строка (7), но не обе сразу.

2.2. Реализация списков

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

Реализация списков посредством массивов

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

last

первый элемент

второй элемент

последний элемент

maxlenght

список

свободный

Рис. 2.1. Представление списка с помощью массива (пояснения в тексте)

Нри использовании массива мы определяем тип LIST как запись, имеющую два поля. Первое поле elements (элементы) - это элементы массива, чей размер считается достаточным для хранения списков любой длины, встречающихся в данной реализации или программе. Второе поле целочисленного типа last (последний) указывает на позицию последнего элемента списка в массиве. Как видно из рис. 2.1, i-й элемент списка, если 1 < i < last, находится в i-й ячейке массива. Позиции элементов в списке представимы в виде целых чисел, таким образом, i-я позиция - это просто целое число /. Функция END(I,) возвращает значение last + 1. Приведем необходимые объявления (константа maxlength определяет максимальный размер массива);

const

maxlength - 100 { или другое подход5щее число };

type



LIST = record

elements: з.тта.у[1. .maxlength] of elementtype; last: integer

end;

position = integer;

function END ( var L-. LIST ) : position,-begin

return(L.last + I) end; { END }

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

Листинг 2.2. Реализация операторов списка

procedure INSERT (х: elementtype; р: position; var Ь: LIST ); { INSERT вставляет элемент х в позждию р в списке L } var

g: position; begin

if L.last >= maxlength then

error(Список полон) else if (p > Z.last + 1) or (p < 1) then error С Такой позрщии не существует) else begin

for g:= i.iast downto p do

{ перемещение элементов из позиций р, р+1/ . - - на

одну П031ЩИЮ к KOHi списка } X.elenients[g+1] := L. elemer.ts[q] ; L. last:= L.last + 1; L.elementslp]:= x

end; { INSERT }

procedure DELETE { p: position; var L: LIST );

{ DELETE удаляет элемент в позиции р списка Ь } var

q: position; begin

if (p > X.Iast) or (p < 1) then

error(Такой позиции не существует) else begin

L.last:= L.last - 1; for g: = p to b.last do

{ перемещение элементов из позиций p-bl, p-l-2, ...

на одну позицию к началу списка } L. elements [д] := i. elements [g-t-l ]



end; { DELETE }

procedure LOCATE { x: elementtype; L: LIST ) : position; { LOCATE возвращает позицию элемента x в списке L } var

g: position; begin

for q:=l to L.last do

if L. elements[q] = x then return (g) ;

retum(i.last + 1) { элемент x не найден } end; { LOCATE }

Легко видеть, как можно записать другие операторы списка, используя данную реализацию списков. Например, функция FIRST всегда возвращает 1, функция NEXT возвращает значение, на единицу большее аргумента, а функция PREVIOUS возвращает значение, на единицу меньшее аргумента. Конечно, последние функции должны делать проверку корректности результата. Оператор MAKENULL(I,) устанавливает L.last в 0.

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

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

Реализация списков с помощью указателей

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

В этой реализации список состоит из ячеек, каждая из которых содержит элемент списка и указатель на следующую ячейку списка. Если список состоит из элементов ai, «2. то для / = 1, 2, л-1 ячейка, содержащая элемент а,-, имеет также

указатель на ячейку, содержащую элемент а,ч-1. Ячейка, содержащая элемент а„, имеет указатель nil (нуль). Имеется также ячейка header (заголовок), которая указывает на ячейку, содержащую а. Ячейка header не содержит элементов списка. В случае пустого списка заголовок имеет указатель nil, не указывающий ни на какую ячейку. На рис. 2.2 показан связанный список описанного вида.

Объявление ячейки заголовка "полноценной" ячейкой (хотя и не содержащей элементов списка) упрощает реализацию операторов списка на языке Pascal. Можете использовать указатели на заголовки, если хотите каким-либо специальным способом реализовать операторы вставки и удаления в самом начале списка.





0 1 2 3 4 5 6 7 8 9 10 11 [12] 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0037