Element in der Mitte einer verketteten Liste einfügen (knifflig)

[Gentooizer]

Sorry, ich verstehe nicht, was du meinst?

[John Doe]

Wenn du zur Ablage deiner Daten ein STL-set oder eine STL-map verwendest
werden deine Daten beim Einfügen gleich sortiert. Wenn du anschliessend
durch den Container iterierst hast du eine "Liste" in geordneter Folge.

mfg JJ

[Gentooizer]

Sorry, ich weiß nicht was ein SLT-set ist, aber würde es trotzdem gerne mit dieser verketteten Listen schaffen. Ich verstehe einfach nicht, woran es liegt.

[John Doe]

Also doch zu Übungszwecken
Da dein Code ausserordentlich schlecht lesbar ist tu ich mir eine genauere
Durchsicht nicht an, sorry. :p Wenn das Fehlverhalten reproduzierbar ist
würd ichs mal mit dem Debugger versuchen.

PS.: Hast dich eigentlich schon mal mit OOP und Strukturierung beschäftigt.
Dadurch wird übrigens auch dier Fehlersucge vereinfacht.

mfg JJ

[Gentooizer]

Es ist eigentlich nur ein Logikfehler, auf den ich nicht komme.
Mit OO hab ich mich bisher nicht so wirklich anfreunden können, da ich zuerst mal etwas besser C/C++ verstehen will, bevor ich anfange OO zu programmieren.

P.S Dafür, dass das Forum die Formatierung so zerschießt, kann ich leider nichts.

[ness]

