[gelöst] Selbstgeschriebene Liste sortiert nicht

Tonikum

Hallo mal wieder!
Ich hantiere ein wenig mit Strukturen, die auf die jeweils nächste zeigen sollen.
Ich wollte eine Routine zum Einfügen schreiben, die mir gleich alles alphabetisch ordnet. Und wie immer bin ch offenbar zu doof dafür und für jede Hilfe dankbar:

struct kunde    {
    std::string name;
    std::string beruf;
    int alter;
    kunde * next;
};

.
.
.

void einfuegenrek(kunde ** temp, kunde ** vorher, kunde * neuerKunde) {      //Sortiert noch nicht!
    if(*temp == NULL)   {                          //ist an der Stelle kein Kunde: füge ein
        *temp = neuerKunde;
    }
    else if((*temp)->name < neuerKunde->name)   {  //ist der aktuelle Kunde lexikalisch kleiner: reiche neuen kunden weiter
        vorher = temp;
        einfuegenrek(&((*temp)->next), vorher, neuerKunde);
    }
    else    {                                 //ist er größer oder gleich: füge ein
        neuerKunde->next = (*vorher)->next;
        (*vorher)->next = neuerKunde;
    }
}

Hallo Tonikum,

die Funktion würde funktionieren, wenn der Wert für 'next' korrekt mit 0 vorbelegt wäre. Da Du keinen Konstruktor für kunde vorgesehen hast, vermute ich, dass es an der mangelhaften Initialisierung von kunde::next liegt.

Tipp: auch bei structs immer einen Konstruktor schreiben, ist dann auch später einfacher im Code.

Also hier:

struct kunde    {
    explicit kunde( const std::string& name = "nobody" /*, usw. */ )
        : name( name )
        , next( 0 ) // <- Wichtig next muss initial immer NULL sein
    {}
    std::string name;
    std::string beruf;
    int alter;
    kunde * next;
};

Also bei mir hat die funktion wie oben ohne Änderung funktioniert.

Tonikum

Hallo Werner,

danke für deine Zeit!
Die Struktur ist teil einer Klasse:

class kartei{
  private:
    kunde * ersterKunde;
    void einfuegen (kunde * neuerKunde);

  public:
    void neu();
    void ausgeben();
    void loeschen(std::string name);
    kartei(kunde * einKunde = NULL)            //Inline Konstruktor
    : ersterKunde(einKunde) {}
};

void kartei::neu()    {
    std::string data;
    std::cout << "Nachname+Vorname, Beruf, Alter: ";
    getline(std::cin, data);
    kunde * neuerKunde = new kunde;

    /* Kopiere Substring mit dem Nachnamen und Vornamen */
    int pos = 0, len = -1;
    while(data[++len] != ',');
    neuerKunde->name = data.substr(0, len);

    /* Kopiere Substring mit dem Vornamen */
    /*  pos = len + 2;                                   //pos ist jetzt der Anfang des Vornamens
    while(data[++len] != ',');
    neuerKunde->vorname = data.substr(pos, len - pos); */

    /* Kopiere Substring mit dem Beruf */
    pos = len + 2;
    while(data[++len] != ',');
    neuerKunde->beruf = data.substr(pos, len - pos);

    /* Lese Alter aus data */
    int alter = 0;
    ++len;
    while(data[++len]) alter = alter*10 + (data[len] - '0');
    neuerKunde->alter = alter;

    neuerKunde->next = NULL;
    einfuegen(neuerKunde);
    //std::cout << neuerKunde->vorname << neuerKunde->nachname << neuerKunde->beruf << neuerKunde->alter;
}

Da müsste next doch mit Null initialisiert werden, oder?
Aber ich versuch es gleich mal mit deinem Vorschlag, danke.

Tonikum

Hallo Testmensch!
Oh, dann liegt es vlt an meiner Ausgabefuntkion... aber das kann ich mi rauch nicht vorstellen, bei einem Durchlauf kann ich ja nicht viel falsch machen.

Werner_logoff schrieb:

Hallo Tonikum,

die Funktion würde funktionieren, wenn der Wert für 'next' korrekt mit 0 vorbelegt wäre.

.. nein, ich habe mich vertan.

Die Funktion einfuegenrek(..) funktioniert nicht zwingend, wenn Du in eine Liste in der sich bereits Elemente befinden, noch eines vor dem ersten Element einfügst.
Wie rufst Du einfuegenrek(..) auf?

Tonikum

Ich bin noch sehr unbeholfen, was Klassen angeht, deswegen habe ich einfuegenrek folgendermaßen verwendet:

void kartei::einfuegen(kunde * neuerKunde)  {                 //In der Funktion neu() verwendet
    einfuegenrek(&ersterKunde, &ersterKunde, neuerKunde);
}

void einfuegenrek(kunde ** temp, kunde ** vorher, kunde * neuerKunde) {      //Sortiert noch nicht!
    if(*temp == NULL)   {
        *temp = neuerKunde;
    }
    else if((*temp)->name < neuerKunde->name)   {
        vorher = temp;
        einfuegenrek(&((*temp)->next), vorher, neuerKunde);
    }
    else    {
        neuerKunde->next = (*vorher)->next;
        (*vorher)->next = neuerKunde;
    }
}

Kannst du mir einen Tipp geben, wie ichs eleganter mache?

Tonikum schrieb:

Kannst du mir einen Tipp geben, wie ichs eleganter mache?

so:

void einfuegenrek( kunde** cur, kunde* neuerKunde ) {
    for( ; *cur; cur = &((*cur)->next) )
    {
        if( !((*cur)->name < neuerKunde->name) )
            break;
    }
    neuerKunde->next = *cur;
    *cur = neuerKunde;
}

.. mehr dazu evt. bis morgen abend

Tonikum

Oh toll, das funktioniert und verstanden hab ich's auch.
Schade, dass ich auf sowas nie von selbst komme.
Vielen Dank für die Hilfe!

Werner Salomon

Hallo Tonikum,

Die Kunst des Programmierens besteht im Wesentlichen darin, die einzelnen Belange von einander zu trennen.
Wenn Du Dir die Methode kartei::neu ansiehst, so werden dort mehrere Dinge vermischt: die Auswahl von std::cin als Datenquelle, das Einlesen der struct kunde und das Einfügen in die Liste.

Das Einlesen solltest Du dort auslagern. Grundsätzlich kann man sich dafür immer eine eigene Funktion schreiben - einen sogenannten Streaming-Operator, der das Einlesen implementiert. Der Prototyp sähe so aus:

std::istream& operator<<( std::istream& in, kunde& k );

benutzt in der Methode kartei::neu wird dann daraus

void kartei::neu() {
    kunde* neuerKunde = new kunde;
    std::cout << "Nachname+Vorname, Beruf, Alter: ";
    if( std::cin >> *neuerKunde )
    {
        einfuegen(neuerKunde);
    }
    else
    {
        delete neuerKunde;
    }
}

Die Implementierung des Streaming-Operators für kunde

std::istream& operator>>( std::istream& in, kunde& k )
{
    using std::ws; // mit in >> ws werden die führenden Leerzeichen überlesen
    getline( in >> ws, k.name, ',' ); // Name lesen; wird durch ',' beendet
    getline( in >> ws, k.beruf, ',' ); // genauso den Beruf
    in >> k.alter; // das Alter ist ein int, also lese ein int!
    return in;
}

der Unterschied zu der String-Fimelei ist, dass direkt die Typen und Werte gelesen werden, die man auch später im Programm haben möchte - inklusive einer Fehlerbehandlung.

Noch ein Hinweis: wenn Du nicht selber unbedingt eine Liste codieren willst/musst so versuche es doch mal mit std::list. Ich finde es wesentlich sinnvoller, wenn Du mit den std-Containern umgehen kannst, statt eine eigenen (evt. leidlich funktionierende) Liste implementieren zu können. Mehr zum Thema Einlesen findest Du bei std::istream.

Gruß
Werner

unskilled

Die Kunst des Programmierens besteht im Wesentlichen darin, die einzelnen Belange von einander zu trennen.

und warum kritisierst du dann nicht die vermischung seiner liste und des nutzers an sich?
hat ein nutzer automatisch einen nachfolger? Oo

Werner Salomon

unskilled schrieb:

Die Kunst des Programmierens besteht im Wesentlichen darin, die einzelnen Belange von einander zu trennen.

und warum kritisierst du dann nicht die vermischung seiner liste und des nutzers an sich?
hat ein nutzer automatisch einen nachfolger? Oo

.. weil es an dem Code den Tonikum vorgestellt hat, einen ganzen Sack von Dingen zu verbessern gibt. Unter anderen auch die Trennung von Liste und Struktur (hier kunde).
Das was Tonikum tut, ist aber absolut typisch für Anfänger und ich will ihn auch nicht überfahren. Das würde ihn wohl eher abschrecken.
Abgesehen davon, macht das auch Arbeit, das alles zu erklären. Ich finde es kontra produktiv und auch negativ für die Forum Kultur, wenn Leute hier Code von Anfänger zerreißen, ohne zu erklären wie man es besser macht und warum das dann besser ist.

Im Übrigen habe ich es zumindest kommentiert:

Werner Salomon schrieb:

Noch ein Hinweis: wenn Du nicht selber unbedingt eine Liste codieren willst/musst so versuche es doch mal mit std::list. Ich finde es wesentlich sinnvoller, wenn Du mit den std-Containern umgehen kannst, statt eine eigenen (evt. leidlich funktionierende) Liste implementieren zu können.

Gruß
Werner

unskilled

Werner Salomon schrieb:

Abgesehen davon, macht das auch Arbeit, das alles zu erklären. Ich finde es kontra produktiv und auch negativ für die Forum Kultur, wenn Leute hier Code von Anfänger zerreißen, ohne zu erklären wie man es besser macht und warum das dann besser ist.

1. ok - das war auch mein problem
2. hab ich ja auch nicht gewollt - war halt nur überrascht davon, dass du es (scheinbar) nicht bemängelt hattest - den einen satz zu std::list hab ich zwar gelesen, aber der hat in meinen augen weniger den misch-masch kritisiert sondern nur eine alternative aufgezeigt.

bb

Tonikum

Ich hab Angst.