Programmierbeispiel doppelt verkettete Liste

[Niels Menke]

Hi NG,

Verzeiht mir falls das ne häufig gestellte Frage ist, aber per google
war nichts zu finden...
Ich soll eine doppelt verkettete Liste programmieren, mit Templates und
den Methoden push, pop, top (lesen des obersten Elements), empty
(liefert true falls liste leer) und dump_elements (alle elemente ausgeben).
Mein Problem: Ich blick nicht so recht, wie ich das machen soll, da
Vorlesung und Skript doch sehr dürftig ausfielen. Hat vielleicht jemand
ein gutes Programmierbeispiel für mein Problem, über dem ich zwecks
Verständnis meditieren könnte?

Grüße

[Albrecht Fritzsche]

Post by Niels Menke
Hi NG,
Verzeiht mir falls das ne häufig gestellte Frage ist, aber per google
war nichts zu finden...

Verwundert mich...

Post by Niels Menke
Mein Problem: Ich blick nicht so recht, wie ich das machen soll, da
Vorlesung und Skript doch sehr dürftig ausfielen. Hat vielleicht jemand
ein gutes Programmierbeispiel für mein Problem, über dem ich zwecks
Verständnis meditieren könnte?

Das Buch "Thinking in C++" ist da vielleicht besser als Deine Skripts,
zB

http://www.briceg.com/ticpp/one/

Ali

[Tobias Wollgam]

Post by Niels Menke
Ich soll eine doppelt verkettete Liste programmieren, mit Templates und
den Methoden push, pop, top (lesen des obersten Elements), empty
(liefert true falls liste leer) und dump_elements (alle elemente
ausgeben). Mein Problem: Ich blick nicht so recht, wie ich das machen
soll, da Vorlesung und Skript doch sehr dürftig ausfielen.

Was konkret ist das Problem?

Post by Niels Menke
Hat vielleicht
jemand ein gutes Programmierbeispiel für mein Problem, über dem ich zwecks
Verständnis meditieren könnte?

Von einer fertigen Lösung lernst Du nichts, Du solltest schon selbst
versuchen die Aufgabe zu lösen!

Bescheib mal, wie Du an die Sache herangehen möchtest!

Gruß,

Tobias

[Niels Menke]

Post by Tobias Wollgam
Was konkret ist das Problem?

Das Problem ist, das unsere Vorlesung "Einführung in die Programmierung
mit C++" im letzten Semester nicht wirklich die viele Zeit wert war, die
ich hineingesteckt habe, denn komplexere Dinge in C++ programmieren kann
ich immer noch nicht, was aber allen anderen Kursteilnehmern ähnlich
geht, an mir allein kanns also nicht liegen. Dennoch wird nun von uns
verlangt, derartige Datenstrukturen zu realisieren. Nur ist das
natürlich etwas schwer, wenn man zwar gedanklich weiß wie's gehen soll,
aber keinen Schimmer hat wie der Code dazu aussehen muss.

Post by Tobias Wollgam
Bescheib mal, wie Du an die Sache herangehen möchtest!

Wie gesagt suchte ich ein Programmierbeispiel, das ich mir Stück für
Stück auseinanderpflücken und verstehen könnte. Auf ähnliche Art und
Weise habe ich schon recht erfolgreich und schnell fließend Pascal, PHP
und HTML gelernt. Es sollte also mit C++ auch klappen. Ich hatte nicht
vor, 'ne fertige Lösung abzugeben ohne meinen eigenen Senf einzubringen,
falls Du Dir das dachtest. Das ich davon längerfristig nichts hätte, ist
mir auch bewusst.

[Heinz Saathoff]

Moin,

Niels Menke schrieb...

Post by Niels Menke
Wie gesagt suchte ich ein Programmierbeispiel, das ich mir Stück für
Stück auseinanderpflücken und verstehen könnte. Auf ähnliche Art und
Weise habe ich schon recht erfolgreich und schnell fließend Pascal, PHP
und HTML gelernt. Es sollte also mit C++ auch klappen.

Da Du fließend Pascal kannst: Könntest Du eine solche Liste in Pascal
programmieren? Wenn ja, ist Dir der Algorithmus bekannt und es hapert
nur mit der konkreten Notation in C++ (pointer, new, delete)?
Wenn's am Algorithmus liegt: Karl Heinz hat sich sehr viel Mühe mit der
Erläuterung gegeben.

[Tobias Wollgam]

Post by Niels Menke

Post by Tobias Wollgam
Bescheib mal, wie Du an die Sache herangehen möchtest!

Wie gesagt suchte ich ein Programmierbeispiel, das ich mir Stück für
Stück auseinanderpflücken und verstehen könnte. Auf ähnliche Art und
Weise habe ich schon recht erfolgreich und schnell fließend Pascal, PHP
und HTML gelernt. Es sollte also mit C++ auch klappen. Ich hatte nicht
vor, 'ne fertige Lösung abzugeben ohne meinen eigenen Senf einzubringen,
falls Du Dir das dachtest. Das ich davon längerfristig nichts hätte, ist
mir auch bewusst.

Wenn Du Pascal kannst, dann entwerfe Deine Lösung doch zunächst in Pascal.
Entwerfe dann analog eine Klasse in C++ und erweitere diese dann zum Schluß
zu einem Template.

Ich glaube übrigens nicht, daß man C++ so einfach lernt indem man sich ein
fullfeatured Beispiel ansieht und das analysiert. Wenn dem doch so ist,
dann schnapp Dir STLport und analysiere dort die Klasse list.

IMHO kommt man auch ohne ordentliche Literatur nicht sehr weit.

Viel Erfolg,

Tobias

[helmut zeisel]

Post by Tobias Wollgam
Wenn Du Pascal kannst, dann entwerfe Deine Lösung doch zunächst in Pascal.

Das halte ich fuer keine gute Idee. Pascal ist zu unterschiedlich. Von
einer anderen objektorientierten Sprache auf C++ uebertragen, ist
möglich; von einer "klassischen" heraus ist aber schwierig.

Post by Tobias Wollgam
Entwerfe dann analog eine Klasse in C++ und erweitere diese dann zum Schluß
zu einem Template.

Zustimmung.

Helmut

[Tobias Wollgam]

Post by helmut zeisel

Post by Tobias Wollgam
Wenn Du Pascal kannst, dann entwerfe Deine Lösung doch zunächst in Pascal.

Das halte ich fuer keine gute Idee. Pascal ist zu unterschiedlich. Von
einer anderen objektorientierten Sprache auf C++ uebertragen, ist
möglich; von einer "klassischen" heraus ist aber schwierig.

Um doppeltverkettete Listen zu verstehen und zu testen ist (IMHO) jede
Sprache gut, die das ermöglicht. Datenstrukturen sind von Sprachen
weitgehend unabhängig.

Abgesehen davon, ist das Stoff eines Informatikkurses der Klasse 12. (Und
wir hatten damals Turbo-Pascal)

[Helmut Zeisel]

Post by Tobias Wollgam
Um doppeltverkettete Listen zu verstehen und zu testen ist (IMHO) jede
Sprache gut, die das ermöglicht. Datenstrukturen sind von Sprachen
weitgehend unabhängig.

Richtige Programmierer programmieren FORTRAN in jeder Sprache ;-)

Post by Tobias Wollgam
Abgesehen davon, ist das Stoff eines Informatikkurses der Klasse 12. (Und
wir hatten damals Turbo-Pascal)

Dann solltest Du wissen, dass Pascal nicht objektorientiert ist. Wenn Du
die Pascal-Lösung in C++ nachbaust, kommt ein Schmarrn heraus.
Klarerweise kannst Du eine objektorientierte Lösung in Pascal nachbauen;
das Ergebnis ist aber ganz anders als die "naive" Pascal Lösung.

Helmut

[Karl Heinz Buchegger]

Post by Helmut Zeisel

Post by Tobias Wollgam
Um doppeltverkettete Listen zu verstehen und zu testen ist (IMHO) jede
Sprache gut, die das ermöglicht. Datenstrukturen sind von Sprachen
weitgehend unabhängig.

Richtige Programmierer programmieren FORTRAN in jeder Sprache ;-)

Post by Tobias Wollgam
Abgesehen davon, ist das Stoff eines Informatikkurses der Klasse 12. (Und
wir hatten damals Turbo-Pascal)

Dann solltest Du wissen, dass Pascal nicht objektorientiert ist. Wenn Du
die Pascal-Lösung in C++ nachbaust, kommt ein Schmarrn heraus.

Mit Verlaub. Soo kompliziert ist eine Liste nun auch wieder nicht vom
Interface her. Natuerlich kann ich eine Liste zunaechst mal prozedural
aufbauen. Danach packe ich die einzelnen Funktionen in eine Klasse und habe
ein wunderschoenes Objekt ohne dass da gleich Schmarrn herauskommt. Gut
ich habe vielleicht etwas mehr Arbeit als unbedingt notwendig, auf der
anderen Seite hat der OP damit zumindest sehr schnell etwas was er als HÜ
abgeben kann, auch wenns Punkteabzuege gibt.
Wenn er sich dann noch Literatur reinzieht, bzw. wenn ihm jemand zeigt wie
wie man das ganze in ein Template umwandelt, ist er schon auf der Siegerstrasse.

[Helmut Zeisel]

Post by Karl Heinz Buchegger
Mit Verlaub. Soo kompliziert ist eine Liste nun auch wieder nicht vom
Interface her. Natuerlich kann ich eine Liste zunaechst mal prozedural
aufbauen. Danach packe ich die einzelnen Funktionen in eine Klasse und habe
ein wunderschoenes Objekt ohne dass da gleich Schmarrn herauskommt.

Genau das ist das Problem. Nicht jeder prozedurale Code laesst sich so
einfach in eine Klasse packen, es sei denn, man denkt schon von Anfang
an objektorientiert.

Post by Karl Heinz Buchegger
Gut
ich habe vielleicht etwas mehr Arbeit als unbedingt notwendig,

Genau. Eine der Programmiersprache unangepasste Programmstruktur
umzubauen ist mehr, unter Umständen sogar sehr viel mehr Arbeit als
notwendig. Prozeduraler und objektorientierter Code schauen eben
unterschiedlich aus.

Post by Karl Heinz Buchegger
auf der
anderen Seite hat der OP damit zumindest sehr schnell etwas was er als HÜ
abgeben kann, auch wenns Punkteabzuege gibt.
Wenn er sich dann noch Literatur reinzieht, bzw. wenn ihm jemand zeigt wie
wie man das ganze in ein Template umwandelt, ist er schon auf der Siegerstrasse.

Wenn es einmal zur Klasse geworden ist, ist die Umwandlung auf Templates
tatsaechlich ein relativ kleines Problem.

Helmut

[Karl Heinz Buchegger]

Post by Helmut Zeisel

Post by Karl Heinz Buchegger
Mit Verlaub. Soo kompliziert ist eine Liste nun auch wieder nicht vom
Interface her. Natuerlich kann ich eine Liste zunaechst mal prozedural
aufbauen. Danach packe ich die einzelnen Funktionen in eine Klasse und habe
ein wunderschoenes Objekt ohne dass da gleich Schmarrn herauskommt.

Genau das ist das Problem. Nicht jeder prozedurale Code laesst sich so
einfach in eine Klasse packen, es sei denn, man denkt schon von Anfang
an objektorientiert.

Post by Karl Heinz Buchegger
Gut
ich habe vielleicht etwas mehr Arbeit als unbedingt notwendig,

Genau. Eine der Programmiersprache unangepasste Programmstruktur
umzubauen ist mehr, unter Umständen sogar sehr viel mehr Arbeit als
notwendig. Prozeduraler und objektorientierter Code schauen eben
unterschiedlich aus.

Das sehe ich im Prinzip alles so wie Du. Nur reden wir hier halt nicht
von irgendeinem prozeduralen Code, sondern von einer Liste. Und soooo
viele Moeglichkeiten wie die Funktionen sich praesentieren gibts da
auch prozedural nicht. Im Gegenteil, solche 'Container' lassen sich
normalerweise sehr gut von prozedural auf objektorientiert umstellen.

[helmut zeisel]

Post by Karl Heinz Buchegger
Das sehe ich im Prinzip alles so wie Du. Nur reden wir hier halt nicht
von irgendeinem prozeduralen Code, sondern von einer Liste. Und soooo
viele Moeglichkeiten wie die Funktionen sich praesentieren gibts da
auch prozedural nicht. Im Gegenteil, solche 'Container' lassen sich
normalerweise sehr gut von prozedural auf objektorientiert umstellen.

So koennen wir noch lange herumdiskutieren. Mein Vorschlag: Wenn Niels
sich an Deinen Vorschlag halten sollte, soll er den Pascal Code hier
posten und Du versprichts, ihm beim Umstellen auf C++ zu helfen.
Einverstanden?

Helmut

[Tobias Wollgam]

Post by helmut zeisel
So koennen wir noch lange herumdiskutieren. Mein Vorschlag: Wenn Niels
sich an Deinen Vorschlag halten sollte, soll er den Pascal Code hier
posten und Du versprichts, ihm beim Umstellen auf C++ zu helfen.
Einverstanden?

Ich finde, daß das ein Ansatz wäre (im Gegensatz zu "scheiß Vorlesung -> der
Prof. hat's versaut ... etc.") Ich bin Tibors Meinung, daß da ein Funke
Eigenleistung erkennbar sein sollte. Wer "fließend" Pascal kann, der kann
doch zumindest dort eine funktionierende Lösung entwerfen! (dann p2c, dann
Klassen und zuletzt Templates)

Wenn dann dabei konkrete Fragen auftauchen, wird (und ist) ihm mehr
geholfen.

Möglicherweise sollte man aber erst Pascal entwerfen und dann direkt einen
neuen Entwurf in C++ machen.

[Karl Heinz Buchegger]

Post by helmut zeisel

Post by Karl Heinz Buchegger
Das sehe ich im Prinzip alles so wie Du. Nur reden wir hier halt nicht
von irgendeinem prozeduralen Code, sondern von einer Liste. Und soooo
viele Moeglichkeiten wie die Funktionen sich praesentieren gibts da
auch prozedural nicht. Im Gegenteil, solche 'Container' lassen sich
normalerweise sehr gut von prozedural auf objektorientiert umstellen.

So koennen wir noch lange herumdiskutieren. Mein Vorschlag: Wenn Niels
sich an Deinen Vorschlag halten sollte, soll er den Pascal Code hier
posten und Du versprichts, ihm beim Umstellen auf C++ zu helfen.
Einverstanden?

War laenger unterwegs, daher bis jetzt keine Antwort.
Aber jetzt: na klar doch.

[Michael Schlenger]

On Wed, 28 Apr 2004 11:13:52 +0200, Helmut Zeisel

Post by Helmut Zeisel

Post by Tobias Wollgam
Um doppeltverkettete Listen zu verstehen und zu testen ist (IMHO) jede
Sprache gut, die das ermöglicht. Datenstrukturen sind von Sprachen
weitgehend unabhängig.

Richtige Programmierer programmieren FORTRAN in jeder Sprache ;-)

Post by Tobias Wollgam
Abgesehen davon, ist das Stoff eines Informatikkurses der Klasse 12. (Und
wir hatten damals Turbo-Pascal)

Dann solltest Du wissen, dass Pascal nicht objektorientiert ist. Wenn Du
die Pascal-Lösung in C++ nachbaust, kommt ein Schmarrn heraus.
Klarerweise kannst Du eine objektorientierte Lösung in Pascal nachbauen;
das Ergebnis ist aber ganz anders als die "naive" Pascal Lösung.

"Objektorientierung" heißt doch - grob vereinfacht -

- Kapselung
- Vererbung
- Polymorphismus.

Für eine Liste (linear oder doppelt verkettet oder Prio oder
irgendwas) braucht man aber

- Verweise
- dynmischen Speicher
- Generik

Das macht das Wesen einer solchen Liste aus. Dass man die
Zugriffsfunktionen, internen Daten etc. evtl. noch in eine Klasse
kapselt, tritt hier in den Hintergrund, und ist ein Nebeneffekt, mit
dem man die Sache zum Schluss noch rund machen wird. Wahrscheinlich
will der Ausbilder aber den Umgang mit dynamischem Speicher sowie
Zeigern sehen. Wollte er primär Klassen und Kapselung sehen, hätte er
eine andere Aufgabe gewählt.

Hier gleich noch Generik mit reinzunehmen, ist IMHO Unsinn. Schablonen
sollten erst viel später gemacht werden,

Und, BTW: Sowohl Pascal (in den modernen Sprachvarianten) als auch
C++ und sogar Basic (modernes Basic, natürlich) halten Sprachmittel
zur Implementierung der Objektorientierung bereit.

MY 2 cents...




------------------------------------------------
Michael Schlenger
------------------------------------------------

[Helmut Zeisel]

Post by Michael Schlenger
On Wed, 28 Apr 2004 11:13:52 +0200, Helmut Zeisel

Post by Helmut Zeisel
Dann solltest Du wissen, dass Pascal nicht objektorientiert ist. Wenn Du
die Pascal-Lösung in C++ nachbaust, kommt ein Schmarrn heraus.
Klarerweise kannst Du eine objektorientierte Lösung in Pascal nachbauen;
das Ergebnis ist aber ganz anders als die "naive" Pascal Lösung.

Und, BTW: Sowohl Pascal (in den modernen Sprachvarianten) als auch
C++ und sogar Basic (modernes Basic, natürlich) halten Sprachmittel
zur Implementierung der Objektorientierung bereit.

Das ist kein Widerspruch. Wer OO programmieren kann, kann das auch in
Assembler. Das Ergebnis ist aber ganz anders als die "naive"
Pascal/Assembler oder was immer Lösung.

Helmut

[Niels Menke]

Post by Tobias Wollgam
Wenn Du Pascal kannst, dann entwerfe Deine Lösung doch zunächst in Pascal.
Entwerfe dann analog eine Klasse in C++ und erweitere diese dann zum Schluß
zu einem Template.

Das ist es ja, wovon ich keinen Schimmer habe...
Das gedachte ich halt mit einem halbwegs brauchbaren Beispiel klarer zu
sehen...

[Helmut Zeisel]

Post by Niels Menke
Das gedachte ich halt mit einem halbwegs brauchbaren Beispiel klarer zu
sehen...

Habe es zwar schon einmal geschrieben; hier ist es aber nochmals:

http://www.lernnetz-sh.de/kmlinux/doc/C++-Lehrgang/dyn_obj/dyn_ob25.htm

Das ist eine doppelt verkette Liste mit char* Elementen.

Helmut

[Tibor Pausz]

Post by Niels Menke
Wie gesagt suchte ich ein Programmierbeispiel, das ich mir Stück für
Stück auseinanderpflücken und verstehen könnte.

Das ist gelinde gesagt ziemlicher Blödsinn. Aber wenn Du es trotzdem tun
willst, der g++ Compiler enthält den Sourcecode für die std::list
Template Klasse. Exakt das was Du suchst.

Sinnvoller wäre aber der Weg aus der anderen Richtung. Es ist nicht die
Aufgabe, daß Dir hier jemand Deine Aufgabe löst. Die meisten können das
und brauchen das nicht mehr lernen.

Wenn Du Problem beim Formulieren und dem Verständnis von C++ hast wird
Dir hier in der Group weitergeholfen.

[Helmut Zeisel]

Post by Tibor Pausz

Post by Niels Menke
Wie gesagt suchte ich ein Programmierbeispiel, das ich mir Stück für
Stück auseinanderpflücken und verstehen könnte.

Das ist gelinde gesagt ziemlicher Blödsinn.

Wieso? Es gibt unterschiedliche Lernstile. Der eine tut sich leichter,
wenn er ein fertiges Beispiel analysieren kann, der andere baut sich
synthetisch aus dem theoretischen Wissen seine Lösung zusammen.

Post by Tibor Pausz
Aber wenn Du es trotzdem tun
willst, der g++ Compiler enthält den Sourcecode für die std::list
Template Klasse. Exakt das was Du suchst.

Bei aller Hochachtung vor der STL - didaktisch ist sie unbrauchbar.

Post by Tibor Pausz
Sinnvoller wäre aber der Weg aus der anderen Richtung. Es ist nicht die
Aufgabe, daß Dir hier jemand Deine Aufgabe löst.

Das will er ja nicht. Er will, dass ihm jemand die Ecke zeigt, an der er
zu bauen beginnen muss.

Helmut

[Tibor Pausz]

Post by Helmut Zeisel
Wieso?

Ein wichtiger Lernschritt ist es, von selbst die Grenzen des eigenen
Wissen zu verschieben. Wenn man nur das wiederkäut was andere schon
vorher gelöst haben, dann wird man das nie schaffen.

Ich weiß aus eigener Erfahrung wie anstrengend das ist.

Post by Helmut Zeisel
Der eine tut sich leichter, wenn er ein fertiges Beispiel analysieren
kann, der andere baut sich synthetisch aus dem theoretischen Wissen seine
Lösung zusammen.

Nur will er kein Beispiel sondern eine Musterlösung. Was bleibt dann
noch als Lerneffekt für ihn übrig?

Post by Helmut Zeisel
Bei aller Hochachtung vor der STL - didaktisch ist sie unbrauchbar.

ROFTL, ich halte das nicht für einen didaktisch sinnvollen Weg, ob die
STL damit didaktisch sinnvoll ist oder nicht ist damit hinfällig. Die
STL enthält eine Template Klasse, exakt wie sie die Zielvorgaben des OP
beinhalten.

Post by Helmut Zeisel
Das will er ja nicht.

Irrtum, er will genau das, auch wenn er es anders formuliert.

[Helmut Zeisel]

Post by Tibor Pausz
Irrtum, er will genau das, auch wenn er es anders formuliert.

Ich sehe bis jetzt keinen Grund an seinen Worten zu zweifeln. Wie dem
auch sei, auf ein Beispiel habe ich bereits verwiesen, und vorgekaute
Lösung bekommt er von mir sowieso nicht.

Helmut

[Tibor Pausz]

Post by Helmut Zeisel
Ich sehe bis jetzt keinen Grund an seinen Worten zu zweifeln.

Tut ja niemand, nur er läßt sich nicht darauf ein zu erklären was er
denn nicht versteht und das ist nicht gut.

[Rolf Magnus]

Post by Tibor Pausz

Post by Helmut Zeisel
Wieso?

Ein wichtiger Lernschritt ist es, von selbst die Grenzen des eigenen
Wissen zu verschieben. Wenn man nur das wiederkäut was andere schon
vorher gelöst haben, dann wird man das nie schaffen.

Das stimmt zwar, aber manche schaffen es nicht, von Grund auf was neues
Anzufangen, was sie noch nie gemacht haben. Geht mir oft auch so. Ich
bin dann immer froh über ein Beispiel, wo schon mal jemand zumindest
was ähnliches gemacht hat. Das nehme ich dann als Ansatz und baue es
unter Zuhilfenahme von Literator weiter aus oder um. Ich bin jemand,
der schnell zumindest ein kleines Ergebnis sehen will und sich dann
schrittweise zum Ziel weiterarbeitet.
Es geht schließlich nicht darum, was wiederzukäuen, sondern einen
Startpunkt zu haben, bei dem schon etwas funktionierendes da ist.

Post by Tibor Pausz
Ich weiß aus eigener Erfahrung wie anstrengend das ist.

Post by Helmut Zeisel
Der eine tut sich leichter, wenn er ein fertiges Beispiel analysieren
kann, der andere baut sich synthetisch aus dem theoretischen Wissen
seine Lösung zusammen.

Nur will er kein Beispiel sondern eine Musterlösung.

Er schrieb "Hat vielleicht jemand ein gutes Programmierbeispiel für mein
Problem...?".

Post by Tibor Pausz
Was bleibt dann noch als Lerneffekt für ihn übrig?

Post by Helmut Zeisel
Bei aller Hochachtung vor der STL - didaktisch ist sie unbrauchbar.

ROFTL, ich halte das nicht für einen didaktisch sinnvollen Weg, ob die
STL damit didaktisch sinnvoll ist oder nicht ist damit hinfällig. Die
STL enthält eine Template Klasse, exakt wie sie die Zielvorgaben des
OP beinhalten.

Post by Helmut Zeisel
Das will er ja nicht.

Irrtum, er will genau das, auch wenn er es anders formuliert.

Du hast vermutlich noch nie die Header einer STL-Implementation
angesehen. Ein Anfänger versteht davon nämlich mit Sicherheit absolut
nichts.

[Karl Heinz Buchegger]

Post by Rolf Magnus

Post by Tibor Pausz

Post by Helmut Zeisel
Wieso?

Ein wichtiger Lernschritt ist es, von selbst die Grenzen des eigenen
Wissen zu verschieben. Wenn man nur das wiederkäut was andere schon
vorher gelöst haben, dann wird man das nie schaffen.

Das stimmt zwar, aber manche schaffen es nicht, von Grund auf was neues
Anzufangen, was sie noch nie gemacht haben. Geht mir oft auch so.

Nicht nur Dir :-)
Eine Demo mal im Debugger durchsteppen ist halt doch ganz was anderes
als sich die Doku von x Funktionsaufrufen reinziehen und raetseln
welcher Ausgabewert denn nun wo leicht veraendert wieder als Eingabeparameter
auftaucht.
Manchmal sind Algorithmen wunderbar komplex beschrieben und wenn
Du Dir die Implementierung ansiehst faellt es Dir wie Schuppen von den
Augen: "Mein Gott, so simpel ist das in Wirklichkeit". Manchmal sieht man
den Wald vor lauter Baeumen nicht mehr :-)

Das wirklich wichtige daran ist: Uebernehm ich den Code einfach so
ohne zu wissen wie er funktioniert oder arbeite ich mit dem was ich
bekommen habe. Gegen letzteres ist IMHO absolut nichts einzuwenden.

[Tibor Pausz]

Post by Rolf Magnus
Es geht schließlich nicht darum, was wiederzukäuen, sondern einen
Startpunkt zu haben, bei dem schon etwas funktionierendes da ist.

Damit ist doch das eigentliche Problem längst gelöst. Der Problemansatz
ist der Punkt an dem der Grips wirklich gebraucht wird, der Rest ist
bloß noch Handwerk.

Post by Rolf Magnus
Er schrieb "Hat vielleicht jemand ein gutes Programmierbeispiel für mein
Problem...?".

Da er sich nicht äußert wobei er Probleme hat, läuft das auf eine
Musterlösung hinaus. Er sagt nichts dazu, ob ein verkette Listen
verstanden hat. Er schreibt nichts dazu, wie er sich das Interface mit
den geforderten Methoden zumindest im Ansatz vorstellt. Er schreibt
nichts dazu, wie er das Problem in Pascal lösen würde etc. pp.

Fazit: Bisher keinerlei Eigenleistung von ihm

Post by Rolf Magnus
Du hast vermutlich noch nie die Header einer STL-Implementation
angesehen.

Doch habe ich, nur ich sprache von einer Musterlösung die er haben will
und meinte damit nicht unbedingt die STL.

Post by Rolf Magnus
Ein Anfänger versteht davon nämlich mit Sicherheit absolut nichts.

Tja, das ist sein Problem, wenn er keinerlei Bemühen zeigt, das Problem
zu lösen. Eigeninitiative muß irgend wie schon vorhanden sein.

[Helmut Zeisel]

Post by Niels Menke
Wie gesagt suchte ich ein Programmierbeispiel, das ich mir Stück für
Stück auseinanderpflücken und verstehen könnte.

http://www.lernnetz-sh.de/kmlinux/doc/C++-Lehrgang/dyn_obj/dyn_ob25.htm

Das ist eine doppelt verkette Liste mit char* Elementen.

Helmut

[Werner Jakobi]

Post by Niels Menke
Wie gesagt suchte ich ein Programmierbeispiel, das ich mir Stück für
Stück auseinanderpflücken und verstehen könnte.

Warum nimmst du in C++ nicht list aus der STL? Das ist doch eine doppelt
verzeigerte Liste, die mit Templates funktioniert und alle deine Wünsche
erfüllt. Man muß die Welt nicht immer neu erfinden?

Ansonsten müßtest du halt die übliche C-Liste anpassen:
typedef struct node {
node* next;
node* previous;
void* data;
};

typedef class list {
node* head; // zeigt auf den Kopf der Liste
node* tail; // immer 0
node* tailpred; // zeigt auf den Vorgänger von tail
};

list::list() {
head = 0;
tail = 0;
tailpred = *head;
}

...

Das wird allerdings recht mühsam werden.

Gruss, Werner

[Helmut Zeisel]

Post by Werner Jakobi

Post by Niels Menke
Wie gesagt suchte ich ein Programmierbeispiel, das ich mir Stück für
Stück auseinanderpflücken und verstehen könnte.

Warum nimmst du in C++ nicht list aus der STL?

Bitte nicht; die STL ist alles andere als ein didaktische gutes Beispiel.

Helmut

[Werner Jakobi]

Post by Helmut Zeisel

Post by Werner Jakobi
Warum nimmst du in C++ nicht list aus der STL?

Bitte nicht; die STL ist alles andere als ein didaktische gutes
Beispiel.

Das finde ich nicht. Die STL ist ein integrer Bestandteil von C++.
Solange irgendwas daraus paßt, verwendet man das. So ist C++. Ganz davon
abgesehen beschreibt Stroustrup die Fähigkeiten in seinem Schmöker
ziemlich ordentlich. Mittlerweile funktioniert AFAIK die STL ja auch
zumindestens mit g++ OS-übergreifend richtig, so daß es keinen Grund
gibt selbstgestrickte Listen zu verwenden

Wenn er wissen will, wie generell Listen programmiert werden ist er hier
eigentlich falsch. Das gehört eher nach de.comp.lang.misc

Ganz abgesehen davon habe ich ja die grundlegenden Datenstrukturen
mitgeliefert.

Ganz abgesehen davon halte ich die Selbstimplementation eine
Listenklasse für grundsätzlich falsch. Eine doppelt verzeigerte Liste
ist offensichtlich ein sehr klar strukturiertes Objekt und scheint sich
als Lernbeispiel geradezu anzubieten. In der Praxis ist es jedoch so,
daß es ziemlich aufwendig ist, eine *funktionierende* Liste zu
schreiben.

Gruss, Werner

[Helmut Zeisel]

Post by Werner Jakobi

Post by Helmut Zeisel

Post by Werner Jakobi
Warum nimmst du in C++ nicht list aus der STL?

Bitte nicht; die STL ist alles andere als ein didaktische gutes Beispiel.

Das finde ich nicht. Die STL ist ein integrer Bestandteil von C++.
Solange irgendwas daraus paßt, verwendet man das.

Volle Zustimmung.

Post by Werner Jakobi
Wenn er wissen will, wie generell Listen programmiert werden ist er hier
eigentlich falsch. Das gehört eher nach de.comp.lang.misc

Das war mein Punkt. Um zu verstehen, wie generell Listen programmiert
werden, ist die STL nicht geeignet.

Helmut

[Georg Maaß]

Post by Niels Menke
Das Problem ist, das unsere Vorlesung "Einführung in die Programmierung
mit C++" im letzten Semester nicht wirklich die viele Zeit wert war, die
ich hineingesteckt habe, denn komplexere Dinge in C++ programmieren kann
ich immer noch nicht

Das dauert auch ein paar Jahre. C++ ist nicht Java. Für Java reicht es,
wenn man bis 5 zählen kann. C++ hat viel mehr Sprachmittel als so ein
Kastrat wie Java. Deshalb darf man da schon mal die Zahlen bis 100 drauf
haben, ehe man wirklich alle Fallstricke und Fettnäpfchen im Kopf statt
im Programm hat.

Die meisten Probleme werden aber durch die C-Kompatibilität verursacht
und den Versuch den Comilerbauern das Leben in einer C-Umgebung
möglichst leicht zu machen.

Dein Problem jedoch ist relativ einfach.

Du brauchst Listenelemente, die aus einer Eigenschaft für den Wert und
zwei Eigenschfaten mit Zeigern auf Listenelemente enthalten.

Außerdem benötigts Du für die im OP genannte Implementierung einen
Container, der die Listenelemente verwaltet. diesem Conatiner spendierst
Du die in deinem OP genannten Funtionalitäten als Methoden, sowie
entwerder nur einen Zeiger auf das erste Listenelement bzw. 0, wenn die
Liste leer ist, oder aber auch noch einen zweiten Zweiger auf das letzte
Listenelement. Der zweite Zeiger ist nur unter Performance-Optimierungen
erforderlich, wenn häufig top, push und pop etwa gleich häufig
vorkommen. Wenn nur push und pop häufig sind, dann genügt ein einziger
Zeiger, den man dann aber auf das Ende setzt, weil ja dort dann die
häufigsten Operationen stattfinden.

Post by Niels Menke
Es sollte also mit C++ auch klappen.

Nein, denn im Unterschied zu PHP besitzt C++ viele Fettnäpchen. Die aber
sieht man im fremden Code nicht, sondern bestenfalls sieht man, daß da
irgendwelche komischen Dinge gemacht werden, ohne daß man wirklich
erkennen kann, warum. Wenn man solche Merkwürdigkeiten dann vereinfcaht,
dann kann es sein, daß es zufällig immer noch funktioniert, genauso kann
es aber auch zum Absturz führen. Umgekehrt, kann man aber auch nicht
automatisch davon ausgehen, daß alles, was abstrus aussieht nur deshalb,
weil man nicht versthet, was da abgeht, tatsächlich richtig bzw. optimal
ist.

C++ ist schwierig. Deshalb ist es sinnvoll hier mit zu diskutieren, denn
auch dies hilft unerkannte Probleme als solche zu erkennen und dann auch
gezielt zu lösen.

[Karl Heinz Buchegger]

Post by Niels Menke
Hi NG,
Verzeiht mir falls das ne häufig gestellte Frage ist, aber per google
war nichts zu finden...

Das ist schwer zu glauben :-)

Post by Niels Menke
Ich soll eine doppelt verkettete Liste programmieren, mit Templates und
den Methoden push, pop, top (lesen des obersten Elements), empty
(liefert true falls liste leer) und dump_elements (alle elemente ausgeben).
Mein Problem: Ich blick nicht so recht, wie ich das machen soll, da
Vorlesung und Skript doch sehr dürftig ausfielen. Hat vielleicht jemand
ein gutes Programmierbeispiel für mein Problem, über dem ich zwecks
Verständnis meditieren könnte?

Der heisseste Tip den ich Dir geben kann, ist: schnap Dir Zettel
und Bleistift und spiel mal ein bischen mit doppelt verketteten Listen
rum. Du kriegst so ein Gefuehl dafuer wie die einzelnen Operationen
laufen muessen und in welcher Reihenfolge welcher Pointer umzusetzen
ist.

Bsp. einen Knoten am Ende einer Liste anhaengen.

Dies sei die Liste (Jeder Knoten besteht aus einem
Wert und 2 Pointern. Der erste Pointer moege next
heisen, der zweite prev)


Root
+------+
| o |
+---|--+
|
v
+-------+ +------+ +-------+
| 3 | | 4 | | 5 |
| o---------->| o--------->| NULL |
| NULL |<----------o |<----------o |
+-------+ +------+ +-------+

und jetzt hast Du da einen neuen Knoten, der hinten ran muss:

Root
+------+
| o |
+---|--+
|
v
+-------+ +------+ +-------+
| 3 | | 4 | | 5 |
| o---------->| o--------->| NULL |
| NULL |<----------o |<----------o |
+-------+ +------+ +-------+



NewNode
+------+
| o------------+
+------+ |
v
+------+
| 6 |
| NULL |
| NULL |
+------+


Nur, wie macht man das? Zunaechst mal, wird es wahrscheinlich
das Bestreben sein, einen Pointer auf das letzte Listenelement
zu kriegen. Das erscheint logisch, den dort muss ja die Liste
manipuliert werden :-) Also ist es Dein erstes Ziel in diesen
Zustand zu kommen:

Root
+------+
| o |
+---|--+
|
v
+-------+ +------+ +-------+
| 3 | | 4 | | 5 |
| o---------->| o--------->| NULL |
| NULL |<----------o |<----------o |
+-------+ +------+ +-------+
^
|
Temp |
+--------+ |
| o------------------------------+
+--------+

NewNode
+------+
| o------------+
+------+ |
v
+------+
| 6 |
| NULL |
| NULL |
+------+

Temp zeigt also aufs letzte Element. Hmm. Wie kommt er dort hin?
Nun Temp uebernimmt zunaechst mal den Wert von Root und 'hangelt'
sich am next Pointer nach rechts, bis der letzte Knoten erreicht
ist. Hmm. Woran erkennt man den letzten Knoten? Schau auf die Zeichnung
und vergleiche den Knoten mit den anderen in der Liste! Richtig:
sein next Pointer ist NULL.

In Code gegossen sieht das ganze dann so aus:

Temp = Root;
while( Temp->next != 0 )
Temp = Temp->next;

Da muss dann noch eine Behandlung des Falles Root == 0 rein, aber
im wesentlichen wars das.

OK. Nun ist der Temp Pointer am letzten Knoten, wie wird der neue
Knoten dort eingehaengt? Indem ein paar Pointer verbogen werden.
Das Endziel sieht so aus:

Root
+------+
| o |
+---|--+
|
v
+-------+ +------+ +-------+
| 3 | | 4 | | 5 |
| o---------->| o--------->| o----------+
| NULL |<----------o |<----------o |<--+ |
+-------+ +------+ +-------+ | |
^ | |
| | |
Temp | | |
+--------+ | | |
| o------------------------------+ | |
+--------+ | |
| |
NewNode | |
+------+ | |
| o------------+ | |
+------+ | | |
v | |
+------+ | |
| 6 | | |
+---->| NULL | | |
| +-----o | | |
| | +------+ | |
| | | |
| +-------------------------------+ |
| |
+-------------------------------------+

und jetzt heist es eine Reihenfolge von Zuweisungen zu finden, die
genau dieses Ergebnis erzeugt. Ausgangspunkt aller Manipulationen
sind immer die Pointer Temp und NewNode. Immer wenn Du in der
Zeichnung einem Pfeil folgen musst, weil Du im dortigen Rechteck
ein Feld aufsuchen musst, schreibst Du ein ->

zB. Ich moechte den Pfeil realisieren, der vom Knoten '5' zum neuen
Knoten '6' fuehrt:

Root
+------+
| o |
+---|--+
|
v
+-------+ +------+ +-------+
| 3 | | 4 | | 5 |
| o---------->| o--------->| NULL |
| NULL |<----------o |<----------o |
+-------+ +------+ +-------+
^
|
Temp |
+--------+ |
| o------------------------------+
+--------+

NewNode
+------+
| o------------+
+------+ |
v
+------+
| 6 |
| NULL |
| NULL |
+------+

von Tmp ausgehend erreiche ich den Knoten '5', indem ich dem Pfeil
folge:

Tmp->

Im dortigen Rechteck brauche ich das next Feld

Tmp->next

Damit habe ich identifiziert wo der Pfeil starten soll. Wo soll
er hin zeigen: Nun, auf das gleiche Rechteck, auf das auch
NewNode zeigt. Also heist die ganze Anweisung:

Tmp->next = NewNode;

und das Ergebnis sieht so aus:

Root
+------+
| o |
+---|--+
|
v
+-------+ +------+ +-------+
| 3 | | 4 | | 5 |
| o---------->| o--------->| o----------+
| NULL |<----------o |<----------o | |
+-------+ +------+ +-------+ |
^ |
| |
Temp | |
+--------+ | |
| o------------------------------+ |
+--------+ |
|
NewNode |
+------+ |
| o------------+ |
+------+ | |
v |
+------+ |
| 6 | |
+---->| NULL | |
| | NULL | |
| +------+ |
| |
| |
| |
+-------------------------------------+

Vergleicht man mit dem angestrebten Ergebnis, so fehlt
nur noch der Reuckwaertspfeil von '6' nach '5'.
Wie kann ich das Feld an dem der Pfeil starten muss identifizieren?
Moegliche Ausgangspunkte sind die Pointer Temp oder NewNode.
Nun am einfachsten, kommt man an das Feld heran, wenn man
ueber NewNode geht: NewNode, immer dem Pfeil entlang und im
Rechteck das prev Feld:

NewNode->prev

Es geht aber auch anders. Ich kann bei Temp starten, dem Pfeil folgen,
im Rechteck das next Feld aufsuchen, nochmals einem Pfeil folgen, bis
ich schliesslich im gesuchten Rechteck lande, von wo ich das prev
Feld brauche. Oder in Code:

Temp->next->prev

Wofuer Du Dich entscheidest ist Deine Sache, auf jeden Fall muss der neue
Pfeil auf den Knoten '5' zeigen. Der ist einfach zu finden: Temp zeigt
schon drauf. Also in Code

NewNode->prev = Temp;

oder aber

Temp->next->prev = Temp;

Tja. das wars. Der neue Knoten ist eingehaengt.
Wie stehts mit Sonderfaellen. Was ist wenn die Liste
leer ist (Root == NULL)? Die Faelle musst Du Dir noch
ueberlegen und ev. Aenderungen am Bisherigen anbringen.

Aber: Unterschaetze nicht den Wert von Papier und Bleistift!
Niemand, und ich meine niemand, kann eine lineare Liste, ob
einfach oder doppelt verkettet, beim ersten Mal fehlerfrei
programmieren. P&B sind da eine exzellente Hilfe zum ausknobeln
und was noch viel wichtiger ist: bei der Fehlersuche. Bei der
Fehlersuche drehst Du den Spiess um: Du spielst Computer und
durchlaeufst Deine Funktion. Am Papier zeichnest Du alle
Aenderungen die Dir die Funktion vorschreibt mit. Normalerweise
sieht man auf diese Weise sehr schnell woran's denn scheitert.

Aber: Uebung macht den Meister. Ich wuerde mal schaetzen, das
ein Durchschnittsprogrammierer so 5 bis 7 Anlauefe braucht, bis
er eine lineare Liste fehlerfrei, einfach so und ohne
grosses Nachdenken, hinkriegt.

[Alexander Stein]

Hallo Karl Heinz,

Post by Karl Heinz Buchegger
Nur, wie macht man das? Zunaechst mal, wird es wahrscheinlich
das Bestreben sein, einen Pointer auf das letzte Listenelement
zu kriegen. Das erscheint logisch, den dort muss ja die Liste
manipuliert werden :-) Also ist es Dein erstes Ziel in diesen

Wir hatten heute genau die gleiche Datenstruktur, aber bei uns hatte die
Liste noch einen Pointer auf das letzte Element, was das durchhangeln
unnötig macht.

Post by Karl Heinz Buchegger
Temp = Root;
while( Temp->next != 0 )

^^^^^^^^^^^^^^

Post by Karl Heinz Buchegger
Temp = Temp->next;

Beim einfügen an eine bestimmte Stelle steht genau der gleiche Code(plus
einer Zähler Dekrementierung). Warum schreibt keiner
while(!Temp->next)
? Das habe ich mich heute bei meinem Dr. auch gefragt. So spart man sich
einen Vergleich.

MfG
Alexander

[Stefan Reuther]

Post by Alexander Stein

Post by Karl Heinz Buchegger
Temp = Root;
while( Temp->next != 0 )

^^^^^^^^^^^^^^

Post by Karl Heinz Buchegger
Temp = Temp->next;

Beim einfügen an eine bestimmte Stelle steht genau der gleiche Code(plus
einer Zähler Dekrementierung). Warum schreibt keiner
while(!Temp->next)
? Das habe ich mich heute bei meinem Dr. auch gefragt. So spart man sich
einen Vergleich.

Wie 'spart einen Vergleich'? Beide Zeilen sind per Definition identisch
und generieren auf jedem Compiler, der sein Geld wert ist, denselben Code.

Die Variante '!= 0' halte ich aber in diesem Fall für besser lesbar.


Stefan

[Martin Winkler]

Post by Stefan Reuther

Post by Alexander Stein

Post by Karl Heinz Buchegger
Temp = Root;
while( Temp->next != 0 )

^^^^^^^^^^^^^^

Post by Karl Heinz Buchegger
Temp = Temp->next;

Beim einfügen an eine bestimmte Stelle steht genau der gleiche Code(plus
einer Zähler Dekrementierung). Warum schreibt keiner
while(!Temp->next)

Alexander meinte:
while( Temp->next )

Post by Stefan Reuther

Post by Alexander Stein
? Das habe ich mich heute bei meinem Dr. auch gefragt. So spart man sich
einen Vergleich.

Wie 'spart einen Vergleich'? Beide Zeilen sind per Definition identisch
und generieren auf jedem Compiler, der sein Geld wert ist, denselben Code.

Mit obiger kleiner Korrektur, ja. (Mir ist klar, daß das ein reiner
Vertipper war, aber da auch Anfänger mitlesen, sei darauf hingewiesen.)

Post by Stefan Reuther
Die Variante '!= 0' halte ich aber in diesem Fall für besser lesbar.

Geschmackssache. Auf jeden Fall schadet es in keinster Weise
(Funktionalität oder Performance, weil es ist derselbe Code.)

Gruß
Martin

[Rolf Magnus]

Post by Stefan Reuther

Post by Alexander Stein

Post by Karl Heinz Buchegger
Temp = Root;
while( Temp->next != 0 )

^^^^^^^^^^^^^^

Post by Karl Heinz Buchegger
Temp = Temp->next;

Beim einfügen an eine bestimmte Stelle steht genau der gleiche
Code(plus einer Zähler Dekrementierung). Warum schreibt keiner
while(!Temp->next)
? Das habe ich mich heute bei meinem Dr. auch gefragt. So spart man
sich einen Vergleich.

Wie 'spart einen Vergleich'? Beide Zeilen sind per Definition
identisch und generieren auf jedem Compiler, der sein Geld wert ist,
denselben Code.
Die Variante '!= 0' halte ich aber in diesem Fall für besser lesbar.

Das kommt ganz darauf an, ob der Code eher ausdrücken soll, was er
macht, oder wie er es macht.

while (Temp->next != 0)

drückt eher das "wie" aus. "So lange der next-Pointer nicht 0 ist..."

while (Temp->next)

eher das "was". "So lange es ein nächstes Element gibt..."

Die zweite Variante finde ich da besser.

[Karl Heinz Buchegger]

Post by Alexander Stein
Hallo Karl Heinz,

Post by Karl Heinz Buchegger
Nur, wie macht man das? Zunaechst mal, wird es wahrscheinlich
das Bestreben sein, einen Pointer auf das letzte Listenelement
zu kriegen. Das erscheint logisch, den dort muss ja die Liste
manipuliert werden :-) Also ist es Dein erstes Ziel in diesen

Wir hatten heute genau die gleiche Datenstruktur, aber bei uns hatte die
Liste noch einen Pointer auf das letzte Element, was das durchhangeln
unnötig macht.

Kannst Du natuerlich machen (und ist auch sinnvoll).

Post by Alexander Stein

Post by Karl Heinz Buchegger
Temp = Root;
while( Temp->next != 0 )

^^^^^^^^^^^^^^

Post by Karl Heinz Buchegger
Temp = Temp->next;

Beim einfügen an eine bestimmte Stelle steht genau der gleiche Code(plus
einer Zähler Dekrementierung). Warum schreibt keiner
while(!Temp->next)

while( Temp->next )

Post by Alexander Stein
? Das habe ich mich heute bei meinem Dr. auch gefragt. So spart man sich
einen Vergleich.

Irrtum. Du sparst dadurch gar nichts, ausser etwas Tippparbeit. Das aber
ist es aber IMHO gar nicht wert, wie Dein 'Fehler' eindrucksvoll
demonstriert hat.

[Marco Budde]

Post by Niels Menke
Mein Problem: Ich blick nicht so recht, wie ich das machen soll, da
Vorlesung und Skript doch sehr dürftig ausfielen.

Ist doch an der Uni immer so. Am besten beides vergessen und sich
ein paar gute Bücher zulegen. C++ ist ein wichtiges Handwerkszeug,
das man erlernen sollte.

Post by Niels Menke
Hat vielleicht jemand
ein gutes Programmierbeispiel für mein Problem,

Schau Dir doch einfach mal das Interface der STL Container von C++
an (vector, deque, list).

Post by Niels Menke
über dem ich zwecks
Verständnis meditieren könnte?

Du mußt schon genauer erklären, wo jetzt Dein Problem genau liegt.
Pauschal würde ich Dir zu Templates das Buch "C++ Templates" von
Vandevoorde und Josuttis empfehlen.

cu, Marco

[Olaf Krzikalla]

Hi,

Post by Niels Menke
Ich soll eine doppelt verkettete Liste programmieren, mit Templates und
den Methoden push, pop, top (lesen des obersten Elements), empty
(liefert true falls liste leer) und dump_elements (alle elemente ausgeben).

Was ist eingentlich das 'oberste' Element einer doppelt verketteten
Liste. Sicherlich ist wohl das letzte Element gemeint.
Mit Templates hab ich auch eine:

people.freenet.de/turtle++/ilist.h

Das allerdings ist eine intrusive Liste - die allerdings der _mir
bekannten_ Aufgabenstellung auch entspricht, wenn man von einigen
Namensunterschieden absieht. Wie und wann man die aber anwendet, bleibt
dem geneigten Leser als Übung überlassen. Ich hab seit 3 Monaten keine
Zeit/Lust, da mal bisschen was dazu ins Netz zu stellen, obwohl die
Dinger [ilist.h kann auch durch imultiset.h ersetzt werden] unheimlich
nützlich sind, wenn es um raw speed geht.


MfG
Olaf Krzikalla