Datenstrukturen und Algorithmen - cs.ubbcluj.rodianat/SDA/curs/V5.pdf · Die Ordnungs-Relation •Die Relation ist eine Funktion mit zwei Parameters (zwei TComp Elemente): relation(c

Datenstrukturen und Algorithmen

Vorlesung 5

Überblick

• Vorige Woche:• ADT MultiMap

• Einfach verkettete Listen (singly linked lists)

• Doppelt verkettete Listen (doubly linked lists)

• Heute betrachten wir:• Sortierte Listen (sorted list/ ordered list)

• Verkettete Listen auf Arrays

• ADT PriorityQueue

• ADT Deque

Sortierte Liste

• Eine sortierte Liste ist eine Liste deren Elemente aus den Knoten in einer bestimmten Reihenfolge sind, bezüglich einer Ordnungs-Relation

• Die Ordnungs-Relation kann <,≤,>, oder ≥ sein, aber man kannauch mit einer abstrakten Relation arbeiten

• Eine abstrakte Relation bietet eine höhere Flexibilität an: man kanndie Ordnungs-relation ein ändern (ohne den Code für sortierte Listen zu ändern)

• Man kann z.B. in derselben Anwendung mehrere Listen haben mitunterschiedlichen Ordnungs-Relationen

Die Ordnungs-Relation

• Die Relation ist eine Funktion mit zwei Parameters (zwei TCompElemente):

relation(c1, c2) = ቐ

𝑡𝑟𝑢𝑒, 𝑓𝑎𝑙𝑙𝑠 𝑐1 𝑣𝑜𝑟 𝑐2𝑜𝑑𝑒𝑟 𝑐1 𝑔𝑙𝑒𝑖𝑐ℎ 𝑚𝑖𝑡 𝑐2 𝑖𝑠𝑡

𝑓𝑎𝑙𝑠𝑒, 𝑓𝑎𝑙𝑙𝑠 𝑐2 𝑣𝑜𝑟 𝑐1 𝑖𝑠𝑡

Sortierte Liste - Repräsentierung

• Wenn man eine sortierte Liste speichern will (oder einen anderen sortierten Container oder Datenstruktur), dann speichert man die Ordnungs-Relation als Teil der Datenstruktur (als ein Feld in dem ADT)

• Wir besprechen sortiere einfach verkettete Listen (die Repräsentierung und Implementierung für eine sortierte doppeltverkettete Liste sind ähnlich)

Sortierte Liste - Repräsentierung

• Man braucht zwei Datenstrukturen: • Knoten – SSLLNode

• Sortierte einfach verkettete Liste (Sorted Singly Linked List) - SSLL

SSLLNode:info: TCompnext: ↑ SLLNode

SSLL:head: ↑ SLLNoderel: ↑ Relation

SSLL - Initialisierung

• Für die Initialisierung braucht man auch die Relation als Parameter

• So kann man mehrere SSLLs mit unterschiedlichen Relationen erstellen

subalgorithm init (ssll, rel) is://pre: rel ist eine Relation//post: ssll ist eine leere SSLL

ssll.head ← NILssll.rel ← rel

end-subalgorithm

• Komplexität: Θ(1)

SSLL - Operationen

• Der Hauptunterschied zwischen der Operationen eines SLLs und der Operationen eines SSLLs ist bei der Einfügeoperation:• Für ein SLL kann man am Anfang der Liste, am Ende der Liste, an einer

gegebenen Position, vor/nach einem gegebenen Element einfügen (es gibt also mehrere Einfügeoperationen)

• Für ein SSLL gibt es eine einzige Einfügeoperation: wir können nicht mehr selber entscheiden wo man ein Element einfügt, sondern das wird von der Ordnungs-Relation bestimmt

• Bei den Löschoperationen ist es aber ähnlich: man kann mehrereLöschoperationen haben

• Die anderen Operationen sind auch ähnlich: Suche, ein Element zurückgeben

SSLL - Einfügeoperation

• In einem einfach verketteten Liste muss man den Knoten davor finden, um ein Element nach diesem Knoten einfügen zu können (sonst kann man die Links nicht richtig bestimmen)

• Der Knoten, den wir also finden müssen, ist der erste Knoten deren Nachfolger größer als das Element zum Einfügen ist (größer heißt, dass die Relation den Wert 1 zurückgibt)

• Es gibt zwei Ausnahmefälle:• Eine leere SSLL

• Wenn man vor dem ersten Knoten einfügen muss

SSLL - insertsubalgorithm insert (ssll, elem) is://pre: ssll ist eine SSLL; elem ist ein TComp//post: das Element elem wurde in ssll an der richtigen Position eingefügt

newNode ← allocate()[newNode].info ← elem[newNode].next ← NILif ssll.head = NIL then//die Liste ist leer

ssll.head ← newNodeelse if ssll.rel(elem, [ssll.head].info) = true then//elem ist “kleiner als" das info Element aus dem Head

[newNode].next ← ssll.headssll.head ← newNode

else// Fortsetzung auf der nächsten Folie ...

SSLL - insert

cn ← ssll.head //cn - current nodewhile [cn].next ≠ NIL and ssll.rel(elem, [[cn].next].info) = false execute

cn ← [cn].nextend-while//jetzt füge das Element nach cn ein[newNode].next ← [cn].next[cn].next ← newNode

end-ifend-subalgorithm

• Komplexität: 𝑂(n)

SSLL - andere Operationen

• Die Suche ist identisch mit der Suche in einem SLL (mit dem einzigen Unterschied, dass man früher mit dem Suchen aufhören kann: wenn man zu dem ersten Element größer als das gesuchte Element ankommt)

• Die Löschoperationen sind identisch mit den Löschoperationen für ein SLL

• Die Operationen um ein Element zurückzugeben ist identisch wie bei SLL

• Der Iterator für ein SSLL ist identisch mit dem Iterator für ein SLL

SSLL - Beispiel

• Wir definieren eine Funktion, die zwei ganze Zahlen vergleicht:

function compareGreater(e1, e2) is://pre: e1, e2 ganze Zahlen//post: compareGreater gibt true zurück falls e1 ≤ e2; und false falls e1 > e2

if e1 ≤ e2 thenCompareGreater ← true

elsecompareGreater ← false

end-ifend-function

SSLL - Beispiel• Wir definieren eine Funktion, die zwei ganze Zahlen vergleicht in Bezug auf die Summe der Ziffern

• Wir vermuten die Funktion sumOfDigits ist schon implementiert

function compareGreaterSum(e1, e2) is://pre: e1, e2 ganze Zahlen//post: compareGreaterSum gibt true zurück falls die Summe der Ziffern aus e1 kleiner oder gleich//ist als die von e2; und false falls die Summe der Ziffern aus e1 größer ist

sumE1 ← sumOfDigits(e1)sumE2 ← sumOfDigits(e2)if sumE1 ≤ sumE2 then

compareGreaterSum ← trueelse

compareGreaterSum ← falseend-if

end-function

SSLL - Beispiel• Wir definieren einen Subalgorithmus, der die Elemente des SSLLs mit Hilfe

eines Iterators ausdruckt

subalgorithm printWithIterator(ssll) is://pre: ssll its ein SSLL; post: die Elemente des ssll werden ausgedruckt

iterator(ssll, it) //create an iterator for ssllwhile valid(it) execute

getCurrent(it, elem)write elemnext(it)

end-whileend-subalgorithm

SSLL - Beispiel• Eine kurze Main-Methode, die ein SSLL erstellt, Elemente einfügt und dann

ausdruckt

subalgorithm main() is:init(ssll, compareGreater) //man benutzt compareGreater als Relationinsert(ssll, 55)insert(ssll, 10)insert(ssll, 59)insert(ssll, 37)insert(ssll, 61)insert(ssll, 29)printWithIterator(ssll)

end-subalgorithm

SSLL - Beispiel

• Die Main-Methode von der vorigen Folie druckt Folgendes aus: 10, 29, 37, 55, 59, 61

• Wenn wir anstatt compareGreater die Ordnungs-Relation compareGreaterSum benutezn, dann würde die Main-MethodeFolgendes ausdrucken: 10, 61, 37, 55, 29, 59

• Man kann eigentlich zwei Listen haben, eine mit der Ordnungs-Relation compareGreater und eine mit compareGreaterSum ⇒ mit einerabstrakten Ordnungs-Relation gibt es eine hohe Flexibilität

Verkettete Listen auf Arrays

• Was wäre wenn man eine verkettete Liste braucht, aber man arbeitet in einer Programmiersprache, die keine Pointers oder Referenzen hat?

• Man kann verkettete Datenstrukturen implementieren ohne explizite Pointers oder Referenzen zu benutzen, indem man diese mit Hilfe von Arrays und Indexe simuliert werden.


• Wenn man normalerweise mit einem Array arbeitet, dann werden die Elemente nacheinander gespeichert anfangend von ganz links (keine leeren Plätze in der Mitte sind erlaubt)

• Die Reihenfolge der Elemente in einem Array ist gleich mit der Reihenfolge in dem diese in dem Array gespeichert werden

• Reihenfolge der Elemente: 46, 78, 11, 6, 59, 19

46 78 11 6 59 19elems

Verkettete Listen auf Arrays• Man kann eine verkettete Datenstruktur auf einem Array definieren,

wenn man annimmt, dass die Reihenfolge der Elemente nicht von der relativen Position in dem Array gegeben wird, sondern von einer zugehörigen ganzen Zahl, die den Index des nächsten Elementes angibt


46 78 11 6 59 19

5 6 1 -1 2 4

elems

next

Head = 3

Verkettete Listen auf Arrays• Wenn man jetzt das Element 46 löschen will (eigentlich das zweite

Element aus der Liste), dann muss man nicht alle Elemente aus dem Array nach link verschieben, sondern man muss nur die Links ändern

• Reihenfolge der Elemente: 11, 59, 78, 19, 6

78 11 6 59 19

6 5 -1 2 4

elems

next

Head = 3

Verkettete Listen auf Arrays• Wenn man jetzt das Element 44 an die Position 3 einfügen will, dann

kann man das Element an irgendeiner Position in dem Array speichern und dann die Links richtig ändern


78 11 6 59 19 44

6 5 -1 8 4 2

elems

next

Head = 3

Verkettete Listen auf Arrays• Bei dem Einfügen eines neuen Elementes, kann dieses an einer leeren

Position in dem Array gespeichert werden. Um aber eine leere Position zu finden ist die Komplexität O(n), d.h. die Komplexität für die Einfüge Operation wird auch O(n) sein (egal wo man einfügen will).

• Um das zu vermeiden speichert man auch eine verkettete Liste von leeren Positionen.

78 11 6 59 19 44

7 6 5 -1 8 4 9 2 10 -1

elems

next

Head = 3

firstEmpty = 1


• Um also eine einfach verkettete Liste auf Arrays zu simulieren braucht man:

• Ein Array, der die Elemente speichert

• Ein Array der die Links speichert (als Indexe zu dem nächsten Element)

• Die Kapazität der zwei Arrays (diese haben dieselbe Kapazität, also man braucht nur einen Wert)

• Ein Index der uns den Listenkopf angibt

• Ein Index zu der ersten leeren Position in dem Array

SLL auf Arrays – Repräsentierung

• Die Repräsentierung einer einfach verketteten Liste auf einem Array (SLLA) ist:

SLLA:elems: TElem[]next: Integer[]cap: Integerhead: IntegerfirstEmpty: Integer

SLLA - Operationen

• Man kann alle Operationen, die es für SLL gibt, auch für SLLA implementieren:• Suche ein Element mit einem gegebenen Wert

• Füge ein Element ein: am Anfang der Liste, am Ende der Liste, auf einer gegebenen Position, vor/nach einem bestimmten Wert

• Lösche ein Element: vom Anfang der Liste, vom Ende der Liste, an einer bestimmten Position, mit einem gegebenen Wert

• Gebe ein Element an einer bestimmten Position zurück

SLLA - initsubalgorithm init(slla) is:

//pre: true; post: slla ist ein leeres SLLA

slla.cap ← INIT_CAPACITY

slla.elems ← @an array with slla.cap positions

slla.next ← @an array with slla.cap positions

slla.head ← -1

for i ← 1, slla.cap-1 execute

slla.next[i] ← i + 1

end-for

slla.next[slla.cap] ← -1

slla.firstEmpty ← 1

end-subalgorithm

• Komplexität: Θ(n)

SLLA - search

function search (slla, elem) is:

//pre: slla ist ein SLLA, elem ist ein TElem

//post: gibt die erste Position zurück falls elem in slla ist, -1 (ungültig) ansonsten

current ← slla.head

while current ≠ -1 and slla.elems[current] ≠ elem execute

current ← slla.next[current]

end-while

search ← current

end-function

• Komplexität: O(n)

SLLA - search

• In dem search Funktion sieht man wie eine SLLA durchlaufen werden kann (ähnlich wie ein SLL):

• Man braucht ein current Element, das mit dem Head initialisiert wird

• Man hört auf wenn current -1 wird (also es zeigt zu keinem gültigen Element mehr)

• Man geht zu dem nächsten Element mit der Anweisung:

current ← slla.next[current]

SLLA - addToBeginningsubalgoritm addToBeginning (slla, elem) is:

//pre: slla ist ein SLLA, elem ist ein TElem

//post: das Element elem wird am Anfang von slla eingefügt

if slla.firstEmpty = -1 then

newElems ← @an array with slla.cap * 2 positions

newNext ← @an array with slla.cap * 2 positions

for i ← 1, slla.cap execute

newElems[i] ← slla.elems[i]

newNext[i] ← slla.next[i]

end-for

for i ← slla.cap + 1, slla.cap*2 - 1 execute

newNext[i] ← i + 1

end-for

newNext[slla.cap*2] ← -1

//Fortsetzung auf der nächsten Folie ...

SLLA - addToBeginning

//free slla.elems and slla.next if necessary

slla.elems ← newElems

slla.next ← newNext

slla.firstEmpty ← slla.cap+1

slla.cap ← slla.cap * 2

end-if

newPosition ← slla.firstEmpty

slla.elems[newPosition] ← elem

slla.firstEmpty ← slla.next[slla.firstEmpty]

slla.next[newPosition] ← slla.head

slla.head ← newPosition

end-subalgorithm

Komplexität: Θ(1) amortisiert

SLLA - addToPositionsubalgorithm addToPosition(slla, elem, pos) is:

//pre: slla ist ein SLLA, elem ist ein TElem, pos ist eine ganze Zahl

//post: das Element elem wird in slla an der Position pos eingefügt

if (pos < 1) then

@error, invalid position

end-if

if slla.firstEmpty = -1 then

@resize

end-if

newElem ← slla.firstEmpty

slla.firstEmpty ← slla.next[firstEmpty]

slla.elems[newElem] ← elem

slla.next[newElem] ← -1


SLLA - addToPositionif pos = 1 then

if slla.head = -1 then

slla.head ← newElem

else

slla.next[newElem] ← slla.head

slla.head ← newElem

end-if

else

currentPos ← 1

currentNode ← slla.head

while currentNode ≠ -1 and currentPos < pos - 1 execute

currentPos ← currentPos + 1

currentNode ← slla.next[currentNode]

end-while


SLLA - addToPosition

if currentNode ≠ -1 then

slla.next[newElem] ← slla.next[currentNode]

slla.next[currentNode] ← newElem

else

@error, invalid position

end-if

end-if

end-subalgorithm

Komplexität: 𝑂(𝑛)

SLLA - addToPosition

• Bemerkungen:• Die resize Operation ist gleich mit der resize Operation von addToBeginning

• Ähnlich wie bei SLL, muss man die Liste iterieren bis man das Element gefunden hat, nach welchem man einfügen muss (currentNode)

• Ein Ausnahmefall ist das Einfügen an der ersten Position (es gibt keinen Knoten nach welchem man einfügen muss)

SLLA - Removesubalgorithm remove (slla, elem) is:

//pre: slla ist ein SLLA; elem ist ein TElem

//post: das Element elem wird aus SLLA gelöscht

nodC ← slla.head

prevNode ← -1

while nodC ≠ -1 and slla.elems[nodC] ≠ elem execute

prevNode ← nodC

nodC ← slla.next[nodC]

end-while

if nodC ≠ -1 then

if nodC = slla.head then

slla.head ← slla.next[slla.head]

else

slla.next[prevNode] ← slla.next[nodC]

end-if


SLLA - Remove

//add the nodC position to the list of empty spaces

slla.next[nodC] ← slla.firstEmpty

slla.firstEmpty ← nodC

else

@the element does not exist

end-if

end-subalgorithm


SLLA – Iterator

• Der Iterator für SLLA ist eine Mischung aus dem Iterator für ein Array und dem Iterator für eine einfach verkettete Liste

• Da die Elemente in einem Array gespeichert sind, ist das currentElement ein Index aus dem Array

• Aber, da es sich um eine verkettete Liste handelt, kann man nicht mit einer Inkrementierung von currentElement zu dem nächsten Element gehen, sondern man muss die next Links folgen

DLLA

• Ähnlich kann man auch eine doppelt verkettete Liste ohne Pointers definieren, mit Hilfe von Arrays

• Für DLLA besprechen wir eine andere Möglichkeit von Repräsentierung für verkettete Listen auf Arrays:

• Die Grundidee ist gleich, man benutzt Indexe in dem Array für die Links zwischen den Elementen

• Wir benutzten dieselbe Information, aber es wird anders strukturiert

• Es ähnelt mehr der verketteten Listen mit dynamischer Allokation

DLLA - Knoten

• Man kann eine Knotenstruktur auch mit Hilfe von Arrays definieren

• Ein Knoten (für eine doppelt verkettete Liste) enthält die Daten und die Links zu dem vorigen und nächsten Knoten:

DLLANode:info: TElemnext: Integerprev: Integer

DLLA

• Um die Liste zu repräsentieren brauchen wir jetzt ein Array von DLLANodes

• Da es sich um eine doppelt verkettete Liste handelt, speichern wir den Head und den Tail des Liste

DLLA:nodes: DLLANode[]cap: Integerhead: Integertail: IntegerfirstEmpty: Integer

DLLA – Speicherplatz allokieren und freigeben • Damit die Repräsentierung und Implementierung ähnlich sind zu

dynamisch allokierte verkettete Listen, kann man auch die Funktionen allocate und free definieren

function allocate(dlla) is:

//pre: dlla ist ein DLLA

//post: ein neues Element wird allokiert und die Position wird zurückgegeben

newElem ← dlla.firstEmpty

if newElem ≠ -1 then

dlla.firstEmpty ← dlla.nodes[dlla.firstEmpty].next

dlla.nodes[dlla.firstEmpty].prev ← -1

dlla.nodes[newElem].next ← -1

dlla.nodes[newElem].prev ← -1

end-if

allocate ← newElem

end-function

DLLA – Speicherplatz allokieren und freigeben

subalgorithm free (dlla, pos) is:

//pre: dlla ist ein DLLA, pos ist eine ganze Zahl

//post: die Position pos wurde freigegeben

dlla.nodes[pos].next ← dlla.firstEmpty

dlla.nodes[pos].prev ← -1

dlla.nodes[dlla.firstEmpty].prev ← pos

dlla.firstEmpty ← pos

end-subalgorithm

DLLA - addToPositionsubalgorithm addToPosition(dlla, elem, pos) is:

//pre: dlla ist ein DLLA, elem ist ein TElem, pos ist eine ganze Zahl

//man nimmt an, dass pos eine gültige Position ist

//post: das Element elem wird in dlla an der Position pos eingefügt

newElem ← alocate(dlla)

if newElem = -1 then

@resize

newElem ← alocate(dlla)

end-if

dlla.nodes[newElem].info ← elem

if pos = 1 then

if dlla.head = -1 then

dlla.head ← newElem

dlla.tail ← newElem

else


DLLA - addToPositiondlla.nodes[newElem].next ← dlla.head

dlla.nodes[dlla.head].prev ← newElem

dlla.head ← newElem

end-if

else

nodC ← dlla.head

posC ← 1

while nodC ≠ -1 and posC < pos - 1 execute

nodC ← dlla.nodes[nodC].next

posC ← posC + 1

end-while

if nodC ≠ -1 then

nodNext ← dlla.nodes[nodC].next

dlla.nodes[newElem].next ← nodNext

dlla.nodes[newElem].prev ← nodC

dlla.nodes[nodC].next ← newElem


DLLA - addToPosition

if nodNext = -1 then

dlla.tail ← newElem

else

dlla.nodes[nodNext].prev ← newElem

end-if

end-if

end-if

end-subalgorithm


DLLA - Iterator

• Der Iterator für DLLA enthält als aktuelle Element den Index für den aktuellen Knoten aus dem Array

DLLAIterator:list: DLLAcurrentElement: Integer

DLLAIterator - init

• Für ein (ADT) (dynamisches) Array wird currentElement mit 0 initialisiert bei dem Erstellen des Iterators.

• Für DLLA muss das currentElement zu dem Listenkopf zeigen (dieser kann sich auf Position 0 oder auf einer anderen Position befinden)

subalgorithm init(it, dlla) is:

//pre: dlla ist ein DLLA

//post: it ist ein DLLAIterator für dlla

it.list ← dlla

it.currentElement ← dlla.head

end-subalgorithm

DLLAIterator - getCurrent

subalgorithm getCurrent(it, e) is:

//pre: it ist ein DLLAIterator, it ist gültig

//post: e ist ein TElem, e ist das aktuelle Element aus it

e ← it.list.nodes[it.currentElement].info

end-subalgorithm

DLLAIterator - next

• Für ein (dynamisches) Array wird currentElement mit 1 inkrementiert wenn man zu dem nächsten Element geht.

• Für DLLA muss man die Links folgen.

subalgoritm next (it) is:

//pre: it ist ein DLLAIterator, it ist gültig

//post: das aktuelle Element aus it wird zu dem nächsten Element verschoben

it.currentElement ← it.list.nodes[it.currentElement].next

end-subalgorithm

DLLAIterator - valid

function valid (it) is:

//pre: it ist ein DLLAIterator

//post: valid gibt den Wert wahr zurück falls das aktuelle Element gültig

// ist, falsch ansonsten

if it.currentElement = -1 then

valid ← False

else

valid ← True

end-if

end-function

ADT Prioritätsschlange/Vorrangwarteschlange (Priority Queue)• ADT Prioritätsschlange ist ein Container, in welchem jedes Element

eine zugewiesene Priorität hat

• In einer Prioritätsschlange hat man Zugriff nur auf das Element mit der höchsten Priorität

• Es gilt also das HPF Prinzip (Highest Priority First)

ADT Prioritätsschlange

• Generell, kann man die Relation R auf die Menge der Prioritäten definieren: R : TPriority × TPriority

• Das Element mit der höchsten Priorität wird von der Relation Rbestimmt

• Zum Beispiel, falls die Relation R = ”≥”, dann ist das Element mit der höchsten Priorität das größte Element (Maximum)

ADT Prioritätsschlange

• Domäne:

PQ = { pq | pq ist eine Prioritätsschlange mit Elementen (e, p), e ∈TElem, p ∈ TPriority }

ADT Prioritätsschlange - Interface

• init(pq, R)• descr: erstellt eine leere Prioritätsschlange

• pre: R ist eine Relation auf die Menge der Prioritäten, R : TPriority × TPriority

• post: pq ∈ PQ, pq ist eine leere Prioritätsschlange

• destroy(pq)• descr: zerstört eine Prioritätsschlange

• pre: pq ∈ PQ

• post: pq wurde zerstört


• push(pq, e, p)• descr: fügt ein neues Element in die Prioritätsschlange ein• pre: pq ∈ PQ, e ∈ TElem, p ∈ TPriority• post: pq’ ∈ PQ, pq’ = pq ⊕ (e,p)

• pop(pq, e, p)• descr: liefert das Element mit der höchsten Priorität aus der Prioritätsschlange und

entfernt es von der Schlange. Die Priorität des Elementes wird auch zurückgegeben.• pre: pq ∈ PQ

• post: e ∈ TElem, p ∈ TPriority, e ist das Element mit der höchsten Priorität aus pqund p ist seine Priorität, pq’ ∈ PQ, pq’ = pq ⊖ (e,p)

• throws: ein Underflow Error, falls die Prioritätsschlange leer ist


• top(pq, e, p)• descr: liefert das Element mit der höchsten Priorität aus der Prioritätsschlange

zusammen mit seiner Priorität. Die Prioritätsschlange wird nicht geändert.• pre: pq ∈ PQ

• post: e ∈ TElem, p ∈ TPriority, e ist das Element mit der höchsten Priorität aus pq und p ist seine Priorität

• throws: ein Underflow Error, falls die Prioritätsschlange leer ist

• isEmpty(pq)• descr: überprüft ob die Prioritätsschlange leer ist• pre: pq ∈ PQ

• post: isEmpty ← ቊ𝑤𝑎ℎ𝑟, 𝑓𝑎𝑙𝑙𝑠 𝑝𝑞 𝑘𝑒𝑖𝑛𝑒 𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑒 𝑒𝑛𝑡ℎä𝑙𝑡

𝑓𝑎𝑙𝑠𝑐ℎ, 𝑎𝑛𝑠𝑜𝑛𝑠𝑡𝑒𝑛


• isFull(pq)• descr: überprüft ob die Schlange voll ist

• pre: pq ∈ PQ

• post: isFull ← ቊ𝑤𝑎ℎ𝑟, 𝑓𝑎𝑙𝑙𝑠 𝑝𝑞 𝑣𝑜𝑙𝑙 𝑖𝑠𝑡𝑓𝑎𝑙𝑠𝑐ℎ, 𝑎𝑛𝑠𝑜𝑛𝑠𝑡𝑒𝑛

• Bemerkung!

Die Prioritätsschlange kann nicht iteriert werden!

Dafür gibt es auch keine iterator Operation.

ADT Prioritätsschlange - Repräsentierung

• Um ADT Prioritätsschlange zu implementieren kann man folgende Datenstrukturen für die Repräsentierung benutzen:

• Dynamisches Array

• Verkettete Liste

• Heap


• Falls die Repräsentierung ein Dynamisches Array oder eine Verkettete Liste ist, dann muss man entscheiden wie die Elemente gespeichert werden:

• Man kann die Elemente sortiert nach der Priorität speichern

• Man kann die Elemente in der Reihenfolge, in der sie eingefügt wurden, speichern


• Komplexität der Operationen für die zwei Repräsentierungs-Möglichkeiten:

• Was passiert wenn man in einem separaten Feld das Element mit der höchsten Priorität speichert?

Operation Sortiert Nicht-sortiert

push O(n) Θ(1)

pop Θ(1) Θ(n)

top Θ(1) Θ(n)

Prioritätsschlange – Anwendungen

• Aufgaben, die mit Hilfe einer Prioritätsschlange gelöst werden können:• Stipendienvergabe (siehe Seminar 5)

• Triage Prozedur in Krankenhäusern

Documents

Datenstrukturen und Algorithmen - cs.ubbcluj.rodianat/SDA/curs/V5.pdf · Die Ordnungs-Relation •Die Relation ist eine Funktion mit zwei Parameters (zwei TComp Elemente): relation(c