Реализация списков:динамические структуры ListList clasclas структура одного элемента type LIST = celltype; celltype = record element: eltype; next: LIST. - презентация

1 Реализация списков:динамические структуры ListList clasclas структура одного элемента type LIST = celltype; celltype = record element: eltype; next: LIST end; position = celltype;

2 Реализация списков:динамические структуры Функция ENDL function ENDL ( L: LIST ): position; Var q: position; begin q:= L; while q.next nil do q:= q.next; ENDL :=q end;

3 Реализация списков:динамические структуры Оператор INSERT procedure INSERT (x: eltype; p:position); var temp: position; begin temp:= p.next; new(p. next); p.next.element := x; p.next.next:= temp end; { INSERT } INSERT

4 Реализация списков:динамические структуры Процедура DELETE procedure DELETE ( p: position ) ; begin p.next:= p.next.next end; { DELETE } delete

5 Реализация списков:динамические структуры Функция LOCATE function LOCATE ( x: eltype; L: LIST ): position; var p: position; begin p:= L; while р.next nil do if p.next.element = x then begin LOCATE := p; Exit end else p:= p.next; LOCATE := p{ элемент не найден } end; { LOCATE )

6 Сравнение реализаций Реализация списков с помощью массивов расточительна в отношении компьютерной памяти. Реализация с помощью указателей использует столько памяти, сколько необходимо для хранения текущего списка, но требует дополнительную память для указателя каждой ячейки. Таким образом, в разных ситуациях по критерию используемой памяти могут быть выгодны разные реализации.

7 Реализация на основе курсоров cursor Var Space: array [1..maxlength] of record element: eltype; next :integer end;

8 Реализация на основе курсоров move function move ( var p, q: integer ) : boolean; var Temp: integer; begin if p = 0 then begin writeln (Элемент не существует') move := false end

9 Реализация на основе курсоров else begin temp:= q; q:= p; p:= SPACE[q].next; SPACE [q]. next: = temp; move := true end end; { move }

10 Двунаправленные списки

11 type point = celltype; celltype = record element: eltype; next, previous: point end; position = point;

12 Двунаправленные списки procedure DELETE ( var р: position ) ; begin if p.previous nil then { удаление ячейки, которая не является первой} p.previous.next:= p.next; if p.next nil then { удаление ячейки, которая не является последней } p.next. previous:= p.previous Dispose (P); end;

13 Двунаправленные списки

14 Стеки (stack) Стек это специальный тип списка, в котором все вставки и удаления выполняются в начале, называемом вершиной (top). Стеки также иногда называют "магазинами" или список с дисциплиной LIFO (last-in-first-out).

15 Стеки (stack)

16 MAKENULL(S). Делает стек S пустым. TOP(S)-возвращает элемент из вершины стека S - RETRIEVE(FIRST(S), S). POP(S). Удаляет элемент из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как DELETE(FIRST(S), S).

17 Стеки (stack) PUSH (x, S). Помещает элемент х в вершину стека: INSERT (x, FIRST (S), S) EMPTY (S) равна TRUE, если стек пустой и FALSE, в противном случае

18 Реализация Стеков type STACK = record top: integer; element: array[1..maxlength] of eltype end

19 Реализация Стеков procedure MAKENULL (var S: STACK ) ; begin S.top:= maxlength + 1 end; { MAKENULL }

20 Реализация Стеков function EMPTY ( S: STACK ): boolean; begin if S.top > maxlength then empty := true else empty := false end; { EMPTY }

21 Реализация Стеков function TOPS ( var S: STACK ): eltype; begin if EMPTY(S) then Write('Стек пустой') else Tops := S.element [S.top]) end; { TOPS }

22 Реализация Стеков procedure POP ( var S: STACK ) ; begin if EMPTY(S) then Write ('Стек пустой') else S.top:= S.top + 1 end; { POP }

23 Реализация Стеков procedure PUSH (x:eltype; var S:STACK) ; begin if S. top = 1 then Write('Стек полон') else begin S.top:= S.top – 1; S.elements[S.top]:= x end end; { PUSH }

24 Реализация Стеков (Указатели) Type PElement = ^TElement; TElement = record Item: TItem; Next: PElement; end; Var TopPointer: PElement;

25 Реализация Стеков procedure ClearStack(Var TopPointer: PElement); Var Temp: PElement; Begin while TopPointernil do begin Temp := TopPointer; TopPointer := TopPointer^.Next; Dispose(Temp); end;

26 Реализация Стеков function IsEmpty( Var TopPointer: PElement ): Boolean; begin IsEmpty := TopPointer=nil; end;

27 Реализация Стеков procedure Push( Var TopPointer: PElement, Item: TItem); Var Temp: PElement; Begin Temp := New(PElement); Temp^.Item := Item; Temp^.Next := TopPointer; TopPointer := Temp; end;

28 Реализация Стеков function Pop(Var TopPointer: PElement ): TItem; Var Temp: PElement; begin if TopPointer=nil then RunError; Pop := TopPointer^.Item; Temp :=TopPointer^.Next; Dispose(TopPointer); TopPointer := Temp; end;

29 Реализация Стеков Использование стека - Вложенные вызовы подпрограмм - Размещение локальных переменных в блоках - Преобразование арифметических выражений в польскую запись - Аппаратные стеки

30 Реализация Стеков Польская запись: 1-2/3*4+5 ссылка

31 Очереди Очередь – специальный тип списка- (queue), в котором вставка элементов осуществляется с одного конца (rear), а удаление с другого (front). Очереди также называют "списками типа FIFO" (first-in-first-out)

32 Операторы работы с очередями MAKENULL(Q) очищает очередь Q, делая ее пустой FRONT(Q) функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q), Q) ENQUEUE(x, Q) вставляет элемент х в конец очереди Q: INSERT(x, END(Q), Q).

33 Операторы работы с очередями DEQUEUE(Q) удаляет первый элемент очереди Q: DELETE(FIRST(Q), Q). EMPTY(Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью.

34 Реализация очередей Элемент очереди: type point = celltype; celltype = record element: eltype; next: point end;

35 Реализация очередей АТД QUEUE type queue = record front,rear: point end;

36 MAKENULL procedure MAKENULL (var Q: QUEUE ) ; begin new(Q. front); Q. front.next:= nil; Q.rear:= Q. front end; { MAKENULL }

37 EMPTY function EMPTY ( Q: QUEUE ): boolean; begin if Q.front = Q.rear then Empty := true else Empty := false end; { EMPTY }

38 FRONT function FRONT ( Q: QUEUE ): eltype ; begin if EMPTY(Q) then Write('Очередь пуста') else Front := Q. Front.next.element end; { FRONT }

39 ENQUEUE procedure ENQUEUE(x:eltype;var Q:QUEUE) ; begin New (Q.rear.next) ; Q.rear:= Q.rear.next; Q.rear.element:= x; O.rear.next:= nil end; { ENQUEUE }

40 DEQUEUE procedure DEQUEUE ( var Q: QUEUE ) ; begin if EMPTY(Q) then Write('Очередь пуста') else Q.front:= Q.front.next end; {DEQUEUE}

41 Примеры очередей 1. Буфер клавиатуры 2. Очереди в многозадачных ОС 3. Очереди сообщений для параллельно выполняемых задач 4. Очереди в имитационном моделировании

42 Деки(deq - double ended queue) Дек – структура данных с двусторонним доступом, хранящая упорядоченное множество значений, для которой определены следующие операции:

43 Деки очистить дек (сделать структуру пустой); проверить на пустоту; добавить элемент в начало; добавить элемент в конец; взять элемент из начала; взять элемент из конца;

44 Циклические списки

45

46 Мультисписки