Einfach verkettete Liste / Methode Liste aufsteigend sortieren

[manni66]

Da du den äußeren sortiercounter auf 1 setzt und danach nie wieder veränderst, wird das wohl nichts.

Unabhängig davon wäre ein bool für den angestrebten Zweck völlig ausreichend.

[as1as]

manni66 schrieb:

Da du den äußeren sortiercounter auf 1 setzt und danach nie wieder veränderst, wird das wohl nichts.

Unabhängig davon wäre ein bool für den angestrebten Zweck völlig ausreichend.

Aber ich veränder den counter doch mit ++ und --. Und wenn kein tausch mehr stattfindet geht er auf 0. wo ist mein logicfehler?

Und wie soll das mit bool gehen.
da stehe cih doch wieder vor dem gleichen problem
ich erstelleam anfanng der funktion eine bool varible gab_es_tausch = false;
in der funktion wenn getauscht wird wird sie true. trotzdem bin ich in der dauerschleife gefangen.

void Liste_einfach_verkettet::sortiere_liste_aufsteigend()
    {
         bool gab_es_tausch;
        do
        {

        Liste_einfach_verkettet  *tmp = Next;
        Liste_einfach_verkettet *zwischenspeicher = 0;
        gab_es_tausch=false;

        while (tmp->Next != 0 )
        {

            if (tmp->Element > tmp->Next->Element)
            {
                //vertausche listeneinträge
                Liste_einfach_verkettet *z = tmp->Next;
                zwischenspeicher = tmp;
                tmp = z;
                tmp->Next = zwischenspeicher;

                gab_es_tausch=true;
            }
            tmp = tmp->Next;
        }

        } while (gab_es_tausch ==true);
    }

[manni66]

Welcher Counter wird gezählt ?
Welcher wird geprüft?
Wie oft wird hoch- und runtergezählt?
Wo sollte eine bool Variable auf false gesetzt werden?

Benutze einen Debugger!

[as1as]

Kannst du mir nicht einfach sagen wo in meinem Code der Fehler ist und warum?
Es ist eifnach so frustrierend
Ich setzte die boolvariable am anfang der do schleife auf false.
Ich gehe in die do schleife. meine bool variable wird auf false gesetzt.
nun geht er durch die liste und tauscht. wenn getauscht wird, wird die boolvariable auf true gesetzt. nun wird die whilebeding der do schleife kontrolliert . da getauscht wurde ist diese ja nun true. also while bedinugen erfüllt und start von neu. nun wird die variable wieder auf false gesetzt und es wird wieder durch die liste gegangen. wenn nicht getauscht wird, wird die variable von false ja nicht auf true gesetzt , die while bedinugnen ist nicht mehr erfüllt und es müsste terminieren. macht es aber nicht. und ich bin einfach so festgefahren das ich nicht herausfinde warum

void Liste_einfach_verkettet::sortiere_liste_aufsteigend()
    {
         bool gab_es_tausch;
        do
        {

        Liste_einfach_verkettet  *tmp = Next;
        Liste_einfach_verkettet *zwischenspeicher = 0;
        gab_es_tausch=false;

        while (tmp->Next != 0 )
        {

            if (tmp->Element > tmp->Next->Element)
            {
                //vertausche listeneinträge
                Liste_einfach_verkettet *z = tmp->Next;
                zwischenspeicher = tmp;
                tmp = z;
                tmp->Next = zwischenspeicher;

                gab_es_tausch=true;
            }
            tmp = tmp->Next;
        }

        } while (gab_es_tausch ==true);
    }

[Swordfish]

Zeig bitte mal kompletten Code.

[as1as]

Swordfish schrieb:

Zeig bitte mal kompletten Code.

Es geht ja um einfach verkettete Listen
Ich hänge jetzt schon seit 2 tagen an einer Methode, die eine Liste aufsteigend sortiert.

Meine Klassendefinition

// Klassendefinition: Verkettete Liste
#pragma once
#include <iostream>
using namespace std;

// Klasse einer Liste, welche einfach verkettet ist
class Liste_einfach_verkettet {
public:
    int Element;  // Daten der Liste
    Liste_einfach_verkettet *Next; // Referenz auf das nächste Listenelement
    Liste_einfach_verkettet() : Next(0), Element(0) {} // Konstruktor
    Liste_einfach_verkettet(int Data, Liste_einfach_verkettet *Node = 0) : Element(Data), Next(Node) {}

