Listen und ihre Verarbeitung Klaus Becker 2009. 2 Listen und ihre Verarbeitung Inhalte:...

Listen und ihre Verarbeitung

Klaus Becker

2 Listen und ihre Verarbeitung

Inhalte: Datenstruktur Liste Listen als Objekte Datenmodellierung mit Listen Stapel Schlangen

amueller@gmx.de carla2@hotmail.org herbert.fluhr@web.de petra@dahm.de ewen@t-online.de t_schmidt@web.de nicole.weber@gmx.de ...

BrotButterJoghurtSchokoladeMehlEier...

Äpfel

3 Teil 1

Datenstruktur Liste

4 Verwaltung von DatenListen werden in der Informatik - wie auch im täglichen Leben - benutzt, wenn man mehrere zusammengehörende Daten als eine Einheit darstellen und verwalten will. Da solche Zusammenstellungen von Daten sehr häufig vorkommen, bildet die Datenstruktur Liste ein zentrales Konstrukt bei der automatisierten Verarbeitung von Daten.

Einkaufsliste Mailingliste

Äpfel

5 Einstieg - Mailingliste

M = ['amueller@gmx.de', 'carla2@hotmail.org', ... ]

M = [\'amueller@gmx.de',\'carla2@hotmail.org',\'herbert.fluhr@web.de',\'petra@dahm.de',\'ewen@t-online.de',\'t_schmidt@web.de',\'nicole.weber@gmx.de'\]Mailingliste

Liste mit Zeichenketten

6 Einstieg - Aufgaben (siehe 8.1.1)Bearbeiten Sie die Aufgaben des Abschnitts 8.1.1.

Aufgabe 1: Eine Liste in Python eingeben

Aufgabe 2: Listenoperationen ausprobieren

Aufgabe 3: Ein Element entfernen

Aufgabe 4: Ein Element hinzufügen.

Bei Bedarf können Sie sich im Abschnitt 8.1.3 über Listen und ihre Verarbeitung informieren.

7 Einstieg - Lotto

# Version 1tipp1 = 1tipp2 = 12tipp3 = 21tipp4 = 31tipp5 = 37tipp6 = 46ziehung1 = 1ziehung2 = 21ziehung3 = 25ziehung4 = 40ziehung5 = 44ziehung6 = 45

# Version 2tipp = [1, 12, 21, 31, 37, 46]ziehung = [1, 21, 25, 40, 44, 45]

# Version 3tipp = [ \ True , False, False, False, False, False, False, \ False, False, False, False, True , False, False, \ False, False, False, False, False, False, True , \ False, False, False, False, False, False, False, \ False, False, True , False, False, False, False, \ False, True , False, False, False, False, False, \ False, False, False, True , False, False, False, \ ]ziehung = [ \ True , False, False, False, False, False, False, \ False, False, False, False, False, False, False, \ False, False, False, False, False, False, True , \ False, False, False, True , False, False, False, \ False, False, False, False, False, False, False, \ False, False, False, False, True , False, False, \ False, True , True , False, False, False, False, \ ]

einzelne Zahlen

Liste mit Zahlen

Liste mit Wahrheitswerten

8 Einstieg - Aufgaben (siehe 8.1.2)Bearbeiten Sie die Aufgaben des Abschnitts 8.1.2.

Aufgabe 1: Zugriff auf Listenelemente

Aufgabe 2: Verarbeitung von Listen

Aufgabe 4: Analyse von Programmen

Aufgabe 5: Ergänzung von Programmen

Aufgabe 6: Entwicklung eines Programms

Bei Bedarf können Sie sich im Abschnitt 8.1.3 über Listen und ihre Verarbeitung informieren.

9 Lösungen - Aufgaben (siehe 8.1.1)Aufgabe 2: Listenoperationen

>>> M?>>> M[0]?>>> M[1]?>>> M[4]?>>> M[0:2]?>>> M[2:5]?>>> M[1:4]?>>> M[3:3]?>>> M + ['b-krewer@t-online.de']?>>> ['b-krewer@t-online.de'] + M?

>>> M[0:1] + M[2:7]?>>> M[0:3] + M[4:7]?>>> M[0:2] + ['b-krewer@t-online.de'] + M[2:7]?>>> M[0:5] + ['b-krewer@t-online.de'] + M[5:7]?>>> len(M)?>>> len(M[3:6])?

10 Lösungen - Aufgaben (siehe 8.1.1)Aufgabe 3: Element entfernen

M = [\'amueller@gmx.de',\'carla2@hotmail.org',\'herbert.fluhr@web.de',\'petra@dahm.de',\'ewen@t-online.de',\'t_schmidt@web.de',\'nicole.weber@gmx.de'\]

# Element entfernendef entfernen(L, i): H = L[0:i] + L[(i+1):len(L)] return H

# Testprint Mprint entfernen(M, 2)print M

Aufgabe 4: Element einfügen

M = [\'amueller@gmx.de',\'carla2@hotmail.org',\'herbert.fluhr@web.de',\'petra@dahm.de',\'ewen@t-online.de',\'t_schmidt@web.de',\'nicole.weber@gmx.de'\]

# Element einfügendef einfuegen(L, x, i): H = L[:i] + [x] + L[i:] return H

