| Zeile 1: | Zeile 1: | ||
=Listen= | =Listen= | ||
| − | == | + | ==Liste / Tabelle== |
| − | Man muss verkettete Listen von Tabellen unterscheiden. Bei einer Tabelle sind gleichgrosse Elemente hintereinander in der Memory angeordnet und können durch einen „Index“ (= Element-Nummer) gezielt adressiert werden. | + | Man muss verkettete Listen von Tabellen unterscheiden. Bei einer Tabelle (Array) sind gleichgrosse Elemente hintereinander in der Memory angeordnet und können durch einen „Index“ (= Element-Nummer) gezielt adressiert werden. |
Bei Bascom hat übrigens das erste Tabellenelement den Index „1“, bei GCC und anderen gilt hier der Index „0“ | Bei Bascom hat übrigens das erste Tabellenelement den Index „1“, bei GCC und anderen gilt hier der Index „0“ | ||
Beides hat was, aber darauf wollen wir hier nicht eingehen | Beides hat was, aber darauf wollen wir hier nicht eingehen | ||
| − | Bei verketteten Listen kann sich jedes Element irgendwo im Speicher befinden, | + | Bei verketteten Listen kann sich jedes Element irgendwo im Speicher befinden, daher gibt es üblicherweise einen „Header“, der zumindest auf das das Anfangselement verweist. |
| − | + | Listen-Elemente können auch unterschiedlich lang sein, dann muss oder sollte jedes Element auch eine Längenangabe enthalten (Bei Strings reicht natürlich ev. auch der „NUL“ Terminator). Das Auffinden eines bestimmten Elements kann hier aber nur erfolgen, indem man der Verkettung vom ersten Element weg folgt, bis man das gesuchte gefunden hat. | |
| + | Wenn die Element umsortiert werden sollen, dann reicht es, die Verkettungs-Zeiger zu verändern, bei einer Tabelle muss man die gesamten Daten verschieben. Ebenso, wenn man einzelne Element entfernen oder einfügen will. | ||
| − | |||
| − | == | + | ==Verweise/Adressen== |
| − | + | Ich werde in der Folge immer wieder unterscheiden zwischen „Verweis“ und „Adresse“ . Das wird zwar in vielen Fällen ein und dasselbe sein, aber eben nicht unbedingt. | |
| − | + | Bei einem Computer /PC mit 32-Bit Adressen (4 Byte) und keinen (kaum) Speicherproblemen ist die Verwendung der Adresse als Verweis sicher eine praktikable Methode. | |
| + | Auf einem µC reicht meistens eine 16-Bit (2Byte) Adresse, um eine 64k memory abzudecken. Aber wenn einem die 2 Byte für den Verweis je Element zu viel sind oder die 64k Adressraum zu wenig, muss man sich was überlegen. | ||
| + | Das ist aber auch ein eigenes Thema. | ||
| + | Bei meinen diversen Pseudo-Codes werde ich daher der Ordnung halber zwei Hilfs-Funktionen verwenden, die aus einem Verweis eine Adresse und umgekehrt machen. Ich gehe aber nicht drauf ein, wie diese Funktionen genau beschaffen sind. | ||
| + | Verweis = makeVerweis(Adresse) | ||
| + | Adresse = makeAdresse(Verweis) | ||
| − | == | + | ==Einfach verkettete Listen== |
| − | + | jedes Element enthält nur einen Verweis auf das folgende Element. Das letzte Element hat einfach (und meistens) den Wert NULL als Verweis. Man muss aber berücksichtigen, „0“ ist eine zumindest theoretisch mögliche Adresse. | |
| − | + | Der List-Header bei einer solchen Liste muss einen Verweis auf das erste Element haben. Ein zusätzlicher Verweis auf das aktuelle letzte Element hat nur Sinn, wenn ich auch am Ende der Liste einfügen will. Wird ohnehin immer an einer beliebigen Stelle eingefügt (sortierte Liste) oder immer nur ganz vorne (FILO = First-In Last-out) kann ich mir einen solchen Verweis auch sparen. Im schlimmsten Falle muss ich mir hat das letzte Element suchen (das ist das mit dem „NULL“-Verweis). | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | === | + | * Eine leere Liste |
| − | + | [[Bild:List1.JPG|center]] | |
| − | * | + | * Liste mit zwei Elementen |
| − | * | + | [[Bild:List2.JPG|center]] |
| − | * | + | * Einfügen von Elementen |
| + | [[Bild:List3.JPG|center]] | ||
| + | ==Grundsätzliche MEthoden== | ||
| + | * Init Head (HEAD) | ||
| + | HEAD.FIRST = makeVerweis(NULL) | ||
| + | HEAD.LAST = makeVerweis(NULL) | ||
| + | * Insert Head (HEAD, NEW) | ||
| + | FIRST = makeAddresse(HEAD.FIRST) | ||
| + | ? FIRST = NULL HEAD.LAST = makeVerweis(NEW) | ||
| + | HEAD.FIRST = makeVerweis(NEW) | ||
| + | NEW.FWD = makeVerweis(FIRST) | ||
| + | * Insert Tail (HEAD, NEW) | ||
| + | LAST = makeAddresse(HEAD.LAST) | ||
| + | ? LAST = NULL HEAD.FIRST = makeVerweis(NEW)</br> | ||
| + | else LAST.FWD = makeVerweis(NEW)</br> | ||
| + | HEAD.LAST = makeVerweis(NEW) optional</br> | ||
| + | NEW.FWD = „NULL“ | ||
| + | * Insert Behind (POSITION, NEW) | ||
| + | NEW.FWD = POSITION.FWD</br> | ||
| + | POSITION.FWD = makeVerweis(NEW)</br> | ||
| + | ? NEW.FWD = NULL HEAD.LAST = makeVerweis(NEW) optional</br> | ||
| − | + | * Read First(HEAD) | |
| + | NEXT = makeAddresse(HEAD.FIRST)</br> | ||
| + | ? NEXT = NULL end-of-list | ||
| + | * Read Next(POSITION) | ||
| + | NEXT = makeAddresse(POSITION.FWD)</br> | ||
| + | ? NEXT = NULL end-of-list | ||
| + | * Remove First(HEAD) | ||
| + | FIRST = makeAddresse(HEAD.FIRST)</br> | ||
| + | ? FIRST = NULL HEAD.LAST = NULL optional end-of-list </br> | ||
| + | else HEAD.FIRST = FIRST.FWD | ||
| + | * Remove(POSITION, PREV) | ||
| + | Entfernen eines beliebigen Elements aus der Liste geht nur, wenn auch der Vorgänger gegeben ist. | ||
| + | PREV.FWD = POSITION.FWD | ||
| − | == | + | ==Doppelt verkettete Listen== |
| − | + | Bei eine „doppelt“ verketteten Liste enthält jedes Element zusaätzlich auch einen Verweis auf seinen Vorgänger, dadurch kann dann in der Liste direkt in beiden Richtungen navigiert werden. | |
| − | + | ||
| − | + | ===NULL-Verweise=== | |
| − | + | Um sich nicht beim Einfügen und Entfernen immer wieder darum kümmern zu müssen, ob man sich am Anfang, mittendrin oder am Ende der Liste befindet und ob die Liste leer ist oder nicht, hat es sich bewährt, KEINE NULL-Verweise zu verwenden. Die entsprechenden Methoden sind einfacher, weil sie kein Wenn und Aber brauchen. | |
| − | === | + | |
| − | + | ===List Header = Element Header=== | |
| − | + | * Einen Verweis auf das nächste Element (beim List-Header ist das das erste) | |
| − | + | * einen Verweis auf das vorherige Element (beim List-Header ist das das letzte ) | |
| + | |||
| + | |||
| + | Bei den Lese-Routinen spielt die Unterscheidung List / Element-Header eine Rolle (um Anfang und Ende der Liste erkennen zu können). | ||
| + | |||
| + | * Leere Liste | ||
[[Bild:Chain2.JPG|center]] | [[Bild:Chain2.JPG|center]] | ||
| − | + | Ein Header eine leeren Liste zeigt vorwärts und rückwärts auf sich selbst. | |
| + | * Liste mit einem Element | ||
[[Bild:Chain3.JPG|center]] | [[Bild:Chain3.JPG|center]] | ||
| − | + | * Liste mit mehreren Elementen | |
[[Bild:Chain4.JPG|center]] | [[Bild:Chain4.JPG|center]] | ||
| + | Das letzte Element verweist „vorwärts“ wieder auf den List-Header, das erste „rückwärts“ ebenfalls. | ||
==Element einfügen== | ==Element einfügen== | ||
Version vom 26. August 2011, 14:56 Uhr
Inhaltsverzeichnis
Listen
Liste / Tabelle
Man muss verkettete Listen von Tabellen unterscheiden. Bei einer Tabelle (Array) sind gleichgrosse Elemente hintereinander in der Memory angeordnet und können durch einen „Index“ (= Element-Nummer) gezielt adressiert werden. Bei Bascom hat übrigens das erste Tabellenelement den Index „1“, bei GCC und anderen gilt hier der Index „0“ Beides hat was, aber darauf wollen wir hier nicht eingehen
Bei verketteten Listen kann sich jedes Element irgendwo im Speicher befinden, daher gibt es üblicherweise einen „Header“, der zumindest auf das das Anfangselement verweist. Listen-Elemente können auch unterschiedlich lang sein, dann muss oder sollte jedes Element auch eine Längenangabe enthalten (Bei Strings reicht natürlich ev. auch der „NUL“ Terminator). Das Auffinden eines bestimmten Elements kann hier aber nur erfolgen, indem man der Verkettung vom ersten Element weg folgt, bis man das gesuchte gefunden hat. Wenn die Element umsortiert werden sollen, dann reicht es, die Verkettungs-Zeiger zu verändern, bei einer Tabelle muss man die gesamten Daten verschieben. Ebenso, wenn man einzelne Element entfernen oder einfügen will.
Verweise/Adressen
Ich werde in der Folge immer wieder unterscheiden zwischen „Verweis“ und „Adresse“ . Das wird zwar in vielen Fällen ein und dasselbe sein, aber eben nicht unbedingt. Bei einem Computer /PC mit 32-Bit Adressen (4 Byte) und keinen (kaum) Speicherproblemen ist die Verwendung der Adresse als Verweis sicher eine praktikable Methode. Auf einem µC reicht meistens eine 16-Bit (2Byte) Adresse, um eine 64k memory abzudecken. Aber wenn einem die 2 Byte für den Verweis je Element zu viel sind oder die 64k Adressraum zu wenig, muss man sich was überlegen. Das ist aber auch ein eigenes Thema. Bei meinen diversen Pseudo-Codes werde ich daher der Ordnung halber zwei Hilfs-Funktionen verwenden, die aus einem Verweis eine Adresse und umgekehrt machen. Ich gehe aber nicht drauf ein, wie diese Funktionen genau beschaffen sind. Verweis = makeVerweis(Adresse) Adresse = makeAdresse(Verweis)
Einfach verkettete Listen
jedes Element enthält nur einen Verweis auf das folgende Element. Das letzte Element hat einfach (und meistens) den Wert NULL als Verweis. Man muss aber berücksichtigen, „0“ ist eine zumindest theoretisch mögliche Adresse. Der List-Header bei einer solchen Liste muss einen Verweis auf das erste Element haben. Ein zusätzlicher Verweis auf das aktuelle letzte Element hat nur Sinn, wenn ich auch am Ende der Liste einfügen will. Wird ohnehin immer an einer beliebigen Stelle eingefügt (sortierte Liste) oder immer nur ganz vorne (FILO = First-In Last-out) kann ich mir einen solchen Verweis auch sparen. Im schlimmsten Falle muss ich mir hat das letzte Element suchen (das ist das mit dem „NULL“-Verweis).
- Eine leere Liste
- Liste mit zwei Elementen
- Einfügen von Elementen
Grundsätzliche MEthoden
- Init Head (HEAD)
HEAD.FIRST = makeVerweis(NULL) HEAD.LAST = makeVerweis(NULL)
- Insert Head (HEAD, NEW)
FIRST = makeAddresse(HEAD.FIRST) ? FIRST = NULL HEAD.LAST = makeVerweis(NEW) HEAD.FIRST = makeVerweis(NEW) NEW.FWD = makeVerweis(FIRST)
- Insert Tail (HEAD, NEW)
LAST = makeAddresse(HEAD.LAST) ? LAST = NULL HEAD.FIRST = makeVerweis(NEW)</br> else LAST.FWD = makeVerweis(NEW)</br> HEAD.LAST = makeVerweis(NEW) optional</br> NEW.FWD = „NULL“
- Insert Behind (POSITION, NEW)
NEW.FWD = POSITION.FWD</br> POSITION.FWD = makeVerweis(NEW)</br> ? NEW.FWD = NULL HEAD.LAST = makeVerweis(NEW) optional</br>
- Read First(HEAD)
NEXT = makeAddresse(HEAD.FIRST)</br> ? NEXT = NULL end-of-list
- Read Next(POSITION)
NEXT = makeAddresse(POSITION.FWD)</br> ? NEXT = NULL end-of-list
- Remove First(HEAD)
FIRST = makeAddresse(HEAD.FIRST)</br> ? FIRST = NULL HEAD.LAST = NULL optional end-of-list </br> else HEAD.FIRST = FIRST.FWD
- Remove(POSITION, PREV)
Entfernen eines beliebigen Elements aus der Liste geht nur, wenn auch der Vorgänger gegeben ist. PREV.FWD = POSITION.FWD
Doppelt verkettete Listen
Bei eine „doppelt“ verketteten Liste enthält jedes Element zusaätzlich auch einen Verweis auf seinen Vorgänger, dadurch kann dann in der Liste direkt in beiden Richtungen navigiert werden.
NULL-Verweise
Um sich nicht beim Einfügen und Entfernen immer wieder darum kümmern zu müssen, ob man sich am Anfang, mittendrin oder am Ende der Liste befindet und ob die Liste leer ist oder nicht, hat es sich bewährt, KEINE NULL-Verweise zu verwenden. Die entsprechenden Methoden sind einfacher, weil sie kein Wenn und Aber brauchen.
List Header = Element Header
- Einen Verweis auf das nächste Element (beim List-Header ist das das erste)
- einen Verweis auf das vorherige Element (beim List-Header ist das das letzte )
Bei den Lese-Routinen spielt die Unterscheidung List / Element-Header eine Rolle (um Anfang und Ende der Liste erkennen zu können).
- Leere Liste
Ein Header eine leeren Liste zeigt vorwärts und rückwärts auf sich selbst.
- Liste mit einem Element
- Liste mit mehreren Elementen
Das letzte Element verweist „vorwärts“ wieder auf den List-Header, das erste „rückwärts“ ebenfalls.
Element einfügen
Vorher
Nachher
List-Tree
Autoren
Siehe auch
