Verkettete Liste

Student83

Hallo, ich schaffe es einfach nicht eine Funktion zu schreiben die ein beliebiges Element aus einer einfach verketteten Liste löscht. Mein Code sieht bis jetzt so aus:

struct TListe{
  int data;
  TListe *next;
};

bool DeleteNode(int Position, TListe *pKnoten)
{
  //Falls die Wurzel gelöscht werden soll
  if (Position==0)
  {
	TListe *pTmpKnoten = pKnoten->next; //Zeiger auf das nächste Element
	delete pKnoten; //Lösche aktuellen Knoten (Wurzel)
	pKnoten=pTmpKnoten; //Macht das "nächste" Element zur Wurzel
	return 1; //Gibt TRUE zurück bei Erfolg
  }

  int Zähler=0;

  //Falls ein mittleres Element gelöscht werden soll
  while (pKnoten!=NULL)
  {
	if (Zähler==(Position-1)) //Zu löschender Knoten gefunden
	{
          //Zeiger auf das nächste (zu löschende Element)
          TListe* pTmpKnoten = pKnoten->next;
          //Aktueller Knoten soll auf übernächstes Element verweisen
          pKnoten->next=pKnoten->next->next;
          //lösche den "nächsten" Knoten
          delete pTmpKnoten;
	  return 1; //Gibt TRUE zurück bei Erfolg
	}
	else //Kette wird durchlaufen
	  pKnoten=pKnoten->next;

	Zähler++;
  }

  cout<<"ERROR: Knoten existiert nicht!\n\n";
  return 0;
}

int main()
{
  int Position;
  TListe *pWurzel = new TListe;
  CreateList(pWurzel);
  ...
  DeleteNode(Position,pWurzel)
  ...
  DeleteList(pWurzel);
  return 0;
}

Das Problem ist, dass die Funktion "DeleteNode" so wie sie dort steht nicht funktioniert. Genauer gesagt, geht im Falle von Position==0 der Teil wo die Wurzel gelöscht werden soll nicht.
Definiere ich die Funktion folgendermaßen mit einem zusätzlichen & geht das Löschen von mittleren Elementen nicht mehr, aber die Wurzel kann gelöscht werden:
bool DeleteNode(int Position, TList *&pNode)
Leider bekomme ich es nicht hin, dass beide Teile in der Funktion funktionieren.
Weis jemand Rat?

Mfg

bauerb

Hi!

Bitte das CPP-Tag verwenden. Sonst kriegen wir einen Augenschaden.

mfg bauerb

dust

delete pKnoten;
    pKnoten=pTmpKnoten;

?

XaTrIxX

komischer code:

Bei dir macht irgendwie alles nur so halb sinn.
Irgendwie ist das ganze auch ziemlich unübersichtlich.

der teil z.B:

if (Position==0)
  {
    TListe *pTmpKnoten = pKnoten->next;
    delete pKnoten;
    pKnoten=pTmpKnoten;   
    return 1;
  }

Fang mal bei dem Teil an, am besten kommentierst du jede Zeile damit was sie macht, wenn dir dann immer noch nichts einfällt, dann poste den kommentieren Teil mal...dann sehen wir auch sofort, wo es dir beim Verständnis mangelt.

DrPhil_Guth

Hm, ich weiß nicht was alle irgendwie immer mit ihren verketteten listen haben...
Ist das so ne art "prüfungsgebiet" oder wie?

Nimm doch einfach std::list für doppelt verkettete Listen, und std::slist für einfach verkettete. Dann nimmst du den dazugehörigen Iterator und suchst nach dem element.

#include <slist>

int main()
{
  int position;
  std::slist<int> liste_mit_daten;

  // ... liste fuellen

  std::slist<int>::iterator it;

  // element suchen
  for (int count < 0; count < position; i++, it++);

  // hier müsste man noch überpruefen, ob der Iterator auch gültig ist...

  // element löschen
  liste_mit_daten.erase(it);

  return 0;
}

dust

Im Informatikstudium is das mit das erste was man macht ... (in der Regel)

Student83