# Testprint Mprint einfuegen(M, 'b-krewer@t-online.de', 2)print M

11 Lösungen - Aufgaben (siehe 8.1.2)Aufgabe 2/3: Anzahl der Richtigen

# Version 3tipp = [ \ True , False, False, False, False, False, False, \ False, False, False, False, True , False, False, \ False, False, False, False, False, False, True , \ False, False, False, False, False, False, False, \ False, False, True , False, False, False, False, \ False, True , False, False, False, False, False, \ False, False, False, True , False, False, False, \ ]ziehung = [ \ True , False, False, False, False, False, False, \ ... False, True , True , False, False, False, False, \ ]# Anzahl der Richtigenrichtige = 0for i in range(49): if (tipp[i] == True) and (ziehung[i] == True): richtige = richtige + 1print richtige

# Version 2tipp = [1, 12, 21, 31, 37, 46]ziehung = [1, 21, 25, 40, 44, 45]# Anzahl der Richtigenrichtige = 0for t in tipp: for z in ziehung: if t == z: richtige = richtige + 1print richtige

12 Lösungen - Aufgaben (siehe 8.1.2)Aufgabe 4/5: Erzeugung der Lottoziehung

# Version 3from random import *ziehung = []for i in range(49): ziehung = ziehung + [False]for i in range(6): zahl = randint(1, 49) ziehung[zahl-1] = Truefor i in range(49): if ziehung[i] == True: print(i+1)

# Version 2from random import *ziehung = []for i in range(6): zahl = randint(1, 49) ziehung = ziehung + [zahl]print ziehung

# Version 3from random import *ziehung = []for i in range(49): ziehung = ziehung + [False]for i in range(6): ok = False while not ok: zahl = randint(1, 49) if ziehung[zahl-1] == False: ok = True ziehung[zahl-1] = Truefor i in range(49): if ziehung[i] == True: print(i+1)

13 Lösungen - Aufgaben (siehe 8.1.2)Aufgabe 6: Wiederholte Lottoziehungen

from random import *def tipp(): t = [ \ True , False, False, False, ... ... False, False, False, True , ... ] return tdef ziehung(): z = [] for i in range(49): z = z + [False] for i in range(6): ok = False while not ok: zahl = randint(1, 49) if z[zahl-1] == False: ok = True z[zahl-1] = True return z

def richtige(z, t): r = 0 for i in range(49): if (t[i] == True) and (z[i] == True): r = r + 1 return rdef simulation(n): t = tipp() haeufigkeiten = [0, 0, 0, 0, 0, 0, 0] i = 0 while i < n: z = ziehung() r = richtige(z, t) haeufigkeiten[r] = haeufigkeiten[r] + 1 i = i + 1 return haeufigkeitendef ausgabe(h): for i in range(7): print i, " Richtige: ", h[i]

# Testhaeufigkeiten = simulation(10000)ausgabe(haeufigkeiten)

14 Fachkonzept - Liste

Eine Liste ist eine endliche Folge von Elementen, bei der man neue Elemente hinzufügen und vorhandene Elemente entfernen kann.

Äpfel Zur Darstellung von Listen verwenden wir - wie in Python - eckige Klammern.

Alle Elemente einer Liste werden mit Kommata getrennt.

Eine besondere Liste ist die leere Liste. Sie enthält keine Elemente.

Die Elemente einer Liste können (in unserer Darstellung hier) von beliebigem - also auch unterschiedlichem - Typ sein.

Eine Liste kann selbst wieder Listen als Elemente haben. Listen können also geschachtelt werden.['amueller@gmx.de', 'carla2@hotmail.org', 'herbert.fluhr@web.de', ...]

[1, 12, 21, 31, 37, 46]

[1, 21, 25, 40, 44, 45, ("Zusatzzahl", 3), ("Superzahl", 5)]

[[1, 12, 21, 31, 37, 46], [3, 8, 10, 30, 31, 49], [5, 12, 20, 22, 29, 40]]

[10, 15, 21, 33, 37, 40]

0 1 2 3 4 5

Element

>>> L = [10, 15, 21, 33, 37, 40]>>> L[0]10>>> L[1]15

lesender Zugriff

>>> L = [10, 15, 21, 33, 37, 40]>>> L[10, 15, 21, 33, 37, 40]>>> L[4] = 36>>> L[10, 15, 21, 33, 36, 40]

schreibender Zugriff

Die Elemente einer Liste sind (in unserer Darstellung hier) alle durchnummeriert. Die Nummerierung beginnt dabei mit 0. Die Nummer eines Listenelements wird auch Index genannt.

Wir gehen (in unserer Darstellung hier) davon aus, dass ein Zugriff auf jedes Listenelement möglich ist. Wenn L eine Liste bezeichnet, dann beschreibt der Ausdruck L[i] das Listenelement mit der Nummer i.

['g', 't', 'e', 'c', 's', 'k', 'p']

0 1 2 3 4 5

Element

>>> L = ['g', 't', 'e', 'c', 's', 'k', 'p']>>> L[0:2]['g', 't']>>> L[2:5]['e', 'c', 's']>>> L[1:5]['t', 'e', 'c', 's']>>> L[3:3][]

Teillisten

>>> L = ['g', 't', 'e', 'c', 's', 'k', 'p']>>> L[2:]['e', 'c', 's', 'k', 'p']>>> L[:2]['g', 't']>>> L[:]['g', 't', 'e', 'c', 's', 'k', 'p']

Wenn L eine Liste bezeichnet, dann beschreibt der Ausdruck L[i:j] die Liste, die alle Elemente der Ausgangsliste L mit den Nummern von i bis j-1 enthält. Beachte, dass diese Teilliste auch leer sein kann.

Teillisten

['g', 't', 'e', 'c', 's', 'k', 'p']

0 1 2 3 4 5

Element

>>> L = ['g', 't', 'e', 'c', 's', 'k', 'p']>>> M = ['a', 'g', 't']>>> L + M['g', 't', 'e', 'c', 's', 'k', 'p', 'a', 'g', 't']>>> L + ['u']['g', 't', 'e', 'c', 's', 'k', 'p', 'u']>>> [] + M['a', 'g', 't']

Konkatenation

>>> L = ['g', 't', 'e', 'c', 's', 'k', 'p']>>> len(L)7>>> len([])0>>> len([1, [2, 3]])2

Da Listen dynamisch wachsen oder schrumpfen können, benötigt man häufig eine Operation zur Bestimmung der Länge der Liste. Die Länge einer Liste beschreibt dabei die Anzahl der Listenelemente. Wenn L eine Listen bezeichnet, dann beschreibt der Ausdruck len(L) die Länge der Liste.

Bei der Konkatenation von Listen werden diese zu einer Gesamtliste verbunden. Wenn L und M zwei Listen bezeichnen, dann beschreibt der Ausdruck L+M die Liste, die zunächst alle Elemente von L und danach alle Elemente von M enthält.

Länge

18 Übungen (siehe 8.1.4)Bearbeite die Aufgaben 1 .. 7.

19 Teil 2

Listen als Objekte

20 Einstieg - merkwürdiges VerhaltenIm folgenden Python-Dialog wird ein Lotto-Tipp kopiert und anschließend etwas abgeändert.Was fällt auf?

>>> tipp1 = [4, 13, 21, 33, 34, 42]>>> tipp2 = tipp1>>> tipp2[1] = 8>>> tipp2[4, 8, 21, 33, 34, 42]>>> tipp1[4, 8, 21, 33, 34, 42]>>> tipp1 = [4, 13, 21, 33, 34, 42]>>> tipp1[4, 13, 21, 33, 34, 42]>>> tipp2[4, 8, 21, 33, 34, 42]>>> tipp2[0] = 3>>> tipp2[3, 8, 21, 33, 34, 42]>>> tipp1[4, 13, 21, 33, 34, 42]

Verwaltung von Listen mit Variablen

Jedes Datenobjekt hat (in Python) eine Identitätsnummer, einen Typ und einen bestimmten Wert.

>>> id([4, 13, 21, 33, 34, 42])12289008>>> type([4, 13, 21, 33, 34, 42])<type 'list'>>>> [4, 13, 21, 33, 34, 42][4, 13, 21, 33, 34, 42]

Variablen dienen in der Informatik dazu, Datenobjekte zu verwalten. Variablen werden an Datenobjekte angebunden, um die betreffenden Datenobjekte verwalten zu können.Eine Variable, die ein Datenobjekt referenziert, ist eine Art Name für das betreffende Datenobjekt. Mit dem Variablennamen kann man sich die Identitätsnummer, den Typ und den Wert des referenzierten Datenobjekts verschaffen.

>>> tipp1 = [4, 13, 21, 33, 34, 42]>>> id(tipp1)12289008>>> type(tipp1)<type 'list'>>>> tipp1[4, 13, 21, 33, 34, 42]

Verwaltung von Listen mit Variablen

>>> tipp1 = [4, 13, 21, 33, 34, 42]>>> tipp2 = tipp1>>> tipp2[1] = 8>>> tipp2[4, 8, 21, 33, 34, 42]>>> tipp1[4, 8, 21, 33, 34, 42]>>> tipp1 = [4, 13, 21, 33, 34, 42]>>> tipp1[4, 13, 21, 33, 34, 42]>>> tipp2[4, 8, 21, 33, 34, 42]>>> tipp2[0] = 3>>> tipp2[3, 8, 21, 33, 34, 42]>>> tipp1[4, 13, 21, 33, 34, 42]

23 Listen als Objekte

>>> L = []>>> L[]>>> L.append(3)>>> L[3]>>> L.append(5)>>> L[3, 5]>>> L.insert(1, 7)>>> L[3, 7, 5]>>> L.insert(0, 5)>>> L[5, 3, 7, 5]>>> L.remove(5)>>> L[3, 7, 5]>>> L.extend([4, 2])>>> L[3, 7, 5, 4, 2]

Listen sind (in Python) Objekte vom Typ list, die Daten verwalten und die dem Benutzer Operationen zur Verarbeitung der Daten zur Verfügung stellen.

>>> L[3, 7, 5, 4, 2]>>> L.__len__()5>>> L.__getitem__(1)7>>> L.__setitem__(1, 8)>>> L[3, 8, 5, 4, 2]>>> L.__delitem__(1)>>> L[3, 5, 4, 2]>>> L.__len__()4

24 Listenverarbeitung

>>> L = [1, 2, 3]>>> L[1, 2, 3]>>> id(L)12283056>>> L = L + [4]>>> L[1, 2, 3, 4]>>> id(L)12289008>>> L = L[1:]>>> L[2, 3, 4]>>> id(L)12257720>>> L = [1, 2] + L[1:]>>> L[1, 2, 3, 4]>>> id(L)12289008

>>> L = [1, 2, 3]>>> L[1, 2, 3]>>> id(L)12283536>>> L[1] = 5>>> L[1, 5, 3]>>> id(L)12283536>>> L.remove(5)>>> L[1, 3]>>> id(L)12283536>>> L.insert(1, 2)>>> L[1, 2, 3]>>> id(L)12283536

Erzeugung neuer Listen

Veränderung einer bestehenden Listen

L = Listenkonstruktor L.Listenoperation

25 Übungen (siehe 8.2.5)Bearbeiten Sie die Aufgaben des Abschnitts 8.2.5.

26 Teil 3

Datenmodellierung mit Listen

27 Einstieg - Magische QuadrateEin magisches Quadrat ist ein Zahlenschema, bei dem alle Zeilen-, Spalten- und Diagonalsummen gleich sind.

>>> q = [[16, 5, 9, 4], [2, 11, 7, 14], [3, 10, 6, 15], [13, 8, 12, 1]]>>> q[0][16, 5, 9, 4]>>> q[0][0]16>>> q[0][1]5>>> q[0][0] + q[0][1] + q[0][2] + q[0][3]34

Darstellung mit Listen

28 Einstieg - Aufgaben (siehe 8.3.1)Entwickle eine Funktion zeilensumme(quadrat, i), eine Funktion spaltensumme(quadrat, i) und zwei Funktionen diagonalsumme_lr(quadrat) und diagonalsumme_rl(quadrat), mit deren Hilfe man die entsprechenden Summen bei einem gegebenen Zahlenschema berechnen kann.Entwickle auch eine Funktion, die überprüft, ob ein Zahlenschema ein magisches Quadrat darstellt.

>>> q = [[16, 5, 9, 4], [2, 11, 7, 14], [3, 10, 6, 15], [13, 8, 12, 1]]>>> zeilensumme(q, 0)34>>> spaltensumme(q, 3)34>>> diagonalsumme_lr(q)34>>> magischesQuadrat(q)True

29 Lösung - Aufgaben (siehe 8.3.1)

def zeilensumme(q, n): summe = 0 l = len(quadrat) i = 0 while i < l: summe = summe + q[n-1][i] i = i + 1 return summe

def spaltensumme(q, n): ... while i < l: summe = summe + q[i][n-1] i = i + 1 return summe

def diagonalsumme_lr(q): ... while i < l: summe = summe + q[i][i] i = i + 1 return summe

def diagonalsumme_rl(q): summe = 0 l = len(quadrat) i = 0 while i < l: summe = summe + q[i][l-i-1] i = i + 1 return summe

def magischesQuadrat(q): magisch = True s = diagonalsumme_lr(q) if diagonalsumme_rl(q) != s: magisch = False n = 0 while n < len(quadrat): if zeilensumme(q, n+1) != s: magisch = False if spaltensumme(q, n+1) != s: magisch = False n = n + 1 return magisch

30 Datenstrukturen

# Lottoscheinschein = [[3, 6, 19, 21, 38, 41], [4, 9, 17, 37, 38, 39], [18, 23, 28, 36, 38, 46]]

Datenstrukturen ermöglichen es, strukturierte Daten als Einheit zu verwalten.

Reihung aus Reihungen

31 Reihung / Verbund

# Reihung[10, 15, 21, 33, 37, 40]

Bei einer Reihung werden Daten desselben Typs zu einer Einheit zusammengefasst.

Reihung

Bei einem Verbund werden Daten zu einer Einheit zusammengefasst, die von unterschiedlichem Typ sein können.

# Verbund["Albert", "Einstein", 1879, 1955]

Darstellung als ListeDarstellung als Liste

Verbund

# Verbund("Albert", "Einstein", 1879, 1955)

Darstellung als Tupel

Schachtelung von Reihung u. Verbund

# Schachtelung von Reihung und Verbund[["Albert", "Einstein", [14, 3, 1879], [18, 5, 1955]], ...]

Reihungen und Verbunde können beliebig ineinander geschachtelt werden.

ReihungZeichenkette

Zeichenkette

Verbund von Zahlen

Verbund

33 Mehrdimensionale Reihung

# zweidimensionale Reihung[[16, 5, 9, 4], [2, 11, 7, 14], [3, 10, 6, 15], [13, 8, 12, 1]]

Mehrdimensionale Reihungen sind Reihungen von Reihungen ....

Reihung

34 Dynamische Datenstrukturen

# Liste["Anna", "Peter", "Tim", "Greta", "Katrin"]

Dynamische Datenstrukturen sind Datenstrukturen, die sich dynamisch verändern können.

# Baum["Andreas", \ ["Peter", \ [Matthias], \ [Katharina]], \ ["Christiane", \ ["Winfried"], \ ["Ursula"]]]

