Sortierte Liste in C

Guten Tag zusammen,

ich habe hier eine kleine Übung doch ich verstehe nicht so ganz wie es gehen soll.
Also hier einmal der Übungstext:

Implementieren Sie in C folgende einfach verkettete sortierte Liste für double-Zahlen, in der die Zahlen absteigend sortiert sind:

Eine Datenstruktur für ein Listenelement
Eine Datenstruktur, sortList, in der neben den benötigten Zeigern auch die aktuelle Anzahl der Listenelemente gespeichert ist.
Ein Unterprogramm insert(), dem einen Zeiger auf sortList und ein Zahlenwert übergeben wird. Erstellt wird ein neues Listenelement und dieses wird mittels recInsert() eingefügt.
Ein Unterprogramm recInsert(), das zwei Zeiger auf Listenelemente übergeben bekommt und einen solchen Zeiger auch zurückgibt. Der erste Zeiger (z1), verweist in die bestehende Liste. Der zweite Zeiger (z2) zeigt auf das einzufügende Listenelement. recInsert() soll folgendermaßen arbeiten:
z1 == NULL -> Erg = z2
z1.wert < z2.wert -> z1 wird der Nachfolger von z2. Rückgabe: z2
z1.wert >= z2.wert -> rekursiver Aufruf mit dem Nachfolger von z1. Das Ergebnis dieses rekursiven Aufrufs wird als neuer Nachfolger von z1 gesetzt. Rückgabe: das geänderte z1.
Bis jetzt habe ich meine Header-Datei die sieht so aus:
C:
typedef struct listenElement {
    double wert;
    struct listenElement *next;
}node;

typedef struct sortList {
    node *anfang;
    int anzahl;
}list;

void insert(list *l, double x);
node *recInsert(node *l, node *x);
C:
#include "einfachverketteteliste.h"
#include <stdio.h>
#include <stdlib.h>

void insert(list *l, double x) {
    node *new = (node *) malloc(sizeof(node));
    if (new == NULL) {
        printf("Fehler nicht genug Speicherplatz!\n");
        return;
    }
    new->wert = x;
    recInsert(l->anfang, new);
}

node *recInsert(node *z1, node *z2) {
    if (z1 == NULL)
        return z2;
    if (z1->wert < z2->wert)
        return z2;
    else if (z1->wert >= z2->wert)
        return recInsert(z1->next, z2);

}
Vorab oben der Code ist quatsch!
Ich verstehe an dieser Aufgabe folgende 2 Dinge nicht:
Wie soll die Rekursion funktionieren :-( und
Wie soll der Knoten dann eingefügt werden?

Also es steht da ja wenn die bestehende Liste = NULL ist gebe ich den Zeiger (z2) des Listenelements zurück. Sollte z1.wer kleiner sein als z2.wert dann muss es rechts eingefügt werden da die Liste absteigend sortiert werden soll.
Nun der dritte Fall: Wenn der erste Wert z. B. größer ist als der nächste Wert der eingefügt werden soll also in der Liste stehe eine 8 und ich möchte nun eine 1 einfügen, dann steht dort rekusiver Aufruf von z1->next. Da die Liste aber doch absteigend Sortiert sein sollte, würde ich doch nur noch ein größeres Element bekommen?

Danach (sagen wir mal die Rekursion würde irgendwann laufen) verstehe ich auch nicht was ich mit diesem Rückgabewert anfangen soll? Super ich bekomme einen Knoten zurück. Ist das dann der Vorgänger des einzufügenden Knoten? So das man in der insert Prozedur dann nur noch die Pointer umhängen muss?


Danke im voraus :)

LG
 
Visualisieren, immer visualisieren :)

Code:
Liste: Z -> Y -> K
z2 = [wert: T, next: NULL]
z1 = Z

recInsert(z1, z2):

Z -> Y -> K
^
Z >= T, Nachfolger := recInsert(Y, z2)

Z -> Y -> K
     ^
     Y >= T, Nachfolger := recInsert(K, z2)

Z -> Y -> K
     ^
     Y >= T, Nachfolger := recInsert(K, z2)