Also ich habe den Code jetzt nochmal kommentiert.
Das Programm soll einfach einen Knoten aus einer einfach verketteten Liste löschen. Hier muss man aber unterscheiden ob es sich um einen mittleren Knoten oder ob es sich um die Wurzel handelt.
Handelt es sich um einen mittleren Knoten, dann muss ich den Knoten vor dem zu löschenden Knoten identifizieren und einen Zeiger auf den nächsten (zu löschenden) Knoten erstellen. Außerdem muss der aktuelle Knoten auf den übernächsten Knoten zeigen. Jetzt kann ich den mittleren Knoten löschen.
Ist aber die Wurzel zu löschen brauche ich einen Zeiger auf das zweite Element der Liste und kann die Wurzel löschen und mache anschließend das zweite Element zum Ersten.
So, das wollte ich mit dem Code machen. Ob das mit der Wurzel so klappt weis ich nicht bzw. es geht wenn ich die Liste aus der main-Funktion als Adresse an DeleteNode übergebe.
Das Löschen eines mittleren Elements geht auch, aber nur wenn ich die Liste aus der main-Funktion als Zeiger übergebe. Also geht je nachdem ob ich die Funktion so

bool DeleteNode(int Position, TListe *&pKnoten)

oder so

bool DeleteNode(int Position, TListe *pKnoten)

definiere das eine aber nicht das andere.

Aber fangen wir vielleicht erst mal von ganz vorne an. Was das Programm können soll habe ich ja schon geschrieben.
Ich definiere mir also eine Liste

TListe *pWurzel = new TListe;

in der main-Funktion. Diese muss jetzt an die Funktion Deletenode übergeben werden. Da ich die Liste ja in der Funktion ändern möchte muss also nicht die Liste übergeben werden, sondern deren Adresse oder?
Hier fängt schon mein Problem an.
Macht es einen Unterschied ob ich die Funktion so definiere

bool DeleteNode(int Position, TListe **pKnoten)

und anschließend so aufrufe

DeleteNode(4,&pWurzel)

oder ob ich die Funktion so definiere

bool DeleteNode(int Position, TListe *&pKnoten)

und so aufrufe?

DeleteNode(4,pWurzel)

Ich denke in beiden Fällen wird die Adresse übergeben oder?

Im letzteren Fall funktioniert zumindest das Löschen der Wurzel einwandfrei. aber das Löschen eines mittleren Knotens funktioniert nicht mehr richtig. Was kann hier falsch sein?

drakon

Also ich würde mal sagen, dass du hier:

if (Zähler==(Position-1)) //Zu löschender Knoten gefunden

mit dem - 1 ein Problem hast.. Du gibst ja die Position "richtig" an, also du beginnst beim zählem mit 0 und nicht mit 1, also kannst du das ohne das - 1 machen.

Ausserdem würde ich für eine Liste eine Template Klasse deklarieren und dann kannst du das ganze auch viel einfach mit einem Zeiger auf das Element löschen.

Bei dem Code glaube ich müsste wenn das Ding durch ist das erste Element wieder auf sich selber zeigen oder?

{
    TListe *pTmpKnoten = pKnoten->next; //Speicheradresse des 2. Knotens wird gespeichert
    delete pKnoten; //Lösche aktuellen Knoten (Wurzel)
                    //pKnoten ist ein Zeiger,  
                    //also wird hier denke ich auch nur der Zeiger gelöscht 
    pKnoten=pTmpKnoten; 
                    //Macht das "nächste" Element zur Wurzel
                    //das kopiert die Speicheradresse des einen auf eine
                    //eigentlich freigegebene Ressource, kann das sein das das
                    //abschmiert?
    return 1; //Gibt TRUE zurück bei Erfolg
  }

Hab ewig nicht mehr in C++ programmiert, deswegen Entschuldigung wenn das Blödsinn sein sollte. Aber ich hoffe doch das die Anmerkungen soweit stimmen.
Ich versuch mich auch mal an ner Lösung:

{
    TListe *nodeToDelete = pKnoten; //Speicheradresse des 1. Knotens wird gespeichert
    pKnoten = pKnoten->next; //Zeiger wird vom ersten auf den zweiten Knoten gelegt
    delete *nodeToDelete; //erster Knoten wird gelöscht
    return 1; //Gibt TRUE zurück bei Erfolg
  }

Wie gesagt, seit langem mal wieder mein erster Versuch.

MfG

Student83

@Dragon
Das -1 ist schon richtig, denn man startet zwar bei 0, aber der zu löschende Knoten ist nicht der aktuelle, sondern der nächste.

@Jasc
Jupp, gebe dir recht, dein Code ist etwas schöner allerdings musste ich das

delete *nodeToDelete;

noch zu

delete nodeToDelete;

ändern, damit es funktioniert. Aber der Code von mir hat auch funktioniert. Es kann allerdings sein, dass dabei wirklich freie Ressourcen überschrieben wurden.

Es gibt jetzt allerdings immer noch das Problem, dass der Code, der ein mittleres Element löschen soll, nicht richtig funktioniert. Was könnte da falsch sein?

dust

Na, ...

//Falls ein mittleres Element gelöscht werden soll
  while (pKnoten!=NULL)
  {
    if (Zähler==(Position-1)) //Zu löschender Knoten gefunden
    {
          //Zeiger auf das nächste (zu löschende Element)
          TListe* pTmpKnoten = pKnoten->next;
          //Aktueller Knoten soll auf übernächstes Element verweisen
          pKnoten->next=pKnoten->next->next;
          //lösche den "nächsten" Knoten
          delete pTmpKnoten;
      return 1; //Gibt TRUE zurück bei Erfolg
    }
    else //Kette wird durchlaufen
      pKnoten=pKnoten->next;

    Zähler++;
  }

müsste eigentlich so aussehen:

//Falls ein mittleres Element gelöscht werden soll
  while (pKnoten!=NULL)
  {
    if (Zähler==(Position-1)) //Zu löschender Knoten gefunden
    {
          //Zeiger auf das nächste (zu löschende Element)
          TListe* pTmpKnoten = pKnoten->next;
          //Aktueller Knoten soll auf übernächstes Element verweisen
          pKnoten=pKnoten->next->next;
          //lösche den "nächsten" Knoten
          delete pTmpKnoten;
      return 1; //Gibt TRUE zurück bei Erfolg
    }
    else //Kette wird durchlaufen
      pKnoten=pKnoten->next;

    Zähler++;
  }

Student83

Juhuu, es geht endlich. War aber auch eine schwere Geburt.
Das Problem beim Löschen eines mittleren Elements war, dass alleine, wenn ich mit pNode->next die Liste durchgegangen bin, sämtliche Knoten die durchlaufen waren gelöscht/vergessen wurden. Warum auch immer. Ich habe dann einfach nochmal einen Hilfszeiger auf pNode erstellt und mit diesem geht es jetzt.

@dust
Danke für den Tipp. Der leuchtet mir auch ein, aber komischerweise stürzt das Programm ab, wenn ich die Änderung vornehme.

Hier nochmal die fertige Funktion die funktioniert, auch wenn ich es gerade nicht nachvollziehen kann:

bool DeleteNode(int Position, TListe *&pKnoten)
{
  //Falls die Wurzel gelöscht werden soll
  if (Position==0)
  {
    TListe *nodeToDelete = pKnoten;
    pKnoten = pKnoten->next;
    delete nodeToDelete;
    return 1;
  }

  int Zähler=0;

  TListe *pHilfsKnoten = pKnoten;
  while (pHilfsKnoten!=NULL)
  {
	if (Zähler==(Position-1))
	{
          TListe *pTmpKnoten = pHilsKnoten->next;
	  pHilfsKnoten->next=pHilfsKnoten->next->next;
          delete pTmpKnoten;
	  return 1;
	}
	else
	  pHilfsKnoten=pHilfsKnoten->next;

	Zähler++;
  }

  cout<<"ERROR: Knoten existiert nicht!\n\n";
  return 0;
}

Achso, nochmal danke für die Hilfe.

dust

Hier nochmal die fertige Funktion die funktioniert, auch wenn ich es gerade nicht nachvollziehen kann

xD ... was du auf jeden Fall noch einbauen musst sind ein paar if-Abfragen, denn zum jetztigen Zeitpunkt dereferenzirst du noch Zeiger, von denen du nicht weißt ob sie gültig sind. Beispielsweise bekommst du Probleme, wenn du das letzte Element (nennen wir es Element n) deiner Liste löschst, weil du dem (n-1)ten Element das (n+1)te Element als Nachfolgerknoten zuweist, das (n+1)te Element existiert aber gar nicht (schließlich war das letzte Element ja Element n).