# Graph[ \ ["TR", ["KO", "KL"]], \ ["KO", ["TR", "MZ", "KL"]], \ ["MZ", ["KO", "KL"]], \ ["KL", ["TR", "KO", "MZ"]] \]

35 Übungen (siehe 8.3.3)Bearbeiten Sie Aufgabe 3 (Simulation eines Tischtennisspiels) oder Aufgabe 4 (Irrlauf in Mannheim).

36 Teil 4

Stapel

37 Einstieg - Rechenterme

(92 - 79) * 27

Rechenterm

Auswertung eines Rechenterms

38 Einstieg - Aufgaben (siehe 8.4.1)

(92 - 79) * 27

Aufgabe 1: Darstellung von Rechentermen mit Listen

Aufgabe 2: Algorithmus zur Auswertung von Rechentermen

[27, 79, 92, "-", "*"]

39 Stapel

Ein Stapel ist eine Datenstruktur, die als Behälter für Datenobjekte dient und nach dem LIFO-Prinzip (last in, first out) arbeitet.

Stapeloperationen:

top(): liefert das oberste Datenobjekt (sofern der Stapel nicht leer ist)

push(e): legt das übergebene Datenobjekt oben auf den Stapel

pop(): entfernt das oberste Stapelobjekt (sofern der Stapel nicht leer ist)

40 Implementierung als Klasse

class Stapel(object): def __init__(self): self.liste = []

def isEmpty(self): if self.liste == []: return True else: return False

def push(self, element): self.liste = [element] + self.liste

def pop(self): if not self.isEmpty(): self.liste = self.liste[1:]

def top(self): if self.isEmpty(): return None else: return self.liste[0]

def size(self): return len(self.liste)

def getStapel(self): return self.liste

def setStapel(self, liste): self.liste = liste

>>> s = Stapel()>>> s.push(6)>>> s.getStapel()[6]>>> s.push(3)>>> s.getStapel()[3, 6]>>> s.top()3>>> s.pop()>>> s.getStapel()[6]

41 Übungen (siehe 8.4.3/8.4.4)

8.4.3: Aufgabe 1:Testen Sie die Stapeloperationen.

>>> t = Stapel()>>> t.setStapel([27, 79, 92, "-", "*"])>>> s = Stapel()>>> print t.getStapel()[27, 79, 92, '-', '*']>>> print s.getStapel()[]>>> e = t.top()>>> s.push(e)>>> t.pop()>>> print t.getStapel()[79, 92, '-', '*']>>> print s.getStapel()[27]...

8.4.4: Aufgabe 1:Die in den Abbildungen gezeigten Operationen sollen mit Hilfe von zwei Stapel-Objekten durchgespielt werden.

42 Übungen (siehe 8.4.3/8.4.4)8.4.4: Aufgabe 2: Ergänzen Sie die Implementierung, so dass der folgende Python-Dialog möglich wird. Testen Sie die Funktion auswerten auch mit anderen Termen.

>>> auswerten([27, 79, 92, "-", "*"])T: [27, 79, 92, '-', '*']S: []

T: [79, 92, '-', '*']S: [27]

T: [92, '-', '*']S: [79, 27]

T: ['-', '*']S: [92, 79, 27]

T: [13, '*']S: [27]

T: ['*']S: [13, 27]

T: [351]S: []...

def auswerten(term): t = Stapel() t.setStapel(term) s = Stapel() while t.size() > 0: print "T:", t.getStapel() print "S:", s.getStapel() print e = t.top() t.pop() if type(e) == int: s.push(e) else: ... print "T:", t.getStapel() print "S:", s.getStapel() print return s.top()

43 Lösungen (siehe 8.4.3/8.4.4)8.4.4: Aufgabe 1:

>>> t = Stapel()>>> t.setStapel([27, 79, 92, "-", "*"])>>> s = Stapel()>>> print t.getStapel()[27, 79, 92, '-', '*']>>> print s.getStapel()[]>>> e = t.top()>>> print e27>>> t.pop()>>> s.push(e)>>> print t.getStapel()[79, 92, '-', '*']>>> print s.getStapel()[27]...

...>>> e = t.top()>>> print e->>> m = s.top()>>> s.pop()>>> n = s.top()>>> s.pop()>>> t.push(m-n)>>> print t.getStapel()[13, '-', '*']>>> print s.getStapel()[27]>>> ...

44 Lösungen (siehe 8.4.3/8.4.4)

def auswerten(term): t = Stapel() t.setStapel(term) s = Stapel() while t.size() > 0: print "T:", t.getStapel() print "S:", s.getStapel() print e = t.top() t.pop() if type(e) == int: s.push(e) else: ...

print "T:", t.getStapel() print "S:", s.getStapel() print return s.top()

m = s.top() s.pop() n = s.top() s.pop() op = e if op == "+": t.push(m+n) elif op == "-": t.push(m-n) elif op == "*": t.push(m*n) elif op == "/": t.push(m/n)

45 Teil 5

Schlangen

46 Einstieg - Warteschlange

Simulation einer Druckerwarteschlange

