AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

doppelt verkettete listen

Ein Thema von daswurm · begonnen am 14. Dez 2005 · letzter Beitrag vom 14. Dez 2005
Antwort Antwort
Seite 1 von 2  1 2   
daswurm

Registriert seit: 8. Dez 2005
4 Beiträge
 
#1

doppelt verkettete listen

  Alt 14. Dez 2005, 17:04
huhu
ich habe eine dummes problem und kann es leider absolut nicht alleine lösen. wir müssen im informatik unterricht ein programm machen welches folgende kriterien erfüllen soll ( alles delphi 4 ) :

- doppelt verkettete liste
- einfügen neuer einträge alphabetisch
- ausgabe der daten in einer listbox
- suchen
- löschen des gefundenen eintrags
- speichern und laden auf der festplatte

so das wars auch schon was wir machen müssen, nur leider habe ich keine ahnung was wir machen sollen, da unser lehrer sehr kompliziert erklärt und leider auch nicht so ganz auf fragen eingeht, naja egal ich tue mir auf jeden fall sehr schwer zu begreifen wie ich sowas programmieren soll....

kann mir vielleicht jemand nettes dabei helfen ... ich würde mich sehr freuen ... danke schon mal im vorraus fürs erklären
  Mit Zitat antworten Zitat
Benutzerbild von Binärbaum
Binärbaum

Registriert seit: 19. Jan 2005
Ort: Elstra
764 Beiträge
 
Delphi 7 Enterprise
 
#2

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 17:11
Also gut.
Der grundgedanke bei doppelt verketteten Listen ist, dass man bei jedem Element auch einen Zeiger auf das vorherige und nachfolgende Listenelement hat. Damit kann man (im Gegensatz zu einfach verketteten Listen) von jedem Element aus in beide Richtungen einer Liste gehen.
Eine Typdeklaration könnte etwa so aussehen:

Delphi-Quellcode:
type
  PListelement = ^TListelement;//Zeiger auf Listenelement
  TListelement = record
                     data: char; //oder Integer oder String
                                 //oder was auch immer man gerade benötigt
                     vorheriges, //Zeiger auf vorheriges Element
                     naechstes: PListenElement; //Zeiger auf nachfolgendes Element
  end;

MfG
Binärbaum
There are exactly 10 kinds of people: those who understand binary, and those who don't.
---
"Software reift beim Kunden. Bei Hardware ist es anders: Hardware fault beim Kunden." - Rainer G. Spallek
  Mit Zitat antworten Zitat
daswurm

Registriert seit: 8. Dez 2005
4 Beiträge
 
#3

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 17:16
ok das hab ich begriffen, hab ich auch schon eingebaut in meine procdure ... aba wie gehts jetzt weiter mit dem alphabetischen einfügen ??
  Mit Zitat antworten Zitat
Benutzerbild von Binärbaum
Binärbaum

Registriert seit: 19. Jan 2005
Ort: Elstra
764 Beiträge
 
Delphi 7 Enterprise
 
#4

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 17:21
Zitat von daswurm:
ok das hab ich begriffen, hab ich auch schon eingebaut in meine procdure ... aba wie gehts jetzt weiter mit dem alphabetischen einfügen ??
Nun ja, wenn du das bloße Einfügen beherrschst, ist das kein zu großes Problem: man läuft einfach die Liste vom Anfang an durch und prüft, ob das Element, bei dem man sich gerade befindet, im Alphabet vor oder nach dem einzufügenden Element kommt, und fügt dann an der entsprechenden Stelle das neue Element ein. Dabei sind allerdings einige Sonderfälle wie z.B. das Einfügen in eine noch leere Liste zu beachten.

MfG
Binärbaum
There are exactly 10 kinds of people: those who understand binary, and those who don't.
---
"Software reift beim Kunden. Bei Hardware ist es anders: Hardware fault beim Kunden." - Rainer G. Spallek
  Mit Zitat antworten Zitat
daswurm

Registriert seit: 8. Dez 2005
4 Beiträge
 
#5

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 17:32
ähm das klingt jetzt bestimmt völlig behemmert für dich aba so ganz hab ich das jetzt nicht verstanden ! sry ...
mir war schon bewusst das ich die liste von vorne durch laufen muss, aba wie mach ich das denn genau ??

ich bin leider vollkommen verwirrt ... ich habe bis jetzt nur mit einfacher verkettungung gearbeitet, nun wäre es ja eigentlich auch sehr sinnvoll könnte man einfach die einfache verkettung umschreiben, aba dies stellt sich als recht schwer für mich heruas .. naja ich weiß echt nicht weiter

scheiße, auch wenns jetzt bestimmt nervt kannst du mir das vll anhand eines beispieles erläutern mit dem einfügen ... ich möchte auch wirklich nicht, wenn das den schein erwecken sollte, dass mir das komplette programm geschrieben wir, denn dies erachte ich als nicht sehr sinnvoll.
  Mit Zitat antworten Zitat
Benutzerbild von Binärbaum
Binärbaum

Registriert seit: 19. Jan 2005
Ort: Elstra
764 Beiträge
 
Delphi 7 Enterprise
 
#6

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 17:59
Zitat von daswurm:
so ganz hab ich das jetzt nicht verstanden ! sry ...
mir war schon bewusst das ich die liste von vorne durch laufen muss, aba wie mach ich das denn genau ??

ich bin leider vollkommen verwirrt ... ich habe bis jetzt nur mit einfacher verkettungung gearbeitet, nun wäre es ja eigentlich auch sehr sinnvoll könnte man einfach die einfache verkettung umschreiben, aba dies stellt sich als recht schwer für mich heruas .. naja ich weiß echt nicht weiter
Wenn du schon mit einfach verketteten Listen gearbeitet hast, hast du doch schon die (sprichwörtliche) halbe Miete. Du kannst ja erstmal "so tun", als ob die Liste nur einfach verkettet wäre und (wie bei einfach verketteten Listen) immer nur den Zeiger auf das nächste Element nutzen, um die Liste zu durchlaufen.

Zitat von daswurm:
kannst du mir das vll anhand eines beispieles erläutern mit dem einfügen ...
Ach du Schreck, da muss ich ja selbst Code schreiben, oder? :p
Nee, Scherz, ich kanns machen, aber das dauert eine Weile, da ich aus der Listenmaterie etwas raus bin.

Aber mal etwas zum allgemeinen Prinzip: nehmen wir an, du hast eine Liste, die nicht leer ist und schon einige alphabetisch sortiete Elemente enthält. Nehmen wir weiterhin an, dass sich folgende Elemente in der Liste befinden:
Code:
'a' <-> 'c' <-> 'f' <-> 'r' <-> 'a'
(Das letze Element ist wieder das Anfangselement.)
Als Beispiel sei mal gesagt, dass wir das Zeichen 'd' einfügen wollen. Also fangen wir am Anfang der Liste an und vergleichen:
a kommt vor d, also ermitteln wir über die Komponente .nachstes das nächste Element in der Liste. Diese wird dann wieder verglichen, und c kommt ja vor d, also gehen wir wieder ein Element weiter. Nun sind wir bei f und merken, dass f nach d kommt, also sind wir eigentlich schon zu weit. Also (und jetzt kommt der komplizierte Teil) müssen wir ein neues Listenelement anlegen und dieses vor f einfügen, indem wir die Zeiger von f und von c entsprechend abändern, sodass der Zeiger .naechstes von c auf das neue Listenelement zeigt und der Zeiger .vorheriges von f ebenfalls auf das neue Listenelement. Jetzt müssen noch die Zeiger .vorheriges bzw. .naechstes von d so geändert werden, dass sie auf die Elemente c bzw. f zeigen.
Fertig.

Zitat von daswurm:
ich möchte auch wirklich nicht, wenn das den schein erwecken sollte, dass mir das komplette programm geschrieben wir, denn dies erachte ich als nicht sehr sinnvoll.
Sehr gut, dass du das von selbst einsiehst. Wenn man etwas selber schreibt, lernt man mehr, als wenn man nur den fertigen Code vorgestzt bekommt.

MfG
Binärbaum
There are exactly 10 kinds of people: those who understand binary, and those who don't.
---
"Software reift beim Kunden. Bei Hardware ist es anders: Hardware fault beim Kunden." - Rainer G. Spallek
  Mit Zitat antworten Zitat
Der_Unwissende

Registriert seit: 13. Dez 2003
Ort: Berlin
1.756 Beiträge
 
#7

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 18:57
Zitat von Binärbaum:
Code:
'a' <-> 'c' &lt;-&gt; 'f' &lt;-&gt; 'r' &lt;-&gt; 'a'
hm, dein letztes a ist aber alphabetisch etwas falsch eingefügt, oder?

@daswurm Wie gut hast du denn die Listen (egal wie die verkettet sind) überhaupt verstanden? Ist nämlich wichtig die gut zu kennen, auf der Idee basiert unter anderem auch ein Binärbaum

Ist echt wichtig, die zu verstehen. Mit dem Sinn hast du schon deswegen recht, weil es (bestimmt immer noch) eine der beliebten Klausur- und Testaufgaben ist. Aber natürlich ist es auch wichtig es einfach verstanden zu haben (und an sich gar nicht so schwer).
Solltest nur nie Angst haben nachzufragen, wenn du etwas nicht verstehst (hast du zum Glück nicht).

Gruß Der Unwissende
  Mit Zitat antworten Zitat
Benutzerbild von Binärbaum
Binärbaum

Registriert seit: 19. Jan 2005
Ort: Elstra
764 Beiträge
 