Also, nur mal so, wenn du dich für soweit hälst eine Liste implementieren zu wollen (das bezweifle ich nicht unbedingt), dann solltest du dich auch mal mit oop und strukturierung beschäftigen... (Ich hab das nur mal so überflogen, aber sehe ich das richtig, du willst eine Liste _ohne_ Klasse implementiern???"

[camper]

ich hab mir zum spass mal die mühe gemacht, dass zu formatieren, und dann wird eigentlcih auch schnell klar warum es nicht funktioniert:

#include <iostream>
#include <cstring>

using namespace std;

struct schueler
{
	int		katalognummer;
	char	vorname[20];
	char	nachname[20];
	schueler *next;
};

schueler *kopfzeiger = NULL;							// Globalen Kopfzeiger definieren, um den Kopf der verk. Liste
														// nicht zu verlieren, wenn Unterprogramme darauf zugreifen wollen.

void ausgeben()
{
	cout << "Schülerliste wird ausgegeben...\n";
	cout << "Katnr.\t\t Vorname\t Nachname\n";
	cout << "-----------------------------------------------------------------------\n";
	schueler *aktuell = kopfzeiger;
	while ( aktuell )
	{
		cout << aktuell->katalognummer << "\t\t" << aktuell->vorname << "\t\t" << aktuell->nachname << "\n";
		aktuell = aktuell->next;
	}
    cout << "\n";
}

bool checkkatnr(int katnbr)
{
	schueler *aktuell = kopfzeiger;
    while ( aktuell )
	{
		if ( aktuell->katalognummer == katnbr ) return true;
        aktuell = aktuell->next;
	}
	return false;
}

void hinzufuegen()										// In dieser Funktion werden die Elemente gleich so eingefügt,
{														// dass die Liste nach Katalognummern sortiert ist.
	char temp[20];
	int katnr;// aktuelle_katalognr;					// aktuelle_katalognr wird beim vergleichen benötigt, katnr zum Einlesen.
//	int kat_nr_von_nahesten_schueler;					// wird auch zum Vergleichen benötigt.
	schueler *neuer_schueler;

	cout << "Katalognummer: ";							// Katalognummer einlesen und prüfen,
	cin >> katnr;										// bevor überhaupt eine neue Instanz erzeugt wird.

	while ( checkkatnr( katnr ) )						// Check ob Katalognummer bereits exisitert.
	{
		cout << "Diese Katalognummer existiert bereits!\n";
		cout << "Katalognummer: ";
		cin >> katnr;
	}

	neuer_schueler = new schueler;						// Neue Instanz erzeugen.
	neuer_schueler->katalognummer = katnr;
	cout << "Vorname: ";
	cin >> temp;
	strcpy( neuer_schueler->vorname, temp );
	cout << "Nachname: ";
	cin >> temp;
	strcpy( neuer_schueler->nachname, temp );
	cout << "\n";
/*	schueler *aktuell = kopfzeiger;						// Jetzt den Schüler suchen, der der nächst-kleinere nach
														// der eingegebenen Katalognummer ist.
	schueler *nahester_schueler = kopfzeiger;			// Beide Zeiger zeigen zuerst mal auf den Anfang.
	if ( aktuell )										// Die nächste Schleife funktioniert erst,
	{													// wenn schon Elemente in der verk. Liste existieren.
		while ( aktuell )
		{
			aktuelle_katalognr = aktuell->katalognummer;
			kat_nr_von_nahesten_schueler = nahester_schueler->katalognummer;
			if ( aktuelle_katalognr < katnr && aktuelle_katalognr > kat_nr_von_nahesten_schueler )
			{
				// Falls der gerade durchlaufende Schüler eine niedrigere Katnr als die Eingabe, aber eine größere als der
				// näheste Schüler hat, wird der Zeiger des nähesten Schülers mehr in Richtung aktuelle Eingabe auf den aktuellen
				// Zeiger gerückt, da noch nicht der zum eingegebenen Katalognr-Wertes näheste Schüler gefunden wurde.
				nahester_schueler = aktuell;
			}
			aktuell = aktuell->next;
		}
		neuer_schueler->next = nahester_schueler->next;	// Next Zeiger d. neuen Elements auf den Schüler zeigen lassen,
														// auf den bisher der näheste Schüler gezeigt hat.
		nahester_schueler->next = neuer_schueler;		// Den nähesten Schüler jetzt auf den neuen Schüler zeigen lassen.
		kopfzeiger = nahester_schueler;					// Den Kopfzeiger jetzt auf den nähesten Schüler zeigen lassen.
	}
	else
	{
		neuer_schueler->next = kopfzeiger;				// Next Zeiger des neuen Elements auf den aktuellen Wert
														// des Kopfzeigers richten, der hier nur NULL sein kann.
		kopfzeiger = neuer_schueler;					// Jetzt ist der neue Schüler komplett in der Liste eingefügt...
	}*/
    if ( kopfzeiger )									// bereits Einträge vorhanden ?
	{
		if ( kopfzeiger->katalognummer > katnr )		// am Kopf der Liste einfügen ?
		{
			neuer_schueler->next = kopfzeiger;
			kopfzeiger = neuer_schueler;
		}
		else
		{
			schueler *prev = kopfzeiger;
			schueler *next = kopfzeiger->next;
			while ( next && next->katalognummer < katnr ) // durchgehen bis ende der liste oder erste grössere katnr gefunden
			{
				prev = next;
				next = next->next;
			}
			prev->next = neuer_schueler;
			neuer_schueler->next = next;
		}
	}
	else
	{
		neuer_schueler->next = NULL;
		kopfzeiger = neuer_schueler;
	}
}

int main()
{
	int x;

	do
	{
		cout << "Treffen sie ihre Wahl:" << "\n\n";
		cout << "Schüler hinzufügen (Taste 1)." << "\n";
		cout << "Schüler nach Katalognummer suchen (Taste 2)." << "\n";
		cout << "Schülerliste nach Katalognr sortieren und ausgeben (Taste 3)." << "\n";
		cout << "Programm beenden (Taste 0)" << "\n";
		cin >> x;

		switch ( x )
		{
			case 1:
				hinzufuegen();
				break;
			case 3:
				ausgeben();
				break;
			case 0:
				exit(1);
				break;
			default:
				cout << "Ungültige Eingabe " << "\n";
		}
	}
	while ( x );

	return 0;
}

das

if (aktuelle_katalognr < katnr && aktuelle_katalognr > kat_nr_von_nahesten_schueler)    {

ist in meinen augen einfach nur merkwürdig - was genau soll das bezwecken?
solange die aktuelle katalognr zu klein ist, wird nahester_schueler nicht aktualisiert - folglich gehen dann alle einträge die zwischendurch durchlaufen wurden verloren.

[Gentooizer]

Danke für die Hilfe. Ich werde mir das morgen in Ruhbe durchsehen. Heute bin ich nicht mehr fit genug dafür

[ness]

Wenn ich du wäre, würde ich den Fehler beheben und mir dann was zu Klassen anschauen und das ganze noch mal als Klasse bauen, haste gleich 'n tolles Übungsbeispiel...

[Gentooizer]

Also ich habe mir jetzt das ausgebesserte Programm angesehen, aber das funktioniert eigentlich noch weniger als mein Ursprüngliches. Wenn ich mehr als 2 Einträge mache, und mir dann die Schülerliste ausgeben lasse, ensteht plötzlich eine Endlosschleife. Immerhin bin ich jetzt schon dem Verlierengehen der Elemente auf die Spur gekommen. Es war einfach diese Zeile:

kopfzeiger = nahester_schueler;

Ich weiß jetzt auch nicht, warum ich den Kopfzeiger umgebogen habe. Jedenfalls sortiert er jetzt noch falsch, aber das werde ich auch sicher bald haben.