3. dynamische Listen (doppelt verkettet)

dynamische Listen (doppelt verkettet)

  • T

    Hallo,

    ich zerbereche mir nun schon mehrere Stunden den Kopf darüber, wie ich eine dynamische Liste invertieren kann...
    Die Suchfunktion brachte leider keine für meinen Wissensstand hilfreichen Erkenntnisse und deshalb poste ich hier mal meinen Quelltext:

    main.cpp

    #include <stdlib.h>  //für NULL
#include <stdio.h>   //für Ein- und Ausgabe
#include "definition.h"  //für Vereinbarungen

//Zeiger auf Beginn und Ende der Liste:
T_elem *p_list_start=NULL,*p_list_stop=NULL;

void add_first (unsigned k)
{
   if(!p_list_start)
   {
      p_list_start=p_list_stop=new T_elem;
      p_list_start->key=k;
      p_list_start->prev=p_list_start->next=NULL;
      return;
   }
   p_list_start->prev=new T_elem;
   p_list_start->prev->next=p_list_start;
   p_list_start=p_list_start->prev;
   p_list_start->key=k;
   p_list_start->prev=NULL;
}//add_first

void del_first ()
{
   if(!p_list_start) return;
   if(!p_list_start->next)
   {
      delete p_list_start;
      p_list_start=p_list_stop=NULL;
      return;
   }
   p_list_start=p_list_start->next;
   delete p_list_start->prev;
   p_list_start->prev=NULL;
}//del_first

void add_last (unsigned k)
{
   if(!p_list_start) { add_first(k); return; }
   p_list_stop->next=new T_elem;
   p_list_stop->next->prev=p_list_stop;
   p_list_stop=p_list_stop->next;
   p_list_stop->key=k;
   p_list_stop->next=NULL;
}//add_last

void del_last ()
{
   if(!p_list_start) return;
   if(!p_list_start->next)
   {
      delete p_list_start;
      p_list_start=p_list_stop=NULL;
      return;
   }
   p_list_stop=p_list_stop->prev;
   delete p_list_stop->next;
   p_list_stop->next=NULL;
}//del_last

void print_from(T_elem * p)
{
   if(!p) { printf(" !\n"); return; }
   printf(" %2u",p->key);
   print_from(p->next);
}//print_from

void print()
{   print_from(p_list_start); }

int main()
{
	char c;
	unsigned k,kk;

	while(1)
	{
		scanf("%c",&c);
		if(c=='e') break;

		switch(c)
		{
			case 'f': scanf("%u",&k);add_first(k);break;
			case 'l': scanf("%u",&k);add_last(k); break;
			case 'd': scanf("%u",&k);del_first(); break;
		}
	}
	print();
	rev(p_list_start,p_list_stop);
	print();

}

    definition.h

    struct T_elem
{
   unsigned key;
   T_elem * prev, * next;
};
//Prototypen
void add_first (unsigned);
void add_last (unsigned);
void del_first ();
void del_last ();
void print();
void rev(T_elem*,T_elem*);

    und schließlich meine Funktion, welche die Invertierung ermöglichen sollte:

    #include "definition.h"
#include <iostream>
extern T_elem * p_list_start, *p_list_stop;

void rev(T_elem *p,T_elem *q)
{
	unsigned int count=1;

	 do //Länge der Liste bestimmen
	{
	    p_list_start=p_list_start->next;
	    if(p_list_start->next->key != NULL)
	    {
	    	count++;
		 }
	}
	    	while  (p_list_start->next->key != NULL);

	 for (unsigned int i=0; i<=count; i++) // Elemente vertauschen
	 {
		 p_list_start->next->prev= NULL;
		 p_list_start->prev=p_list_stop->next;
		 p_list_stop->next=p_list_start->prev;
		 p_list_start->next=NULL;
	 }

    das Programm lässt sich zwar kompilieren und es ist auch möglich, die Liste zu erstellen, aber sobald ich mit "e" die Konstruktion der Liste abbreche, erhalte ich einen Fehler "Programm hat einen Fehler festgestellt und muss beendet werden"
    => ich gehe mal davon aus, dass die Invertierungsfunktion rev(p_list_start,p_list_stop) fehlerhaft ist.(und sehr wahrscheinlich auch sehr umständlich 😃 ) Leider kann ich den bzw. die Fehler nicht finden.

    Ich hoffe ihr könnt mir einige Denkanstöße geben.

    Vielen Dank & lg Dragon

    0
  • B

    ich gehe mal davon aus, dass die Invertierungsfunktion rev(p_list_start,p_list_stop) fehlerhaft ist

    Wenn du dein Progrmm beenden rufst du auch noch deine "print()" funktionen auf.. bevor sich einer die die mühe macht den fehler frü dich zu suchen, solltest du mal debuggen 😉

    stetz nen breakpoint zum ersten print und geh dann schritt für schritt druch und schau die deine zeiger der listenelement an, ob sie richtig verknüft wurden. WEnn du dann den fehler genauer spezifizieren kannst und nich weiter kommst, kommen wir isn spiel;)

    P.S.: Damit dir das debuggen nicht zu schwer fällt, würde ich deine print_from funktion nicht rekursiv machen mach ne schleife
    bspw. so:

    void printlist(){
//vorwärts
for(T_elem* p= p_list_start; p!= NULL; p= p->next){
printf(" %2u",p->key);
}
//rückwärts
for(T_elem* p= p_list_ende; p!= NULL; p= p->prev){
printf(" %2u",p->key);
}

}

    in der art. Die printf funktion gibt die list nun vorwärts und rückwärts aus, so kansnt überprüfen ob du sie richtg verkettet hast;) Vll. helfen dir die schleifen auch deine Rückwärtssuceh zu ermöglichen ^^

    P.P.S: Wieso hat deine funktion "rev" parameter, welche du nicht mal in der funktion verwendest?

    0
  • T

    Hallo und danke für deine Antwort...

    ich habe anscheinend nicht beachtet, dass es sich hierbei um eine doppelt verkettete Liste handelt und somit sind die Zeiger inkorrekt gesetzt...

    ich werde diese nochmals überarbeiten und anschließend melde ich mich hier erneut...

    lg Dragon

    /EDIT: nun ist die Funktion zumindest funktionsfähig, wenn auch nicht optimal:

    #include "vorgP3.6.h"
