Informatik: Heiße AlgoRhythmen: Ganz schön link
Released by matroid on Do. 15. Juni 2006 00:28:19 [Statistics]
Written by Gockel - 5533 x read [Outline] Printable version Printer-friendly version -  Choose language   
Informatik

\(\begingroup\) Logo 'Heiße AlgoRhythmen'

Linked Lists - Verkettete Listen


\geo ebene(600,100) x(0,12) y(-1,1) noaxis() nolabel() punktform(.) replace() konst(k,0.15) konst(kk,0.7) makro(pfeil,\ konst(a,%1) konst(b,%2) konst(c,%3) konst(d,%4)\ konst(l,sqrt((c-a)*(c-a)+(b-d)*(b-d))) konst(f,k/l)\ konst(u,c-f*(c-a+kk*(b-d)))\ konst(v,d-f*(d-b+kk*(c-a)))\ konst(uu,c-f*(c-a+kk*(-b+d)))\ konst(vv,d-f*(d-b+kk*(-c+a)))\ p(a,b,p1) p(c,d,p2) s(p1,p2) p(u,v,p3) p(uu,vv,p4)\ f(p2,p3,p4,black)) makro(box,\ konstante(xp1,%1+0.5)\ konstante(yp1,%2+0.5)\ konstante(xp2,%1+1)\ \ konstante(x3,%1+0.75)\ konstante(x4,%1+1.5)\ konstante(y5,%2+0.25)\ \ punkt(%1,%2, p1_box_%3)\ punkt(xp1,%2, p2_box_%3)\ punkt(xp2,%2, p3_box_%3)\ punkt(%1,yp1, q1_box_%3)\ punkt(xp1,yp1,q2_box_%3)\ punkt(xp2,yp1,q3_box_%3)\ s(p1_box_%3,q1_box_%3) s(p2_box_%3,q2_box_%3)\ s(p3_box_%3,q3_box_%3) s(p1_box_%3,p3_box_%3)\ s(q1_box_%3,q3_box_%3)\ punktform(of) p(x3,y5) punktform(.)\ pfeil(x3,y5,x4,y5)\ ) box(0.0,0,b1) box(1.5,0,b2) box(3.0,0,b3) box(4.5,0,b4) box(6.0,0,b5) print(42,0.2,0.4) print(opimg(=),1.7,0.4) print(6,3.2,0.4) print(opimg(*),4.7,0.45) print(9,6.2,0.4) print(\big\ NULL,7.6,0.4) \geooff \geoprint(,,-0.2,-0.2,8.5,0.7)
Dynamische Datenstrukturen sind ein wesentlicher Grundpfeiler beinahe jedes Programms. Umso wichtiger ist es für Programmierer und solche, die es werden wollen, mit den einfachsten Typen von dynamischen Datenstrukturen umgehen zu können. Zu jenen grundlegenden Typen zählt auch die so genannte Verkettete Liste, über die ich hier schreiben werde.


Inhalt



Zeig' mal!

Um Datenstrukturen überhaupt "dynamisch" werden zu lassen, muss man sich mit dem Konzept des Zeigers vertraut machen. Zeiger sind zunächst erstmal Variablen wie alle anderen. Bedeutend ist jedoch, dass sie im Gegensatz zu anderen Variablen wie Integern o.Ä. nicht direkt den Wert speichern, für den sich der Programmierer und sein Programm interessieren. Zeiger speichern nur Speicheraddressen von anderen Variablen. Sie sind sozusagen nur Adresskärtchen, die einem sagen, wo das Gewünschte zu finden ist, ohne mitzuteilen, was genau sich dort eigentlich befindet. Auf den ersten Blick mag das befremdlich und umständlich erscheinen, denn wozu sollte man den "Umweg" über Zeiger machen, anstatt direkt auf die Objekte zuzugreifen, die man benötigt. Der Clou an Zeigern ist jedoch ihre Dynamik: Auf welche Adresse sie zeigen, kann und soll während der Laufzeit des Programms verändert werden. Mit Zeigern wird es möglich, im laufenden Betrieb neuen Speicher anzufordern und nicht mehr benötigten freizugeben. Nun wird erkenntlich, dass Zeiger den Schlüssel zu jeder Form von dynamischer Datenstruktur bieten und eine Beschäftigung mit ihnen unabdingbar ist. Ein alternativer Zugang, den einige Programmiersprachen wie Java bieten, sind die sogenannten Referenzen, die im Prinzip aber ähnlich funktionieren. Auch sie stellen nur "Verweise" auf die eigentliche Variable dar. In der Tat ist in Java z.B. jede Instanz einer Klasse in Wirklichkeit nur eine Referenz auf die eigentlichen Daten, so dass man in Java mehr Referenzen als "gewöhnliche" Variablen sieht, auch wenn der Unterschied in der Verwendung der Objekte (absichtlich) nicht zu merken ist: In Java z.B. sind sie syntaktisch von normalen Variablen wie Integern so gut wie nicht zu unterschieden. Referenzen werden intern mit Zeigern verwaltet, daher sollte man sich in jedem Fall mit Zeigern auseinandersetzen, auch wenn man in der Praxis vielleicht Referenzen lieber benutzt, da sie meistens (wie z.B. in Java) sehr viel intuitiver benutzt werden können. Zeiger sind, wie gesagt, kleine Variablen, die nicht mehr als eine Adresse im Hauptspeicher beinhalten. Zu so einer Adresse gehört bei vernünftiger Programmierung natürlich auch eine Variable, auf die der Zeiger zeigt, d.h. deren Position im Speicher mit der übereinstimmt, die in der Zeigervariablen gespeichert ist. \geo noaxis() nolabel() punktform(.) p(0,0.2,A) p(0,0.95,B) p(1.5,0.95,C) p(1.5,0.2,D) s(A,B) s(B,C) s(C,D) s(D,A) print(\big\ 0x87dd67e6,0.2,0.75) p(2.5,0.2,A2) p(2.5,0.95,B2) p(4,0.95,C2) p(4,0.2,D2) s(A2,B2) s(B2,C2) s(C2,D2) s(D2,A2) print(0x87dd67e6,2.5,1.2) print(\big\ 42,2.7,0.75) \geooff \geoprint(,,0,0,4.2,1.2) In diesem Beispiel kann man das Prinzip sehen. Der eigentliche Zeiger ist links abgebildet. Eine einfache Variable, die nur die Speicheradresse 0x87dd67e6 enthält. An dieser Speicheradresse ist der eigentliche Inhalt zu finden, eine Integer-Variable mit dem Wert 42. Da die Adresse an sich vollkommen unwichtig ist und i.d.R. bei jedem Programmstart anders lautet - das Betriebssystem entscheidet ja jedes Mal neu, wo im RAM der von der Variablen benötigte Speicher liegen soll - wird sie nicht mitnotiert in solchen Diagrammen. Dass es sich um einen Zeiger handelt, wird stattdessen durch - Achtung: große Überraschung - einen Pfeil dargestellt: \geo # noaxis() nolabel() punktform(.) replace() konst(k,0.2) konst(kk,0.5) makro(pfeil,\ konst(a,%1) konst(b,%2) konst(c,%3) konst(d,%4)\ konst(l,sqrt((c-a)*(c-a)+(b-d)*(b-d))) konst(f,k/l)\ konst(u,c-f*(c-a+kk*(b-d)))\ konst(v,d-f*(d-b+kk*(c-a)))\ konst(uu,c-f*(c-a+kk*(-b+d)))\ konst(vv,d-f*(d-b+kk*(-c+a)))\ p(a,b,p1) p(c,d,p2) s(p1,p2) p(u,v,p3) p(uu,vv,p4)\ f(p2,p3,p4,black)) p(0,0.2,A) p(0,0.95,B) p(1.5,0.95,C) p(1.5,0.2,D) s(A,B) s(B,C) s(C,D) s(D,A) p(2.5,0.2,A2) p(2.5,0.95,B2) p(4,0.95,C2) p(4,0.2,D2) s(A2,B2) s(B2,C2) s(C2,D2) s(D2,A2) punktform(of) p(0.75,0.575) punktform(.) pfeil(0.75,0.575,2.5,0.575) print(\big\ 42,2.7,0.75) \geooff \geoprint(,,0,0,4.2,1.2)

