15.12.2013САОД, кафедра ОСУ1 Реализация списков:динамические структуры ListList classclass структура одного элемента type LIST = celltype; celltype = record. - презентация

1 САОД, кафедра ОСУ1 Реализация списков:динамические структуры ListList classclass структура одного элемента type LIST = celltype; celltype = record element: eltype; next: LIST end; position = celltype; Java_nodeJava_node

2 САОД кафедра ОСУ 2 Поиск в списке

3 САОД кафедра ОСУ 3 Поиск в списке List_Search(L, к) 1 х head[L] 2 while х nil и кеу[х] k 3 do х next[x] 4 return x Временная сложность T(n) = O(n)

4 САОД, кафедра ОСУ4 Реализация списков:динамические структуры Функция ENDL function ENDL ( L: LIST ): position; var q: position; begin q:= L; while q.next nil do q:= q.next; ENDL :=q end;

5 САОД, кафедра ОСУ5 Реализация списков:динамические структуры Оператор 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

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

7 САОД, кафедра ОСУ7 Реализация списков:динамические структуры Функция 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 )

8 САОД, кафедра ОСУ8 Сравнение реализаций 1.Реализация списков с помощью массивов расточительна в отношении компьютерной памяти. 2.Реализация с помощью указателей использует столько памяти, сколько необходимо для хранения текущего списка, но требует дополнительную память для указателя каждой ячейки. 3.Таким образом, в разных ситуациях по критерию используемой памяти могут быть выгодны разные реализации.

9 САОД, кафедра ОСУ9 Реализация на основе курсоров cursor var Space: array [1..maxlength] of record element: eltype; next :integer end;

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

11 САОД, кафедра ОСУ11 Реализация на основе курсоров else begin temp:= q; q:= p; p:= SPACE[q].next; SPACE [q]. next: = temp; move := true end end; { move }

12 САОД, кафедра ОСУ12 Двунаправленные списки

13 САОД кафедра ОСУ 13 Вставка в списке (на 1 позицию) List_Insert(L, x) 1 nехt[х] head[L] 2 if head[L] nil 3 then prev[head[L]] x 4 head[L] x 5 prev[x] nil Временная сложность T(n) = O(1)

14 САОД кафедра ОСУ 14 Удаление в списке List_Delete(L, х) 1 if prev[x] nil 2 then next[prev[x]] next[x] 3 else head[L] next[x] 4 if next[x] nil 5then prev[next[x]] prev[x] Временная сложность T(n) = O(1) Удаление с заданным ключом T(n) = O(n)

15 САОД, кафедра ОСУ15 Двунаправленные списки АТД «связный список» (linked list) является объектно - ориентированным расширением конкретной структуры данных связного списка. Он описывает методы доступа и обновления, основанные на инкапсуляции узлов связного списка. Данные абстрактные узлы-объекты называются позициями, так как содержат ссылки на «места» хранения элементов, независимые от особенностей реализации списка.

16 САОД, кафедра ОСУ16 Двунаправленные списки В данной схеме список рассматривается как контейнер элементов, хранящихся в определенных позициях, и эти позиции линейно упорядочены. Позиция сама по себе является абстрактным типом данных, который поддерживает следующий метод: element(): возвращает элемент, хранящийся в данной позиции. Input: нет; Output: объект.

17 САОД, кафедра ОСУ17 Двунаправленные списки АТД «связный список». поддерживает следующие методы, выполняемые над списком S: first(): возвращает позицию первого элемента списка S last(): возвращает позицию последнего элемента списка S isFirst (p) : возвращает логическое значение, показывающее, является ли данная позиция первой в списке. isLast( p) возвращает логическое значение, показывающее, является ли данная позиция последней в списке.

18 САОД, кафедра ОСУ18 Двунаправленные списки before(p): возвращает позицию элемента S, который предшествует элементу позиции p,если р является первой позицией, выдается сообщение об ошибке. after(p): возвращает позицию элемента S, который следует элементом позиции p; если p является последней позицией, выдается сообщение об ошибке. replaceElement(p,e): замещает элемент в позиции р на е и возвращает элемент, который до этого был в позиции р.

19 САОД, кафедра ОСУ19 Двунаправленные списки swapElements(p,q): меняет местами элементы в позициях р и q insertFirst(e): вставляет новый элемент е в S в качестве первого элемента списка. insertLast(e): вставляет новый элемент е в S качестве последнего элемента списка. insertBefore(p, e): вставляет новый элемент е в S перед позицией p если р является первой позицией, выдается сообщение об ошибке. insertAfter(p, e): вставляет новый элемент е в S после позиции p если р является последней позицией, выдается сообщение об ошибке

20 САОД, кафедра ОСУ20 Двунаправленные списки remove(p): удаляет из S элемент в позиции р.