Beim Drucken von Aufträgen kann es vorkommen, dass neue Druckaufträge den Drucker erreichen, bevor der aktuelle Druckauftrag abgearbeitet ist. Drucker sehen für diesen Fall einen Puffer vor, in dem die neuen Druckaufträge zwischengespeichert werden.>>> simuliereDrucken()S: ['Eine']S: ['Eine', 'Warteschlange']S: ['Eine', 'Warteschlange', 'bildet']S: ['Eine', 'Warteschlange', 'bildet', 'sich,']EineS: ['Warteschlange', 'bildet', 'sich,', 'wenn']S: ['Warteschlange', 'bildet', 'sich,', 'wenn', 'mehr']WarteschlangeS: ['bildet', 'sich,', 'wenn', 'mehr', 'Anforderungen']bildetsich,wennS: ['mehr', 'Anforderungen', 'pro']S: ['mehr', 'Anforderungen', 'pro', 'Zeiteinheit']...

47 Schlange

Eine Schlange ist eine Datenstruktur, die als Behälter für Datenobjekte dient und nach dem FIFO-Prinzip (first in, first out) arbeitet.

Schlangenoperationen:

erstes(): liefert das erste Schlangenelement (sofern die Schlange nicht leer ist)

mitLetztem(e): fügt das übergebene Schlangenelement hinten in die Schlange ein

ohneErstes(): entfernt das erste Schlangenelement (sofern die Schlange nicht leer ist)

48 Implementierung als Klasse

class Schlange(object): def __init__(self): self.liste = []

def istLeer(self): if self.liste == []: return True else: return False

def mitLetztem(self, element): self.liste = self.liste + [element]

def ohneErstes(self): if not self.istLeer(): self.liste = self.liste[1:]

def erstes(self): if self.istLeer(): return None else: return self.liste[0]

def anzahlElemente(self): return len(self.liste)

def getSchlange(self): return self.liste

def setSchlange(self, liste): self.liste = liste

>>> s = Schlange()>>> s.getSchlange()[]>>> s.mitLetztem(4)>>> s. mitLetztem(7)>>> s.getSchlange()[4, 7]>>> s.erstes()4>>> s.ohneErstes()>>> s.getSchlange()[7]

8.5.3: Aufgabe 1:Testen Sie die Schlangenoperationen.

8.5.4: Aufgabe 1:Ziel ist es, eine Druckerwarteschlange zu simulieren. Dabei sollen Python-Protokolle der folgenden Art entstehen....

>>> simuliereDrucken()S: ['Eine']S: ['Eine', 'Warteschlange']S: ['Eine', 'Warteschlange', 'bildet']S: ['Eine', 'Warteschlange', 'bildet', 'sich,']EineS: ['Warteschlange', 'bildet', 'sich,', 'wenn']S: ['Warteschlange', 'bildet', 'sich,', 'wenn', 'mehr']WarteschlangeS: ['bildet', 'sich,', 'wenn', 'mehr', 'Anforderungen']bildetsich,wennS: ['mehr', 'Anforderungen', 'pro']S: ['mehr', 'Anforderungen', 'pro', 'Zeiteinheit']S: ['mehr', 'Anforderungen', 'pro', 'Zeiteinheit', 'an']mehrS: ['Anforderungen', 'pro', 'Zeiteinheit', 'an', 'ein']S: ['Anforderungen', 'pro', 'Zeiteinheit', 'an', 'ein', 'System']AnforderungenS: ['pro', 'Zeiteinheit', 'an', 'ein', 'System', 'gerichtet']proZeiteinheitaneinSystemgerichtetS: ['werden,']S: ['werden,', 'als']S: ['werden,', 'als', 'dieses']...

...werden,alsdiesesS: ['in']inS: ['der']derS: ['selben']S: ['selben', 'Zeit']selbenZeitS: ['verarbeiten']verarbeitenS: ['kann.']kann.

8.5.4: Aufgabe 1:...Analysiere zunächst den Quelltext und kläre folgende Fragen:* Woher stammen die als Druckaufträge dienenden Zeichenketten?* Welche Rolle spielt der Zufallsgenerator bei der Simulation?Vervollständige den Quelltext und teste das Simulationsprogramm.

# -*- coding: iso-8859-1 -*-

from schlange import *from random import *

def simuliereDrucken(): f = file("warteschlange.txt", 'r') text = f.read() liste = text.split() s = Schlange() i = 0 while (len(liste) > 0) or not s.istLeer(): z = randint(0, 1) if z == 0: # Auftrag drucken else: # Auftrag erteilen

52 Lösungen (siehe 8.4.3/8.4.4)8.5.4: Aufgabe 1:

# -*- coding: iso-8859-1 -*-

from schlange import *from random import *

def simuliereDrucken(): f = file("warteschlange.txt", 'r') text = f.read() liste = text.split() s = Schlange() i = 0 while (len(liste) > 0) or not s.istLeer(): z = randint(0, 1) ...

... if z == 0: # Drucken if not s.istLeer(): auftrag = s.erstes() s.ohneErstes() print auftrag else: # Auftrag if len(liste) > 0: auftrag = liste[0] liste = liste[1:] s.mitLetztem(auftrag) print "S:", s.getSchlange()

53 Teil 6

Miniprojekt: Monoalphabetische Chiffriersysteme

54 Einstieg - Caesar-Verschlüsselung

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Schlüssel: DQuelltext:

