Основные абстрактные типы данных: списки В математике список представляет собой последовательность элементов определенного типа. Список представляется. - презентация

1 Основные абстрактные типы данных: списки В математике список представляет собой последовательность элементов определенного типа. Список представляется в виде последовательности элементов: a 1,a 2, a 3,…,a n все а i имеют один тип. Количество элементов п будем называть длиной списка. Если п 1, то a 1 называется первым элементом, а a n последним элементом списка. В случае n=0 имеем пустой список, который не содержит элементов.

2 Основные абстрактные типы данных: списки П остулируем существование позиции, следующей за последним элементом списка. Функция END( L) будет возвращать позицию, следующую за позицией n в n -элементном списке L. П озиция END (L), рассматриваемая как расстояние от начала списка, может изменяться при увеличении или уменьш е нии списка

3 Основные абстрактные типы данных: списки INSERT(x, р, L) Этот оператор вставляет объект х в позицию р в списке L, перемещая элементы от позиции р и далее в следующую, более высокую позицию. Если список L состоит из элементов a 1,a 2, a 3,…,a n то после выполнения этого оператора он будет иметь вид a 1,a 2, a 3,a p-1,x,a p …,a n Если р принимает значение END(L), то будем иметь a 1,a 2, a 3,…,a n,, х. Если в списке L нет позиции р, то результат выполнения этого оператора не определен.

4 Основные абстрактные типы данных: списки LOCATE(x, L) Функция возвращает позицию объекта х в списке L. Если в списке объект х встречается несколько раз, то возвращается позиция первого от начала списка объекта х. Если объекта х нет в списке L, то возвращается END(L).

5 Основные абстрактные типы данных: списки RETRIEVE(p, L) Эта функция возвращает элемент, который стоит в позиции р в списке L. Результат не определен, если р = END(L) или в списке L нет позиции р. Отметим, что элементы должны быть того типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.

6 Основные абстрактные типы данных: списки DELETE(p, L) Этот оператор удаляет элемент в позиции р списка L. если список L состоит из элементов a 1,a 2, a 3,…,a n то после выполнения этого оператора он будет иметь вид a 1,a 2, a 3,…a p-1, a p+1 …,a n Результат не определен, если в списке L нет позиции р или р = END(L).

7 Основные абстрактные типы данных: списки NEXT(p, L) и PREVIOUS(p, L). Функции возвращают соответственно следующую и предыдущую позиции от позиции р в списке L. Если р последняя позиция в списке L, то NEXT(p, L) = END(L). Функция NEXT не определена, когда р = END(L). Функция PREVIOUS не определена, если р = 1. Обе функции не определены, если в списке L нет позиции р.

8 Основные абстрактные типы данных: списки MAKENULL(L) Эта функция делает список L пустым и возвращает позицию END(L).

9 Основные абстрактные типы данных: списки FIRST(L) Эта функция возвращает первую позицию в списке L. Если список пустой, то возвращается позиция END(L).

10 Основные абстрактные типы данных: списки PRINTLIST(L) Печатает элементы списка L в порядке из расположения.

11 Реализация списков Представление списка с помощью массива Первый элемент Второй элемент Последний элемент 1 2 список свободный last maxlenght

12 Реализация списков Const maxl = 1000; Type List = record elements: array[1..maxl] of eltype; last: integer end; position = integer;

13 Реализация списков Function EndL (var L:List) : position; begin EndL := L.last+1 end;

14 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

15 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 }

16 procedure DELETEL ( p: position; var L: LIST ) ; {удаляет элемент в позиции р списка L } var q: position; begin if (p > L.last) or (p < 1) then Writeln ('Такой позиции не существует') else

17 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 }

18 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 }