Einfach verkettete Listen

ShadowEater

Hi Leute ,

ich hab hier nen kleinen Code geschrieben um verkettete Listen zu lernen.
Natürlich erst mal einfach verkettete später dann doppelt verkettete.
Hier der Code:

#include <iostream>
using namespace std;

struct Listenknoten
{	
	int data;
	static int counter;
	Listenknoten *next;
};

static int counter = 0;
Listenknoten *head = NULL;
Listenknoten *neu = NULL;

void main()
{
	int inhalt = 0;
	int i = 0;

	for (i = 0; i < 10; i++)
	{
		Listenknoten *neu = new Listenknoten;

                neu->next = head;
		head = neu;
	 	neu->data = inhalt + 1;
		counter++;
		inhalt++;
	}

// **************************** Erstes Element eingefuegen ***********************************
		Listenknoten *neu = new Listenknoten;	

                neu->next = head;
		head = neu;										neu->data = inhalt + 200;
		counter++;

 		cout << head->data << endl << endl << endl;

}

Ich hab per Forschleife ne Liste mit 10 Elementen erstellt und versuche dann ein neues erstes Element einzufügen.
Wenn ich dann die Ausgabe mache

cout << head->data << endl << endl << endl;

wird das erste (das neu eingefügte) Element ausgegeben 210.

Mit head->next kann ich mich über die Nachfolger durchhangeln bis zum Ende der Liste.

ABER 1. müsste dann nicht diese Ausgabe

cout << head->next->data << endl << endl << endl;

dazu führen dass die Zahl 1 ausgegeben wird und nicht die Zahl 10.

2. wie füge ich z.b.: 3 Elemente zwischen das beispielsweise 5. und 6. Element der Liste ein.

3. wie lasse ich das z.b.:4. 6. und 9. Element ausgeben?

Tut mir leid wenn sich die Fragerei etwas dämlich anhört aber ich verknot mir schon seit Stunden das Gehirn. Ich weiss auch dass in c++ statt Structs die Klassen die erste Wahl sind aber ich wollts erst in C verstanden haben.

Vielen Dank schon mal vorab

ShadowEater

David_pb

2. Indem du eine Methode Insert schreibst und ihr den gewünschten Knoten übergibts

3. Da deine verlinkte Liste nicht indiziert wird musst du beim ersten Element anfangen und die gewünschte Anzahl von Elementen, in einer Schleife, durchlaufen.

grüße

ShadowEater

Aha.

ESS_CB

du fügst das Item nicht am Ende sondern am Anfang ein, deine Liste sieht also so aus:

210 10 9 8 7 6 5 4 3 2 1

und da ist nunmal head->next gleich 10

items einfügen ist einfach

Listenknoten* links,*rechts,* neu = new Listenknoten;
links = head;
rechts = head->next;

// neu setzen
...

links->next = neu;
neu->next = rechts;

ShadowEater

D*A*N*K*E* ESS_CB,

das hat mich schonmal nen Schritt weitergebracht.
Bei Deinem Code, wo kann ich sagen ab wo das Element eingefügt wird?

Thx.
ShadowEater

David_pb

Hat er doch bereits gesagt.
Wenn du irgendwo in die Liste ein Element einfügen willst nimmst du nicht head sondern einen anderen Knoten...

void InsertAfter( Listenknoten *node )
{
  Listenknoten *newnode = new Listenknoten;
  newnode->next = node ->next;
  node ->next = newnode;
}

grüße

ShadowEater

Sry,

tut mir echt leid aber ich steh echt aufm Schlauch und seh den Wald vor lauter Bäumen net .
Könntet ihr mir an Hand meines Bsp. von ober das hier zeigen:

3 Elemente zwischen das beispielsweise 5. und 6. Element der Liste ein.
4. 6. und 9. Element ausgeben.

Ich will echt keinen source leechen oder andere meine Arbeit tun lassen aber ich raffs grad echt net.

Vielen Dank für eure Mühe schon mal vorab

ShadowEater

David_pb

Hi!

Dann hier ein schnelles Beispiel:

#include <iostream>

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

void InsertAfter( ListNode *node, int value )
{
	ListNode *newnode = new ListNode;
	newnode->data = value;
	newnode->next = node->next;
	node->next = newnode;
}

ListNode *GetByIndex( ListNode *root, int index )
{
	ListNode *p = root->next;

	while ( index-- )
	{
		if ( !p->next )
			return 0;

		p = p->next;
	}

	return p;
}

int main()
{
	int i;
	ListNode *root = new ListNode;
	root->next = 0;

	// Fuellen 9, 8, 7, ...
	for ( i = 0; i < 10; ++i )
	{
		InsertAfter( root, i );
	}

	// Suche node an "Index" 5
	ListNode *node = GetByIndex( root, 5 );

	if ( !node )
	{
		std::cout << "Nichts entsprechendes gefunden\n";
	}
	else
	{
		for ( i = 0; i < 3; ++i )
		{
			InsertAfter( node, ((i+1)*10) );
		}
	}

	// Nodes 4, 6 und 9 ausgeben
	int indice[] = { 4, 6, 9 };

	for ( i = 0; i < 3; ++i )
	{
		ListNode *nochmalnenode = GetByIndex( root, indice[ i ] );

		if ( nochmalnenode )
		{
			std::cout << "Node an Index " << indice[ i ] << " " << nochmalnenode->data << std::endl;
		}
	}

	// Ganze Liste ausgeben
	ListNode *p = root->next;

	for( ; p; p = p->next )
	{
		std::cout << p->data << std::endl;
	}

	std::cin.get();
	return 0;
}

Schöner wärs übrigens wenn du alles in eine Klasse packen würdest. Und freigeben des Speichers bitte nicht vergessen!

grüße

ShadowEater

Oh Mann,

danke David_pb Du bist echt gut!

Vielen Dank für Deine Mühe!
P.S.:

Könnten wir mal Chatten?

Bye
ShadowEater