Zeiger-Operationen

Die beiden wichtigsten (und meist auch einzigen) Operationen, die man mit Zeigern durchführen kann, sind das Referenzieren und das Dereferenzieren. Wie die Namen schon andeuten, handelt es sich um zwei gegensätzliche Operationen: Das Referenzieren ist jene Operation, die zu einer beliebigen Variablen einen Zeiger auf eben diese Variable zurückliefert. Wichtig ist bei beiden Operationen, dass man in typstrengen Sprachen wie C/C++, Java, Pascal etc. vor allem typgebundene Zeiger hat, d.h. es gibt für jeden Datentyp, den man im Programm verwenden kann (sofern möglich auch für selbst erstellte Datentypen), einen entsprechenden Zeigertyp und bei Zuweisungen und Umwandlungen gelten dieselben Regeln wie beim Umgang mit "normalen" Datentypen. \sourceon C int *zeiger; int i = 42; // Referenzieren der Variable i zeiger = &i; // der Zeiger beinhaltet nun die // Speicheradresse von i \sourceoff Das Derefenzieren ist fast noch wichtiger als das Referenzieren. Durch das Derefenzieren bekommt man von einem Zeiger aus Zugriff auf jene Variable, auf die der Zeiger zeigt und an der man ja eigentlich interessiert ist. \sourceon C // Die Variable j wird durch das // Dereferenzieren des Zeigers mit einem // Wert versehen int j = *zeiger; // j enthält nun denselben Wert wie die // Variable, auf die der Zeiger zeigte, // also den Wert 42. \sourceoff In Java und anderen Sprachen, die Referenzen benutzen, ist das (De)Referenzieren nicht zu spüren, sondern wird implizit bei jeder Art von Zugriff verwendet. Eine weitere implizite Benutzung des Derefenzierens gibt es auch in C/C++. Arbeitet man nämlich Zeiger mit Strukturen, Unions bzw. Klasseninstanzen, so verwendet man oftmals den Pfeil-Operator ->. \sourceon C struct complex { double re; double im; } // Eine komplexe Zahl struct complex z = {0.0,1.0}; // und ein Zeiger auf eine solche struct complex *s = &z; [...] printf("%d+%d*i", s->re, s->im); // diese Anweisung ist eine Abkürzung für printf("%d+%d*i",(*s).re,(*s).im); \sourceoff Für den Zugriff auf das Objekt, auf das s zeigt, kann man wie oben den Stern-Operator * zur Derefenzierung benutzen. Und durch den Punkt-Operator haben wir Zugriff auf die Elemente in diesem Objekt. Zur Abkürzung des Ganzen und zur Vermeidung der auf diese Weise nötigen Klammern gibt es den Pfeil-Operator, der eine Kombination aus genau diesen beiden Vorgängen darstellt: Dereferenzierung des Objektzeigers und Zugriff auf die im Objekt enthaltenen Elemente/Methoden etc. Überall, wo ein Pfeil-Operator steht, ist also auch eine Dereferenzierung inbegriffen.

Das Nix

Ein spezieller Zeiger, den man immer braucht, ist der so genannte NULL-Zeiger. Er ist ein reservierter Wert, der signalisiert, dass die Zeigervariable an kein Objekt gebunden ist. Er wird oft dafür verwendet, um Ausnahmezustände zu signalisieren, z.B. Fehler, die während eines Programms aufgetreten sind. Wir werden ihn später u.A. dazu benutzen, um das Ende einer verketteten Liste zu markieren. Sofern eine automatische Variablen-Initialisierung vorgenommen wird, werden Zeiger mit eben diesem NULL-Zeiger initialisiert, genau wie Zahlen immer mit dem Wert 0 oder 0.0 initialisiert werden. Es gibt in jeder Sprache, die Zeiger oder Referenzen unterstützt, eine Entsprechung des NULL-Zeigers, in Java z.B. die null-Referenz. In Pascal und Delphi heißt dieser Wert nil. Ein NULL-Zeiger kann auch nicht derefenziert werden, denn es gibt ja keine Variable, auf die man durch das Derefenzieren zugreifen könnte. Eine der häufigsten Fehlerursachen ist der Versuch eines Programms, einen NULL-Zeiger zu derefenzieren. Man sollte sich die größte Mühe geben, sein Programm vorher gründlichst zu durchdenken, um eben diesen Fehler zu vermeiden, denn er ist eine der Hauptgründe dafür, dass sich unter Windows9x viele Programme gerne mal "aufgehängt" haben. Wenn man sein Programm testen will, ist es auch immer eine gute Idee, dabei u.A. solche Testdaten zu benutzen, mit denen man die verwendeten Zeiger NULL werden lassen kann, um so zu prüfen, ob in diesen Fällen eine unzulässige Derefenzierung vorgenommen wird.

Literatur-Hinweis

Sowohl zu C/C++ als auch zu Java findet man sehr gute Einführungen als E-Books bei www.galileocomputing.de, die ich jedem ans Herz legen möchte, der sich z.B. durch die doch recht kurz gehaltene Einführung in die Zeiger-Problematik noch nicht genügend informiert fühlt oder beide Sprachen bisher gar nicht genutzt hat oder einfach nur ein Nachschlagewerk braucht. C von A bis Z Java ist auch eine Insel Die Titel könnten von mir sein, oder?

Gelinkt!

