einfache verkettete Liste mit C++

[sammy2ooo]

Hallo Leute,

folgender Versuch einer LinkedList...

Node.h

#ifndef _NODE_H_
#define _NODE_H_
#include <iostream>

class Node {
	public:
		int data;
		Node* next;
		Node(void);
		Node(int);
};
#endif

Node.cpp

#include "Node.h"
Node::Node(void) {
	next = NULL;
}

Node::Node(int i_data) {
	data = i_data;
	next = NULL;
}

LinkedList.h

#ifndef _LINKEDLIST_H_
#define _LINKEDLIST_H_
#include "Node.h"

class LinkedList {
	private:
		Node start;
		int counter;
		
	public:
		LinkedList(void);
		void add(int);
		bool remove(int);
		int size(void);
};

#endif

LinkedList.cpp

#include "LinkedList.h"

LinkedList::LinkedList(void) {
	counter = 0;
}

void LinkedList::add(int data) {
	// anzahl element inkrementieren
	counter++;
	
	// neues Element erzeugen
	Node node(data);

	// Liste leer?
	if(start.next == NULL) {
		start.next = &node;
	}

	// ansonsten letztes Element suchen und anfuegen
	else {	
		// temp Node auf Anfang setzen
		Node act;
		act.next = start.next;

		// bis zum Ende der List durchiterieren
		while(act.next != NULL) {
			[B]act = &act.next;[/B]
		}
		
		// Node anfuegen
		act.next = &node;
	}
}

kann mir jemand sagen was hier bei act = &act.next; falsch ist und wie ich das lösen kann? Mir ist das mit dem iterieren einfach nicht klar...

 

[xbit]

Mal ne andere Frage. Warum nimmst Du nicht std::list? Die ist als verkettete Liste implementiert und bietet so ziemlich alle Sachen, die man so braucht.

Achso, wenn Du Dir das letzte Element merkst, ist das Einfuegen einfacher und vor allem schneller.

Und Dein Pointer bei act.next = &node ist beim Verlassen der Methode auch ungueltig, weil Dein Object node nicht mehr existiert.

 

[sammy2ooo]

Danke für deine Antwort. Es geht mir nicht um die praktische Anwendung einer LinkedList sondern mehr um das Verständnis. (zumindest um den Versuch!)
Okay das mit dem letzten Element merken macht Sinn und funktioniert auch wunderbar. Nur bekomme ich wieder das Problem mit dem Iterieren, wenn ich versuche ein bestimmtes Element zu löschen. Wie gehe ich dann vor?

 

[Tron]

Das hier riecht übel nach Java.
Node act; ist KEINE Referenz wie in Java. Das ist ein Objekt vom Typ Node. Folglich kannst du daran nicht eine Adresse zuweisen, um eauf ein anderes Objekt zu verweisen. Du brauchst einen Zeiger, ergo Node*.

Anbei ist _LINKEDLIST_H_ als Name keine gute Idee, da es ein reservierter Name ist (wie alle Wörter, die mit _ beginnen und worauf ein Großbuchstabe oder _ folgt).

 

[sammy2ooo]

also in der Art? Der beschwert sich der Compiler fürchterlich!

$ g++ -c LinkedList.cpp
LinkedList.cpp: In member function `void LinkedList:rint()':
LinkedList.cpp:28: error: cannot convert `Node**' to `Node*' in assignment
LinkedList.cpp:30: error: request for member `next' in `temp', which is of non-c
lass type `Node*'
LinkedList.cpp:31: error: request for member `data' in `temp', which is of non-c
lass type `Node*'
LinkedList.cpp:32: error: request for member `next' in `temp', which is of non-c
lass type `Node*'

void LinkedList::print(void) {
	if(counter != 0) {
		Node* temp;
		temp = &start.next;
	
		while(temp.next != end.next) {
			std::cout << temp.data << std::endl;
			temp = &temp.next;
		}
	}
	
	else std::cout << "List ist leer!" << std::endl;
}

 

[Tron]

Das sieht immernoch nach Java aus.
Objekt.Attribut, aber Zeiger->Attribut.
Leg dir ein Buch zum Thema C++ zu.

 

[nicolas]

Hallo Leute,

folgender Versuch einer LinkedList...

kann mir jemand sagen was hier bei act = &act.next; falsch ist und wie ich das lösen kann? Mir ist das mit dem iterieren einfach nicht klar...

Hallo sammy2000,

vorneweg bin auch nicht gerade der C++ Guru allerdings habe ich was gefunden, was dir eventuel weiterhelfen könnte.....

interesant dabei das programm hier wird einmal in java und dann in C++ realisiert die unterschiede sind nicht besonders gross....

schau es dir doch mal einfach an vielleicht hilft es Dir ein weing weiter

http://www.wachtler.de/informatik_2/node59.html

hoffe ich konnte Dir ein wenig helfen, denke der verweiss auf ein buch ohne anzugeben was für eins bringt nix ausser verwirrung...

salü nicolas

 

[nert]

So macht man das in C++? Ach nee, ich weiss schon warum ich bei C bleibe.

 

[M@tt]

also in der Art? Der beschwert sich der Compiler fürchterlich!

void LinkedList::print(void) {
	if(counter != 0) {
		Node* temp;
		//temp = &start.next;
		temp = start.next; // probier es so
	
		while(temp.next != end.next) {
			std::cout << temp.data << std::endl;
			temp = &temp.next;
		}
	}
	
	else std::cout << "List ist leer!" << std::endl;
}

Das Problem war, dass Du den Adressoperator noch mit im Statement hattest. temp ist ein Pointer, dem musst Du auch einen Pointer zuweisen. In Deinem Statement wolltest Du dem Pointer (durch den Adressoperator &) jedoch die Adresse auf den Pointer zuweisen. Da meckert der Compiler natürlich.

Alles klar?

Grüße


Mathias