kap8d.pps - Lehrstuhl 11 Algorithm Engineering

 Datenstruktur

 26 views
of 32
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Wintersemester 2007/08 Einführung in die Informatik für Naturwissenschaftler und Ingenieure (alias Einführung in die Programmierung) (Vorlesung) Prof. Dr.…
Share
Transcript
Wintersemester 2007/08 Einführung in die Informatik für Naturwissenschaftler und Ingenieure (alias Einführung in die Programmierung) (Vorlesung) Prof. Dr. Günter Rudolph Fakultät für Informatik Lehrstuhl für Algorithm Engineering Kapitel 8: Elementare Datenstrukturen Inhalt ● Definition  ● ADT Keller  ● ADT Schlange  ● ADT Liste  ● ADT Binärbaum  - Exkurs: Einfache Dateibehandlung - Exkurs: Strings (C++) heute - Anwendung ● ADT Graphen Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 2 Exkurs: Einfache Dateibehandlung Datei := speichert Daten in linearer Anordnung Zwei Typen: ● ASCII-Dateien - sind mit Editor les- und schreibbar - Dateiendung („suffix“ oder „extension“) meist .txt oder .asc - betriebssystem-spezifische Übersetzung von Zeichen bei Datentransfer zwischen Programm und externem Speicher ● Binär-Dateien - werden byteweise beschrieben und gelesen - lesen / schreiben mit Editor ist keine gute Idee - schnellerer Datentransfer, da keine Zeichenübersetzung Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 3 Exkurs: Einfache Dateibehandlung Hier: einfache Dateibehandlung! ● Dateien können gelesen oder beschrieben werden. ● Vor dem ersten Lesen oder Schreiben muss Datei geöffnet werden. ● Man kann prüfen, ob das Öffnen funktioniert hat. ● Nach dem letzten Lesen oder Schreiben muss Datei geschlossen werden. ● Bei zu lesenden Dateien kann gefragt werden, ob Ende der Datei erreicht ist. ● Beim Öffnen einer zu schreibenden Datei wird vorheriger Inhalt gelöscht! ● Man kann noch viel mehr machen … wir benötigen: #include bzw. Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 4 Exkurs: Einfache Dateibehandlung ● Eingabe-Datei = input file ● Ausgabe-Datei = output file ifstream Quelldatei; ofstream Zieldatei; Datentyp Bezeichner Datentyp Bezeichner ● Öffnen der Datei: ● Öffnen der Datei: Quelldatei.open(dateiName); Zieldatei.open(dateiName); ist Kurzform von ist Kurzform von Quelldatei.open(dateiName, modus); Quelldatei.open(dateiName, modus); wobei fehlender modus bedeutet: wobei fehlender modus bedeutet: ASCII-Datei, ASCII-Datei, Eingabedatei (weil ifstream) Ausgabedatei (weil ofstream) Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 5 Exkurs: Einfache Dateibehandlung modus: ios::binary binäre Datei ios::in öffnet für Eingabe (implizit bei ifstream) ios::out öffnet für Ausgabe (implizit bei ofstream) ios::app hängt Daten am Dateiende an ios::nocreate wenn Datei existiert, dann nicht anlegen Warnung: teilweise Compiler-abhängig (nocreate fehlt in MS VS 2003, dafür trunc) Man kann diese Schalter / Flags miteinander kombinieren via: ios::binary | ios::app (öffnet als binäre Datei und hängt Daten an) Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 6 Exkurs: Einfache Dateibehandlung ● Datei öffnen file.open(fileName) bzw. file.open(fileName, modus) falls Öffnen fehlschlägt, wird Nullpointer zurückgegeben ● Datei schließen file.close() sorgt für definierten Zustand der Datei auf Dateisystem; bei nicht geschlossenen Dateien droht Datenverlust! ● Ende erreicht? ja falls file.eof() == true ● Lesen (von ifstream) file.get(c); liest ein Zeichen file >> x; liest verschiedene Typen ● Schreiben (von ofstream) file.put(c); schreibt ein Zeichen file << x; schreibt verschiedene Typen Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 7 Exkurs: Einfache Dateibehandlung Merke: 1. Auf eine geöffnete Datei darf immer nur einer zugreifen. 2. Eine geöffnete Datei belegt Ressourcen des Betriebssystems.  Deshalb Datei nicht länger als nötig geöffnet halten. 3. Eine geöffnete Datei unbekannter Länge kann solange gelesen werden, bis das Ende-Bit (end of file, EOF) gesetzt wird. 4. Der Versuch, eine nicht vorhandene Datei zu öffnen (zum Lesen) oder eine schreibgeschützte Datei zu öffnen (zum Schreiben), führt zu einem Nullpointer.  Das muss überprüft werden, sonst Absturz bei weiterer Verwendung! 5. Dateieingabe und -ausgabe (input/output, I/O) ist sehr langsam im Vergleich zu den Rechenoperationen.  I/O Operationen minimieren. “The fastest I/O is no I/O.“ Nils-Peter Nelson, Bell Labs Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 8 Exkurs: Einfache Dateibehandlung #include #include using namespace std; int main() { // zeichenweise kopieren ifstream Quelldatei; ofstream Zieldatei; Quelldatei.open("quelle.txt"); if (!Quelldatei.is_open()) { cerr << "konnte Datei nicht zum Lesen öffnen\n"; exit(1); } Zieldatei.open("ziel.txt"); if (!Zieldatei.is_open()) { cerr << "konnte Datei nicht zum Schreiben öffnen\n"; exit(1); } Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 9 Exkurs: Einfache Dateibehandlung while (!Quelldatei.eof()) { char c; Quelldatei.get(c); Zieldatei.put(c); } Quelldatei.close(); Zieldatei.close(); } offene Datei Start aktuelle Position eof() == true Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 10 Exkurs: C++ Strings Bisher: Zeichenketten wie char str[20]; → Relikt aus C-Programmierung! → bei größeren Programmen mühevoll, lästig, … → … und insgesamt fehlerträchtig! Jetzt: Zeichenketten aus C++ → sehr angenehm zu verwenden (keine 0 am Ende, variable Größe, …) → eingebaute (umfangreiche) Funktionalität wie benötigen: #include und using namespace std; Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 11 Exkurs: C++ Strings Datendefinition / Initialisierung string s1; // leerer String string s2 = "xyz"; // initialisieren mit C-String string s3 = s2; // vollständige Kopie! string s4("abc"); // initialisieren mit C-String string s5(s4); // initialisieren mit C++-String string s6(10, ‘*‘); // ergibt String aus 10 mal * string s7(1‚‘x‘); // initialisieren mit einem char string sx(‘x‘); // FEHLER! string s8(""); // leerer String Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 12 Exkurs: C++ Strings Eingebaute Funktionen ● Konvertierung C++-String nach C-String via c_str() const char *Cstr = s2.c_str(); ● Stringlänge length() cout << s2.length(); ● Index von Teilstring finden int pos = s2.find(“yz“); ● Strings addieren s1 = s2 + s3; s4 = s2 + “hello“; s5 += s4; ● substr(), replace(), ● Strings vergleichen erase(), if (s1 == s2) s3 += s2; … if (s3 < s8) flag = true; Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 13 Kapitel 8: Elementare Datenstrukturen ADT Binäre Bäume: Anwendung Aufgabe: Gegeben sei eine Textdatei. Häufigkeiten der vorkommenden Worte feststellen. Alphabetisch sortiert ausgeben. Strategische Überlegungen: Lesen aus Textdatei → ifstream benutzen! Sortierte Ausgabe → Binärbaum: schnelles Einfügen, sortiert „von selbst“ Worte vergleichen → C++ Strings verwenden! Programmskizze: Jeweils ein Wort aus Datei lesen und in Binärbaum eintragen. Falls Wort schon vorhanden, dann Zähler erhöhen. Wenn alle Wörter eingetragen, Ausgabe (Wort, Anzahl) via Inorder-Durchlauf. Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 14 Kapitel 8: Elementare Datenstrukturen struct BinBaum { string wort; gelesenes Wort int anzahl; wie oft gelesen? BinBaum *links, *rechts; }; BinBaum *Einlesen(string &dateiname) { ifstream quelle; quelle.open(dateiname.c_str()); Datei öffnen if (!quelle.is_open()) return 0; string s; BinBaum *b = 0; while (!quelle.eof()) { Worte einzeln quelle >> s; auslesen und im b = Einfuegen(s, b); Baum einfügen } quelle.close(); Datei schließen + return b; Zeiger auf Baum } zurückgeben Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 15 Kapitel 8: Elementare Datenstrukturen BinBaum *Einfuegen(string &s, BinBaum *b) { if (b == 0) { b = new BinBaum; b->wort = s; b->anzahl = 1; b->links = b->rechts = 0; return b; } if (b->wort < s) b->rechts = Einfuegen(s, b->rechts); else if (b->wort > s) b->links = Einfuegen(s, b->links); else b->anzahl++; return b; } Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 16 Kapitel 8: Elementare Datenstrukturen void Ausgabe(BinBaum *b) { if (b == 0) return; Ausgabe(b->links); cout << b->anzahl << " " << b->wort.c_str() << endl; Ausgabe(b->rechts); } Dies ist die Inorder-Ausgabe. Präorder: Postorder: cout …; Ausgabe(…); Ausgabe(…); Ausgabe(…); Ausgabe(…); cout …; Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 17 Kapitel 8: Elementare Datenstrukturen Hauptprogramm: #include #include #include using namespace std; int main() { string s("quelle.txt"); BinBaum *b = Einlesen(s); Ausgabe(b); return 0; } Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 18 Kapitel 8: Elementare Datenstrukturen Durchlaufstrategien: z.B. Ausdruck des Knotenwertes ● Tiefensuche („depth-first search“, DFS) - Präorder Vor (prä) Abstieg in Unterbäume die „Knotenbehandlung“ durchführen - Postorder Nach (post) Abstieg in bzw. Rückkehr aus Unterbäumen die „Knotenbehandlung“ durchführen - Inorder Zwischen zwei Abstiegen „Knotenbehandlung“ durchführen ● Breitensuche („breadth-first search“, BFS; auch: „level search“) auf jeder Ebene des Baumes werden Knoten abgearbeitet, bevor in die Tiefe gegangen wird Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 19 Kapitel 8: Elementare Datenstrukturen Breitensuche Beispiel: eingegebene Zahlenfolge 17, 4, 36, 2, 8, 40, 19, 6, 7, 37 17 4 36 2 8 19 40 6 37 Ausgabe: 17, 4, 36, 2, 8, 19, 40, 6, 37, 7 7 Implementierung: → Praktikum! Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 20 Kapitel 8: Elementare Datenstrukturen ADT Graph ● Verallgemeinerung von (binären) Bäumen ● Wichtige Struktur in der Informatik ● Zahlreiche Anwendungsmöglichkeiten - Modellierung von Telefonnetzen, Versorgungsnetzwerken, Straßenverkehr, … - Layout-Fragen bei elektrischen Schaltungen - Darstellung sozialer Beziehungen - etc. ● Viele Probleme lassen sich als Graphenprobleme „verkleiden“ und dann mit Graphalgorithmen lösen! Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 21 Kapitel 8: Elementare Datenstrukturen Definition EIn Graph G = (V, E) besteht aus einer Menge von Knoten V („vertex, pl. vertices“) und einer Menge von Kanten E („edge, pl. edges“) mit E  V x V. 1 2 6 (G) = 6 (G) = 3 7 3 5 Schlinge 4 Eine Kante (u, v) heißt Schlinge (“loop“), wenn u = v. Der Grad („degree“) eines Knotens v  V ist die Anzahl der zu ihm inzidenten Kanten: deg(v) = | { (a, b)  E : a = v oder b = v } | . Maxgrad von G ist (G) = max { deg(v) : v  V } Mingrad von G ist (G) = min { deg(v) : v  V } Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 22 Kapitel 8: Elementare Datenstrukturen Definition Für vi  V heißt (v0, v1, v2, …, vk) ein Weg oder Pfad in G, wenn (vi,vi+1)  E für alle i = 0, 1, …, k-1. Die Länge eines Pfades ist die Anzahl seiner Kanten. Ein Pfad (v0, v1, v2, …, vk) mit v0 = vk wird Kreis genannt. Distanz dist(u, v) von zwei Knoten ist die Länge des kürzesten Pfades von u nach v. Durchmesser diam(G) eines Graphes G ist das Maximum über alle Distanzen: diam(G) = max { dist(u, v) : (u, v)  V x V }. Graph ist zusammenhängend, wenn 8 u, v  V mit u  v einen Pfad gibt. G heißt Baum gdw. G zusammenhängend und kreisfrei. Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 23 Kapitel 8: Elementare Datenstrukturen Darstellung im Computer 1 falls (vi,vj)  E ● Adjazenzmatrix A mit aij = 0 sonst Problem: Da | E |  | V |2 = n2 ist Datenstruktur ineffizient (viele Nullen) wenn | E | verschwindend klein. ● Adjazenzlisten: Für jeden Knoten v eine (Nachbarschafts-) Liste L(v) mit L(v) = { u  V : (v, u)  E } Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 24 Kapitel 8: Elementare Datenstrukturen Beispiel c Adjazenzlisten b d L(a) = ( b, e ) L(b) = ( a, c, d ) ADT Liste L(c) = ( b, d ) L(d) = ( b, c, e ) a e L(e) = ( a, d ) Adjazenzmatrix a b c d e a 0 1 0 0 1 b 1 0 1 1 0 Array[][] c 0 1 0 1 0 d 0 1 1 0 1 e 1 0 0 1 0 Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 25 Kapitel 8: Elementare Datenstrukturen Mögliche Funktionalität typedef unsigned int uint; typedef Datentyp TypName; Graph *createGraph(uint NoOfNodes); void addEdge(Graph *graph, uint Node1, uint Node2); void deleteEdge(Graph *graph, uint Node1, uint Node2); bool hasEdge(Graph *graph, uint Node1, uint Node2); uint noOfEdges(); uint noOfNodes(); void printGraph(); Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 26 Kapitel 8: Elementare Datenstrukturen struct Graph { AdjList uint NoOfNodes; List **AdjList; // Zeiger auf Zeiger auf Listen }; List List List List Graph *createGraph(uint NoOfNodes) { Graph *graph = new Graph; graph->NoOfNodes = NoOfNodes; graph->AdjList = new List*[NoOfNodes]; Speicher reservieren for (uint i = 0; i < NoOfNodes; i++) initialisieren! graph->AdjList[i] = create(); return graph; } Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 27 Kapitel 8: Elementare Datenstrukturen struct Graph { AdjList uint NoOfNodes; List **AdjList; // Zeiger auf Zeiger auf Listen }; List List List List uint noOfNodes(Graph *graph) { return graph == 0 ? 0 : graph->NoOfNodes; } uint noOfEdges(Graph *graph) { Ineffizient! if (noOfNodes(graph) == 0) return 0; unsigned int cnt = 0, i; Falls häufig for (i = 0; i < noOfNodes(graph); i++) benutzt, dann cnt += size(graph->AdjList[i]); besser Zähler return cnt / 2; NoOfEdges im } struct Graph Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 28 Kapitel 8: Elementare Datenstrukturen AdjList struct Graph { uint NoOfNodes; List **AdjList; // Zeiger auf Zeiger auf Listen }; List List List List bool hasEdge(Graph *graph, uint Node1, uint Node2) { if (graph == 0) error("no graph"); uint n = noOfNodes(graph); if (Node1 >= n || Node2 >= n) error("invalid node"); return is_elem(Node2, graph->AdjList[Node1]); } void addEdge(Graph *graph, uint Node1, uint Node2) { if (!hasEdge(graph, Node1, Node2)) { append(Node2, graph->AdjList[Node1]); append(Node1, graph->AdjList[Node2]); } } Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 29 Kapitel 8: Elementare Datenstrukturen struct Graph { AdjList uint NoOfNodes; List **AdjList; // Zeiger auf Zeiger auf Listen }; List List List List void printGraph(Graph *graph) { if (noOfNodes(graph) == 0) return; unsigned int i, n = noOfNodes(graph); for (i = 0; i < n; i++) { cout << i << ": "; printList(graph->AdjList[i]); } } Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 30 Kapitel 8: Elementare Datenstrukturen struct Graph { AdjList uint NoOfNodes; List **AdjList; // Zeiger auf Zeiger auf Listen }; List List List List Graph *clearGraph(Graph *graph) { if (graph == 0) return 0; unsigned int cnt = 0, i; for (i = 0; i < noOfNodes(graph); i++) clearList(graph->AdjList[i]); delete[] graph->AdjList; delete graph; return 0; } Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 31 Kapitel 8: Elementare Datenstrukturen int main() { 0 Graph *graph = createGraph(7); addEdge(graph, 0, 2); 6 1 addEdge(graph, 1, 2); addEdge(graph, 3, 2); addEdge(graph, 2, 4); 5 2 addEdge(graph, 4, 6); 4 3 addEdge(graph, 6, 5); addEdge(graph, 5, 2); addEdge(graph, 2, 3); nodes: 7 addEdge(graph, 3, 0); edges: 11 addEdge(graph, 6, 3); 0: 2 1 addEdge(graph, 0, 1); 1: 2 cout << "nodes: " << noOfNodes(graph) << endl; 2: 4 3 cout << "edges: " << noOfEdges(graph) << endl; 3: 2 0 printGraph(graph); 4: 6 graph = clearGraph(graph); 5: 2 cout << "nodes: " << noOfNodes(graph) << endl; cout << "edges: " << noOfEdges(graph) << endl; 6: 5 3 return 0; nodes: 0 } edges: 0 Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 32
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks