Druckbare Version
Ich hab da einen Artikel über verkettete Listen angefangen
http://www.rn-wissen.de/index.php/Listen
Wäre nett, wenn ein paar kluge Leute mal drüberlesen könnten
1. Ob irgendein Schwachsinn drin steht
2. Ob das irgendeiner auch verstehen kann, was ich da erzähle.
mein ewiger dank ist gewiss !
Vorschlag für eine kleine Änderung des einleitenden Absatzes:
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. Das Anfangselement (und jedes weitere Element) verweisen dann auf den Speicherort des jeweils darauffolgenden Elements. 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. 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).
Ansonsten habe ich mich bei den grafischen Darstellungen gefragt, ob man bei den Listeneinträgen nicht noch andeuten sollte, dass da (außer den Verweisen auf die anderen Listenelemente) auch noch Daten drinstehen. So sieht das irgendwie nach Selbstzweck aus.
Ich sollte vielleicht dazusagen, dass ich mich vor 20 Jahren mal mit Pascal befasst habe, sonst aber hochgradig ahnungslos bin, was höhere Programmiersprachen betrifft. Die Pseudocode Beispiele habe ich deshalb nicht so ganz kapiert, wahrscheinlich auch wegen momentaner Denkfaulheit. Ansonsten für einen Dilettanten wie mich durchaus zu verstehen.
Zitat:
„Gleitende Statistik“
gleitende Mittelung(?) (engl. moving window averaging) ftp://ftp.microedition.de/KBase/kb005.pdf
----
Ich finde diese Hashtabellen noch besonders interessant, gibt es eine Stelle im Artikel an der man auf sie verweisen kann?
http://de.wikipedia.org/wiki/Hashtabelle
Die Bäume sind nicht nur eine Anwendung, sondern eine andere Form der Verknüpfung. Der Unterschied ist sogar größer als zu den doppelt verlinkten Listen. Beim Baum hat jedes Element (Knoten) mehr als einen Verweiß auf "Nachfolger".
Für das Gleitende Mittel ist in der Regel ein Zirkularer Puffer auch die bessere Wahl als eine Liste. In der Regel sind da die Elemente ja auch alle gleich groß.
Danke mal an alle :-)
@ranke: Ist angekommen, ich werde in der Richtung arbeiten
@Manfred: "moving window averaging" ? Gefällt mir, das klingt doch gleich fachmännischer. in der Tat.
Ich glaub fast, diese Tabellen/Listen Kombination bei Hash-Tables wären einen eigenen Artikel wert, in dem man speziell die eingeschränkten Möglichkeiten bei µC-s berücksichtigt. Dann wär das eine (imho sinnvolle) Ergänzung zur Wikipedia. Aber erstmal einen Verweis dorthin kann mal auf jeden Fall reintun, da hast du recht.
@Besserwessi: "Gleitendes Mittel" find ich gut, auf jeden Fall treffender als "Statistik". Ringbuffer sind dafür sicher eine gute Möglichkeit, da hast du recht. Mir ging's nur darum, eine weitere Verwendungsmöglichkeit anzuführen.
Bei Bäumen kommts wohl darauf an, wie man sie "technisch" realisiert. In dem Sinne, wie ich es in dem Artikel noch darstellen werde, ist das aber keine andere bzw. spezielle Verknüpfungs-Art.
na, dann hab' ich ja zu tun :-)