Реализация списков: динамические структуры List clas структура одного элемента

Реализация списков:динамические структуры

• List clas

• структура одного элемента

• type

• LIST = celltype;

• celltype = record

• element: eltype;

• next: LIST

• end;

• position = celltype; Java_node

Реализация списков:динамические структуры

• Функция ENDL

• function ENDL ( L: LIST ): position;

• var q: position;

• begin

• q:= L;

• while q .next <> nil do

• q:= q .next;

• ENDL :=q

• end;

Реализация списков:динамические структуры

• Оператор 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

Реализация списков:динамические структуры

• Процедура DELETE

• procedure DELETE ( p: position ) ;

• begin

• p .next:= p .next .next

• end; { DELETE }

• delete

Реализация списков:динамические структуры

• Функция 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 )

Сравнение реализаций

• Реализация списков с помощью массивов расточительна в отношении компьютерной памяти.

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

• Таким образом, в разных ситуациях по критерию используемой памяти могут быть выгодны разные реализации.

Реализация на основе курсоров

• cursor

• var

• Space: array [1..maxlength] of

• record

• element: eltype;

• next :integer

• end;

Реализация на основе курсоров

• move

• function move ( var p, q: integer ) : boolean;

• var

• Temp: integer;

• begin

• if p = 0

• then begin

• writeln (‘Элемент не существует')

• move := false

• end

Реализация на основе курсоров

• else begin

• temp:= q;

• q:= p;

• p:= SPACE[q].next;

• SPACE [q] . next: = temp;

• move := true

• end

• end; { move }

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

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

• type

• point =  celltype;

• celltype = record

• element: eltype;

• next, previous: point

• end;

• position = point;

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

• 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;

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

Коллекции

• Коллекция LinkedList реализует связанный список.

• В отличие от массива, который хранит объекты в последовательных ячейках памяти,

• связанный список хранит объекты отдельно, но вместе со ссылками на следующее и предыдущее звенья последовательности.

Коллекции

• В добавление ко всем имеющимся методам в LinkedList реализованы методы

• void addFirst(Object ob)

• void addLast(Object ob)

• Object getFirst()

• Object getLast()

• Object removeFirst()

• Object removeLast

Коллекции

• /* пример: добавление и удаление элементов : */

• import java.util.*;

• public class DemoLinkedList {

• public static void main(String[] args){

• LinkedList aL = new LinkedList();

• for(int i = 10; i <= 20; i++)

• aL.add("" + i);

Коллекции

• Iterator it = aL.iterator();

• while(it.hasNext())

• System.out.print(it.next() + " -> ");

• ListIterator list = aL.listIterator();

• Object o = list.next();

Коллекции

• System.out.println("\n" + list.nextIndex()

• + "-й индекс");

• //удаление элемента с текущим индексом

• list.remove();

• while(list.hasNext()) //переход к

• // последнему индексу

• Object o = list.next();

• while(list.hasPrevious())

• /*вывод в обратном порядке */

• System.out.print(list.previous() + " ");

Коллекции

• //методы, характерные для LinkedList

• aL.removeFirst();
• aL.removeLast();
• aL.removeLast();
• aL.addFirst("FIRST");
• aL.addLast("LAST");
• System.out.println("\n" + aL);

• }

• }

Стеки (stack)

• Стек — это специальный тип списка, в котором все вставки и удаления выполняются в начале , называемом вершиной (top).

• Стеки также иногда называют "магазинами" или список с дисциплиной LIFO (last-in-first-out).

Стеки (stack)

Стеки (stack)

Стеки (stack)

• MAKENULL(S). Делает стек S пустым.

• TOP(S)-возвращает элемент из вершины стека S - RETRIEVE(FIRST(S), S).

• POP(S). Удаляет элемент из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как

• DELETE(FIRST(S), S).

Стеки (stack)

• PUSH (x, S).

• Помещает элемент х в вершину стека:

• INSERT (x, FIRST (S), S)

• EMPTY (S) равна TRUE, если стек пустой и FALSE, в противном случае

Реализация Стеков

• Линейная реализация:

• type

•   STACK = record

• top: integer;

• element: array[1..maxlength] of eltype

• end

Реализация Стеков

• procedure MAKENULL (var S: STACK );

• begin

• S.top:= maxlength + 1

• end; { MAKENULL }

Реализация Стеков

• function EMPTY ( S: STACK ): boolean;

• begin

• if S.top > maxlength

• then empty := true

• else empty := false

• end; { EMPTY }

Реализация Стеков

• function TOPS ( var S: STACK ): eltype;

• begin

• if EMPTY(S)

• then Write('Стек пустой')

• else Tops := S.element [S.top])

• end; { TOPS }

Реализация Стеков

• procedure POP ( var S: STACK ) ;

• begin

• if EMPTY(S)

• then Write ('Стек пустой')

• else S.top:= S.top + 1

• end; { POP }

Реализация Стеков

• 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

Реализация Стеков

• Динамическая реализация:

• Type PElement = ^TElement;

• TElement = record

• Item: TItem;

• Next: PElement;

• end;

• var TopPointer: PElement;

Реализация Стеков

• procedure ClearStack(var TopPointer:

• PElement);

• var Temp: PElement;

• begin

• while TopPointer<>nil do

• begin

• Temp := TopPointer;

• TopPointer := TopPointer^.Next;

• dispose (Temp);

• end;

• end;

Реализация Стеков

• function IsEmpty(var TopPointer:

• PElement ): boolean;

• begin

• IsEmpty := TopPointer=nil;

• end;

Реализация Стеков

• procedure Push(var TopPointer:

• PElement, Item: TItem);

• var Temp: PElement;

• begin

• Temp := new (PElement);

• Temp^.Item := Item;

• Temp^.Next := TopPointer;

• TopPointer := Temp;

• end;

Реализация Стеков

• 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_Stack

Реализация Стеков

• Использование стека

• Вложенные вызовы подпрограмм

• Размещение локальных переменных в

• блоках

• Преобразование арифметических

• выражений в польскую запись

• Аппаратные стеки

Реализация Стеков

• Польская запись:

• 1-2/3*4+5

• ссылка

Очереди

• Очередь – специальный тип списка- (queue), в котором вставка элементов осуществляется с одного конца (rear), а удаление с другого (front).

• Очереди также называют "списками типа FIFO" (first-in-first-out)

Операторы работы с очередями

• MAKENULL(Q) очищает очередь Q, делая ее пустой

• FRONT(Q) — функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q), Q)

• ENQUEUE(x, Q) вставляет элемент х в конец очереди Q:

• INSERT(x, END(Q), Q).

Операторы работы с очередями

• DEQUEUE(Q) удаляет первый элемент очереди Q:

• DELETE(FIRST(Q), Q).

• EMPTY(Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью.

Реализация очередей

• Элемент очереди:

• type

• point =  celltype;

• celltype = record

• element: eltype;

• next: point

• end;

Реализация очередей

• АТД QUEUE

• type

• queue = record

• front,rear: point

• end;

MAKENULL

• procedure MAKENULL (var Q: QUEUE ) ;

• begin

• new (Q. front);

• Q. front .next:= nil;

• Q.rear:= Q. front

• end; { MAKENULL }

EMPTY

• function EMPTY ( Q: QUEUE ): boolean;

• begin

• if Q.front = Q.rear

• then Empty := true

• else Empty := false

• end; { EMPTY }

FRONT

• function FRONT ( Q: QUEUE ): eltype ;

• begin

• if EMPTY(Q)

• then Write('Очередь пуста')

• else Front := Q. Front.next.element

• end; { FRONT }

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 }

DEQUEUE

• procedure DEQUEUE ( var Q: QUEUE ) ;

• begin

• if EMPTY(Q)

• then Write('Очередь пуста')

• else Q.front:= Q.front.next

• end; {DEQUEUE}

• Java_implementation Java.util. QUEUE

Примеры очередей

• Буфер клавиатуры

• Очереди в многозадачных ОС

• Очереди сообщений для параллельно выполняемых задач

• Очереди в имитационном моделировании

Деки(deq - double ended queue)

• Дек – структура данных с двусторонним доступом, хранящая упорядоченное множество значений, для которой определены следующие операции:

Деки

• очистить дек (сделать структуру пустой);

• проверить на пустоту;

• добавить элемент в начало;

• добавить элемент в конец;

• взять элемент из начала;

• взять элемент из конца;

Деки

Деки

• public interface Deque extends Container {

• Object getHead ();

• Object getTail ();

• void enqueueHead (Object object);

• void enqueueTail (Object object);

• Object dequeueHead ( );

• Object dequeueTail ();

• }

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

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

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