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

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

2. Выполнение некоторых операторов в одной реализации требует больших вычислительных затрат, чем в другой. Например, процедуры INSERT и DELETE выполняются за постоянное число шагов в случае связанных списков любого размера, но требуют времени, пропорционального числу элементов, следующих за вставляемым (или удаляемым) элементом, при использовании массивов. И наоборот, время выполнения функций PREVIOUS и END постоянно при реализации списков посредством массивов, но это же время пропорционально длине списка в случае реализации, построенной с помощью указателей.

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

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

Реализация списков на основе курсоров

Некоторые языки программирования, например Fortran и Algol, не имеют указателей. Если мы работаем с такими языками, то можно смоделировать указатели с помощью курсоров, т.е. целых чисел, которые указывают на позиции элементов в массивах. Для всех списков элементов, имеющих тип elementtype, создадим один массив SPACE (область данных), состоящий из записей. Каждая запись будет состоять из поля element для элементов списка и поля next для целых чисел, используемых в качестве курсора. Чтобы создать описанное представление, определим

SPACE: array [1. .maxlength] of record element: elementtype; next: integer

Для списка L объявим целочисленную переменную (например, Lhead) в качестве заголовка списка L. Можно трактовать Lhead как курсор ячейки заголовка массива SPACE с пустым значением поля element. Операторы списка можно реализовать точно так же, как описано выше в случае использования указателей.

Здесь мы рассмотрим другую реализацию, позволяющую использовать ячейки заголовков для специальных случаев вставки и удаления элементов в позиции 1. (Эту же технику можно использовать и в однонаправленных списках.) Для списка L значение SPACElLheadI.elementpaBHO первому элементу списка, значение 8РАСЕ[Екеай\.пех1является индексом ячейки массива, содержащей второй элемент списка, и т.д. Нулевое значение Lhead или нуль в поле next указывает на "указатель nil", это означает, что последующих элементов нет.



Список будет иметь целочисленный тип, поскольку заголовок, представляющий список в целом, является целочисленной переменной. Позиции также имеют тип целых чисел. Мы изменим соглащение о том, что позиция / в списке L является индексом ячейки, содержащей (i - 1)-й элемент списка L, поскольку поле next этой ячейки содержит курсор, указывающий на i-й элемент списка. При необходимости первую позицию любого списка можно представить посредством О. Поскольку имя списка является обязательным параметром операторов, использующих позиции элементов, с помощью имен можно различать первые позиции различных списков. Позиция END(L) - это индекс последнего элемента списка L.

На рис. 2.5 показаны два списка, L - а, Ь, с vi М= d, е, вложенные в один массив SPACE длиной 10. Отметим, что все ячейки массива, незанятые элементами списков, образуют отдельный список, называемый свободным (ниже в листингах он обозначается available). Этот список используется как "источник" пустых ячеек при вставке элементов в любой список, а также как место хранения перед дальнейщим использованием освободивщихся (после удаления элементов) ячеек.

SPACE

свободньш


element next

Рис. 2.5. Реализация связанных списков с использованием курсоров

Для вставки элемента х в список L мы берем первую ячейку из свободного списка и помещаем ее в нужную позицию списка L. Далее элемент х помещается в поле element этой ячейки. Для удаления элемента х из списка L мы удаляем ячейку, содержащую элемент х, из списка и помещаем ее в начало свободного списка. Эти два действия являются частными случаями следующей операции. Пусть есть ячейка С, на которую указывает курсор р, необходимо сделать так, чтобы на ячейку С указывал другой курсор q, курсор ячейки С должен указывать на ячейку, на которую ранее указывал курсор q, курсор р должен указывать на ячейку, на которую до выполнения этой операции указывал курсор ячейки С. Другими словами, надо переместить ячейку из одного места списка (указываемого курсором р) в другое место того же или другого списка, новое место указывается курсором q. Например, если необходимо удалить элемент Ь из списка L (рис. 2.5), то С - это строка 8 в массиве SPACE, р равно 5РЛС£[5].гесд;(,а курсор q указывает на первую ячейку свободного списка. На рис. 2.6 схематически показан процесс перемещения ячейки С из одного списка в другой (курсоры до и после выполнения операции показаны соответственно сплощ-ными и пунктирными линиями). Код функции move (перемещение), выполняющей описанную операцию, приведен в листинге 2.5. Если в массиве нет ячейки С, то функция возвращает значение false (ложь), при успещном выполнении функции возвращается значение true (истина).



femp

Рис. 2.6. Перемещение ячейки из одного списка в другой

Листинг 2.5. Функция перемещенкш ячейки

function move ( var р, g: integer ) : boolean; var

temp: integer;

begin

if p = 0 then begin { ячейка не существует } writeln(Ячейка не существует) return(false)

else begin

temp:- q; q: = p;

p: = SPACE [ q] . nex t; SPACE[q). next: = temp; return(true)

end; { move }

В листинге 2.6 приведены коды процедур INSERT и DELETE, а также процедуры initialize (инициализация), связывающей ячейки массива SPACE в свободный список. В этих процедурах опущены проверки "нештатных" ситуаций, которые могут вызвать ошибки (оставляем написание кода этих проверок читателю в качестве упражнений). Кроме того, в Качестве упражнений оставляем читателю реализацию других операторов, выполняемых над списками (их код подобен коду аналогичных процедур при использовании указателей).

Листинг 2.6. Реализация некоторых операторов списка при использовании курсоров

procedure INSERT ( х: elementtype; р: position; var L: LIST ); begin

if p = 0 then begin { вставка x в первую позицию } if moveiavailable, L) then SPACE [L] .element: X

else { вставка x в позицию, отличную от первой } if. move (available, SPACE[p] .next) then SPACE[ SPACE[p] .next] . element := x end; { INSERT }





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.0036