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

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

2 САОД кафедра ОСУ 2 Поиск в списке Для заданного элемента списка х указатель next [x] указывает на следующий элемент связанного списка. Если next [x] = NIL, то у элемента х нет последующего, поэтому он является последним, т.е. хвостовым в списке. Атрибут head [L] указывает на первый элемент списка. Если head [L] = NIL, то список пуст

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 Реализация на основе курсоров cursor var Space: array [1..maxlength] of record element: eltype; next :integer end;

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

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

11 САОД, кафедра ОСУ ИК ТПУ11 Двунаправленные списки

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

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 Двунаправленные списки САОД, кафедра ОСУ ИК ТПУ Алгоритм insertAfter(p,e): Create a new node v v.setElement(e) y.setPrev(p) // j связывает v с предшествующим узлом v.setNext(p.getNext()) // связывает v с последующим узлом (p.getNext()).setPrev(v) // связывает ранее следовавший за р узел с v p.setNext(v) // связывает р с новым последующим узлом v return v //позиция элемента е

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

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

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

26 САОД, кафедра ОСУ ИК ТПУ26 Двунаправленные списки

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

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

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

30 САОД, кафедра ОСУ ИК ТПУ30 Коллекции 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();">

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

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

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

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

35 САОД, кафедра ОСУ ИК ТПУ35 Стеки (stack)

36 САОД, кафедра ОСУ ИК ТПУ36 Стеки (stack)

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

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

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

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

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

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

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

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

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

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

47 САОД, кафедра ОСУ ИК ТПУ47 Реализация Стеков 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

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

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

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

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

52 САОД, кафедра ОСУ ИК ТПУ52 Реализация Стеков 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

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

54 САОД, кафедра ОСУ54 Реализация Стеков САОД, кафедра ОСУ ИК ТПУ

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

56 САОД, кафедра ОСУ ИК ТПУ56 Реализация Стеков В микропроцессорах семейства Intel, как и в большинстве современных процессорных архитектур, поддерживается аппаратный стек. Аппаратный стек расположен в ОЗУ, указатель стека содержится в паре специальных регистров - SS:SP, доступных для программиста.

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

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

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

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

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

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

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

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

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

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

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

68 САОД, кафедра ОСУ ИК ТПУ68 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 }

69 САОД, кафедра ОСУ ИК ТПУ69 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

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

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

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

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

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

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

76 САОД, кафедра ОСУ ИК ТПУ76 Деки

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

78 САОД, кафедра ОСУ ИК ТПУ78 Циклические списки

79 САОД, кафедра ОСУ ИК ТПУ79 Циклические списки

80 САОД, кафедра ОСУ ИК ТПУ80 Мультисписки