Einfach verkettete Liste / Methode Liste aufsteigend sortieren
-
as1as schrieb:
Ich dachte ich brauche einen Hilfspointer um mir dann im Falle
wenn ich was vertauschen muss, den einen Wert speichern kann.Variablen deklariert man nicht, wenn man sie nicht braucht, bzw. eben dort, wo man sie braucht.
as1as schrieb:
Nun gehe ich in die while-Schleife
Die einmal bis zum Listenende läuft? Hast Du denn nicht schon herausgefunden, daß die Sortierschleife sooft laufen muss, bis die Sortierung abgeschlossen ist, also nichts mehr vertauscht werden musste?
also
do { for( Liste_einfach_verkettet current = this; current != nullptr; current = current->Next ) { // check was ... // vertausch ggf. was ... } } while( sortiercounter != 0 );
-
Ich habe den Code mal umgeschrieben. Geht das so?
Nun bin ich jedoch wieder bei meinem Anfangsproblem.
Das tauschen von p1 und p2.Liste_einfach_verkettet *tmp = Next; int sortiercounter =1; do { for( ; tmp != nullptr; tmp = tmp->Next ) { if (tmp->Element > tmp->Next->Element) {// vertausche } } sortiercounter--; } while( sortiercounter != 0 );
-
if (tmp->Element > tmp->Next->Element) std::swap(tmp->Element, tmp->Next->Element) ;
-
@manni: ich glaub fast, das hat sich der Aufgabensteller anders gedacht
-
Swordfish schrieb:
@manni: ich glaub fast, das hat sich der Aufgabensteller anders gedacht
Möglich
-
as1as schrieb:
int sortiercounter = 1; do { // ... } sortiercounter--; } while( sortiercounter != 0 );Die Logik check ich noch nicht.
-
Hab mich heute morgen nochmal drangesetzt aber komme einfach nicht auf ein Ergebniss. Richtig frustierend
Mein Sortieralgorithmus soll ja einfach nur durch die verkettete Liste gehen.
Beispiel 2 4 1 6 8
Man geht von links nach rechts. Ist das Linke Element größer als das Rechte wird getauscht. Also ist 2>4 nein, also weiter 4>1 ja, also tausch, und weiter in der Liste.
Man geht immer von Anfang bis zum Ende der Liste. Gab es nur einen einzigen Tausch oder mehr wiederholt man den Vorgang. Gab es in einem kompletten Durchlauf keinen einzigen Tausch mehr ist man fertig.Mein neuer Code sieht nun so aus
void Liste_einfach_verkettet::sortiere_liste_aufsteigend() { int sortiercounter=1; do { int sortiercounter = 1; Liste_einfach_verkettet *tmp = Next; Liste_einfach_verkettet *zwischenspeicher = 0; 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; //erhöhe Sortiercounter sortiercounter++; } tmp = tmp->Next; } sortiercounter--; } while (sortiercounter !=0); }Jedoch terminiert mein Programm bei der 2 4 1 6 8 Liste nicht
-
Wie viele sortiercounter hast du definiert?
-
Ich hatte erst nur einen in do. aber dann habe ich einne fehler bekommen in meiner while bedinugng vom do das sortiercounter nicht gefunden werden kann.
daher hab ichnoch einen davor gemacht. dann könnte ich quaso den in der do rausnehmen. hilft mir und meinem problem aber vermutlich nicht weiter.
lg
-
as1as schrieb:
hilft mir und meinem problem aber vermutlich nicht weiter.
Dann erklär mal, wie die äußere Schleife sonst jemals terminieren soll.
-
ich hatte mir das sogedacht das der counter ja am anfang 1 ist. wenn es was zu sortieren gibt geht er ja höher, 2, 3 ect. wenn es nichts mehr zu sortieren gibt, bleibt er ja auf 1 und wird dann um -- reduziert, ist also 0 und ich komme aus meiner to do schleife raus.
-
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.
-
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); }
-
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!
-
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 warumvoid 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); }
-
Zeig bitte mal kompletten Code.
-
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; } }
-
Sind denn die Einträge in deiner Liste getauscht?
Warum nicht?
-
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.
-
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 diemain().Wer gibt den mit
newangeforderten Speicher wieder frei?
