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

deader

Рис. 2.2. Связанный список

список

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

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

type

celltype = record

element: elementtype; next: t celltype

end;

LIST = t celltype; position = T celltype;

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

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

2. Исключить использование функции END(I,) там, где это возможно, заменив ее другими операторами. Например, условие р О END(L) в строке (2) листинга 2.1 можно заменить условием pT.next о nill, но в этом случае программа становится зависимой от реализации списка.

Листинг 2.3. Функция END

function END . { L: LIST ) : position;

{ END возвращает указатель на последнюю ячейкусписка L } var

q: position; begin

(1) g:=

(2) while gT.next <> nil do

(3) g:= gt.next;

(4) return tg) end; { END }

Листинг 2.4 содержит процедуры для операторов INSERT, DELETE, LOCATE и MAKENULL, которые используются в реализации списков с помощью указателей. Другие необходимые операторы можно реализовать как одношаговые процедуры, за исключением PREVIOUS, где требуется просмотр списка с начала. Мы оставляем на-



писание этих процедур читатедю в качестве упражнений. Отметим, что многие команды не требуют параметра L, списка, поэтому он опущен.

Листинг 2.4. Реализация некоторьгх операторов при представлении списков с помощью указателей

procedure DJSERT { х: elementtype; р: position ); var

temp: position;

begin

(1) temp:= pT.next;

(2) new(pT.next)

(3) pX .nextt .element := x;

(4) pT. nextt.wext:= temp end; { INSERT }

procedure DELETE { p: position ); begin

pT.wext:= pT. лехсТ. next

end; { DELETE }

function LOCATE { x: elementtype; L: LIST ): position; var

p: position; begin

p:= L;

while pt.next о nil do

if pT.nextt.eiement = x then return(p)

else

p:= pt.next; return(p) { элемент не найден } end; { LOCATE }

function MAKENULL { var L: LIST ) : position; begin

new{L) ;

bt .next: = nil; return(L)

end; { MAKENULL )

Механизм управдения указатедями в процедуре INSERT (дистинг 2.4) показан на рис. 2.3. Рис. 2.3, а показывает ситуацию перед выподнением процедуры INSERT. Мы хотим вставить новый эдемент перед эдементом Ъ, поэтому задаем р как указатель на ячейку, содержащую эдемент Ъ. В строке (2) дистинга создается новая ячейка, а в поде next ячейки, содержащей эдемент а, ставится указатель на новую ячейку. В строке (3) поле element вновь созданной ячейки принимает значение х, а в строке (4) поле next этой ячейки принимает значение переменной temp, которая хранит указатель на ячейку, содержащую элемент Б. На рис. 2.3, б представлен результат выполнения процедуры INSERT, где пунктирными линиями показаны новые указатели и номерами (совпадающими с номерами строк в листинге 2.4) помечены этапы из создания.

Процедура DELETE более простая. На рис. 2.4 показана схема манипулирования указателем в этой процедуре. Старые указатели показаны сплошными линиями, а новый - пунктирной.

52 ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХ



temp

f i

(3) (4)

Puc. 2.3. Диаграммы, иллюстрирующие работу процедуры INSERT

Рис. 2.4. Диаграмма, иллюстрирующая работу процедуры DELETE

Еще раз подчеркнем, что позиции в реализации однонаправленных списков ведут себя не так, как позиции в реализации списков посредством массивов. Предположим, что есть список из трех элементов а, Ь н с н переменная р типа position (позиция), чье текущее значение равно позиции 3, т.е. это указатель, находящийся в ячейке, содержащей элемент Ъ, и указывающий на ячейку, содержащую элемент с. Если теперь мы выполним команду вставки нового элемента х в позицию 2, так что список примет вид а, х, Ь, с, элемент Ъ переместится в позицию 3. Если бы мы использовали реализацию списка с помощью массива, то элементы ft и с должны были переместиться к концу массива, так что элемент b в самом деле должен оказаться на третьей позиции. Однако при использовании реализаций списков с помощью указателей значение переменной р (т.е. указатель в ячейке, содержащей элемент Ь) вследствие вставки нового элемента не изменится, продолжая указывать на ячейку, содержащую элемент с. Значение этой переменной надо изменить, если мы хотим использовать ее как указатель именно на третью позицию, т.е. как указатель на ячейку, содержащую элемент Ь.

Сравнение реализаций

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

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





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