Implementierung — Datentypen, Kontrollstrukturen und einfache Algorithmen
Datentypen und Variablen
Programme verarbeiten Daten unterschiedlichen Typs, u. a.:
- Ganzzahl (Integer): ganze Zahlen ohne Nachkommastellen, z. B. 5, -12
- Gleitkommazahl (Float/Double): Zahlen mit Nachkommastellen, z. B. 3.14
- Zeichenkette (String): Text, z. B. "Hallo"
- Wahrheitswert (Boolean): genau zwei mögliche Werte, wahr oder falsch
- Array/Liste: eine geordnete Sammlung mehrerer Werte gleichen Typs, zugreifbar über einen Index (Position)
Eine Variable ist ein benannter Speicherplatz für einen Wert eines bestimmten Typs. Eine Variable, die nur innerhalb einer Funktion sichtbar ist und ausserhalb nicht existiert, heisst lokale Variable.
Kontrollstrukturen
Kontrollstrukturen steuern den Ablauf eines Programms:
- Verzweigung (if/else): Abhängig von einer Bedingung wird der eine oder der andere Codeblock ausgeführt.
- Zählschleife (for): Ein Codeblock wird eine im Voraus bekannte Anzahl Mal wiederholt (z. B. für i = 1 bis 5).
- Bedingte Schleife (while): Ein Codeblock wird wiederholt, solange eine Bedingung erfüllt ist — die Anzahl Durchläufe ist im Voraus nicht zwingend bekannt.
- Verschachtelte Schleifen: Eine Schleife innerhalb einer anderen Schleife; die Gesamtzahl der Durchläufe des inneren Blocks entspricht dem Produkt der beiden Durchlaufzahlen.
- Strukturierte Programmierung: Beschränkt sich auf Sequenz, Verzweigung und Schleife und vermeidet Sprunganweisungen (Spaghetti-Code).
continueüberspringt den Rest des Schleifendurchlaufs,breakbeendet die Schleife (Beispiele: Summe von 1 bis 8 ohne Vielfache von 3 ergibt 1 + 2 + 4 + 5 + 7 + 8 = 27; wird die Folge 7, 9, 13, 17 … addiert und bei 17 mitbreakabgebrochen, ergibt die Summe 7 + 9 + 13 = 29).
Beim Nachvollziehen (Tracing) von Pseudocode wird jede Codezeile Schritt für Schritt gedanklich ausgeführt, um den Endzustand der Variablen zu bestimmen.
Einfache Algorithmen
- Lineare Suche: Ein Array wird Element für Element von vorne durchsucht, bis der gesuchte Wert gefunden ist oder das Ende erreicht wird. Im schlechtesten Fall sind so viele Vergleiche nötig wie Elemente vorhanden sind.
- Binäre Suche: Setzt ein sortiertes Array voraus. Es wird stets mit dem mittleren Element verglichen; je nachdem, ob der gesuchte Wert kleiner oder grösser ist, wird nur noch in der linken oder rechten Hälfte weitergesucht. Dadurch werden deutlich weniger Vergleiche benötigt als bei der linearen Suche, besonders bei grossen Arrays.
- Sortieralgorithmen (Grundgedanke): Einfache Sortierverfahren wie Bubble Sort vergleichen wiederholt benachbarte Elemente und vertauschen sie bei falscher Reihenfolge, bis das Array vollständig sortiert ist.
Datentypen im Detail
- Elementare (primitive) Datentypen nehmen nur einen Wert ihres Wertebereichs auf (Ganzzahl, Zeichen, Wahrheitswert). Wahrheitswerte sind je nach Sprache TRUE/FALSE oder ungleich 0/gleich 0. Ein Aufzählungstyp (ENUM) hat einen frei gewählten Wertebereich (z. B. SCHWARZ, ROT, BLAU). Ein Datum lässt sich als Ganzzahl speichern (z. B. Millisekunden seit 1. Januar 1970). Ein Nullzeiger (NULL, None, NIL) verweist auf kein Objekt und ist von allen Zeigern auf Objekte verschieden; er zeigt nicht auf ein Objekt mit dem Wert 0.
- Wertebereiche: Ein vorzeichenloser 16-Bit-Typ stellt $2^{16} = 65,536$ Werte dar; mit Vorzeichen reicht er von $-2^{15}$ bis $2^{15} - 1 = 32,767$. Gleitkommazahlen haben nur eine begrenzte Genauigkeit, weil elementare Datentypen eine festgelegte, endliche Zahl von Bits haben.
- Abstrakter Datentyp (ADT): Daten sind mit allen Operationen verbunden, die auf sie zugreifen; der Zugriff erfolgt nur über diese Operationen, die Daten sind nach aussen gekapselt.
- Zeichenkodierung: UTF-8 kodiert ein Zeichen mit einer bis vier 8-Bit-Einheiten (ASCII-Zeichen mit einer, drei Einheiten = 24 Bit). Ein CHAR (eine Code-Einheit) entspricht deshalb in UTF-8 nur bei ASCII-Zeichen einem vollständigen Zeichen, in UTF-16 nicht bei Zeichen, die zwei Code-Einheiten brauchen.
- Datenstrukturen: Ein Stack (Stapel) arbeitet nach LIFO, eine Queue (Warteschlange) nach FIFO (z. B. für Druckaufträge in Eingangsreihenfolge). Ein Array erlaubt direkten Indexzugriff, eine einfach verkettete Liste nur sequenziellen Zugriff.
Algorithmen und Aufwand
- Lineare Suche braucht keine Sortierung; im schlechtesten Fall ist der Aufwand $O(n)$ (z. B. 19 im Array [5, 12, 8, 3, 19, 7] nach 5 Vergleichen). Binäre Suche halbiert den Suchraum; bei 1'000 Elementen braucht sie höchstens 10 Vergleiche ($2^{10} = 1,024$). Die O-Notation beschreibt den Aufwand in Abhängigkeit von der Eingabegrösse. Eine rekursive Funktion braucht eine Abbruchbedingung. Verschachtelte Schleifen: 60 mal 60 = 3'600 Durchläufe des inneren Rumpfs. Doppelt vorhandener Code (z. B. dieselbe Umrechnung an fünf Stellen) wird in eine einzige Funktion ausgelagert. Eine zählergesteuerte
for-Schleife nimmt man, wenn die Zahl der Durchläufe feststeht. - Ausnahmebehandlung (try-catch; für Python siehe unten «Ausnahmen») fängt erwartete und unerwartete Fehler ab, ohne dass die Applikation unkontrolliert abbricht. Ein Fehlerprotokolleintrag enthält Zeitstempel, Fehlermeldung und Kontext. Ein Compiler übersetzt den Quellcode vor der Ausführung vollständig (Kompilieren), ein Interpreter führt ihn Zeile für Zeile aus.
Python: Ausdrücke, Zeichenketten, Strukturen
- Operatoren:
/liefert in Python 3 immer eine Gleitkommazahl (8 / 4ergibt2.0,8 / 5ergibt1.6).//ist die ganzzahlige Division mit Abrunden (17 // 3ergibt5,-17 // 5ergibt-4).**bindet stärker als das unäre Minus:-3 ** 2ergibt-9.and/orwerten per Kurzschluss aus: Ist beiA and B and Cdas B falsch, wird C nicht mehr ausgewertet;'' or 'Trondheim'liefert'Trondheim'.passtut nichts (Platzhalter) und beendet keine Schleife;continuespringt zum nächsten Durchlauf;breakverlässt die Schleife. Derelse-Zweig einer Schleife läuft, wenn die Schleife ohnebreakendet.range(5)erzeugt 0 bis 4.forläuft über die Elemente einer beliebigen Folge in deren Reihenfolge.print(i, end='|')hängt|statt eines Zeilenumbruchs an.matchmitcase _als Platzhalter fängt alle übrigen Werte.
Zeichenketten
- Zeichenketten sind unveränderbar (Zuweisung an einen Index löst einen Fehler aus). Slices wie
wort[3:7](aus'Programm'wird'gram') sind fehlertolerant:wort[4:42]undwort[42:]ergeben keinen Fehler (leere Zeichenkette bzw. Rest).2 * 'ab' + 'cd'ergibt'ababcd'. Zwei Literale nebeneinander werden verbunden, eine Variable und ein Literal nicht. In einer Raw-Zeichenkette (r'...') bleiben Backslashes erhalten; ohnerwird\nzum Zeilenumbruch.
Listen
- Listen: veränderbar. Eine Zuweisung
rgba = rgbkopiert nicht (beide Namen zeigen auf dieselbe Liste); eine Kopie entsteht mitb = a[:].list.count(x)zählt,list.index(x)liefert den Index des ersten Treffers,list.sort()sortiert an Ort und gibtNonezurück.appendlegt oben ab undpop()entnimmt das oberste Element (Stapel); für eine Warteschlange nimmt mancollections.dequemitappendundpopleft.del a[0],del a[2:4]undletters[2:5] = []entfernen Elemente. Listen-Abstraktionen:[(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]ergibt 7 Paare; verschachtelte Schleifen laufen von links nach rechts. Ein Generatorausdruck in runden Klammern erzeugt die Werte erst bei Bedarf, nicht sofort die ganze Liste.
Tupel, Mengen, Wörterbücher
- Tupel, Mengen, Wörterbücher: Ein Tupel mit einem Element schreibt man
('hallo',)(das Komma zählt, nicht die Klammer). Tupel können veränderbare Elemente enthalten. Eine leere Menge erzeugt man mitset(), nicht mit{}(das ist ein leeres Wörterbuch). Mengen enthalten kein Element doppelt;a ^ bist die symmetrische Differenz. Wörterbuchschlüssel müssen unveränderbar sein, eine Liste ist deshalb als Schlüssel unzulässig.d[key]löst bei fehlendem Schlüssel einenKeyErroraus,getliefertNone.list(d)liefert die Schlüssel in Einfügereihenfolge. Wörterbuch-Abstraktion{x: x**2 for x in (2, 4, 6)}[4]ergibt 16.zip(xvec, yvec)paart Elemente (Skalarprodukt von [10, 20, 30] und [7, 5, 3] = 260). Fehlertypen:NameError(unbekannter Name),ZeroDivisionError(1 / 0),KeyError,ValueError(removeeines nicht enthaltenen Werts),StopIteration(Iterator erschöpft),TypeError(z. B. Schlüsselwort-Übergabe an einen nur-positionellen Parameterarg, /).
Python: Funktionen, Gültigkeit, Klassen, Ausnahmen
- Funktionen: Ohne
returnliefert eine FunktionNone. Der Standardwert eines Parameters wird einmal bei der Definition ausgewertet (i = 5; def f(arg=i)bleibt bei 5, auch wennidanach 6 ist). Deshalb nimmt man beidef f(a, L=None)Noneund legt die Liste im Rumpf an; mitL=[]teilen sich alle Aufrufe dieselbe Liste. Eine Funktion erhält eine Referenz auf übergebene Listen; einappendist für den Aufrufer sichtbar. Ein positionelles Argument darf nicht hinter einem Schlüsselwortargument stehen.*argssammelt zusätzliche positionelle,**kwargsSchlüsselwortargumente (f(1, 2, a=3, b=4, c=5)zählt 5). Ein alleinstehender Stern (def f(a, *, b)) macht b nur als Schlüsselwortargument übergebbar; ein/macht Parameter nur positionell. Ein Lambda (lambda x: x + n) ist eine kleine namenlose Funktion aus genau einem Ausdruck, nie aus mehreren Anweisungen. Der Docstring ist die Zeichenkette als erste Anweisung im Rumpf. Ein Generator liefert mityieldnacheinander Werte und merkt sich seinen Zustand. - Gültigkeitsbereich: Eine in einer Funktion deklarierte Variable ist lokal; eine Zuweisung innerhalb der Funktion ändert eine gleichnamige globale Variable nicht (
x = 1; f()mit lokalemx = 2druckt 1). Mitglobal xwirkt die Zuweisung global (druckt 2); in verschachtelten Funktionen braucht eine Neuzuweisung der Variable der umgebenden Funktionnonlocal. - Klassen: Der Konstruktor (
__init__) initialisiert ein neues Objekt. Instanzvariablen gehören einer Instanz, Klassenvariablen werden von allen Instanzen geteilt (eine Listetricksals Klassenvariable würde von allen Hunden gemeinsam genutzt).x.f()entsprichtMyClass.f(x). Python kennt Mehrfachvererbung und keine echten privaten Attribute; ein führender Unterstrich ist nur eine Konvention.
Ausnahmen
- Ausnahmen:
try/exceptfängt Ausnahmen ab; bei verwandten Klassen stehen die spezielleren abgeleiteten Klassen zuerst, weil die erste passendeexcept-Klausel gewinnt. Eineexcept-Klausel für eine Basisklasse fängt auch abgeleitete Ausnahmen, nicht umgekehrt. Einraiseohne Angabe imexcept-Block reicht die Ausnahme erneut weiter.finallyläuft immer; einreturninfinallyüberschreibt dasreturnimtry(f()liefertFalse).with open(pfad) as fschliesst die Datei nach dem Block immer, auch bei einem Fehler.
Git
- Modell: Git speichert Zustände (Schnappschüsse) eines Projekts, nicht die Änderungen dazwischen. Objekte tragen einen SHA-1-Namen aus 40 Hexadezimalzeichen; der Inhalt eines Objekts lässt sich nicht ändern, ohne dass sich sein Name ändert. Ein Tag ist ein fester Name für einen Commit und rückt nicht mit neuen Commits vor. Ein Branch ist eine Entwicklungslinie, deren neuester Commit (Spitze) vom Branch-Namen bezeichnet wird.
HEAD~4liegt vier Generationen oberhalb von HEAD. Beispiel: master hat A bis E, stable zeigt auf B:git log stable..masterlistet C, D, E (3 Commits). Die Commits, die nur auf einer von zwei Linien liegen (symmetrische DifferenzA...B), sind die Summe der eigenen Commits beider Branches (4 + 3 = 7). Zeigt ein Tag auf C3 und ist C11 die Spitze, liegen 8 Commits (C4 bis C11) nach dem Tag.
Arbeitsbereiche
- Arbeitsbereiche:
git add dateilegt den aktuellen Inhalt als Schnappschuss in den Index (Staging-Bereich);git commit -animmt nur bereits bekannte Dateien auf, nicht neu angelegte.git diff --cachedvergleicht den Index mit dem letzten Commit (genau das, was der nächste Commit enthalten wird). Ein Arbeitsverzeichnis mit uncommitteten Änderungen ist dirty. Detached HEAD: HEAD zeigt direkt auf einen Commit statt auf einen Branch. Commit-Nachricht: kurze Titelzeile (höchstens etwa 50 Zeichen), Leerzeile, dann Details.
Zusammenführen
- Zusammenführen: Ein Fast-Forward entsteht, wenn der andere Branch ein Nachfolger des aktuellen Stands ist; Git rückt nur den Zeiger vor, ohne Merge-Commit.
git rebasewendet Änderungen eines Branches neu auf einer anderen Basis an.git cherry-pickübernimmt die Änderung eines Commits als neuen Commit.git bisectsucht per binärer Suche den Commit, der einen Fehler eingeführt hat.git branch -dlöscht nur bereits zusammengeführte Branches,-Derzwingt es.
Remote
- Remote:
git clonekopiert die gesamte Historie und richtet das Remote origin ein. Ein Remote-Tracking-Branch wieorigin/masterist eine lokale Referenz auf den zuletzt bekannten Stand im Remote.git fetchholt Änderungen, ohne sie mit dem aktuellen Branch zusammenzuführen, und ist auch bei uncommitteten Änderungen sicher.git pushüberträgt lokale Commits; er wird abgelehnt, wenn der Remote-Head kein Vorfahre des lokalen Heads ist. Ein Bare-Repository dient als Veröffentlichungsort ohne Arbeitsverzeichnis. Das Git-Protokoll (git-daemon) läuft auf TCP-Port 9418. Ein bereits gepushter fehlerhafter Commit auf einem gemeinsamen Branch wird mitgit revertdurch einen neuen Commit rückgängig gemacht;git reset --hardauf öffentlichen Branches ist nicht unbedenklich. Der Hauptnutzen einer Versionsverwaltung: Jede Änderung ist mit Autor, Zeitpunkt und Begründung nachvollziehbar.
Häufige Fehler
- Bei verschachtelten Schleifen die Gesamtzahl der Durchläufe addieren statt multiplizieren.
- Bei der ganzzahligen Division Nachkommastellen fälschlicherweise aufrunden statt abzuschneiden (Python rundet mit
//bei negativen Zahlen nach unten:-17 // 5ergibt-4). - Binäre Suche auf einem unsortierten Array anwenden — dafür ist zwingend eine sortierte Reihenfolge Voraussetzung.
- Schleifenbedingung falsch auswerten und dadurch einen Durchlauf zu viel oder zu wenig zählen (Off-by-one-Fehler).