SALVECAESAR

Geheimtext:VDOYHFDHVDU

PYLZFOWBNQCYBUVNCBLGYCHYAYBYCGMWBLCZNYH

NTCZYLN

VDOYHFDHVD

55 Fachkonzept - Chiffriersystem

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Ein Chiffriersystem dient dazu, Klartexte in Geheimtexte und umgekehrt Geheimtexte in Klartexte zu transformieren. Zum Ver- und Entschlüsseln (man sagt auch Codieren und Decodieren) wird in der Regel jeweils ein Schlüssel benötigt.

Verschiebe-Chiffriersystem

56 Fachkonzept - Chiffriersystem

Ein monoalphabetisches Chiffriersystem ist ein Chiffriersystem, bei dem jedem Buchstaben des Alphabets ein anderer Buchstabe des Alphabets fest zugeordnet wird.

G O Z L N C R E W K A X B J F Q Y I S M V D U P H T

monoalphabetisches Chiffriersystem

57 Exkurs - Python-Implementierung

# -*- coding: iso-8859-1 -*-

def buchstabeCodieren(c, v): m = ord(c) n = m + v if n > 90: n = n - 26 d = chr(n) return d def buchstabeDecodieren(c, v): m = ord(c) n = m - v if n < 65: n = n + 26 d = chr(n) return d def textCodieren(text, v): geheimtext = '' for c in text: geheimtext = geheimtext + buchstabeCodieren(c, v) return geheimtext

def textDecodieren(text, v): klartext = '' for c in text: klartext = klartext + buchstabeDecodieren(c, v) return klartext

def textLaden(dateiname): f = file(dateiname, 'r') text = f.read() return text

def textVorbereiten(text): grossText = text.upper() bereinigterText = '' for c in grossText: if (ord(c) >= 65) and (ord(c) <= 90): bereinigterText = bereinigterText + c return bereinigterText

58 Projekt - AuftragEntwickeln Sie ein Programm, mit dem man ein beliebiges monoalphabetisches Chiffriersystem betreiben kann. Mit diesem Programm soll man beliebige Texte mit einer beliebigen festen Zuordnungstabelle verschlüsseln und auch wieder entschlüsseln können.

Zusätzlich soll es das System ermöglichen, die Häufigkeiten von Buchstaben in Texten zu ermitteln, so dass man das System auch nutzen kann, um eine unbekannte Zuordnungstabelle zu rekonstruieren.

59 Projekt - ModellierungZunächst ist zu klären, wie eine Zuordnungstabelle und eine Häufigkeitstabelle mit Datenstrukturen beschrieben werden soll.

['G', 'O', 'Z', 'L', 'N', 'C', 'R', 'E', 'W', ..., 'T'] 0 1 2 3 4 5 6 7 8 ... 25 A B C D E F G H I ... Z

3 1 0 1 9 1 2 3 1 0 1 2 3 6 1 0 0 4 5 5 1 0 0 0 0 0

[ 3, 3, 1, 0, 1, 9, 1, 2, 3, ..., 0] 0 1 2 3 4 5 6 7 8 ... 25 A B C D E F G H I ... Z

Zuordnungstabelle

Häufigkeitstabelle

60 Projekt - ModellierungZusätzlich muss geklärt werden, welche Operationen mit Hilfe von Funktionen implementiert werden sollen.

def zeichenCodieren(c, Z): ... return ...

def zeichenDecodieren(c, Z): ... return ...

def textCodieren(text, Z): ... return ...

def textDecodieren(text, Z): ... return ...

Für weitere Informationen siehe 8.6.5.

def textAnalysieren(text): ... return ...

61 Projekt - ImplementierungIm vorangegangenen Abschnitt sind eine Reihe von Funktionen / Prozeduren modelliert worden. Diese müssen jetzt alle implementiert werden. Natürlich könnte jetzt jeder für sich die Sache anpacken.

Bei größeren Software-Entwicklungsprojekten teilt man sich in solch einer Situation die Arbeit auf. Das spart dann viel Zeit - sofern alle gute Arbeit leisten.

Probieren Sie das auch mal hier aus. Jeder ist für eine Teilaufgabe zuständig und verantwortlich. Wenn alle Funktionen / Prozeduren fertig sind, dann kann das Gesamtsystem aus den Teilen zusammengebaut werden.

62 Projekt - TestenMit dem entwickelten (De-) Chiffriersystem soll der folgende Geheimtext decodiert werden. Tipp: bello.