    //Methodenprototypen( Beschreibung und Implementierung in zugehöriger liste.cpp Datei
    void neues_element_einfuegen(int& NewElement);
    void erstelle_neue_liste();
    void print() const;
    bool element_loeschen(int& DelElement);
    void loesche_kleinstes_element(Liste_einfach_verkettet x);
    bool ist_liste_leer_fragezeichen();
    void sortiere_liste_aufsteigend();

};

Mein Hauptprogramm. Ist jetzt nur draufausgelegt zu testen ob meine Funktion
welche die Liste sortiert funktioniert

#include <iostream>
using namespace std;
#include "liste.h"

int main()
{

    Liste_einfach_verkettet a;

    a.erstelle_neue_liste();

    a.print();

    a.sortiere_liste_aufsteigend();

    a.print();

    system("PAUSE");
    return 0;

}

Die Funktion die aktuell eingesetzt werden

/ Ausgabe der verketteten Liste
void Liste_einfach_verkettet::print() const {
    // Alle Listenelemente ausgeben
    cout << "Alle Elemente in der Liste: ";

    Liste_einfach_verkettet *ptr = Next;

    if (Next == nullptr)
        cout << "Leere Liste." << endl;
    // wenn next nullpointer ist, ist liste leer

    else
    do
    {
    cout << ptr->Element;

    if (ptr->Next != nullptr) cout << " - ";
    else cout << " ";
    ptr = ptr->Next;
    } while (ptr != nullptr);

    cout  << endl;

    }

void Liste_einfach_verkettet::neues_element_einfuegen( int& NewElement) {

    /*
     ein neues Listenelement wird erstellt, dieses bekommt die gewünschte Zahl zugeteilt und ihr nächstes
     Listenelement ist logischerweise der nullptr, weil es ja das letze Element ist.
    */
    Liste_einfach_verkettet *neuer_eintrag = new Liste_einfach_verkettet();
    neuer_eintrag->Element = NewElement;
    neuer_eintrag->Next = nullptr;

    if (Next == 0)
    {
        Next = neuer_eintrag;
    }
    else // anker != 0, d.h. dies ist nicht der erste Eintrag der Liste
    {
        Liste_einfach_verkettet *ptr = Next;
        // pointer ptr = anker (ist verweis auf das erste element eier dynamischen datenstruktur)

        while (ptr->Next != nullptr) // laufe durch Liste bis zum letzten Eintrag
                                     // *ptr.next != nullptr

            ptr = ptr->Next;
        // pointer ptr =  *ptr.next

        ptr->Next = neuer_eintrag;
        // *ptr.next  = neuer_eintrag

    }
}

void Liste_einfach_verkettet::erstelle_neue_liste() {
    int NewElement;
    int terminierende_wunschzahl;

    cout << "Eingabe der Listen-Elemente. Terminierende Wunschzahl?: ";
    cin >> terminierende_wunschzahl;

    cout << "Geben Sie ganze Zahlen ein: ";
    cin >> NewElement;

    while (NewElement != terminierende_wunschzahl) {
    neues_element_einfuegen(NewElement);
    cout << "Geben Sie ganze Zahlen ein: ";
    cin >> NewElement;
    }
    }

[manni66]

Sind denn die Einträge in deiner Liste getauscht?
Warum nicht?

[as1as]

manni66 schrieb:

Sind denn die Einträge in deiner Liste getauscht?
Warum nicht?

Verstehe die Frage nicht ganz.
Listen kann man selbst eintragen.
Z.B man sucht sich die terminierende zahl 22.
gibt 2 4 1 6 8 ein dann 22. nun hat man die liste 2 4 1 6 8.
auf diese würde ich gerne eine funktion anwenden welche sie sortiert 1 2 4 6 8.
Dort komme ich jedoch nicht weiter.

[Swordfish]

Mal zum Rest, Kommentare im Code:

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

class Liste_einfach_verkettet {
public: // <<-- Daten deiner Klasse sind alle public? wieso nicht gleich ne struct?
	int Element;
	Liste_einfach_verkettet *Next;
	Liste_einfach_verkettet() : Next( 0 ), Element( 0 ) {}
	Liste_einfach_verkettet( int Data, Liste_einfach_verkettet *Node = 0 ) : Element( Data ), Next( Node ) {}