Delphi 7 Enterprise
 
#8

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 19:13
Zitat von Der_Unwissende:
Zitat von Binärbaum:
Code:
'a' <-> 'c' &lt;-&gt; 'f' &lt;-&gt; 'r' &lt;-&gt; 'a'
hm, dein letztes a ist aber alphabetisch etwas falsch eingefügt, oder?
Nein, das stimmt schon und ist so beabsichtigt. Das letzte 'a' soll nur verdeutlichen, dass die Liste dann wieder von vorn beginnt, weil der Zeiger .naechstes von r wieder auf das a am Anfag der Liste zeigt.
Alternativ könnte man es auch so machen, dass der entsprechende Zeiger im letzten Element nil ist (das würde wahrscheinlich auch die Programmierung der Funktionen/Prozeduren fürs Einfügen u.a. erleichtern).
There are exactly 10 kinds of people: those who understand binary, and those who don't.
---
"Software reift beim Kunden. Bei Hardware ist es anders: Hardware fault beim Kunden." - Rainer G. Spallek
  Mit Zitat antworten Zitat
Der_Unwissende

Registriert seit: 13. Dez 2003
Ort: Berlin
1.756 Beiträge
 
#9

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 19:25
Ok, sorry hab es dann nur falsch verstanden, wusste nicht dass du gleich eine zirkuläre verwenden wolltest. Denke aber auch dass es für einen Anfänger leichter wird, wenn du mit nil anfängst (wobei es ja nur ein anderer Vergleich ist).
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#10

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 20:33
Ich würde Listen/Bäume etc., also verkettete Strukturen immer mit einem 'Wurzelknoten' beginnen. Dann sollte der Rest ohne Probleme gehen. Ob man die zirkulär oder nicht implementiert ist dann eigentlich Wurscht, soweit ich mich erinnere (o.k. eine Abfrage fällt weg).

Delphi-Quellcode:
Procedure EinfuegenInListe (EinWert : string; EineListe : PListenElement);
Var
  Q : PListenElement;

Begin
  P := FindeEinfuegePosition (EineListe, EinWert); // P ist das größte Element, das kleiner als EinWert ist.
  New (Q);
  Q^.Next := P^.Next; // Der Nachfolger vom neuen Knoten Q ist der alte Nachfolger von P
  P^.Next := Q; // Der neue Nachfolger von P ist Q.
  Q^.Prev := P; // Der Vorgänger vom neuen Knoten ist P (den haben wir ja deswegen gesucht)
  If Q^.Next<>Nil Then // Wenn der neue Knoten überhaupt einen Nachfolger hat, dann
     Q^.Next^.Prev := Q; // ist Q der Vorgänger des Nachfolgers von Q (irgendwie logisch)
End;
Die 'leere Liste' wird einfach so initialisiert:
Delphi-Quellcode:
Function LeereListe : PListenElement;
Begin
  New(Result);
  Result^.Element := EinWertDerGarantiertKleinerAlsAlleJemalsEinzufuegendenElementeIst;
  Result^.Next := Nil;
  Result^.Prev := Nil;
End;
Wenn man die Liste zirkulär machen will (also dann zeigt das letzte Element nicht ins Leere, sondern wieder auf das vorderste Element, bzw. die Wurzel, dann sieht das so aus:

Delphi-Quellcode:
Procedure EinfuegenInListe (EinWert : string; EineListe : PListenElement);
Var
  Q : PListenElement;

Begin
  P := FindeEinfuegePosition (EineListe, EinWert); // P ist das größte Element, das kleiner als EinWert ist.
  New (Q);
  Q^.Next := P^.Next; // Der Nachfolger vom neuen Knoten Q ist der alte Nachfolger von P
  P^.Next := Q; // Der neue Nachfolger von P ist Q.
  Q^.Prev := P; // Der Vorgänger vom neuen Knoten ist P (den haben wir ja deswegen gesucht)
  Q^.Next^.Prev := Q; // Q ist der Vorgänger des Nachfolgers von Q (irgendwie logisch)
End;
Die 'leere Liste' wird einfach so initialisiert:
Delphi-Quellcode:
Function LeereListe : PListenElement;
Begin
  New(Result);
  Result^.Element := EinWertDerGarantiertKleinerAlsAlleJemalsEinzufuegendenElementeIst;
  Result^.Next := Result;
  Result^.Prev := Result;
End;
Hier noch die Funktion zum Finden der Position:
Delphi-Quellcode:
Function FindeEinfuegePosition (EineListe : PListenElement; EinWert : TListenDatenTyp) : PListeElement;
       External 'IrgendwasMussJaAufDeinemMistGewachsenSein.DLL';
Ach ja: Alles aus dem Gedächtnis, ungetestet und eventuell fehlerhaft...
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +2. Es ist jetzt 22:40 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf