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

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

• List clas

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

• type

• LIST = celltype;

• celltype = record

• element: eltype;

• next: LIST

• end;

• position = celltype;

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

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

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

Стеки (stack)

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

Стеки (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 }

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

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

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

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

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

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

• блоках

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

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

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

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

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

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

• O.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}

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

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

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

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

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

Деки(deq - double ended queue)

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

Деки

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

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

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

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

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

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

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

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

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