#include "stdlib.h"
#include <iostream>
using namespace std;
extern T_elem * p_list_start, *p_list_stop;

void rev(T_elem *p,T_elem *q)
{
	add_first(p_list_stop->key);
	del_last();

	T_elem* temp = p_list_start;   

	while (temp->next != NULL)   
	      {  
	           T_elem* neu = new T_elem; 
	           neu->next = temp->next; 
	           temp->next = neu; 
	           neu->prev = temp; 
	           neu->next->prev = neu; 
	           neu->key = p_list_stop->key; 
	           del_last(); 
	           temp = neu;  
	      }
}
    0
  • T

    gibt es eine elegantere Lösung für das Problem, als diee von mir angegebene?

    lg Dragon

    0
  • T

    Ich denke schon, daß es elegantere Lösungen gibt.
    Bei deiner Lösung fällt mir negativ auf, daß du jedesmal ein neues Element erzeugst und wieder eines löschst (new und del_last).

    Da du die reverse-Funktion ja inplace implementieren willst (also keine Kopie der Liste erzeugst), würde ich einfach die prev- und next-Zeiger der einzelnen Listen-Elemente vertauschen (und halt den Kopf und das Ende der Liste).

    0
  • W

    T-Dragonmaster XII schrieb:

    gibt es eine elegantere Lösung für das Problem, als diee von mir angegebene?

    Hallo Dragon,

    ja - die gibt es. Um die Reihenfolge der Elemente einer doppelt verketteten Liste umzukehren, braucht man doch nur bei jedem Element den prev- und next-Pointer auszutauschen. Das ganze sähe dann so aus:

    void rev()
{
    for( T_elem* p = p_list_start; p; p = p->prev )
    {
        std::swap( p->next, p->prev );
    }
    std::swap( p_list_start, p_list_stop );
}

    (std::swap braucht #include <algorithm>)

    Ich möchte Dir noch wärmstens empfehlen, aus Deinen Funktionen eine Klasse zu machen und die beiden globalen Pointer als Member reinzupacken.

    // --   eine Liste von unsigned
class List
{
public:
    List();
    ~List();

    void add_first (unsigned);
    void add_last (unsigned);
    void del_first ();
    void del_last ();
    void print();
    void rev();

private:
    T_elem* p_list_start;
    T_elem* p_list_stop;

    // --   Kopieren vorläufig stilllegen -> Regel der Drei
    List( const List& );
    List& operator=( const List& );
};

    das schafft Überblick. Weiter könnte man auch für so profane Strukturen wie T_elem einen Konstruktor vorsehen ...

    struct T_elem
{
    T_elem( unsigned k, T_elem* pr, T_elem* nx )
        : key( k ), prev( pr ), next( nx )
    {}
    unsigned key;
    T_elem * prev, * next;
};

    .. dann vereinfacht sich z.B. die Methode add_first zu

    void List::add_first (unsigned k)
{
   T_elem* neu = new T_elem( k, 0, p_list_start );
   if(!p_list_start)
   {
      p_list_start=p_list_stop = neu;
      return;
   }
   p_list_start->prev = neu;
   p_list_start = neu;
}

    Gruß
    Werner

    0
Anmelden zum Antworten