yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Алгоритмы структуры данных

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

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

const

maxiength = 100 { или другое подходящее число };

type

LIST = record

elements: array[1..maxlength] of elementtype;

last: integer

end;

position = integer;

function END ( var L: LIST ): position;

begin

return(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. Реализация операторов списка

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

{ INSERT вставляет элемент х в позицию р В списке L }

var

q: position;

begin

if L.last >= maxlength then

error('Список полон')

else if (p > L.last + 1) or (p < 1) then

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

else begin

for q:= L.last downto p do

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

одну позицию к концу списка }

L.elements[q+l]:= L.elements[q] ;

L.last:- L.last + 1;

L.elements [p]:= x

end

end; { INSERT }

 

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

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

var

q: position;

begin

if (p > L.last) or (p < 1) then

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

else begin

L.last:= L.last - 1;

for q:= p to L.last do

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

на одну позицию к началу списка }

L.elements[q] := L.elements[q+i]

end

end; { DELETE }

procedure LOCATE ( x: elementtype; L: LIST ): position;

{ LOCATE возвращает позицию элемента х в списке L

var   

g: position;

begin

for q:= 1 to L.last do ,

if L.elements[q] = x then   

return (q) ;

return (L. last +1) { элемент х не найден }

end; { LOCATE }

 

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

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

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

 

18