OFVTOFRRLSVLAXLVIKSLXSLRSOSXSLRXSLVSVIFJDVQSUDZVSVILSQSROSKISVFVISKSVILSFWBLXFVSKBVIISVIKLXXSVILSILSLVLZKSKSLOSVSVAEKFYZSCSRXSVLVBVASKSKOFRRLSKOSVFVVXUSKISVALSFRRSBVXSKAYZSLISVALYZBVXSKSLVFVISKLVAEKFYZSOSUDZVZSLXSVBVIOSASXTSVILSOFRRLSKXKSVVXJDVISVFWBLXFVSKVISKGRBAAOFKDVVSJDVISVQSROSKVILSMFKVSBVIILSASLVSILSXFEGSKAXSVFRRILSASKALVIILSQSROSKBVITUFKISAUSOSVUSLRALSJDVISKCBRXBKBVIRSQSVAUSLASISKKDSMLAYZSVEKDJLVTFMUSLXSAXSVSVXGSKVXALVIASZKASRXSVCFBGRSBXSTBILSASVCDMMSVBVIIFAUFATBKJSKUSLYZRLYZBVOISKOSMBSXSKGBSZKXSLVGBSZKSVBVIUSLRALSISVOSKMFVSVILSNSVASLXAISAKZSLVSARSQSVBVIMLXISVSVALSAXFSVILOCKLSOGBSZKSVASZKVFZSALVIFBAILSASMOKBVIBSQSKXKSGGSVFBYZILSZSRJSXLSKILSBSQKLOSVOFRRLSKFVXFEGSKCSLXUSLRALSALYZLVGFAXXFSORLYZSVOSGSYZXSVMLXISVOSKMFVSVMSAASVUDQSLALSILSASSVXUSISKJDVLZKSMOSQLSXGSKVZFRXSVDISKASRQAXLVISKSVOSQLSXCFSMEGSVSLVXSLRIFJDVISVULSOSAFOXILSOFRRLSKQSUDZVSVGLVISXASLVSVBKAEKBVOFVISKKZDVSULKIQSOKSVTXJDVISKOFKDVVSISMDTSFVBVIISMOSQLSXISKQSROSKSKAXKSYCXALYZJDVISVASWBFVS...

...KVBVIZSRJSXLSKVZLVQLATBMKZSLVBVITSLOXVFYZVDKISVIFAOSQLSXISKQSROSKQSOLVVXFVISVFSBAASKAXSVOKSVTSVOFRRLSVASKAXKSYCXALYZQLAFVISVBVXSKSVXSLRISAKZSLVABVIRLSOXVFYZVDKIDAXSVFWBLXFVLSVSKAXKSYCXALYZJDVISMGRBAAOFKDVVSQLAFVILSEHKSVFSSVBVITBISMNSVLOSVXSLRISADTSFVAISKQLAAEFVLSVKSLYZXSARLSOXLVKLYZXBVOVDKIUSAXSV

63 Projekt - ErweiterungenDie Zuordnungstabelle soll mit Hilfe eines Schlüsselwortes erzeugt werden.

I N T A L S E R U G V O B C D F H J K M P Q W X Y Z

Schlüsselwort: INITIALISIERUNGVONVARIABLEN

Listen und ihre Verarbeitung Klaus Becker 2009. 2 Listen und ihre Verarbeitung Inhalte:...

Documents

Listen To Our Future

Listen Klaus Becker 2003. KB Listen 2 Listen Ansgar A., Speyer Claudia B., Koblenz Knut B., Neustadt Annett B., Wörrstadt Stefani D., Bad Ems Jochen F.,

Suffix Arrays – Eine Datenstruktur für Stringalgorithmenls11- fileSuffix Arrays – Eine Datenstruktur für Stringalgorithmen Karsten Klein TU Dortmund, Fakultät Informatik, LS11

XML Verarbeitung

ABC ListenABC - Listen ABC - Listen ABC - Listen Title Etiketten Created Date 9/5/2018 9:09:58 AM

1 Trainingsplan mit Java SS 2011. Ziel Grundidee Datenstruktur Programmbeschreibung Ausblick - Optimierungsmöglichkeiten Fazit Agenda 2

Schiedsrichterfortbildung 09.09.05 und 12.09.05. Tagesordnungspunkte Begrüßung Begrüßung Listen und Info zur Fortbildung Listen und Info zur Fortbildung

Diverse Points-Listen (Übersicht) - germany.ru · 08.04.2003 · Diverse Points-Listen (Übersicht) (letzter Stand 04.08.03) Inhaltsverzeichnis: • Pointsliste von Aldi Nord-Produkten

Technische Listen und Tabellen für Kabel ... - meinhart.at · Meinhart Kabel Österreich GmbH Technische Listen und Tabellen.doc Erstellt: 05.02.2010 Strombelastbarkeit von Leitungen

ArcHive, listen, tAgebücHer

Listen Und Tabellen b1 Deutsch Hallo

Signal Verarbeitung(1)

Listen - sto silent · Acoustic references from all over the world Listen StoSilent Sets the tone in acoustics

Leistungsstarke Remarketing-Listen mit Google Analytics

Schiedsrichterfortbildung 08.09.06 und 11.09.06. Tagesordnungspunkte Begrüßung Begrüßung Listen und Info zur Fortbildung Listen und Info zur Fortbildung

Verarbeitung - Plastic Team

Listen der Fehlercodes - MEYTON · Listen der Fehlercodes Listen der Fehlercodes | 1 MEYTON Elektronik GmbH 3 / 24 Listen der Fehlercodes1 Jeder Fehler hat einen eindeutigen Code

13/01/2003 Raster Datenstruktur und Operationen Proseminar Geoinformation II Thomas Artz

DVG2 - 051 Verkettete Listen. DVG2 - 052 Primitive Datentypen 4 Vorteile: –werden direkt vom Prozessor unterstützt –schneller Zugriff –schnelle Verarbeitung

DVG2 - 03 - Verkettete Listen1 Verkettete Listen