	void neues_element_einfuegen( int& NewElement );
	void erstelle_neue_liste();
	void print() const;
	bool element_loeschen( int& DelElement );
	void loesche_kleinstes_element( Liste_einfach_verkettet x );
	bool ist_liste_leer_fragezeichen();
	void sortiere_liste_aufsteigend();
};

void Liste_einfach_verkettet::print() const
{
	cout << "Alle Elemente in der Liste: ";

	Liste_einfach_verkettet *ptr = Next;

	if( Next == nullptr )
		cout << "Leere Liste." << endl;

	else
		do
		{
			cout << ptr->Element;

			if( ptr->Next != nullptr ) cout << " - ";
			else cout << " ";
			ptr = ptr->Next;
		} while( ptr != nullptr );

		cout << endl;
}

void Liste_einfach_verkettet::neues_element_einfuegen( int& /* <<-- eine Referenz auf einen int. echt jetzt!? O.O */ NewElement )
{
	Liste_einfach_verkettet *neuer_eintrag = new Liste_einfach_verkettet();
	neuer_eintrag->Element = NewElement;   // <<-- dafuer gibts doch den Konstruktor
	neuer_eintrag->Next = nullptr;         // <<-- Liste_einfach_verkettet( int Data, Liste_einfach_verkettet *Node = 0 ) !?

	if( Next == 0 )  // <<-- diesen Fall muss man nicht anders behandeln als alle anderen
	{
		Next = neuer_eintrag;
	}
	else
	{
		Liste_einfach_verkettet *ptr = Next;
		
		while( ptr->Next != nullptr )
			ptr = ptr->Next;

		ptr->Next = neuer_eintrag;
	}
}

void Liste_einfach_verkettet::erstelle_neue_liste() // <<-- Der Name luegt. *)
{
	int NewElement;                 // <<-- deklariere Variablen dort,
	int terminierende_wunschzahl;   // <<-- wo du sie brauchst!

	cout << "Eingabe der Listen-Elemente. Terminierende Wunschzahl?: ";
	cin >> terminierende_wunschzahl;

	cout << "Geben Sie ganze Zahlen ein: ";                 // <<--+
	cin >> NewElement;                                      //     |
	                                                        //     |
	while( NewElement != terminierende_wunschzahl ) {       //    schreit nach
		neues_element_einfuegen( NewElement );              //    do ... while()
		cout << "Geben Sie ganze Zahlen ein: ";             //     |
		cin >> NewElement;                                  //     |
	}                                                       // <<--+
}

void Liste_einfach_verkettet::sortiere_liste_aufsteigend()
{
	bool gab_es_tausch;
	do
	{
		Liste_einfach_verkettet  *tmp = Next;
		Liste_einfach_verkettet *zwischenspeicher = 0;
		gab_es_tausch = false;

		while( tmp->Next != 0 ) // <<-- bei einer leeren Liste fliegt dir das schon um die Ohren,
		{                       // <<-- weil du einen nullptr nicht dereferenzieren (*, ->) darfst.
			if( tmp->Element > tmp->Next->Element )
			{
				Liste_einfach_verkettet *z = tmp->Next;
				zwischenspeicher = tmp;
				tmp = z;
				tmp->Next = zwischenspeicher;

				gab_es_tausch = true;
			}
			tmp = tmp->Next;
		}

	} while( gab_es_tausch == true );
}

int main()
{
	Liste_einfach_verkettet a;
	a.erstelle_neue_liste();
	a.print();
	a.sortiere_liste_aufsteigend();
	a.print();
}

Der Code der Methode erstelle_neue_liste() tut nicht, was der Name suggeriert. Er fragt den Benutzer nach Zahlen und hängt diese an die Liste an.
Benutzerinteraktion ist auch nicht Aufgabe einer Methode einer Listenklasse. In deinem Fall sollte das wohl eher in die main() .

Wer gibt den mit new angeforderten Speicher wieder frei?

[Swordfish]

gefixt:

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

class Liste_einfach_verkettet {
private:
	int Element;
	Liste_einfach_verkettet * Next;

public:
	Liste_einfach_verkettet() : Element(), Next( nullptr ) {}
	Liste_einfach_verkettet( int Data, Liste_einfach_verkettet * Node = nullptr ) : Element( Data ), Next( Node ) {}

	bool neues_element_einfuegen( int NewElement );
	void print() const;
	void sortiere_liste_aufsteigend();
};

