LinkedList mit Node-Objekten

[mathon]

Hi,

Ich arbeite derzeit an der Entwicklung einer LinkedList, dafür verwende ich eine vordefinierte Node-Klasse die ein LinkedList Toolkit zur Verfügung stellt um die LinkedList entsprechend manipulieren zu können. (http://www.cs.colorado.edu/~main/chapter5/node1.h).
Ich entwickle jetzt gerade eine Sequence-Klasse die eine Sequence von Zahlen in einer LinkedList speichern soll.

Mein header file der sequence Klasse bzw. deren methoden und variablen sieht so aus:

public:
        // TYPEDEFS and MEMBER CONSTANTS
        typedef double value_type;
        typedef std::size_t size_type;
        // CONSTRUCTORS and DESTRUCTOR
        sequence( );
        sequence(const sequence& source);
        ~sequence( );
        // MODIFICATION MEMBER FUNCTIONS
        void start( );
        void advance( );
        void insert(const value_type& entry);
        void attach(const value_type& entry);
        void operator =(const sequence& source);
        void remove_current( );
        // CONSTANT MEMBER FUNCTIONS
        size_type size( ) const { return many_nodes; }
        bool is_item( ) const { return (cursor != NULL); }
        value_type current( ) const;
    private:
    node *head_ptr;
    node *tail_ptr;
    node *cursor;
    node *precursor;
    size_type many_nodes;

Ich habe bereits die zwei Konstruktoren, den Destructor und die advance und start-Methode implementiert:

sequence::sequence()
{
    head_ptr = NULL;
    tail_ptr = NULL;
    many_nodes = 0;
}

sequence::sequence(const sequence& source)
{
    node *tail_ptr;
    list_copy(source.head_ptr, head_ptr, tail_ptr);
    many_nodes = source.many_nodes;
}

sequence::~sequence()
{
    list_clear(head_ptr);
    many_nodes = 0;
}

void sequence::start()
{
    cursor = head_ptr;
}

void sequence::advance()
{
    cursor = cursor->link();
}

Ich hoffe, die stimmen so.
Leider habe ich jetzt ein Problem bei der insert-Funktion. Entsprechend der Spezifikation sollte die insert-Funktion einen neuen Knoten vor dem Node-Objekt einfügen auf die der cursor pointer zeigt. Daher muss ich den precursor-pointer verwenden und dieser muss dann auf den Knoten vor dem, auf den der cursor-pointer zeigt, zeigen lassen. Leider ist mir nicht ganz klar, wie ich diese Position herausfinden kann...:((

Weiß vielleicht hier jemand, wie ich diese insert-Methode am effizientesten definieren kann..?:-/

matti

[Werner Salomon]

mathon schrieb:

Leider habe ich jetzt ein Problem bei der insert-Funktion. Entsprechend der Spezifikation sollte die insert-Funktion einen neuen Knoten vor dem Node-Objekt einfügen auf die der cursor pointer zeigt. Daher muss ich den precursor-pointer verwenden und dieser muss dann auf den Knoten vor dem, auf den der cursor-pointer zeigt, zeigen lassen. Leider ist mir nicht ganz klar, wie ich diese Position herausfinden kann...:((

Hallo Matti,

bist Du immer noch nicht fertig mit der Liste ...

Zu Deiner Frage: führe den Member 'precursor' in der advance-Methode mit. Also

void sequence::advance()
{
    precursor = cursor;
    cursor = cursor->link();
}

in der insert-Methode musst Du dann den Fall unterscheiden, ob cursor noch auf 'head_ptr' zeigt - dann list_head_insert() benutzen -, oder eben nicht - dann nimmst Du list_insert() und den 'precursor'. Alles klar?

Gruß
Werner

[mathon]

hi,

ja leider bin noch immer dabei...:(

Habe jetzt mal insert und attach implementiert, soweit funktionieren sie auch nur leider gibt es beim testen noch immer fehler:

void sequence::insert(const value_type& entry)
{
	if(precursor == NULL)
	{
		list_head_insert(head_ptr, entry);
		cursor = head_ptr;
		tail_ptr = head_ptr;
	}
	else
	{
		list_insert(precursor, entry);
		cursor = precursor->link();
	}

    ++many_nodes;
} 

void sequence::attach(const value_type& entry)
{
	if(cursor == NULL)
	{
		list_head_insert(head_ptr, entry);
		cursor = head_ptr;
		tail_ptr = head_ptr;
	}
	else
	{
		list_insert(cursor, entry);
		cursor = cursor->link();
	}

    ++many_nodes;

}

Sieht vielleicht jemand was an den beiden funktionen noch falsch ist...? das insert und attachen funktioniert soweit nur gibt es anscheinend noch probleme mit den boundary-testen.

matti

[CStoll]

mathon schrieb:

Sieht vielleicht jemand was an den beiden funktionen noch falsch ist...? das insert und attachen funktioniert soweit nur gibt es anscheinend noch probleme mit den boundary-testen.

Wenn du noch dazu sagst, wo du diese boundary-tests durchführst und wie sich die Fehler äußern, können wir dir eventuell weiterhelfen

PS: du hast hoffentlich die advance()-Methode so geändert, wie Werner gesagt hat.

PPS: Und vermutlich mußt du in der attach()-Methode auch den precursor nachziehen.

[mathon]

hi,

ja habe ich alles gemacht, ich habe mir das ganze auch ganz genau aufgezeichnet und meine Methoden sehen jetzt so aus:

void sequence::start()
{
        cursor = head_ptr;
        precursor = 0;

}

void sequence::advance()
{
		if(is_item())
		{
			precursor = cursor;
			cursor = cursor->link(); 
		}

} 

void sequence::insert(const value_type& entry)
{
	if(!(is_item()))
		cursor = head_ptr;

	if(precursor == NULL)
	{
		list_head_insert(head_ptr, entry);
		cursor = head_ptr;
		tail_ptr = head_ptr;
	}
	else
	{
		list_insert(precursor, entry);
		cursor = precursor->link();
	}

    ++many_nodes;

	node* cursor1;
	node * precursor1;
	for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
	{
		precursor1 = cursor1;
	}
	tail_ptr = precursor1;
} 

void sequence::attach(const value_type& entry)
{
	if(cursor == NULL)
	{
		list_head_insert(head_ptr, entry);
		cursor = head_ptr;
		tail_ptr = head_ptr;
	}
	else
	{
		list_insert(cursor, entry);
		cursor = cursor->link();
		precursor = cursor;
	}

    ++many_nodes;

	node* cursor1;
	node* precursor1;
	for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
	{
		precursor1 = cursor1;
	}
	tail_ptr = precursor1;
}
void sequence::operator =(const sequence& source)
{
	if(this == &source)
		return;

	list_clear(head_ptr);
	many_nodes=0;
	list_copy(source.head_ptr, head_ptr, tail_ptr);
	many_nodes = source.many_nodes;
}

Ich habe habe bei insert und attach zum schluss immer eine for-schleife, damit der tail_ptr auch sicher immer auf den letzten Knoten zeigt. wenn ich es interaktiv teste funktioniert auch alles, aber wenn ich diesen test durchführe:

int test1( )
{
    sequence empty;                            // An empty sequence
    sequence test;                             // A sequence to add items to
    double items1[4] = { 5, 10, 20, 30 };  // These 4 items are put in a sequence
    double items2[4] = { 10, 15, 20, 30 }; // These are put in another sequence

    // Test that the empty sequence is really empty
    cout << "Starting with an empty sequence." << endl;
    if (!correct(empty, 0, 0, items1)) return 0;

    // Test the attach function to add something to an empty sequence
    cout << "I am now using attach to put 10 into an empty sequence." << endl;
    test.attach(10);
    if (!correct(test, 1, 0, items2)) return 0;

    // Test the insert function to add something to an empty sequence
    cout << "I am now using insert to put 10 into an empty sequence." << endl;
    test = empty;

    test.insert(10);

    if (!correct(test, 1, 0, items2)) return 0;

    // Test the insert function to add an item at the front of a sequence
    cout << "I am now using attach to put 10,20,30 in an empty sequence.\n";
    cout << "Then I move the cursor to the start and insert 5." << endl;
    test = empty;
    test.attach(10);
    test.attach(20);
    test.attach(30);
    test.start( );
    test.insert(5);
    if (!correct(test, 4, 0, items1)) return 0;

    // Test the insert function to add an item in the middle of a sequence
    cout << "I am now using attach to put 10,20,30 in an empty sequence.\n";
    cout << "Then I move the cursor to the start, advance once, ";
    cout << "and insert 15." << endl;
    test = empty;
    test.attach(10);
    test.attach(20);
    test.attach(30);
    test.start( );
    test.advance( );
    test.insert(15);
    if (!correct(test, 4, 1, items2)) return 0;

    // Test the attach function to add an item in the middle of a sequence
    cout << "I am now using attach to put 10,20,30 in an empty sequence.\n";
    cout << "Then I move the cursor to the start and attach 15 ";
    cout << "after the 10." << endl;
    test = empty;
    test.attach(10);
    test.attach(20);
    test.attach(30);
    test.start( );
    test.attach(15);
    if (!correct(test, 4, 1, items2)) return 0;

    // All tests have been passed
    cout << "All tests of this first function have been passed." << endl;
}

Doch bei diesem test.insert(10); in dem Abschnitt I am now using insert to put 10 in an empty sequence, stoppt das programm und es öffnet sich ein popup-fenster, dass das programm einen fehler festgestellt hat und beendet werden musste. ich habe auch versucht zu debuggen,aber ich komme einfach nicht auf den fehler drauf...?

lg matti

[Werner Salomon]

mathon schrieb:

... ich habe auch versucht zu debuggen,aber ich komme einfach nicht auf den fehler drauf...?

Hallo Matti,

DIE Fehler wäre richtig.
Bitte benutze ganz dringend Initialisierungslisten in Deinen Konstruktoren, dann vergisst man nicht so leicht die Member mit Default-Werten zu belegen. Wie auch hier schon erwähnt.

sequence::sequence()
    : head_ptr( 0 )
    , tail_ptr( 0 )
    , cursor( 0 )
    , precursor( 0 )
    , many_nodes( 0 )
{
}

sequence::sequence( const sequence& source )  
    : head_ptr( 0 )
    , tail_ptr( 0 )
    , cursor( 0 )
    , precursor( 0 )
    , many_nodes( 0 )
{
    //node *tail_ptr; achte darauf keine lokalen Variblen mit gleichen Namen wie Member anzulegen!
    list_copy(source.head_ptr, head_ptr, tail_ptr);
    many_nodes = source.many_nodes;
    start(); // 'cursor' auf begin setzen
}

Du hast vergessen den 'cursor' zu initialisieren, deshalb geht insert immer schief, wenn vorher kein start() aufgerufen wurde.

Bei der insert-Methode sind drei Fälle zu unterscheiden.
1.) der Cursor zeigt auf 'end' (auch bei Liste ist leer)
2.) der Cursor zeigt auf den Anfang, dann ist precursor == 0
3.) der Cursor zeigt irgendwo hin und precursor hat einen gültigen Wert

am Ende der Methode sollte der Cursor auf das zuletzt eingefügte Element zeigen. So ist es jedenfalls im C++-Standard. Das bedeutet auch, dass precursor in insert in keinem Fall verändert wird.

Bei der attach-Methode sind es nur zwei Fälle
1.) Die Liste ist leer
2.) sie ist nicht leer
Hier wird der Cursor und auch precursor gar nicht verändert, es wird lediglich ein Element am Ende angehängt.
Bei attach und insert kannst Du Dir die Schleife mit dem precursor sparen. Er sollte nach Aufruf jeder Funktion immer einen korrekten Wert haben.

Im Zuweisungsopertor hast Du vergessen, den Cursor umzusetzen. Am besten Du rufst dort start() auf.

Gruß
Werner