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

Исключить использование функции END(L) там, где это возможно, заменив еедругими операторами. Например, условие р <> END(L) в строке (2) листинга 2.1можно заменить условием pl.next о nill, но в этом случае программа становится зависимой от реализации списка.Листинг 2.3. Функция ENDfunction END .( L: LIST ) : position;{ END возвращает указатель на последнюю ячейку-списка L }varq: position;begin(1)g: = L;(2)while gt.next <> nil do(3)g: = gt.next;(4)return(g)end; { END }Листинг 2.4 содержит процедуры для операторов INSERT, DELETE, LOCATE иMAKENULL, которые используются в реализации списков с помощью указателей.Другие необходимые операторы можно реализовать как одношаговые процедуры, заисключением PREVIOUS, где требуется просмотр списка с начала.

Мы оставляем на2.2. РЕАЛИЗАЦИЯ СПИСКОВ51писание этих процедур читателю в качестве упражнений. Отметим, что многие команды не требуют параметра L, списка, поэтому он опущен.Листинг 2.4. Реализация некоторых операторов при представлении списков с помощью указателей.•.. ..(1)(2)(3)(4)•:'"'.. '••"-""••.•.••':;.'...''".'".'.-.;•-•.'.'•у .. '•' .'• ..-' ..•..;;••:: . -•.•..'•"procedure INSERT ( x: elementtype; p: position );vartemp: position;begintemp:= pt.next;new(pT.next) ;рТ.лехсТ.element:= x;pT.next?.next:= tempend; { INSERT }procedure DELETE ( p: position );beginpt.next:= pT.nextt.nextend; { DELETE }function LOCATE ( x: elementtype; L: LIST ): position;varp: position;beginp:= L;while pT.next о nil doif pT.nextT.element = x thenreturn(p)elsep:= pT.next;return(p) { элемент не найден }end; { LOCATE }function MAKENULL ( var L: LIST ): position;beginnew(L) ;end;I/t.next: = nil;return(L){ 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. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХаb• •::,-.• .- ••-.;• т I-:'• >ft.''- '.'Ч 'af-+a—.\(2)VtempX(3)m*'b!•-J(4)V„^''••••-»•",- -Puc. 2.3. Диаграммы, иллюстрирующие работу процедуры INSERTabсJРис. 2.4.

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

Однако при использовании реализаций списков с помощью указателей значение переменной р (т.е. указатель в ячейке, содержащей элемент Ь) вследствие вставки нового элемента не изменится, продолжая указывать на ячейку, содержащую элемент с. Значение этой переменной надо изменить* если мы хотим использовать ее как указатель именно на третью позицию, т.е. как указатель наячейку, содержащую элемент Ь1.-•--.-• :.; ).;, •-..":: '.' Л гшжяш •• '!:•";.:,.•'.• ' >-.

,'."'.''•'''•••'• ' •• •,„.':"'Сравнение реализацийРазумеется, нас не может не интересовать вопрос о том, в каких ситуация* лучшеиспользовать реализацию списков с помощью указателей, а когда — с помощью массивов. Зачастую ответ на этот вопрос зависит от того, как,ие операторы должны выполняться над списками и как часто они будут использоваться. Иногда аргументом в пользу одной или другой реализации может служить максимальный размер обрабатываемых списков. Приведем несколько принципиальных соображений по этому поводу.1Конечно, можно привести многочисленные примеры ситуаций, когда нужноу чтобы переменная р продолжала указывать на позицию элемента с.2.2.

РЕАЛИЗАЦИЯ СПИСКОВ531.2.3.4.Реализация списков с помощью массивов требует указания максимального размера списка до начала выполнения программ. Если мы не можем заранее ограничить сверху длину обрабатываемых списков, то, очевидно, более рациональным выбором будет реализация списков с помощью указателей.Выполнение некоторых операторов в одной реализации требует больших вычислительных затрат, чем в другой. Например, процедуры INSERT и DELETE выполняются за постоянное число шагов в случае связанных списков любого размера, но требуют времени, пропорционального числу элементов, следующих завставляемым (или удаляемым) элементом, при использовании массивов.

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

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

Чтобы создать' описанное представление, определимvarSPACE: array [1..maxlength] of recordelement: elementtype;next: 'integerendДля списка L объявим целочисленную переменную (например, Lhead) в качествезаголовка списка L. Можно трактовать Lhead как курсор ячейки заголовка массиваSPACE с пустым значением поля element. Операторы списка можно реализовать точно так же, как описано выше в случае использования указателей.Здесь мы рассмотрим другую реализацию, позволяющую использовать ячейкизаголовков для специальных случаев вставки и удаления элементов в позиции 1.(Эту же технику можно использовать и в однонаправленных списках.) Для списка L значение SPACE[Lhead}.element равно первому элементу списка, значениеSPACE[Lhead].next является индексом ячейки массива, содержащей второй элементсписка, и т.д.

Нулевое значение Lhead или нуль в поле next указывает на "указательnil", это означает, что последующих элементов нет.54ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХСписок будет иметь целочисленный тип, поскольку заголовок, представляющийсписок в целом, является целочисленной переменной. Позиции также имеют тип целых чисел. Мы изменим соглашение о том, что позиция i в списке L является индексом ячейки, содержащей (i - 1)-й элемент списка L, поскольку поле next этой ячейкисодержит курсор, указывающий на i-й элемент списка. При необходимости первуюпозицию любого списка можно представить посредством О.