Kapitel 3

 Datenstruktur

 46 views
of 17
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
Kapitel 3 Elementare Datenstrukturen © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 1 3.1 Grundlegendes Elementare Datenstrukturen: …
Share
Transcript
Kapitel 3 Elementare Datenstrukturen © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 1 3.1 Grundlegendes Elementare Datenstrukturen:  Arrays (Felder)  Verkettete Listen bilden die Bausteine für abstrakte Mechanismen, die ausgehend von niederen Ebenen aufgebaut sind und Algorithmen mit zunehmender Komplexität ermöglichen © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 2 3.2 Arrays (Felder) Arrays:  Eine feste Sammlung von Daten desselben Typs, die zusammen- hängend gespeichert und über einen Index zugängig sind  Fundamentale Datenstruktur: Direktes Abbild des Speichersystems. Ein Arrayzugriff a[i] wird in nur wenige Maschinenanweisungen übersetzt  Programme mit Arrays werden in effiziente Maschineprogramme übersetzt. © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 3 3.2 Arrays (Felder) Beispiel: Das Primzahlensieb des Eratosthenes  Ältester und bekanntester Siebalgorithmus, benannt nach Eratosthenes (ca. 200 v. Chr.)  Prinzip von Siebalgorithmen: Eine Menge von Elementen wird in zwei Klassen aufgeteilt: die guten und die schlechten Elemente. Schlechte Elemente sind einfacher zu finden als gute. Ein Siebprozess eliminiert sukzessive Elemente, die als schlecht erkannt wurden. Jedes eliminierte Element hilft, weitere schlechte Elemente zu erkennen. Die überlebenden Elemente müssen die guten sein. Siebalgorithmus für Primzahlen: • gut = ist eine Primzahl • schlecht = ist keine Primzahl © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 4 3.2 Arrays (Felder) Primzahlensieb von Eratosthenes: Alle Primzahlen kleiner gleich n ausgeben  Markiere die kleinste Primzahl, d.h. 2, und entferne alle ihre Vielfachen innerhalb des gewünschten Bereichs 1 … n.  Die kleinste verbleibende Zahl muß prim sein, markiere sie und entferne wieder alle ihre Vielfachen.  Wiederhole diesen Prozess für alle Zahlen bis n (Falls eine ganze Zahl c <= n faktorisiert werden kann als c = a · b, so muß entweder a <= n oder b <= n gelten) © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 5 3.2 Arrays (Felder) © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 6 3.2 Arrays (Felder) static void eratosthenes(int n) { int sqrtn = (int) Math.floor(Math.sqrt((double) n)); Sieve s = new Sieve(n); int p = 2; while (p <= sqrtn) { int i = p * p; while (i <= n) { s.remove(i); i = i + p; } do p++; while (! s.isMember(p)); } int c = 0; for (int i = 2; i <= n; i++) if (s.isMember(i)) { c++; System.out.println("prim(" + c + ") = " + i); } } © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 7 3.2 Arrays (Felder) public class Sieve { public final int n; // Groesse des Sieve private static final int ws = 64; // Anzahl Bit in long private final int as; // Groesse des Arrays private long[] s; // zur Speicherung des Sieve // Konstruktor public Sieve(int n) { this.n = n; as = (n + ws - 1) / ws; s = new long[as]; for (int i = 0; i < as; i++) s[i] = ~0L; } © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 8 3.2 Arrays (Felder) // public Methoden /** * Liefert "true" zurueck, falls das Element im * Sieve enthalten ist, sonst "false". */ public boolean isMember(int e) { if ((1 <= e) && (e <= n)) { int i = (e - 1) / ws; e = (e - 1) % ws; return ((s[i] & (1L << e)) != 0); } else return false; } © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 9 3.2 Verkettete Listen  Listenstrukturen = dynamische Datenstrukturen Mithilfe von Einfüge- und Löschoperationen können Listenstrukturen zur Laufzeit nicht nur die gespeicherten Datenwerte, sondern auch ihre Größe und Struktur verändern  Listen: Schlüsselidee • Alloziere benötigten Speicherplatz nicht wie beim Array in einem großen zusammenhängenden Teil, sondern dynamisch in kleinen Fragmenten, die ein gegebenes Objekt speichern können • Verknüpfung von Datenelementen, die verstreut im Speicher liegen, erfolgt durch Zeiger bzw. Referenzen, d.h. Speicheradressen, an denen die Elemente gegenwärtig abgelegt sind © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 10 3.2 Verkettete Listen  Zeiger oder Referenz • Ein Sprachkonstrukt, das in modernen Programmiersprachen benutzt wird, um das Äquivalent einer Speicheradresse darzustellen • Im wesentlichen eine Speicheradresse, kann aber mehr Informationen enthalten: In Java oder anderen streng getypten Sprachen beziehen sich Zeiger bzw. Referenzen auch auf die Typdefinitionen der Objekte, auf die sie verweisen  Übersetzer kann die konsistente Benutzung von Zeiger- bzw. Referenzvariablen sicherstellen • Zeigervariable bzw. Referenzvariable nimmt Speicheradressen als Werte an © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 11 3.2 Verkettete Listen Definition: Eine verkettete Liste ist eine Menge von Elementen, bei der jedes Element zu einem Knoten gehört, der auch eine Verbindung zu einem Knoten enthält. head tail e1 e2 ... ei ei+1 ... en null public class ListNode { private E element = null; private ListNode next = null; public ListNode() { }; public ListNode(E element) { this.element = element; } © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 12 3.2 Verkettete Listen public void setNextNode(ListNode next) { this.next = next; } public ListNode getNextNode() { return next; } public void setData(E element) { this.element = element; } public E getData() { return element; } } // class ListNode © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 13 3.2 Verkettete Listen  Einfügen eines neuen Knotens als Nachfolger eines Knotens, gegeben durch den Zeiger p: q = new ListNode(y); q.setNextNode(p.getNextNode()); q.next = p.next; p.setNextNode(q); p.next = q; Abkürzende Schreibweise, die aber nicht den Grundsätzen der objekt- orientierten Programmierung (Zugriff auf in einer Klasse gekapselte Attribute nur über spezielle Zugriffsmethoden!) entspricht und daher so nicht in Programmen verwendet werden sollte! q head p tail y e1 e2 ... ei ei+1 ... en null © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 14 3.2 Verkettete Listen  Löschen des Nachfolgers eines Knotens, gegeben durch den Zeiger p: p.next = p.next.next; head p tail e1 e2 ... ei–1 ei ei+1 ... en null © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 15 3.2 Verkettete Listen  Erzeugung einer Liste: ListNode head, tmp; head = new ListNode(0); tmp = head; for (int i = 1; i < 4; i++) { tmp.next = new ListNode(i); tmp = tmp.next; } tmp tmp tmp tmp i 1 3 2 head 0 1 null 2 null 3 null null © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 16 3.2 Verkettete Listen  Traversierung der Liste (Ausgabe): tmp = head; while (tmp != null) { System.out.println(tmp.data + " "); tmp = tmp.next; } tmp tmp  Ausgabe: 0 1 2 3 © Xiaoyi Jiang Informatik II – Datenstrukturen und Algorithmen 17
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