Wie bastelt man sich nun mit Zeigern eine verkettete Liste? Was genau ist das eigentlich? Eine verkettete Liste (engl. linked list) ist dabei eine Menge von Knoten, die in einer bestimmten Reihenfolge auftreten. Jeder Knoten enthält dabei einen Zeiger auf seinen Nachfolgerknoten in der verketteten Liste oder, sofern ein solcher nicht existiert, den NULL-Zeiger. Das heißt, so eine Liste besteht im Wesentlichen aus lauter gleichartigen Strukturen, die jeweils einige Daten und einen Zeiger auf genau eine Struktur desselben Typs enthalten. Ein Beispiel könnte in C/C++ so aussehen. \sourceon C typedef struct _Node *tpNode; typedef struct _Node { int data; tpNode next; } tNode; \sourceoff In diesem Beispiel wird eine Struktur mit dem Alias-Name tNode definiert. Außerdem werden Zeiger auf diese Struktur mit dem Typnamen tpNode definiert. Die Struktur selbst enthält nun einen von diesen Zeigern und eine Integer-Variable, die uns hier als Daten-Speicher dienen soll (natürlich sind verkettete Liste für jede andere Art von Daten machbar). In Java würde man das Ganze natürlich mit Referenzen lösen, wodurch es erstmal auch intuitiver aussähe: \sourceon Java class cNode { public int data; public cNode next; } \sourceoff Diese Knotenstrukturen können nun bereits genutzt werden, um eine verkettete Liste zu formen: In jedem Knoten wird einfach der Zeiger next auf den Nachfolger-Knoten gesetzt, der next-Zeiger des letzten Elements wird auf NULL gesetzt und schon hat man eine einsatzfähige Variante einer verketteten Liste. Graphisch könnte ein verkettete Liste mit 4 Knoten so aussehen: \geo ebene(600,100) x(0,12) y(-1,1) noaxis() nolabel() punktform(.) replace() konst(k,0.15) konst(kk,0.7) makro(pfeil,\ konst(a,%1) konst(b,%2) konst(c,%3) konst(d,%4)\ konst(l,sqrt((c-a)*(c-a)+(b-d)*(b-d))) konst(f,k/l)\ konst(u,c-f*(c-a+kk*(b-d)))\ konst(v,d-f*(d-b+kk*(c-a)))\ konst(uu,c-f*(c-a+kk*(-b+d)))\ konst(vv,d-f*(d-b+kk*(-c+a)))\ p(a,b,p1) p(c,d,p2) s(p1,p2) p(u,v,p3) p(uu,vv,p4)\ f(p2,p3,p4,black)) makro(box,\ konstante(xp1,%1+0.5)\ konstante(yp1,%2+0.5)\ konstante(xp2,%1+1)\ \ konstante(x3,%1+0.75)\ konstante(x4,%1+1.5)\ konstante(y5,%2+0.25)\ \ punkt(%1,%2, p1_box_%3)\ punkt(xp1,%2, p2_box_%3)\ punkt(xp2,%2, p3_box_%3)\ punkt(%1,yp1, q1_box_%3)\ punkt(xp1,yp1,q2_box_%3)\ punkt(xp2,yp1,q3_box_%3)\ s(p1_box_%3,q1_box_%3) s(p2_box_%3,q2_box_%3)\ s(p3_box_%3,q3_box_%3) s(p1_box_%3,p3_box_%3)\ s(q1_box_%3,q3_box_%3)\ punktform(of) p(x3,y5) punktform(.)\ pfeil(x3,y5,x4,y5)\ ) box(0.0,0,b1) box(1.5,0,b2) box(3.0,0,b3) box(4.5,0,b4) print(42,0.2,0.4) print(43,1.7,0.4) print(44,3.2,0.4) print(45,4.7,0.4) print(\big\ NULL,6.1,0.4) \geooff \geoprint(,,-0.2,-0.2,7,0.7) Es gibt verschiedene Varianten von verketteten Listen. Die einfachste haben wir soeben kennengelernt. Diese Variante hat jedoch den Nachteil, dass man die Liste nur in einer Richtung - nämlich von vorne nach hinten - durchwandern kann. Ist man erstmal an einem Knoten, kann man nur noch die nachfolgenden Knoten erreichen (über die next-Zeiger), zurück geht es jedoch nicht. Dieses wird mit einer so genannten doppelt verketteten Liste umgangen. Hier enthält ein Knoten neben dem Zeiger auf den Nachfolger auch einen Zeiger auf den Vorgänger: \sourceon C typedef struct _Node *tpNode; typedef struct _Node { int data; tpNode prev; tpNode next; } tNode; \sourceoff bzw. in Java: \sourceon Java class cNode { public int data; public cNode prev; public cNode next; } \sourceoff Weitere Arten von verketteten Listen existieren zu Hauf. Es gibt Varianten, in denen man noch eine Klasse "drumherum" schreibt, die Zeiger auf verschiedene feste Listenelemente verwalten, wie den Anfang und das Ende. Es gibt auch verkettete Listen, die ihre Struktur dynamisch ändern, um zum Beispiel die Elemente ganz vorne zu haben, auf die häufig zugegriffen wird. All dies jedoch nur am Rande. Die einfach und doppelt verketteten Listen sind diejenigen, die uns interessieren, denn alle wichtigen Prinzipien lassen sich an ihnen veranschaulichen. Wir werden also keine Wrapper-Klassen o.Ä. benutzen, sondern direkt mit diesen zwei Knoten-Strukturen/-Klassen arbeiten. Wollen wir also irgendwo eine Liste als Parameter übergeben, so tun wir dies, indem wir den ersten Knoten der Liste angeben. (Es kann als eine "Dauer-Übungsaufgabe" angesehen werden, jede der vorgestellten Methoden so umzuschreiben, dass sie auch funktionieren, wenn wir eine Wrapper-Klasse benutzen würden, die Zeiger auf den ersten und den letzten Knoten speichert)

And... action!

Was für Aktionen sollte man mit so einer anständigen dynamischen Liste durchführen können? Nun, die naheliegenden natürlich: Wir möchten neue Objekte in die Liste hineinpacken können, wir würden sie auch gerne wieder entfernen. In den meisten Datenstrukturen, wo man etwas hinein tun kann, kann man das Hineingetane auch wiederfinden, also werden wir auch einen Suchalgorithmus implementieren.

Einfügen

Es gibt verschiedene Situationen, in denen wir ein neues Element einfügen wollen könnten: am Anfang, am Ende oder irgendwo dazwischen. Diese drei Fälle werden wir gesondert betrachten. (In jedem Fall muss natürlich erstmal ein neues Knoten-Objekt instanziert werden, das versteht sich von selbst) Wollen wir am Anfang einfügen, so haben wir bei einer einfach verketteten Liste relativ wenig Schwierigkeiten. Wir werden einfach den next-Zeiger des neuen Knotens auf den bisherigen Listenanfang zeigen lassen. Haben wir eine doppelt verkettete Liste, so müssen wir aber noch mehr tun: Dann müssen wir auch den prev-Zeiger des alten Anfangs auf den neuen Knoten setzen, um die innere Struktur der Liste zu wahren. In Code sähe das aus: \sourceon C // InsertAtStart fügt an den Anfang der durch // den Parameter 'start' gegebenen Liste einen // neuen Knoten ein, füllt ihn mit den Daten, die // durch 'newData' gegeben sind, und gibt // anschließend den neuen ersten Knoten zurück. tpNode InsertAtStart(tpNode start,int newData) { tpNode newNode=(tpNode)malloc(sizeof(tNode)); newNode->data = newData; newNode->next = start; /* Falls man doppelt verkettete Listen verwendet, müssen diese Anweisungen dazugenommen werden. Sie behandeln die prev-Zeiger. newNode->prev = NULL; if(start != NULL) { start->prev = newNode; } */ return newNode; } \sourceoff In C++ würde man übrigens statt des malloc-Konstrukts den eingebauten new-Operator verwenden, um den neuen Knoten zu erzeugen. Wollen wir am Ende einfügen, so müssen wir nicht nur die Zeiger von altem und neuem Endknoten entsprechend anpassen, wie wir es beim Einfügen an den Anfang tun. Wir müssen zunächst einmal das Ende der Liste finden. Dazu bedienen wir uns der Standard-Technik zum Durchlaufen einer verketteten Liste: Wir benutzen eine while-Schleife, die solange um ein Element nach vorne rückt, bis die gewünschte Position (oder das Ende der Liste, welches durch den NULL-Zeiger repräsentiert wird) erreicht ist. \sourceon C // InsertAtEnd fügt am Ende der durch // den Parameter 'start' gegebenen Liste einen // neuen Knoten ein, füllt ihn mit den Daten, die // durch 'newData' gegeben sind, und gibt // anschließend den neuen End-Knoten zurück. tpNode InsertAtEnd(tpNode start,int newData) { tpNode iterator=start; tpNode newNode=(tpNode)malloc(sizeof(tNode)); newNode->data = newData; newNode->next = NULL; if(start != NULL) { while(iterator->next != NULL) { iterator = iterator->next; } // An dieser Stelle zeigt iterator // auf den bisher letzten Knoten iterator->next = newNode; } /* Falls man doppelt verkettete Listen verwendet, muss diese Anweisung dazugenommen werden. newNode->prev = iterator; */ return newNode; } \sourceoff Bleibt nur noch ein Fall zu untersuchen: Das Einfügen an einer Stelle irgendwo in der Mitte. Hier müssen wir im Prinzip die Arbeit aus den beiden anderen Algorithmen kombinieren: Wir müssen in einer Schleife die richtige Position suchen und dann mit den beiden Nachbar-Knoten verbinden. Die Position soll dabei nullbasiert angegeben werden, d.h. fügen wir an Position 0 ein, dann wird der neue Knoten am Anfang der veränderten Liste stehen. \sourceon C // Insert fügt an der Position 'pos' in der durch // den Parameter 'start' gegebenen Liste einen // neuen Knoten ein, füllt ihn mit den Daten, die // durch 'newData' gegeben sind, und gibt // anschließend diesen neuen Knoten zurück. tpNode Insert(tpNode start, int newData, int pos) { tpNode iterator=start; tpNode newNode; int ii; if(pos <= 0) { return InsertAtStart(start,newData); } newNode =(tpNode)malloc(sizeof(tNode)); newNode->data = newData; if(start != NULL) { ii=0; while(iterator->next != NULL && iinext; ii++; } // An dieser Stelle zeigt iterator // auf das Ende... if(iterator->next == NULL) { InsertAtEnd(start,newData); } // ... oder auf den (pos-1)ten // Knoten. else { newNode->next = iterator->next; iterator->next= newNode; /* Falls man doppelt verkettete Listen verwendet, müssen diese Anweisungen dazugenommen werden. newNode->next->prev=newNode; newNode->prev = iterator; */ } } else { // Falls eine leere Liste übergeben wurde, // muss der next (und der prev)-Zeiger // NULL sein. newNode->next = NULL; /* newNode->prev = NULL; */ } return newNode; } \sourceoff Man sollte sich des besseren Verständnis' wegen noch einmal genau klar machen (wenn nötig vielleicht skizzieren), was in diesen drei Funktionen geschieht und an welcher Stelle welcher Zeiger wohin zeigt. Es sollte an diesen einfachen Beispielen unbedingt geübt werden, wie man mit verketteten Ketten und Zeigern umzugehen hat. Alle diese Code-Beispiele lassen sich leicht in andere Sprachen wie z.B. Java portieren, da hier noch relativ wenig C-spezifizischer Code verwendet wurde. In der Tat geht es sogar durch simple Text-Ersetzung: Jeder tpNode muss ein cNode werden, jedes -> ein ., das NULL-Makro muss das Schlüsselwort null werden und statt der malloc-Anweisung benutzen wir den new-Operator. Zum Beispiel könnte der letzte Algorithmus so aussehen: \sourceon Java class cNodeActions { public static cNode InsertAtStart(cNode start,int newData) { [...] } public static cNode InsertAtEnd(cNode start,int newData) { [...] } public static cNode Insert(cNode start, int newData, int pos) { cNode iterator=start; cNode newNode; int ii; if(pos <= 0) { return InsertAtStart(start,newData); } newNode = new cNode(); newNode.data = newData; if(start != null) { ii=0; while(iterator.next != null && ii

Entfernen

Kurz umgedacht und weitergemacht, denn wo man was reinpacken kann, sollte man klugerweise auch wieder etwas entfernen können. Kurzum: Wir entwerfen nach dem gleichen Schema die Funktionen zum Löschen von Knoten aus einer (einfach oder doppelt) verketteten Liste. Dabei müssen wir sehr genau beachten, wie und in welcher Reihenfolge wir die Zeiger und ihre zugehörigen Objekte verändern und/oder löschen. Zum Löschen von durch Zeiger repräsentierte Objekte dient in C die Funktion free, die den Speicher, den man vorher dynamisch angefordert hat, wieder freigibt. Dabei muss man etwas beachten: free gibt nur den Speicher frei, auf den der übergebene Zeiger zeigt. Hier wird das problemlos funktionieren, denn unsere Knoten-Struktur ist sehr einfach. Wenn in den Knoten aber statt einer Integer-Variablen andere, komplexere Strukturen stehen, die vielleicht ihrerseits wieder Zeiger enthalten, dann ist dieses Vorgehen falsch, denn diese "inneren" Zeiger verschwinden möglicherweise ganz und es entstehen so genannte "Speicherlecks" (das zweite Hauptproblem, das die Programme unter Windows9x und auch das Betriebssystem selbst so oft zum Absturz brachte). Für solche komplexeren Fälle empfehle ich aber, C++ und eine Klassenstruktur zu benutzen, denn dann würde man statt free das Schlüsselwort delete benutzen, welches bei vernünftiger Programmierung auch geschachtelte Objekte freizugeben in der Lage ist. Noch besser wäre natürlich eine Sprache wie C# oder Java, in deren zugrundeliegender Technologie ein Garbage-Collector gleich eingebaut ist. Wie dem auch sei... auf zur ersten Lösch-Funktion: Sie soll wieder am Anfang beginnen und schlicht das erste der Elemente aus der Liste entfernen. Dazu müssen wir zwei Dinge tun: Das Element selbst löschen und - sofern vorhanden - die Verkettung durch den prev-Zeiger "richten", d.h. wir müssen den zweiten Knoten - sofern vorhanden - so abändern, dass er zum ersten Knoten der Liste wird. \sourceon C // DeleteAtStart löscht den ersten // Knoten der durch 'start' gegebenen // verketteten Liste. Sowohl 'start' // als auch der zurückgegebene Zeiger // enthalten den neuen Anfang nach // der Ausführung der Funktion. tpNode DeleteAtStart(tpNode *start) // start ist ein Zeiger auf einen // Zeiger! Dies ist notwendig, da // wir ihn ja verändern wollen. { tpNode r; // start muss auf eine Liste zeigen // und diese Liste muss nichtleer // sein, wenn wir was löschen wollen. if(start == NULL || *start == NULL) { return NULL; } r = (*start)->next; free(*start); *start = r; /* Falls man eine doppelt verkettete Liste hat, müssen diese Anweisungen wieder entkommentiert werden if(r != NULL) { r->prev = NULL; } */ return r; } \sourceoff Das Portieren nach Java gestaltet sich deutlich trickreicher als vorher, denn hier haben wir einen Zeiger-Parameter benutzt, der das C-Äquivalent eines call-by-Reference-Parameters darstellt. In reinem C gibt es sowas nicht, sondern muss eben mit Zeigern implementiert werden. Erst C++ bietet echte Referenz-Parameter. Nun stellt sich uns aber ein Problem: In Java gibt es gar keine Referenzparameter für Funktionen, obwohl die ganze Sprache vor Referenzen nur so strotzt. In Java müssen wir das Problem also anders lösen. Erstaunlicherweise geht es trotzdem sehr viel unkomplizierter, denn in Java übernimmt das Aufräumen der Garbage-Collector, so dass wir nur die Verkettung unterbrechen müssen und das Fehlen von Referenz-Parametern noch nicht großartig stört: \sourceon Java class cNodeActions { [...] // DeleteAtStart unterbricht die // Verkettung in der durch 'start' // gegebenen Liste. 'start' wird im // Gegensatz zur C-Methode nicht // verändert. Der neue Listenanfang // ist der Rückgabewert der Methode. public static cNode DeleteAtStart(cNode start) { cNode r=null; if(start == null) { return null; } r = start.next; /* Falls man eine doppelt verkettete Liste hat, müssen diese Anweisungen wieder entkommentiert werden if(r != null) { r.prev = null; } */ return r; } [...] } \sourceoff Ganz analog basteln wir uns nun die Funktionen zum Löschen des letzten Knotens. Dabei müssen wir einen zusätzlichen Spezialfall beachten, nämlich den, dass der letzte Knoten gleichzeitig der erste ist. Dann müssen wir die Liste nämlich komplett löschen. Die anderen Fälle laufen aber ähnlich ab wie eben: Wir suchen uns das Element, das vor dem zu löschenden steht (in diesem Fall der vorletzte Knoten) und löschen dann analog zu oben durch Unterbrechen der Verkettung und Freigeben des Speichers. \sourceon C // DeleteAtEnd löscht den letzten // Knoten der durch 'start' gegebenen // verketteten Liste. Rückgabewert // ist der Anfang der verkleinerten // Liste oder NULL, falls die Liste nach // dem Löschen leer ist. tpNode DeleteAtEnd(tpNode *start) { tpNode iterator; // start muss auf eine Liste zeigen // und diese Liste muss nichtleer // sein, wenn wir was löschen wollen. if(start == NULL || *start == NULL) { return NULL; } // Wenn es nur ein Element gibt // löschen wir die Liste komplett if( (*start)->next == NULL) { free(*start); *start=NULL; return NULL; } iterator = *start; while(iterator->next->next != NULL) { iterator = iterator->next; } // iterator zeigt jetzt auf den // vorletzten Knoten und den // nachfolgenden löschen wir. free(iterator->next); iterator->next=NULL; return *start; } \sourceoff Auch hier nimmt uns der Garbage-Collector einiges an Arbeit ab, wenn wir diese Funktion in Java verfassen wollen: \sourceon Java class cNodeActions { [...] // DeleteAtEnd unterbricht die // Verkettung in der durch 'start' // gegebenen Liste. 'start' wird im // Gegensatz zur C-Methode niemals // verändert. Rückgabewert ist der // Anfang der verkleinerten Liste // oder null, falls die Liste nach // dem Löschen leer ist. public static cNode DeleteAtEnd(cNode start) { cNode iterator; if(start == null || start.next == null) { return null; } iterator = start; while(iterator.next.next != null) { iterator = iterator.next; } iterator.next=null; return start; } [...] } \sourceoff Auch hier fehlt noch das Löschen an einer beliebigen Stelle. Ähnlich wie oben nutzen wir jetzt unsere Erfahrungen in den beiden Spezialfällen, um uns eine entsprechende Funktion zusammenzubasteln: \sourceon C // Delete löscht den Knoten an der // Stelle 'pos' aus der durch 'start' // gegebenen Liste. Zurückgegeben // wird der Anfang der verkleinerten // Liste oder NULL, falls die Liste // nach dem Löschen leer ist. tpNode Delete(tpNode *start,int pos) { tpNode iterator,t; int ii; if(start == NULL || *start == NULL) { return NULL; } if(pos <= 0) { return DeleteAtStart(start); } iterator = *start; while(iterator->next->next != NULL && iinext; } // iterator zeigt jetzt auf den vorletzten // oder den (pos-1)ten Knoten in der Liste if(iterator->next->next == NULL) { return DeleteAtEnd(start); } t=iterator->next; iterator->next = iterator->next->next; /* Falls man eine doppelt verkettete Liste hat, müssen diese Anweisungen wieder entkommentiert werden iterator->next->prev = iterator; */ free(t); return *start; } \sourceoff Ähnlich wie bei der dritte Methode von oben, könnten wir auch jetzt aus drei Methoden eine machen, doch genau wie oben, sei erwähnt, dass die beiden Spezialfälle, dass das erste oder das letzte Element gelöscht werden sollen, bei komplexeren Listentypen oft eine Optimierung ermöglichen und/oder zusätzliche Arbeit erfordern. Eine Portierung nach Java gebe ich dieses Mal nicht an, denn hier sähe es im Prinzip genauso aus. Einzig die free-Anweisung fiele weg, der Rest wäre wieder nur eine reine Textersetzungsfrage. Eine Methode, die man auch sehr oft benötigt, ist das Löschen der kompletten Liste, z.B. bei den Aufräumarbeiten am Ende des Programms. Man könnte natürlich in einer Schleife immer wieder das erste Element löschen, bis die Liste komplett weg ist, aber man kann auch gleich Alles in einem Abwasch erledigen. Dabei kann man wie folgt vorgehen: Man besucht die Liste Knoten für Knoten. Nachdem man einen Schritt gegangen ist, löscht man den Knoten, den man vorher besucht hat. Diesen muss man sich natürlich in einer extra Variablen merken. (Das entspricht gut der Vorstellung, beim Überqueren einer Brücke den Stein hinter sich sofort zu zerstören, sobald man einen Schritt nach vorne getan hat.) \sourceon C // DeleteList löscht alle in // der durch 'start' gegebenen // Liste enthaltenen Knoten void DeleteList(tpNode *start) { tpNode iterator,ptr; // Leere Listen zu löschen wäre // irgendwie... sinnbefreit. if(start == NULL || *start==NULL) { return; } iterator = *start; do { ptr=iterator; iterator = iterator->next; free(ptr); }while(iterator != NULL); // Zeiger auf freigegebenen // Speicher sollten nie benutzt // werden, daher machen wir // start unbrauchbar, indem wir // ihn auf NULL setzen. *start = NULL; } \sourceoff Der ein oder andere hat sich vielleicht Gedanken darüber gemacht, ob man bei doppelt verketteten Listen etwas ändern kann/muss. Man könnte z.B. die Idee haben, den ptr-Zeiger dadurch zu ersetzen, dass der prev-Zeiger der Knoten benutzt wird. Es ist eine gute Übung im Umgang mit Zeigern und verketteten Listen, sich zu überlegen, warum das nicht klappen kann. Die Portierung nach Java entfällt hier natürlich, da in Java das Aufräumen vom Garbage-Collector besorgt wird. (Ja in Java darf man fast ungestraft unordentlich sein, da hat man immer jmd., der hinter einem herräumt )

Suchen

Wie schon erwähnt, sollte so eine verkettete Liste der Vollständigkeit halber auch durchsuchbar sein. Das stellt uns vor die Aufgabe, eine Methode zum Durchsuchen zu implementieren. Nach kurzem Nachdenken kommt man da natürlich auf die Idee, die Liste einfach Knoten für Knoten zu durchsuchen. Normalerweise ist es so, dass die erste Idee zwar funktioniert, aber es in der Regel ausgefeiltere Techniken gibt. Gerade Suchalgorithmen wurden lange erforscht und verbessert. Die spezielle Struktur der verketteten Liste lässt aber so gut wie keinen Freiraum zum Optimieren. Selbst mit komplexeren Datentypen und vorsortierten Listen ist die Suche meist nicht wesentlich zu optimieren. Die lineare Suche ist so ziemlich die einzige Option in verketteten Listen. Zum Suchen und Sortieren sind verkettete Listen also denkbar schlecht geeignet. Daher ist die Suchmöglichkeit auch von eher untergeordneter Bedeutung in der Praxis. Verkettete Listen werden oft da eingesetzt, wo wenig oder gar nicht gesucht und sortiert werden muss. Trotzdem, weil es uns soviel Spaß macht, implementieren wir den Algorithmus kurz \sourceon C // Find sucht in der durch 'start' // gegebenen Liste nach einem // Knoten dessen data-Eigenschaft // mit 'value' übereinstimmt und // gibt einen Zeiger auf den ersten dieser // Knoten bzw. NULL bei Misserfolg // zurück. tpNode Find(tpNode start,int value) { tpNode iterator=start; while(iterator != NULL) { if(iterator->data == value) { return iterator; } iterator = iterator->next; } return NULL; } \sourceoff (Die Übersetzung nach Java läuft wieder mit Textersetzung ab...)

Märchenstunde

Manchmal gibt es Situationen, wo man nicht die vollständige Kontrolle über die verkettete Liste hat und dann gerne kontrollieren würde, ob sie immer noch wohlgeformt ist, d.h. es sich immer noch um eine gültige verkettete Liste handelt. In der Regel kann man nicht nachprüfen, ob die Zeiger immer noch auf sinnvolle Objekte zeigen. Was man aber prüfen kann, ist, ob es in der Liste Schleifen gibt, ob die Objekte also "im Kreis" verkettet sind. Dies wird mit dem so genannten Hase-Igel-Algorithmus bewerkstelligt, den ich nun als kleines Schmankerl vorstellen möchte. Wie im Märchen von Hase und Igel gibt es dabei zwei Zeiger, die durch die verkettete Liste laufen. Einer der beiden allerdings deutlich schneller, nämlich in Zweierschritten. Holt der schnellere den langsameren ein, so wissen wir, dass es einen Zyklus geben muss, denn in einer korrekt verketteten Liste kann der schnellere Zeiger nie vor dem langsameren stehen. Erreicht der Zeiger allerdings das Ende der verketteten Liste (d.h. einen NULL-Zeiger), wissen wir, dass die Liste keine Zyklen enthält, sondern korrekt verkettet ist. Ein Beispiel für eine falsch verkettete Liste sähe so aus: \geo ebene(600,200) x(0,12) y(-1,3) noaxis() nolabel() punktform(.) replace() konst(k,0.15) konst(kk,0.7) makro(pfeil,\ konst(a,%1) konst(b,%2) konst(c,%3) konst(d,%4)\ konst(l,sqrt((c-a)*(c-a)+(b-d)*(b-d))) konst(f,k/l)\ konst(u,c-f*(c-a+kk*(b-d)))\ konst(v,d-f*(d-b+kk*(c-a)))\ konst(uu,c-f*(c-a+kk*(-b+d)))\ konst(vv,d-f*(d-b+kk*(-c+a)))\ p(a,b,p1) p(c,d,p2) s(p1,p2) p(u,v,p3) p(uu,vv,p4)\ f(p2,p3,p4,black)) makro(box,\ konstante(xp1,%1+0.5)\ konstante(yp1,%2+0.5)\ konstante(xp2,%1+1)\ \ konstante(x3,%1+0.75)\ konstante(x4,%1+1.5)\ konstante(y5,%2+0.25)\ \ punkt(%1,%2, p1_box_%3)\ punkt(xp1,%2, p2_box_%3)\ punkt(xp2,%2, p3_box_%3)\ punkt(%1,yp1, q1_box_%3)\ punkt(xp1,yp1,q2_box_%3)\ punkt(xp2,yp1,q3_box_%3)\ s(p1_box_%3,q1_box_%3) s(p2_box_%3,q2_box_%3)\ s(p3_box_%3,q3_box_%3) s(p1_box_%3,p3_box_%3)\ s(q1_box_%3,q3_box_%3)\ ) box(0.0,0,b1) box(1.5,0,b2) box(3.0,0,b3) box(4.5,1.0,b4) box(3.0,2.0,b5) box(1.5,1.0,b6) punktform(of) p(0.75,0.25) p(2.25,0.25) p(3.75,0.25) p(4.75,1.25) p(3.25,2.25) p(2.25,1.25) punktform(.) pfeil(0.75,0.25,1.5,0.25) pfeil(2.25,0.25,3.0,0.25) pfeil(3.75,0.25,4.5,1.0) pfeil(4.75,1.25,4.0,2.0) pfeil(3.25,2.25,2.5,1.5) pfeil(2.25,1.25,3.0,0.5) \geooff \geoprint(,,-0.2,-0.2,5.7,2.5) An diesem Beispiel kann man auch gut die Funktionsweise des Algorithmus' nachverfolgen: \sourceon C // ContainsCycle findet mit dem // Hase-Igel-Algorithmus heraus, // ob die durch 'start' gegebene // Liste Schleifen enthält. bool ContainsCycles(tpNode start) { tpNode coyote,roadrunner; if(start == NULL) return false; coyote = start; roadrunner = start; do { // Hier in Einerschritten... coyote = coyote->next; // ... und hier - sofern möglich // in Zweierschritten. roadrunner = roadrunner->next; if(roadrunner != NULL) { roadrunner = roadrunner->next; } }while( coyote != roadrunner && roadrunner != NULL ); // Die Schleife wurde entweder // wegen des Erreichens des // NULL-Zeigers abgebrochen... if(roadrunner == NULL) { return false; } // ...oder weil wir einen Zyklus // gefunden haben. return true; } \sourceoff Kleine Anmerkung: C an sich kennt eigentlich keine Variablen vom Typ bool. Alle logischen Operationen laufen intern über Integer-Variablen, wobei jeder Wert ungleich 0 zu true ausgewertet wird und die 0 als false gilt. In den meisten C-Compilern und/oder den Standard-Headerdatein wird bool mit einem Makro nachdefiniert (wobei manchmal auch alles in Großbuchstaben definiert wird): \sourceon C #define bool int #define true (1) #define false (0) \sourceoff In C++ hingegen ist bool wirklich als Sprachelement integriert. In jedem Fall sollte das Code-Beispiel aber mit den üblichen C/C++ Compilern kompilierbar sein.

Extreme Schlangestehen

Zum Schluss möchte ich noch etwas zu den Anwendungen der linked lists sagen. Eine spezielle und oft verwendete Liste ist die Queue, die auch Warteschlange genannt wird. Sie besteht aus einer verketteten Liste, deren Anfangs- und Endknoten bekannt sind. Sie unterstützt zwei Operationen: Objekte am Anfang der Warteschlange einreihen und Objekte vom Ende entfernen. Und wie man das von einer Warteschlange erwartet, wird hierbei nach dem FIFO-Prinzip gearbeitet: First in, first out, d.h. das Objekt, dass als letztes in die Warteschlange eingereiht wird, kommt auch als letztes wieder heraus. Queues werden überall dort verwendet, wo Daten egal welcher Art asynchron verarbeitet werden müssen. Klassisches Beispiel ist ein Drucker, der die Seiten schön gemütlich eine nach der anderen ausspuckt. Doch während er das tut, können problemlos weitere Druckaufträge erteilt werden. Die werden dann in einer Warteschlange eingereiht und immer wenn der Drucker gerade Zeit findet, holt er sich das nächste wartende Dokument. Ein anderes populäres Beispiel ist die Message-Queue in ereignisbasierten Systemen wie den Windows-Betriebssystemen: Für jedes Ereignis, das man in einem Programm auslösen kann, geht eine Message in die Warteschlange. Das Programm holt es sich, sobald es Zeit dafür hat und wertet dann aus, ob es ein Tastendruck, ein Mausklick oder etwas anderes war und wie demzufolge zu verfahren ist.

Abschluss

So. Das war es bis dahin zu den verketteten Listen. Ich hoffe, der Artikel hat euch gefallen und weitergeholfen. Mindestens eine weitere wichtige Datenstruktur werde ich ebenfalls bald in einem Artikel besprechen: Den Stack. Doch auch andere Themen wie z.B ein Einblick in die Komplexitätstheorie erwarten euch in Kürze in weiteren Artikel der Algorithmen-AG. Seid also gespannt \sourceon this->article->ends_with(mfg->Gockel); \sourceoff
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfpdf-Datei zum Artikel öffnen, 87 KB, vom 08.07.2006 15:05:43, bisher 3589 Downloads


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Informatik :: Programmierung :: Algorithmen :
Heiße AlgoRhythmen: Ganz schön link [von Gockel]  
Ein Artikel über Verkettete Listen. Enthält u.A. Implementierungen der Grundoperationen in C/C++ und Java.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 5533
 
Aufrufstatistik des Artikels
Insgesamt 237 externe Seitenaufrufe zwischen 2012.01 und 2021.12 [Anzeigen]
DomainAnzahlProz
http://google.de15063.3%63.3 %
https://google.de5121.5%21.5 %
https://google.com156.3%6.3 %
http://google.li83.4%3.4 %
http://google.at31.3%1.3 %
http://google.com31.3%1.3 %
http://r.duckduckgo.com10.4%0.4 %
http://10.42.165.1:191010.4%0.4 %
https://www.startpage.com10.4%0.4 %
http://google.lu10.4%0.4 %
http://samsung.de.searchturbo.com10.4%0.4 %
http://suche.t-online.de10.4%0.4 %
http://google.ch10.4%0.4 %

Häufige Aufrufer in früheren Monaten
Insgesamt 209 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2016 (102x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (49x)https://google.de/
201301-01 (14x)http://google.de/url?sa=t&rct=j&q=hase-igel- java
2020-2021 (14x)https://google.com/
201512-12 (9x)http://google.de/url?sa=t&source=web&cd=13&rct=j&q=Igel Hase Algorithmus
201205-05 (7x)http://google.de/search?source=hp&q=Derefenzieren einer referenz
201204-04 (5x)http://google.de/url?sa=t&rct=j&q=objekt-dereferenzierung java doppeltverkett...
201303-03 (5x)http://google.li/url?sa=t&rct=j&q=hase igel algorithmus java
201304-04 (4x)http://google.de/url?sa=t&rct=j&q=hase-igel-algorithmus c#

[Top of page]

"Informatik: Heiße AlgoRhythmen: Ganz schön link" | 7 Comments
The authors of the comments are responsible for the content.

Re: Heiße AlgoRhythmen: Ganz schön link
von: Slider am: Do. 15. Juni 2006 09:34:03
\(\begingroup\)Hi Gockel, dies ist gerade ein thema einer meiner kommenden klausuren (gerade die implementierung in java!), werde mir den artikel später noch genauer durchlesen!! vielen dank dafür! gruß\(\endgroup\)
 

Re: Heiße AlgoRhythmen: Ganz schön link
von: matroid am: Fr. 16. Juni 2006 10:01:36
\(\begingroup\)Ich denke, der Artikel ist sehr gut zu verstehen und für Zeiger-Anfänger eine große Hilfe. So ein einfühlsames und dennoch präzises Tutorial für Zeiger findet man sonst nicht (zumindest ich nicht). Sehr gut finde ich auch, daß der Artikel sprachunabhängig ist, trotz konkreter Codebeispiele. Daß C/C++ häufiger vorkommt, liegt sicher daran, daß man in C/C++ die Zeiger am besten sehen kann, denn - wie Du ja schreibst - wird das Wesen des Zeiges in manchen anderen Sprachen mehr verborgen. Eine Anmerkung zum NULL/null/nil: In C/C++ ist NULL ein Makro, und ist in der Regel als 0 definiert, d.h. NULL ist nichts anderes als 0. Man kann darum, was ich selbst bevorzuge, in C/C++ auch stets 0 schreiben, wenn man 0 meint. In anderen Sprachen mag null/nil ein Schlüsselwort sein. Und den Hase-Igel-Algorithmus kannte ich noch garnicht. Wie ist denn das gemeint: der schnelle Zeiger überholt den langsamen? Das bedeutet doch, daß beide nach dem Start einmal auf dem gleichen Speicherelement landen. Möglicherweise ist das aber erst nach 2n Vorwärtsschritten erreicht (n die Länge der Liste). Immerhin braucht man keinen zusätzlichen Speicher, etwa eine Markierung am Knoten. Wegen des Prüfaufwandes würde ich in den meisten Fällen bevorzugen, die Schleifenfreiheit beim Einfügen in eine Liste zu prüfen, denn i.d.R. wird seltener eingefügt als herausgesucht. Der Hase-Igel-Algorithmus ist aber sicher derjenige, der ohne Rücksicht auf spezielle Strukturen, das Erkennen von Schleifen ermöglicht. Gruß Matroid PS: Die box-Makros für die Diagramme sind genial.\(\endgroup\)
 

Re: Heiße AlgoRhythmen: Ganz schön link
von: Gockel am: Fr. 16. Juni 2006 17:07:54
\(\begingroup\)Hi matroid. Vielen, vielen Dank für das Lob :) Die NULL-0-Frage ist unter C/C++ Programmieren - wie viele solcher Formfragen - heftig diskutiert. Natürlich macht es keinen Unterschied, wenn man 0 schreibt, aber es erleichert das Lesen des Quellcodes, wenn man auf einen Blick erkennen kann, dass das eine ein Zeiger ist und das andere eine Integer-Konstante. (Ich will jetzt aber keine Diskussion vom Zaun darüber brechen, das artet eh nur wieder aus) Und ja, das "überholen" ist so gemeint, dass beide Zeiger irgendwann auf dasselbe Element der Liste zeigen. Bei einer korrekt verketteten Liste kann so etwas nicht vorkommen. Bei einem echten Kreis der Länge n ist das nach n Sprüngen (d.h. n Vorwärts-Schritte des langsameren und 2n Vorwärtsschritte des schnelleren Zeigers) der Fall. Ist an dem Kreis "noch etwas vorne dran" wie in der entarteten Liste, die ich oben als Beispiel hatte, dauert es etwas länger. Das Interessante am Hase-Igel-Algorithmus ist aber eigentlich eine andere Anwendung, die ich im Artikel verschwiegen habe, weil sie mit dem Thema verketteter Listen wenig bis gar nichts zu tun hat. Der Hase-Igel-Algorithmus (im Englischen heißt er irgendwie Floyd's algorithm oder so ähnlich...) wird auch bei Folgen anderer Art verwendet, z.B. bei der Ermittlung der Periodenlänge von rationalen Zahlen oder in bestimmten kryptographischen Algorithmen. Die Pollard-Rho-Methode zur Faktorisierung von Zahlen und die gleichnamige Methode zur Ermittlung diskreter Logarithmen basieren auf demselben Prinzip wie der Hase-Igel-Algorithmus: Die Folge (in welcher Form sie auch immer vorliegt) wird von zwei Objekten durchlaufen, und zwar gleichzeitig in Einer- und in Zweierschritten. Sobald eine Kollision eintritt, hat man ein Vielfaches der Periodenlänge der Folge gefunden und stellt anhand dieser dann Berechnungen zur Faktorisierung, zum diskreten Logarithmus o.Ä. an. Der Knusen an diesem Vorgehen ist genau das, was du sagtest: Man muss sich nicht merken, bei welchen Knoten man schon war, man braucht keinen zusätzlichen Speicherplatz. Das ist gerade in den Dimensionen, in denen die zu Faktorisierenden Zahlen z.B. liegen, von entscheidender Wichtigkeit. mfg Gockel. Auch ein P.S.: Das box-Makro ist aus reiner Faulheit entstanden 😉\(\endgroup\)
 

Re: Heiße AlgoRhythmen: Ganz schön link
von: Ex_Mitglied_40174 am: Sa. 17. Juni 2006 00:05:09
\(\begingroup\)Hi, ein wirklich guter Artikel. Aber ein konkretes Beispiel zu den Vorteilen der dynamischen Speicherverwaltung hat mir gefehlt. Der Vergleich zu einem Array z.B. \(\endgroup\)
 

Re: Heiße AlgoRhythmen: Ganz schön link
von: viertel am: Sa. 17. Juni 2006 02:56:31
\(\begingroup\)Hi Anonymous, dann füge mal in einem Array an einer beliebigen Stelle was ein (oder lösche ein beliebiges). Und wenn das häufig vorkommt, das Array womöglich groß ist, dann kopierst Du Dich tot. Und wenn dann noch das Objekt nicht so simpel ist wie im Beispiel, au weia. Dann wirst Du zumindest schnell dazu übergehen, in dem Array auch wieder nur die Adressen auf die konkreten Objekte zu verwalten. Was aber beim Einfügen/Löschen wiederum nicht ohne nen Haufen Kopiererei abgeht. Gruß vom 1/4\(\endgroup\)
 

Re: Heiße AlgoRhythmen: Ganz schön link
von: Slider am: Sa. 17. Juni 2006 11:14:20
\(\begingroup\)ein weiteres beispiel, wo dynamische datenstrukturen von großem vorteil sind, sind zb dünn besetzte Matrizen. Hier würde man mit arrays unötig enorm viel Platz verbrauchen.\(\endgroup\)
 

Re: Heiße AlgoRhythmen: Ganz schön link
von: viertel am: Fr. 07. Juli 2006 18:45:48
\(\begingroup\)Ein Hinweis zur C++ Programmierung. Es gab hier auf dem Planeten eine Anfrage, wie man den Quellcode zum Einfügen in eine sortierte Liste optinmieren könnte. Wer Hardcore C++ (Pointer auf Pointer, Referenzen) nicht scheut kann sich ja mal dies ansehen: C++: Quellcodeoptimierung (einfach verkettete Liste: insert sorted).\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]