21 САОД, кафедра ОСУ21 Двунаправленные списки

22 САОД, кафедра ОСУ22 Двунаправленные списки интерфейс Listинтерфейс List

23 САОД, кафедра ОСУ23 Двунаправленные списки type point = celltype; celltype = record element: eltype; next, previous: point end; position = point;

24 САОД, кафедра ОСУ24 Двунаправленные списки 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;

25 САОД, кафедра ОСУ25 Двунаправленные списки

26 САОД, кафедра ОСУ26 Коллекции Коллекция LinkedList реализует связанный список. В отличие от массива, который хранит объекты в последовательных ячейках памяти, связанный список хранит объекты отдельно, но вместе со ссылками на следующее и предыдущее звенья последовательности.

27 САОД, кафедра ОСУ27 Коллекции В добавление ко всем имеющимся методам в LinkedList реализованы методы void addFirst(Object ob) void addLast(Object ob) Object getFirst( ) Object getLast( ) Object removeFirst( ) Object removeLast ( )

28 САОД, кафедра ОСУ28 Коллекции /* пример: добавление и удаление элементов : */ import java.util.*; public class DemoLinkedList { public static void main(String[] args){ LinkedList aL = new LinkedList(); for(int i = 10; i

29 САОД, кафедра ОСУ29 Коллекции Iterator it = aL.iterator(); while(it.hasNext()) System.out.print(it.next() + " -> "); ListIterator list = aL.listIterator(); Object o = list.next(); "); ListIterator list = aL.listIterator(); Object o = list.next();">

30 САОД, кафедра ОСУ30 Коллекции System.out.println("\n" + list.nextIndex() + "-й индекс"); //удаление элемента с текущим индексом list.remove(); while(list.hasNext()) //переход к // последнему индексу Object o = list.next(); while(list.hasPrevious()) /*вывод в обратном порядке */ System.out.print(list.previous() + " ");

31 САОД, кафедра ОСУ31 Коллекции //методы, характерные для LinkedList aL.removeFirst(); aL.removeLast(); aL.addFirst("FIRST"); aL.addLast("LAST"); System.out.println("\n" + aL); } }

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

33 САОД, кафедра ОСУ33 Стеки (stack)

34 САОД, кафедра ОСУ34 Стеки (stack)

35 САОД, кафедра ОСУ35 Стеки (stack) АТД стек поддерживает следующие основные методы: push (о): помещает объект о в вершину стека. Input: объект; Output: нет. pop (): удаляет объект из стека и возвращает новый верхний объект стека; если стек пуст, выдается сообщение об ошибке. Input: нет; Output: объект.

36 САОД, кафедра ОСУ36 Стеки (stack) Дополнительнее методы: size (): возвращает число объектов в стеке. Input: нет; Output: целое число. isEmpty (): возвращает логическое значение, подтверждающее, что стек пуст. Input: нет; Output: логическое значение. top (): возвращает верхний объект в стеке, не удаляя его; если стек пуст, выдается сообщение об ошибке. Input: нет; Output: объект.

37 САОД, кафедра ОСУ37 Реализация Стеков Линейная реализация: Algorithm size(): return t +1 Algorithm IsEmpty(): return (t < 0)

38 САОД, кафедра ОСУ38 Реализация Стеков Линейная реализация: Algorithm top(): if isEmpty() then вызов StackEmptyException return S[t] Algorithm push(o): if size() = N then вызов StackFullException t t + 1 S[t] o

39 САОД, кафедра ОСУ39 Реализация Стеков Линейная реализация: Algorithm pop(): if isEmpty() then вызов StackEmptyException e S[t) S[t] null t t - 1 return e

40 САОД, кафедра ОСУ40 Реализация Стеков Линейная реализация: type STACK = record top: integer; element: array[1..maxlength] of eltype end

41 САОД, кафедра ОСУ41 Реализация Стеков procedure MAKENULL (var S: STACK ); begin S.top:= maxlength + 1 end; { MAKENULL }

42 САОД, кафедра ОСУ42 Реализация Стеков function EMPTY ( S: STACK ): boolean; begin if S.top > maxlength then empty := true else empty := false end; { EMPTY }

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

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

45 САОД, кафедра ОСУ45 Реализация Стеков 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 } A simple Java implementation of the stack

46 САОД, кафедра ОСУ46 Реализация Стеков Динамическая реализация: Type PElement = ^TElement; TElement = record Item: TItem; Next: PElement; end; var TopPointer: PElement;

47 САОД, кафедра ОСУ47 Реализация Стеков procedure ClearStack(var TopPointer: PElement); var Temp: PElement; begin while TopPointernil do begin Temp := TopPointer; TopPointer := TopPointer^.Next; dispose (Temp); end;

48 САОД, кафедра ОСУ48 Реализация Стеков function IsEmpty(var TopPointer: PElement ): boolean; begin IsEmpty := TopPointer=nil; end;

49 САОД, кафедра ОСУ49 Реализация Стеков procedure Push( var TopPointer: PElement, Item: TItem); var Temp: PElement; begin Temp := new (PElement); Temp^.Item := Item; Temp^.Next := TopPointer; TopPointer := Temp; end;

50 САОД, кафедра ОСУ50 Реализация Стеков 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; Stack dynamic Class_StackStack dynamic Class_Stack Stack dynamicStack dynamic

51 САОД, кафедра ОСУ51 Реализация Стеков Использование стека 1. Вложенные вызовы подпрограмм 2. Размещение локальных переменных в блоках 3. Преобразование арифметических выражений в польскую запись 4. Аппаратные стеки

52 САОД, кафедра ОСУ52 Реализация Стеков

53 САОД, кафедра ОСУ53 Реализация Стеков Польская запись: 1-2/3*4+5 ссылка

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

55 САОД, кафедра ОСУ55 Очереди АТД «очередь» поддерживает два следующих основных метода: enqueue (о): помещает объект о в конец очереди. Input: объект; Output: нет. dequeue (): производит удаление и возвращает объект из начала очереди; если очередь пуста, выдается сообщение об ошибке. Input: нет; Output: объект.

56 САОД, кафедра ОСУ56 Очереди дополнительные методы АТД «очередь» : size (): возвращает число объектов в очереди. Input: нет; Output: целое число. isEmpty (): возвращает логическое значение, подтверждающее, что очередь пуста. Input: нет; Output: логическое значение. front (): возвращает первый объект в очереди, не удаляя его; если очередь пуста, выдается сообщение об ошибке. Input: нет; Output: объект. Интерфейс

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

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

59 САОД, кафедра ОСУ59 Реализация очередей Элемент очереди: type point = celltype; celltype = record element: eltype; next: point end;

60 САОД, кафедра ОСУ60 Реализация очередей - линейное представление

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

62 САОД, кафедра ОСУ62 MAKENULL procedure MAKENULL (var Q: QUEUE ) ; begin new (Q. front); Q. front.next:= nil; Q.rear:= Q. front end; { MAKENULL }

63 САОД, кафедра ОСУ63 EMPTY function EMPTY ( Q: QUEUE ): boolean; begin if Q.front = Q.rear then Empty := true else Empty := false end; { EMPTY }

64 САОД, кафедра ОСУ64 FRONT function FRONT ( Q: QUEUE ): eltype ; begin if EMPTY(Q) then Write('Очередь пуста') else Front := Q. Front.next.element end; { FRONT }

65 САОД, кафедра ОСУ65 ENQUEUE procedure ENQUEUE(x:eltype; var Q:QUEUE); begin new (Q.rear.next) ; Q.rear:= Q.rear.next; Q.rear.element:= x; Q.rear.next:= nil end; { ENQUEUE }

66 САОД, кафедра ОСУ66 DEQUEUE procedure DEQUEUE ( var Q: QUEUE ) ; begin if EMPTY(Q) then Write('Очередь пуста') else Q.front:= Q.front.next end; {DEQUEUE} Java_implementationJava_implementation Java.util. QUEUEJava.util. QUEUE

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

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

69 САОД, кафедра ОСУ69 Деки АТД «дек» поддерживает следующие базовые методы: insertFirst (e): помещает новый элемент е в начало D. Input: объект; Output: нет. insertLast (e): помещает новый элемент е в конец D. Input: объект; Output: нет.

70 САОД, кафедра ОСУ70 Деки removeFirst (): удаляет и возвращает первый элемент D, если D пуст, выдается сообщение об ошибке. Input: нет; Output: объект. removeLast (): удаляет и возвращает последний элемент D, если D пуст, выдается сообщение об ошибке. Input: нет; Output: объект.

71 САОД, кафедра ОСУ71 Деки дополнительные методы: first(): возвращает первый элемент D, если D пуст, выдается сообщение об ошибке. Input: нет; Output: объект. last(): возвращает последний элемент D, если D пуст, выдается сообщение об ошибке. Input: нет; Output: объект,

72 САОД, кафедра ОСУ72 Деки size (): возвращает число элементов D. Input: нет; Output: целое число. isEmpty (): определяет, является ли D пустым. Input: нет; Output: логическое значение.

73 САОД, кафедра ОСУ73 Деки

74 САОД, кафедра ОСУ74 Деки public interface Deque extends Container { Object getHead (); Object getTail (); void enqueueHead (Object object); void enqueueTail (Object object); Object dequeueHead ( ); Object dequeueTail (); }

75 САОД, кафедра ОСУ75 Циклические списки

76 САОД, кафедра ОСУ76 Циклические списки

77 САОД, кафедра ОСУ77 Мультисписки