АБСТРАКТНЫЙ ТИП ДАННЫХ СПИСОК Лекция 1. Примеры списков списки магазинных покупок списки дел расписания поездов бланки заказов. - презентация

1 АБСТРАКТНЫЙ ТИП ДАННЫХ СПИСОК Лекция 1

2 Примеры списков списки магазинных покупок списки дел расписания поездов бланки заказов

3 o Списки чрезвычайно гибкая структура. o В вычислительной технике списки находят своё применение в таких задачах как поиск информации, трансляция языков программирования и компьютерное моделирование.

4 Определение Математически, список (List) – последовательность из нуля или более элементов заданного типа (TElement). a 1, a 2,..., a n, где n 0 и каждый a i типа TElement.

5 Длина списка - количество элементов n. Если n 1, то a 1 называется первым элементом, а a n – последним элементом списка. Элемент a i предшествует элементу a i+1 для i = 1,2,…,n-1 и a i следует за a i-1 для i = 2,3,…,n. Каждый элемент списка a i имеет позицию i, i=1,2,…,n.

6 Операторы АТД "Список" Обозначим : L – список объектов типа TElement, x – объект этого типа, p – позиция элемента в списке. Функция End(L) будет возвращать позицию, следующую за позицией n в n- элементном списке L. 1. INSERT(x, р, L). Если список L состоит из элементов a 1, a 2,..., а n, то после выполнения этого оператора он будет иметь вид а 1, а 2,..., а р -1, х, а р,..., a n. Если р принимает значение End(L), то будем иметь a 1, a 2,..., a n, х. Если в списке L нет позиции р, то результат выполнения этого оператора не определен.

7 Операторы АТД "Список" 2. LOCATE(x, L). 3. RETRIEVE(p, L). 4. DELETE(p, L). Если список L состоит из элементов a 1, a 2,..., а n, то после выполнения этого оператора он будет иметь вид а 1, а 2,..., a p-1,a p+1,..., а n. 5. NEXT(p, L) и PREVIOUS(p, L). 6. MAKENULL(L). 7. FIRST(L). 8. PRINTLIST(L).

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

9 Приведем необходимые объявления const MaxLength = 100; type TList = record Elements: array[1..MaxLength] of TElement; Last : Integer ; end ; TPosition = Integer; function End(var L: TList): TPosition; begin Result := L.Last + 1; end; procedure Error(strMessage: string); begin Writeln(strMessage); Readln; Halt() end;

10 Реализация оператора списка INSERT procedure INSERT (x: TElement; p: TPosition; var L: TList) ; var q: TPosition; begin if L.last >= maxlength then Error(' Список полон ') else if (p > L.last + 1) or (p < 1) then error(' Такой позиции не существует ') else begin for q := L. last downto p do {перемещение элементов из позиций p, p+1, на одну позицию к концу списка} L.elements[q + 1] := L.elements[q]; L.last := L.last + 1; L.elements[p] := x end end; { INSERT }

11 Реализация оператора списка DELETE procedure DELETE (p: TPosition; var L: TList); var q: TPosition; 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, p+2,... на одну позицию к началу списка} L.elements[q] := L.elements[q + 1] end end; { DELETE }

12 Реализация оператора списка LOCATE procedure LOCATE (x: TElementType; L: TList): TPosition; var q: TPosition; begin for q := 1 to L.last do if L.elements[q] = x then begin Result := q; Exit; end; Result := L.last + 1 {элемент х не найден} end; // LOCATE

13 Задания 1. Реализуйте АТД Список для любого типа данных и его операторы ( INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, FIRST, PRINTLIST ), используя массив. 2. Создайте программу позволяющую объединять несколько списков в один.