Z -> Y -> K
          ^ K < T, K wird Nachfolger von z2, d. h. z2 = [wert: T, next: K], Rückgabe von z2

Jetzt Rekursion zurück:

Z -> Y -> K
     ^
     Y >= T, Nachfolger := recInsert(K, z2) = z2 (geändert)
             Nachfolger von Y wird also z2 = [wert: T, next: K],
             Rückgabe von Y

Z -> Y -> T -> K
^
Z >= T, Nachfolger := recInsert(Y, z2) = Y (geändert)
        Nachfolger von Z wird also (wie bisher) das Y.
 
Hallo,
also ich hab mir deine Beschreibung angeschaut und es mir aufgemalt doch es scheitert einfach an der Rekursion :(
Bin einfach zu doof das zu verstehen!
Ich verstehe nicht wieso ein node zurück gegeben wird und wann ich die next Zeiger umhängen muss.

So nach 1 Stunde habe ich es iterativ hin bekommen :(
Hier mal der Code:
C:
list init() {
    list l = {NULL};
    return l;
}

node *getnode(void) {
    node *p;
    p = (node *) malloc(sizeof(node));
    if (p == NULL)
        puts("Nicht genug Speicher!\0"), exit(1);
    return p;
}

void insert(list *l, double x) {
    if (l->anfang == NULL) {
        l->anfang = getnode();
        l->anfang->wert = x;
        l->anfang->next = NULL;
        l->anzahl++;
    } else if (l->anfang->wert > x) {
        node *new = getnode();
        new->wert = x;
        new->next = l->anfang;
        l->anfang = new;
        l->anzahl++;
    } else {
        node *tmp = l->anfang;
        node *vorgaenger;
        while (tmp != NULL) {
            if (tmp->wert < x) {
                vorgaenger = tmp;
                tmp = tmp->next;
            } else {
                node *new = getnode();
                new->wert = x;
                vorgaenger->next = new;
                new->next = tmp;
            }
        }
        if(tmp == NULL) {
            node *new = getnode();
            new->wert = x;
            new->next = NULL;
            vorgaenger->next = new;
        }
    }
}

int main(void) {

    list l = init();
    insert(&l,2);
    insert(&l,12);
    insert(&l,22);
    insert(&l,-2);
    insert(&l,22.2);
    printList(&l);

    return 0;
}
Das ganze gefällt mir überhaupt nicht :( Ich verwende einen vorgängerZeiger, und vor allem komme ich auch nicht ohne die Prüfung tmp == NULL an das letzte Element :( Geht das ganze eleganter?

Ich dachte wenn ich es iteraitv mache würde ich den rekursiven Ansatz verstehen aber jetzt bin ich wieder mal mehr verwirrt als es mir etwas gebracht hat :/

LG
 
also ich hab mir deine Beschreibung angeschaut und es mir aufgemalt doch es scheitert einfach an der Rekursion
Sieh jeden rekursiven Aufruf einfach als Aufruf einer anderen Methode (die den gleichen Inhalt hat).

Ich verstehe nicht wieso ein node zurück gegeben wird und wann ich die next Zeiger umhängen muss.
Ganz einfach:
z1.wert < z2.wert gilt für z2.wert='T' im Beispiel oben erst, wenn z1.wert = 'K' gilt, also die Situation
Code:
Z -> Y -> K
          ^z1
erreicht ist. An der Stelle soll z1 der Nachfolger von z2 werden. Dadurch ensteht erstmal folgendes Bild:
Code:
Z -> Y -> K <- T
          ^z1  ^z2
z1 zeigt ja das aktuelle Element an, wir befinden uns also noch beim K. Um die Liste zu korrigieren, müsste jetzt der Nachfolger des Vorgängers (Y) geändert werden und zwar zu z2. Das geht aber nicht direkt, weil das K den Vorgänger nicht kennt. Allerdings wurde "das K von Y aus augerufen", d. h. man kann das z2 einfach zurückgeben
Code:
Rückgabe:
Z -> Y -> K <- T
     ^z1       ^Rückgabewert
Setze den Nachfolger von z1 auf den Rückgabewert:
Z -> Y -> T -> K
     ^z1  ^Rückgabewert
Da der rekursive Aufstieg ja weitergeht, muss ab jetzt das aktuelle Element (z1) zurückgegeben werden:
Code:
Rückgabe (Y):
Z -> Y -> K <- T
^z1  ^Rückgabewert
Setze den Nachfolger von z1 auf den Rückgabewert (Y):
Z -> Y -> T -> K
^z1  ^Rückgabewert
Hier findet also keine Änderung mehr statt und das ist auch richtig so.
 
Leider hatte ich nach dem ich heute Mittag das ganze Iterativ versucht habe keine Zeit mehr dafür.
Nun dachte ich mir naja versuchst du das ganze mal anders etwas leichter.
Ich versuchte eine Methode zu schreiben die nur rekursiv einen Knoten in eine verkettete Liste einfügt. Das klappt auch schon nicht :(

Das ganze lässt sich nicht mal übersetzen!
C:
void rInsert(list *l, double x) {
    if(l->anfang == NULL) {
        node *new = getnode();
        new->wert = x;
        new->next = NULL;
        l->anfang = new;
    }
    else rekursivInsert(l->anfang,x);
}

node *rekursivInsert(node *n, double x) {
    if(n->next == NULL) {
        node *new = getnode();
        new->wert = x;
        new->next = NULL;
        return new;
    }
    else return rekursivInsert(n->next,x);
}

Mir ist es auch einfach schleierhaft wie das funktionieren soll wenn ich nur einen Wert zurück gebe das er weiß das soll das ->next Element sein!
 
C:
#include "einfachverketteteliste.h"
#include <stdio.h>
#include <stdlib.h>

void insert(list *l, double x) {
    node *new = (node *) malloc(sizeof(node));
    if (new == NULL) {
        printf("Fehler nicht genug Speicherplatz!\n");
        return;
    }
    new->wert = x;
    l->anfang = recInsert(l->anfang, new);
}

node *recInsert(node *z1, node *z2) {
    if (z1 == NULL) {
        return z2;
    } else if (z1->wert < z2->wert) {
        z2->next = z1;
        return z2;
    } else {
        z1->next = recInsert(z1->next, z2);
        return z1;
    }
}

int main(int argc, char *argv[]) {
    list l;

    insert(&l, 5);
    insert(&l, 8);

    node *cur = l.anfang;
    while (cur != NULL) {
        printf("%f\n", cur->wert);
        cur = cur->next;
    }
    return 0;
}
 
Danke @mihe7 . Auch wenn ich den Code nicht verdient habe.
Ich versuche jetzt mal alle Listen Operationen noch wie z. B. größe, suchen, löschen rekursiv zu erstellen.
Melde mich hier wieder.

LG
 
@ocsme Wenn Du da noch Probleme hast, dir das Vorgehen richtig vorzustellen: Evtl. solltest Du es noch einmal genauer aufmalen und auf einem Papier durchspielen. Bezüglich Rekursion visualisieren: Evtl. jeden Aufruf auf einem neuen Zettel aufmalen. Was bekommt die Funktion übergeben? Was hat sie lokal? Dabei die gemeinsamen Dinge auf einem gemeinsamen Zettel belassen (Also das, worauf die Zeiger gehen).

Aus meiner Sicht ist es bei solchen Datentypen wichtig, dass man da die genaue Vorstellung hat, worauf welcher Zeiger genau zeigt. Ohne eine solche Vorstellung ist da ein Vorgehen nicht möglich.

Ober versuch Dir irgend ein Bild aufzubauen, das für Dich verständlich ist. Bei so Listen könnte dies z.B. die Vorstellung von Eisenbahn-Anhängern sein. Diese sind mit Seilen verbunden, wobei jedes Seil immer einen Festpunkt hat und dann das loose Ende irgendwo festgebunden werden kann. (==> Ein Zeiger, ist irgendwo gespeichert aber zeigt auf etwas anderes.)
Und dann kannst Du bei so einem Bild ohne zu sehen, dich von Wagon zu Wagon tasten, indem du da immer den Seilen folgst.
(Der Zeiger der Liste auf das erste Element ist halt ein Seil, dass außen einen Festpunkt hat ist und das lose Ende geht zum ersten Wagon.)

Also wie gesagt: Nach meiner Erfahrung ist das alles nur eine Frage der Visualisierung. Wenn Du da einmal eine Visualisierung hast, mit der Du klar kommst, dann wird alles ganz einfach.
 
Danke für eure Antworten.
Leider habe ich die Tage viel zu tun und kam nicht dazu.
Bin ja schon froh das ich die Abstrakten Datentypen (Liste, Stack, Queue, Bäume, Graphen) endlich Programmiert bekomme. Wenn auch die meisten Algorithmen eben nur Iterativ :D

Also ich den Code von @mihe7 gesehen habe war es mir auch sofort klar! Das Problem ist eben nur selbst darauf zu kommen :D
Naja es wird schon werden stimmts :p

LG
 
Ufff... bin zu doof dafür!

Hab versucht in einer ganz normalen einfach Verketteten Liste ein Element mit rekursion einzufügen und bekomme das schon nicht hin!

C:
void insert(list *l, double val) {
    node *new = (node *) malloc(sizeof(node));
    if (new == NULL) {
        printf("Fehler nicht genug Speicherplatz!\n");
        return;
    }
    new->value = val;
    l->anfang = recInsert(l->anfang, new);
}

node *recInsert(node *anfang, node *element) {
    if (!anfang)
        return element;
    else {
        anfang->next = recInsert(anfang->next, element);
        return element;
    }
}
Ich dachte jetzt bei l->anfang bekommt er ein Element (node) zurück übergeben durch die Rekursion. Damit wäre weil die Liste anfangs leer ist der l->anfang = NULL ist das erste Element in der Liste das Element was zurück kommt.
Danach laufe ich mit anfang->next über alle Knoten bis einer NULL wird und gib dann das Element an dieser Stelle zurück.
Dadurch das ich das element zurück gegeben habe bekommt der letzte Zeiger dieses Element ja zugewiesen und somit sollte es richtig verkettet sein.

Doch es klappt nicht :( Es wird nur der letzte eingefügte Knoten gespeichert der Rest ist weg :(

LG
 
Schau Dir in recInsert einmal den else Zweig an.

Wenn Du rekursiv einfügst: Was musst Du dann zurück geben?

Wenn anfang null ist, dann ist es das Element - das ist richtig. Aber wenn anfang nicht leer ist: Was gibst Du dann zurück?
 
ufff den anfang knoten muss ich doch dann zurück geben. Sonst verliert ja auch der Stack seinen Anfang Knoten bzw. deswegen konnte ich nur einen Wert speichern.

Also mit rekursion stehe ich ja mega auf Kriegsfuß :(

Danke.

Werde weiter machen denn das nächste Problem was ich wieder hätte wäre, wenn ich eine doppelt Verkettete Liste habe. Doch ich werde das jetzt erst einmal im kleinen für die einfach Verkettete machen und später für die doppelt Verkettete :)

LG
 
Soweit so gut. Mir fehlt jetzt nur noch meine Lösche und Suche Funktion. Da ich heute eh nicht zu gebrauchen bin werde ich da denke ich morgen weiter machen doch einmal vorab:

Rekursives Einfügen:
C:
void push(list *l, double val) {
    node *new = (node *) malloc(sizeof(node));
    if (new == NULL) {
        printf("Fehler nicht genug Speicherplatz!\n");
        return;
    }
    new->value = val;
    l->anfang = recInsert(l->anfang, new);
}

node *recInsert(node *anfang, node *element) {
    if (anfang == NULL){
        return element;
    }
    else {
        anfang->next = recInsert(anfang->next, element);
        return anfang;
    }
}
Rekursives Print:
C:
void print(list l) {
    printf("Liste: ");
    recPrint(l.anfang);
}

void recPrint(node *s) {
    if (s) {
        printf("%f ", s->value);
        recPrint(s->next);
    }
}
Rekursives Killen:
C:
void kill(list *l) {
    recKill(l->anfang);
    l->anfang = NULL;
}

void recKill(node *anfang) {
    if(anfang != NULL) {
        recKill(anfang->next);
        free(anfang);
    }
}
Jetzt möchte ich auch gerne das Entfernen von meinem Letzten Element Rekusiv machen :) das suchen kommt später hab das löschen des letzten Elements erst einmal Iterativ gelöst und zwar so: (nicht wirklich schon aber selten :D)
Code:
double entf(list *l) {
    node *tmp = s->anfang, *vorgaenger, *vvgaenger;
    while(tmp) {
        vvgaenger = vorgaenger;
        vorgaenger = tmp;
        tmp = tmp->next;
    }
    double x = vorgaenger->value;
    vvgaenger->next = NULL;
    free(vorgaenger);
    return x;
}
Kann mir da jemand einen Tipp geben wie ich das Rekursiv hin bekomme?
hatte schon einige Ansätze. Wollte bis in den NULL Pointer laufen und dann returnen z. B. so:

C:
double entf(list *l) {
    return recEntf(l->anfang);
}

double recEntf(node *anfang) {
    if(anfang == NULL)
        return;
        //Es muss nur ein double returnt werden wollte es als einen Flucht Return nutzen
        //klappt so also schon einmal nicht.
    
}
Dann hatte ich den Ansatz so bin ich auf das Kill gekommen hehe:
C:
double entf(list *l) {
    return recEntf(l->anfang);
}

double recEntf(node *anfang) {
    if(anfang != NULL) {
            double x = anfang->value;
            recKill(anfang->next);
            free(anfang);
            return x;
        }
    
}
So lösche ich die ganze Liste was ja auch logisch ist.
Nun verstehe ich nur nicht so ganz wie ich in den NULL Pointer laufen kann mir dann den Wert des Vorgängers zurück geben lassen, diesen Wert zurück gebe. Jetzt wo ich das schreibe :D, denn oben bei der Iterativen version habe ich das intuitiv genutzt, muss der Nachfolger noch mit übergeben werden?

Sry für diese Doofen Fragen und das ich mir dabei echt so mega schwer tu :( Bin echt Dankbar für jede Hilfe :)

LG
 
Nein leider nicht!
Mein erster gedanke war dies hier:

C:
void test(list *l, double x) {
    ttest(s->anfang, x);
}

void ttest(node *anfang, double x) {
    if(anfang == NULL) {
        anfang->value = x;
        anfang->next = NULL;
    }
    else ttest(anfang->next, x);
}
Verstehe nur auch nicht wieso es so nicht geht :D Liegt das nun wieder an C oder liegt es an mir ?
LG
 
Also wenn Du Dir Deinen Code anschaust:
Wenn anfang NULL ist, dann willst Du da etwas setzen? Das geht erst einmal so nicht :) Da fehlt die Erstellung eines Knotens.

Und ein Tipp bezüglich dem Einfügen ohne etwas zurück zu geben: Du darfst nicht so lange gehen, bis Du bei NULL angekommen bist. Sondern du musst schon einen Schritt vorher aufhören. Wie kannst du denn feststellen, ob Du am Ende angekommen bist?
 
Danke nochmals :)
Gestern hatte ich echt einen schlechten Tag aber naja.

So jetzt geht es auch. Schön ist es aber nicht :( Ich hätte gerne die Abfrage vom aller ersten Element auch im Rekursions aufruf.

C:
void test(list *l, double x) {
    node *new = (node *) malloc(sizeof(node));
    new->value = x;
    if(l->anfang == NULL) {
        l->anfang = new;
        l->anfang->next = NULL;
    }
    ttest(l->anfang, NULL, new);
}

void ttest(node *anfang, node *vorgeanger, node *einfuegen) {
    if(anfang == NULL) {
        vorgeanger->next = einfuegen;
        einfuegen->next = NULL;
    }
    else if(anfang != NULL) {
        vorgeanger = anfang;
        ttest(anfang->next, vorgeanger, einfuegen);
    }
}
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben