Einfache verkettete Liste implementieren

Nemesys

Hallo zusammen!

Soll eine einfache verkettete Liste in C++ implementieren.
Leider stürzt mein Programm ab. Habe Testausgaben eingebaut und
festgestellt das das bei der Verkettung schon geschieht.

Die Aufgabe lautet:

Zwei Listenzeiger (Datentyp Element*) anlegen: L zeigt als Anker auf das 1. Listenelement (falls
vorhanden), cursor wird als Zeiger beim Durchlaufen der Liste verwendet.
• Vier Listenelemente x1, x2, x3, x4 anlegen. Als Schlüsselwerte (key) werden fortlaufend die
Werte 1 bis 4 zugewiesen. Als Informationen (info) werden fortlaufend die Werte 11 bis 44
zugewiesen.
• Elemente verketten: durch entsprechende Adreßzuweisungen an die Strukturelemente next soll
die Verkettung in Abbildung 3.1 hergestellt werden. Der next-Zeiger des letzten Element erhält
den Wert NULL.
• Das Element mit dem Schlüsselwert 3 suchen: der Zeiger cursor wird auf den Listenanfang
gesetzt und die Liste solange in einer while-Schleife durchlaufen bis entweder ein Listenelement
mit dem Schlüsselwert 3 gefunden wurde oder das Listenende erreicht wurde (Wert von next
ist NULL)
• Wenn das Element gefunden wurde soll die Elementadresse, der Schlüssel- und Informationswert
sowie die Adresse des nachfolgenden Elementes ausgeben werden.

Dies ist mein Ansatz:

#include <iostream>
#include <iomanip>
#include <stdlib.h>

using namespace std;

struct Element{long key; long info; struct Element *next;};

int main()
{
  int wert;

  Element *L;
  Element *cursor;

  Element x1,x2,x3,x4;

  x1.key=1;
  x1.info=11;
  x2.key=2;
  x2.info=22;
  x3.key=3;
  x3.info=33;
  x4.key=4;
  x4.info=44;

  // Verkettung:
  *x1.next=x2;
  *x2.next=x3;
  *x3.next=x4;
  x4.next=NULL;

  if(x1.key==NULL)
  L->info = NULL;

  else

  L->info = x1.info;

  cursor->info = x1.info;

  while ( (cursor->key!=3)  ||  (cursor->next!=NULL) );
  {
    wert = cursor->key;

    switch (wert)
    {
         case 1: cursor->key = x2.key;
                 cursor->next= x2.next;
         case 2: cursor->key = x3.key;
                 cursor->next= x3.next;
         case 3: cursor->key = x4.key;
                 cursor->next= x4.next;
    }

  }

cout << setw(12);
cout << "Listenelement gefunden:%c" << cursor->info << endl; // noch nicht richtig,Addresse auslesen!
cout << "key = %ll" << cursor->key << endl;
cout << "info = %ll" << cursor->info << endl;
cout << "next = %c" << cursor->info << endl << endl;// noch nicht richtig, nächste Addresse auslesen!

  return 0;
}

Freue mich auf eure Tipps und vielen dank schonmal.

mfg Nemesys

Skym0sh0

sorry kollege, das ist erstmals so gut wie gar kein c++(ausser dem cout) und zweitens ist "mein programm stürzt ab" keine aussagekräftige fehlermeldung...

zumal DU die aufgabe machen sollst und nicht wir...

CStoll

*x1.next=x2; 
  *x2.next=x3; 
  *x3.next=x4;

Das wird nicht so funktionieren: du willst nicht den (gar nicht initialisierten) Zeiger dereferenzieren und den dahinterliegenden Wert (der erstens Datenmüll ist und zweitens vermutlich nicht dir gehört) ändern. du willst den Zeiger selber umbiegen, so daß er auf das Nachfolger-Element verweist.
Richtig wäre

x1.next = &x2;// & bildet die Adresse des Objekts

die übrige Zeiger-Verarbeitung (optional auch dynamische Speicherverwaltung) solltest du dir auch noch einmal ansehen

Werner Salomon

Hallo Nemesys,

willkommen im C++-Forum.

Nemesys schrieb:

Soll eine einfache verkettete Liste in C++ implementieren.

das wäre in C++ immer eine Klasse. Die Implementierung einer doppelt verketteten Liste ist z.B. std::list.

Nemesys schrieb:

Die Aufgabe lautet:

Zwei Listenzeiger (Datentyp Element*) anlegen: L zeigt als Anker auf das 1. Listenelement (falls
vorhanden), cursor wird als Zeiger beim Durchlaufen der Liste verwendet.
• Vier Listenelemente x1, x2, x3, x4 anlegen. Als Schlüsselwerte (key) werden fortlaufend die
Werte 1 bis 4 zugewiesen. Als Informationen (info) werden fortlaufend die Werte 11 bis 44
zugewiesen.
..

Was haben Schlüsselwerte und Information mit einer Liste zu tun? Das wäre doch eher ein Thema für eine map (siehe std::map)

.. und verrätst Du uns noch in welchem Ausbildungsinstitut derartige Aufgaben gestellt werden?

Gruß
Werner

Nemesys

Guten morgen zusammen!

@ CStoll: Danke,

x1.next = &x2;// & bildet die Adresse des Objekts

funktioniert, hätte ich auch drauf kommen können.

@ Werner: Danke für die nette Begrüßung.Studiere Angewandte Informatik an einer
Fachhochschule (2.Sem) und habe dort im Fach Programmierung mit C++2
diese Aufgabe bekommen mit dem Thema "Verkettete Liste
implementieren".
Das struct Element war soweit vorgegeben.

Leider komme ich mit meinem Programm immernoch nicht weiter.

Habe auch noch 2 Warnings: Z34: Null used in arithmetic und Z50:cursor is used uninitialized in this function.

Die IF-Abfrage ist wohl nicht ganz richtig.
Kann den Fehler aber leider nicht identifizieren.

CStoll

Nemesys schrieb:

Habe auch noch 2 Warnings: Z34: Null used in arithmetic

Diese if-Abfrage ist sowieso unverständlich - und der Compiler macht dich darauf aufmerksam, daß du den NULL-Zeiger mit einer Zahl vergleichst

Z50:cursor is used uninitialized in this function.

Das besagt einfach, daß du vergessen hast, cursor mit einem Startwert zu belegen. Du solltest dort noch L = &x1; (damit du den Listen-Anfang hast) und cursor = L; (als Anfangswert der Schleife) ergänzen.

PS: Übrigens dienen solche Datenstrukturen wie verkettete Listen dazu, zur Laufzeit Daten zu ergänzen. Das macht normalerweise wenig Sinn, wenn man die Listenelemente als Variablen zur Verfügung hat

Werner Salomon

Hallo Nemesys,

noch zwei Tipps:
Schreibe für Element einen Konstruktor, der alle Member-Varibalen initialisiert.

struct Element
{
    Element( long key_, long info_, Element* next_ )
        : key( key_ ), info( info_ ), next( next_ )
    {}
    long key; long info; struct Element *next;
};

Das hat zwei Vorteile. Zum einen gewinnst Du Übersicht und zum anderen sorgt jetzt der Compiler dafür, dass Du keine Variable mehr zu initialisieren vergisst (siehe dazu auch Initialisierungsliste).
In der Anwendung kann das dann so aussehen:

// --   Liste aufstellen (von hinten nach vorn!)
    Element x4( 4, 44, NULL );
    Element x3( 3, 33, &x4 );
    Element x2( 2, 22, &x3 );
    Element x1( 1, 11, &x2 );

zum anderen solltest Du Variablen erst dann definieren, wenn Du sie benötigst und auch initialisieren kannst. Also das vorgestellte ..

int wert;

  Element *L;
  Element *cursor;
  // ...

macht man in C++ nicht.
Sondern

Element *L = &x1; // Listenanfang
    Element *cursor = L;

Gruß
Werner

Nemesys

Danke. Aufgabe inzwischen gelöst.

mfg