void Liste_einfach_verkettet::print() const
{
	if( Next == nullptr ) {
		cout << "Leere Liste.\n";
		return;
	}

	for( Liste_einfach_verkettet *ptr = Next; ptr; ptr = ptr->Next )
		cout << ptr->Element << ( ptr->Next ? " - " : " " );
	cout.put( '\n' );
}

bool Liste_einfach_verkettet::neues_element_einfuegen( int NewElement )
{
	Liste_einfach_verkettet * aktueller_knoten = this;

	while( aktueller_knoten->Next )
		aktueller_knoten = aktueller_knoten->Next;

	aktueller_knoten->Next = new Liste_einfach_verkettet( NewElement );

	return aktueller_knoten->Next != nullptr;
}

void Liste_einfach_verkettet::sortiere_liste_aufsteigend()
{
	bool sortiert;

	do {
		sortiert = true;

		/* ... */

	} while( !sortiert );
}

int main()
{
	cout << "Eingabe der Listenelemente. Terminierende Wunschzahl: ";
	int terminierende_wunschzahl;
	cin >> terminierende_wunschzahl;

	Liste_einfach_verkettet a;
	int NewElement;

	do {
		cout << "Geben Sie eine ganze Zahlen ein: ";
		cin >> NewElement;
	} while( NewElement != terminierende_wunschzahl && a.neues_element_einfuegen( NewElement ) );

	a.print();

	a.sortiere_liste_aufsteigend();
	a.print();
}

Jetzt wärs noch schön, wenn wir vernünftige Namen vergeben könnten. Ist was vorgeschrieben? Warum Deutsch und Englisch ( NewElement )? Könnt man sich auf Englisch einigen?

[Swordfish]

Swordfish schrieb:

Könnt man sich auf Englisch einigen?

Ok, ich einige mich jetzt auf Englisch:

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

class list {
private:
	int data;
	list * next;

public:
	list() : data(), next( nullptr ) {}
	list( int value ) : data( value ), next( nullptr ) {}

	bool append( int value );
	void print() const;
	void sort_ascending();
};

void list::print() const
{
	if( !next ) cout << "Leere Liste.";
	else for( list * current = next; current; current = current->next )
		cout << current->data << ( current->next ? " - " : " " );
	cout.put( '\n' );
}

bool list::append( int value )
{
	list * current = this;
	while( current->next )
		current = current->next;
	current->next = new list( value );

	return current->next != nullptr;
}

void list::sort_ascending()
{
	bool sorted;

	do {
		sorted = true;

		/* ... */

	} while( !sorted );
}

int main()
{
	cout << "Eingabe der Listen-Elemente. Terminierende Wunschzahl?: ";
	int terminator;
	cin >> terminator;

	list my_list;
	int new_value;

	do {
		cout << "Geben Sie eine ganze Zahlen ein: ";
		cin >> new_value;
	} while( new_value != terminator  && my_list.append( new_value ) );

	my_list.print();

	my_list.sort_ascending();
	my_list.print();
}

Liest sich doch gleich viel besser!?

[as1as]

Danke für deine Mühen. Aufgabenstellung ist übrigens folgende
Aufgabe 1
Implementieren Sie eine einfach verkettete Liste aufgrund einer dynamischen Datenstruktur zur Speicherung der Listenelemente mit folgenden Methoden:
(a) Neues Element einfügen,
(b) Beliebiges Element entnehmen und löschen,
(c) Methode, die immer nur das kleinste Element entnimmt und löscht,
(d) Überprüfmethode, ob ein Element in der Liste vorhanden ist,
(e) eine Methode, die eine Liste aufsteigend sortiert,
(f) eine Methode, die aus 2 verketteten unsortierten Listen eine aufsteigend sortierte Liste zurückgibt,
(g) Methode zur sequentiellen Ausgabe der gesamten Liste,
(h) ein Hauptprogramm, das sämtliche Methoden auf Korrektheit überprüft (überlegen Sie sich hierbei alle möglichen Sonderfälle zum Testen). Bitte erzeugen Sie eine Möglichkeit, dass wir neue Listen bei der Abnahme eingeben können.
Beispiele: Eingaben für Liste 1: 50 – 35 – 75 – 81
Absteigend sortierte Liste 1: 35 – 50 – 75 - 81
Eingaben für Liste 2: 4 – 76 – 55 – 32 – 3
Absteigend sortierte Liste 2: 3 – 4 - 32 – 55 - 76
Neue gemischte absteigend sortierte Liste: 3 – 4 - 32 – 35 – 50 – 55 – 75 – 76 – 81

Ich bin kein guter Programmieren, eher ein Anfänger. Ich gehe oft sehr wirr und durcheinander vor. Daher oftmals deutsch und englische namen.
Ich perönlch hab es lieber deutsch das ich mich wenn ich das programm später nocheinmal anschaue schneller verstehe.

Ich hänge nun schon seit 2 Tagen bei e) und komme nicht weiter.
Ich werde morgen mich nochmal an die Funktion setzen und hier posten.

Das wäre mein Ansatz. sortiert ist false.
Die Schleife Endet wenn sortiert false ist. Wenn sortiert wird geht sortiert auf true, also bleibt man in der schleife. wenn nicht sortiert wird hat sortiert ja den anfangswert false und man kommt aus der schleife.
aber ob mein ansatz mit dem tasuchen der pointer, also der listenelemente korrekt ist?

void Liste_einfach_verkettet::sortiere_liste_aufsteigend()
{
    bool sortiert;

    do {
        sortiert = false;

        /* ... */
        Liste_einfach_verkettet  *tmp = Next;
        Liste_einfach_verkettet *zwischenspeicher = 0;

        while( tmp->Next != 0 ) //leere liste wird benutzerseits nicht genutzt
        {                       
            if( tmp->Element > tmp->Next->Element )
            {
                Liste_einfach_verkettet *z = tmp->Next;
                zwischenspeicher = tmp;
                tmp = z;
                tmp->Next = zwischenspeicher;

                sortiert = true;
            }
            tmp = tmp->Next;
        }

    } while( sortiert );
}

[Swordfish]

Swordfish schrieb:

Mal zum Rest, Kommentare im Code:

// ...
		while( tmp->Next != 0 ) // <<-- bei einer leeren Liste fliegt dir das schon um die Ohren,
		{                       // <<-- weil du einen nullptr nicht dereferenzieren (*, ->) darfst.
// ...

as1as schrieb:

// ...

        Liste_einfach_verkettet  *tmp = Next;

        // ...

        while( tmp->Next != 0 ) //leere liste wird benutzerseits nicht genutzt
        {                       
// ...

lol? Richtigmachen statt sinnfreie Kommentare hinschreiben?

// ...

        Liste_einfach_verkettet  *tmp = this;

        // ...

        while( tmp->Next )
        {                       
// ...

Aber zum Sortieren brauchst du sowieso den Anker und nicht nur den ersten, sondern zwei nachfolgende Knoten.

// ...

        Liste_einfach_verkettet  *tmp = this;

        // ...

        while( tmp->Next && tmp->Next->Next ) // rechte Seite vom && erlaubt selbst wenn tmp->Next == nullptr wegen short-circuit evaluation.
        {
            if( tmp->Next->Element > tmp->Next->Next->Element ) {

// ...

[as1as]

Funktionert leider auch nicht

void Liste_einfach_verkettet::sortiere_liste_aufsteigend()
	{

		bool gab_es_tausch;

		do	
		{

		Liste_einfach_verkettet *tmp = this;
		Liste_einfach_verkettet *tmp_next = tmp->Next;
		Liste_einfach_verkettet *tmp_next_next = tmp_next->Next;

		gab_es_tausch = false;

		if (tmp_next ==0 )
		{
			cout<<"Kein Sortiervorgang möglich."<<endl;

		}
		else
		{
			while (tmp->Next !=0 )
		{

			if (tmp_next->Element > tmp_next_next->Element)
			{
				//vertausche listeneinträge
				Liste_einfach_verkettet *z = tmp_next_next;
				tmp_next_next = tmp_next;
				tmp_next = z;

				gab_es_tausch = true;

			}
			tmp = tmp->Next;
		}
		}

		} while (gab_es_tausch);
	}

[manni66]

Vergleiche die Adressen in tmp_next und tmp->Next bzw. tmp_next_next und tmp->Nexz->Next nach dem Tausch.

[as1as]

Hab es jetzt mittels Haltepunkte setzen und Wertevergleichen hinbekommen.
Ich hatte die Verkettung bzw. die Neuverkettung nach dem Tausch nicht korrekt.
Danke für die Hilfe
lg