Основные абстрактные типы данных: списки
Основные абстрактные типы данных: списки
В математике список представляет собой последовательность элементов определенного типа.
Список представляется в виде последовательности элементов: a1 ,a2, a3,…,an все аi имеют один тип.
Количество элементов п будем называть длиной списка. Если п 1, то a1 называется первым элементом, а an — последним элементом списка.
В случае n=0 имеем пустой список, который не содержит элементов.
Основные абстрактные типы данных: списки
Постулируем существование позиции, следующей за последним элементом списка.
Функция END(L) будет возвращать позицию, следующую за позицией n в n-элементном списке L.
Позиция END(L), рассматриваемая как расстояние от начала списка, может изменяться при увеличении или уменьшении списка
Основные абстрактные типы данных: списки
INSERT(x, р, L)
Этот оператор вставляет объект х в позицию р в списке L, перемещая элементы от позиции р и далее в следующую, более высокую позицию. Если список L состоит из элементов
a1 ,a2, a3 ,…,an
то после выполнения этого оператора он будет иметь вид a1 ,a2 , a3 ,ap-1,x,ap…,an
Если р принимает значение END(L), то будем иметь a1 ,a2, a3,…,an,, х.
Если в списке L нет позиции р, то результат выполнения этого оператора не определен.
Основные абстрактные типы данных: списки
LOCATE(x, L)
Функция возвращает позицию объекта х в списке L.
Если в списке объект х встречается несколько раз, то возвращается позиция первого от начала списка объекта х.
Если объекта х нет в списке L, то возвращается END(L).
Основные абстрактные типы данных: списки
RETRIEVE(p, L)
Эта функция возвращает элемент, который стоит в позиции р в списке L.
Результат не определен, если р = END(L)
или в списке L нет позиции р.
Отметим, что элементы должны быть того типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.
Основные абстрактные типы данных: списки
DELETE(p, L)
Этот оператор удаляет элемент в позиции р списка L.
если список L состоит из элементов a1 ,a2, a3,…,an то после выполнения этого оператора он будет иметь вид
a1 ,a2 , a3 ,…ap-1, ap+1…,an
Результат не определен, если в списке L нет позиции р или р = END(L).
Основные абстрактные типы данных: списки
NEXT(p, L) и PREVIOUS(p, L).
Функции возвращают соответственно следующую и предыдущую позиции от позиции р в списке L. Если р — последняя позиция в списке L, то NEXT(p, L) = END(L).
Функция NEXT не определена, когда р = END(L).
Функция PREVIOUS не определена, если р = 1.
Обе функции не определены, если в списке L нет позиции р.
Основные абстрактные типы данных: списки
MAKENULL(L)
Эта функция делает список L пустым и возвращает позицию END(L).
Основные абстрактные типы данных: списки
FIRST(L)
Эта функция возвращает первую позицию в списке L.
Если список пустой, то возвращается позиция END(L).
Основные абстрактные типы данных: списки
PRINTLIST(L)
Печатает элементы списка L в порядке из расположения.
Реализация списков
Представление списка с помощью массива
Реализация списков
Const maxl = 1000;
Type
List = record
elements: array[1..maxl] of eltype;
last: integer
end;
position = integer;
Реализация списков
Function EndL (var L:List) : position;
begin
EndL := L.last+1
end;
procedure INSERTL (x: eltype; р: position; var L: LIST );
{ вставляет элемент х в позицию р в списке L }
var
q : position;
begin
if L.last >= maxlength
then Writeln (’Список полон')
else if (р > L.last + 1) or (р < 1)
then
Writeln ('Такой позиции не существует')
else begin
for q:= L.last downto p do
{перемещение элементов на
одну позицию к концу списка } L.elements[q+l]:= L.elements[q];
L.last:= L.last + 1;
L.elements[p]:= x
end
end; { INSERT }
procedure DELETEL ( p: position; var L: LIST ) ;
{удаляет элемент в позиции р списка L }
var
q: position;
begin
if (p > L.last) or (p < 1)
then
Writeln ('Такой позиции не существует')
else
begin
L.last:= L.last – 1;
for q:= p to L.last do
{ перемещение элементов из позиций р+1, р+2, ...
на одну позицию к началу списка } L.elements[q] := L.elements [q+1]
end
end; { DELETE }
function LOCATE ( x:eltype;L: LIST ): position;
{ возвращает позицию элемента x в списке L }
var
q: position;
begin
for q:= 1 to L.last do
if L.elements[q] = x
then begin Locate := q; Exit (LOCATE)
end
else Locate := L.last+1 {х не найден }
end; { LOCATE }
страница 1
скачать
Другие похожие работы: