Delete-Funktion in verketteter Liste

Tomjack

Hi...
ich hab ein kleines Speicherfreigabeproblem und zwar weiss ich nicht wie ich den gelöschten Knoten richtig entferne in der Delete-Funktion.

Meine ListenKlasse sieht so aus:

struct Node
	{
    string nick;
	 string datum;
	 string admin;
	 int invcounter;

    Node *next;
	};

class CListInt
  {
 public:
   CListInt(void);
   virtual ~CListInt();

   Node* Delete(string val);

   void InsertAfter(string val, int invite, string datum, string admin);

 private:

   Node *head, *curr, *tmp;
  };

und in der cpp hab ich folgendes:

CListInt::CListInt(void)
  {
   head=curr=NULL;
  }

CListInt::~CListInt()
  {
   while(head!=NULL)
     {
      Node *nextHead=head->next;
      delete head;
      head=nextHead;
     }
   curr=NULL;
  }

void CListInt::InsertAfter(string val, int invite, string datum, string admin)
  {
   if (curr!=NULL)
      if (head!=NULL) for(curr=head; curr->next!=NULL; curr=curr->next);

   Node *newNode=new Node;

   if (newNode==NULL)
     {
      cerr << "CListInt::InsertAfter: Nicht genuegend Speicher!" << endl;
      exit(-1);
     }

   newNode->nick=val;
	newNode->invcounter=invite;
	newNode->datum=datum;
	newNode->admin=admin;

   if (head==NULL)
     {
      newNode->next=NULL;
      head=newNode;
     }
   else
     {
      newNode->next=curr->next;
      curr->next=newNode;
     }
   curr=newNode;
  }

Node* CListInt::Delete(string val)
	{
	 curr=head;
	 if(curr->nick == val) 
		{
		 tmp = head;
		 if (tmp!=NULL)
			{
			 head = tmp->next;
			 delete (curr); // Ist das so richtig
			 curr = NULL;   // Das auch ?
			 return (tmp);
			}
		} 
	 else
		{
		 while(curr->next != NULL)
			{
			 if(curr->next->nick == val)
				{		
				 tmp = curr->next;
				 if (tmp != NULL) 
					{
					 curr->next = tmp->next;
					 // delete (?); Keine Ahnung
					 // ? = NULL; ebenso
					 return (tmp);
					}
				}	
			 curr = curr->next;	
			}
		}
	 return false;	
	}

Ich hab jetzt nur das was mir wichitg erscheint reingeschrieben und den Rest weggelassen.
Es funktioniert auch soweit perfekt bis auf das delete da komm ich irgendwie net mit warum er net will bzw. mir manchmal - meistens den falschen Knoten löscht.

Vielen DANK für die Hilfe !

flammenvogel

Ich verstehe dein Problem nicht ganz. Was wird nicht gelöscht? Du must mit delete alles löschen wenn du die Liste nicht mehr benutzt.

Tomjack

ne ich will net alles löschen ich will nur den Knoten löschen den ich nicht mehr brauche ! Das alles löschen übernimmt ja der Destruktor bei Programmende für mich !

flammenvogel

Es macht keinen Sinn jeden Knoten nach dem Durchgehen zu löschen, las am Ende den Destruktor einmal durchgehen. Sonst kannst du deine List ja auch nicht zweimal von vorne an durchlaufen.

leo aka qsch

deim delete musst du natuerlich mehrere faelle unterscheiden

erstes element wird geloescht
letztes element wird geloescht
oder eines mit einem vorgaenger und nachfolger

delete (curr); // Ist das so richtig
 curr = NULL;   // Das auch ?

definitiv nicht!
zu dem zeitpunkt bei dem du delete aufrufts, wird dem betriebsystem gesagt es darf diesen speicher wieder fuer etwas anderes verwenden,

also mit der anweisung

curr = NULL;

nach delete(curr)
schreibst du in speicher der dir nicht mehr gehoert!!!

Tomjack

Anscheinend verstehst du net was ich bezwecke oder hast dir den Code net angescaut oder miene erklärungen waren unzureichend oder ich bin stock dumm

Ich hab hier eine einfach verkettet Liste mit nextzeigern mit der Delete Funktion nehme ich EINEN Eintrag aus der Liste raus d.h. das kein einziger Zeiger in der Liste mehr auf dieses Element zeigt und wenn ich mehr lösche das diese Elemente dann net sinnlos im Speciher rumeiern, will ich diese auch gleich wieder löschen.

Tomjack

Dacht ich mir fast das das falsch ist leo aka qsch
Aber wie muss das richtig ausschauen ?

leo aka qsch

einfach vorher die liste verketten, so wie du es gemacht hast
und danach wenn alles richtig verkettet ist, delete aufrufen

// verkette hier deine liste

// danach rufe delete auf
delete (foo)

// fertig

eigentlich genauso wie du es gemacht hast, nur ohne dem zuweisen von NULL nach delete

ness

Naja, ich glaube erklärungen der Art art hatten wir schon oft, ich machs nochmal: sei

[daten|next]

Ein listenelement. Eine Liste sähe dann so aus:

[4|]
    [5|]
       [7|]
          [3|0]

WObei der Schrägstrich den Zeiger andeuten soll...
Wenn du jetzt was löshen willst, geht das in etwa so:

[4|]
    [5|]<--next merken
       [7|]
          [3|0]

[4|]
    [5|]
          [3|0]

[4|]
    [5|]<--Zeiger umbiegen
       ---[3|0]

Und den gemerkten Zeiger mit delete Löschen.
Wobei du aber wie von leo aka qsch angesprochen aufpassen musst obs der erste oder letzte Zeiger ist und in dem Fall halt gesondert reagieren musst...

Tomjack

Arghl jetzt glaub ich hab ichs !
Das war mir schon alles klar was ihr mir da erklärt habt das hab ich auch, soweit ich das sehe, so gemacht. Was mein Fehler war, dass ich das delete ausgeführt hab nachdem ich den curr->next zeiger überschrieben hab so kanns ja net gehen weil der dann garnimmer auf das Element ezigt das ich löschen will.

Ich habs jetzt so gelöst und hoffe das es richitg ist:

Node* CListInt::Delete(string val)
    { 
     curr=head; 
     if(curr->nick == val) 
        { 
         tmp = head;
			del = head; 
         if (tmp!=NULL) 
            { 
             head = tmp->next; 
             delete (del);
             return (tmp); 
            } 
        } 
     else 
        { 
         while(curr->next != NULL) 
            { 
             if(curr->next->nick == val) 
                {        
                 tmp = curr->next; 
					  del = curr->next;
                 if (tmp != NULL) 
                    { 
                     curr->next = tmp->next; 
                     delete (del);
                     return (tmp); 
                    } 
                }    
             curr = curr->next;    
            } 
        } 
     return false;    
    }

Sry aber manchmal hab ich schon krazze Aussetzer

flammenvogel

Haben wir alle manchmal

Für Fragen gibt es ja das Forum