Sortierte Liste in C

[ocsme]

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:

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);

#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

 

[mihe7]

Visualisieren, immer visualisieren

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.

 

[insanezulu]

mihe7 hat doch wieder zu viel Zeit.

 

[mihe7]

@insanezulu Tobias?!?

Das lustige ist ja, dass sich die Probleme von @ocsme gefühlt jedesmal durch eine Zeichnung erklären lassen

 

[ocsme]

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:

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

 

[mihe7]

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

Z -> Y -> K
          ^z1

erreicht ist. An der Stelle soll z1 der Nachfolger von z2 werden. Dadurch ensteht erstmal folgendes Bild:

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

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:

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.

 

[ocsme]

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!

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!

 

[mihe7]

#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;
}

 

[ocsme]

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

 

[mihe7]

Vergleich ihn mal mit Deinem Ursprungscode

 

[kneitzel]

@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.

 

[ocsme]

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

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

LG

 

[ocsme]

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!

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

 

[kneitzel]

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?

 

[ocsme]

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

 

[ocsme]

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:

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:

void print(list l) {
    printf("Liste: ");
    recPrint(l.anfang);
}

void recPrint(node *s) {
    if (s) {
        printf("%f ", s->value);
        recPrint(s->next);
    }
}

Rekursives Killen:

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 )

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:

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:

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 , 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

 

[mihe7]

Könntest Du denn recInsert rekursiv so umschreiben, dass nichts zurückgegeben wird?

 

[ocsme]

Nein leider nicht!
Mein erster gedanke war dies hier:

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 Liegt das nun wieder an C oder liegt es an mir ?
LG

 

[kneitzel]

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?

 

[ocsme]

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.

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);
    }
}

 

[mihe7]

Du könntest auch einfach dafür sorgen, dass beim Aufruf von ttest immer anfang != NULL gilt:

void ttest(node *anfang, node *einfuegen) {
    if (anfang->next == NULL) {
         anfang->next = einfuegen;
         einfuegen->next = NULL;
    } else {
        ttest(anfang->next, einfuegen);
    }
}

Natürlich musst Du dann auch test() anpassen.

 

[kneitzel]

Nur um Dir einmal zu zeigen, wie so eine Funktion auch aussehen könnte:

void ttest(node *anfang, double x) {
    if(anfang->next == NULL) {
        anfang->next = (node *) malloc(sizeof(node));
        anfang->next->value = x;
        anfang->next->next = null;
    }
    else {
        ttest(anfang->next, einfuegen);
    }
}

Mit folgenden Hinweisen:
- Wenn Du den neuen Node aufbaust: Setz da auch gleich next=null. Beziehungsweise: ich habe das einfach mit in das ttest aufgenommen.
- Und das if bei dem else ist unnötig. if (anfang == null) -> dann ist klar: im else Zweig ist anfang != null.

Also die Hauptänderung ist, dass du gar nicht erst bis anfang==null gehst sondern scohon aufhörst, ehe es keinen Sinn mehr macht. Das ist ein Pattern, das aus meiner Sicht üblich ist und das Du zur Übung ja mal in den ganzen anderen rekursiven Funktionen einbauen kannst.

Edit: vorgaenger parameter vergessen zu löschen und mihe7 war schneller

 

[ocsme]

stehe ich jetzt wieder auf dem Schlauch? Wenn ich beides so mache dann habe ich doch immer noch das Problem wenn
l->anfang = NULL ist das er nichts einfügt! oder?
LG

 

[kneitzel]

stehe ich jetzt wieder auf dem Schlauch? Wenn ich beides so mache dann habe ich doch immer noch das Problem wenn
l->anfang = NULL ist das er nichts einfügt! oder?
LG

Ja, den Fall fängst Du doch in Deiner Funktion test auf. ttest wird nur aufgerufen, wenn die Liste nicht leer ist.

 

[kneitzel]

Ich bringe mal beide Funktionen zusammen (da mir gerade auch aufgefallen ist, dass Du da einen Fehler hattest in test!):

void test(list *l, double x) {
    /* Create new node first */
    node *new = (node *) malloc(sizeof(node));
    new->value = x;
    new->next = NULL;
    
    /* Check if list is empty */
    if(l->anfang == NULL) {
        l->anfang = new;
    } else { /* else fehlte  */
        ttest(l->anfang, new);   
    }
}

void ttest(node *anfang, node *new) {
    if(anfang->next == NULL) {
        /* Wir sind am letzten Element, daher fügen wir das Element ein. */
        anfang->next = new;
    }
    else {
        /* Wir sind nicht am letzten Element - also rekursiver Aufruf */
        ttest(anfang->next, new);
    }
}

 

[ocsme]

So sollte es nun halbwegs okay sein:

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

void recInsert(node *anfang, node *einfuegen) {
    if (anfang->next == NULL)
        anfang->next = einfuegen;
    else
        recInsert(anfang->next, einfuegen);
}

 

[ocsme]

Weiter habe ich aber immer noch nicht das Löschen gelöst, wobei ich jetzt dachte naja suchen sollte leichter sein
Naja fehl anzeige! Ich bin ja überhaupt froh das ich es so halbwegs hin bekomme. Wenn ich mir überlege wie ich vor 1/2 Jahr hier gesessen habe! Da konnte ich gar keine Datenstrukturen :/

Nun mal zum Suchen mein versuch es Iterativ hin zu bekommen sieht so aus:

//  search Iterativ!
node *search(list *l, int x) {
    node *tmp = l->anfang;
    while (tmp != NULL) {
        if (tmp->value == x)
            return tmp;
        tmp = tmp->next;
    }
    return NULL;
}

Sobald ich das in meiner main Teste sehe ich keine Ausgabe mehr

int main(void) {

    list test = init();
    insert(&test, 2.3);
    insert(&test, 2.4);
    insert(&test, 2.5);
    insert(&test, 2.6);
    print(test);
    node *t;
    t  = search(&test,2.4);
    printf("%f: \n", t->value);

    return 0;
}

naja und mein rekursiver Versuch sieht ähnlich aus:

//node *search(list *l, double x) {
//    return recSearch(l->anfang, x);
//}
//
//node *recSearch(node *anfang, double x) {
//    if (anfang != NULL) {
//        if (anfang->value == x)
//            return anfang;
//        return recSearch(anfang->next, x);
//    }
//    return NULL;
//}

Denn erst einmal nicht beachten! Ich verstehe nämlich schon nicht wieso es nicht Iterativ läuft?

LG

 

[kneitzel]

Also das sieht erst einmal auf den ersten Blick ok aus. Wenn ich Dich richtig verstanden habe, dann hast Du eine Endlosschleife? Das könnte an Deinem Insert oder so liegen. Kannst Du da einmal den ganzen Code zeigen?

Und rekursiv ist es doch gleich:
Abbruchbedingung ist etwas komplexer, denn da hast Du zwei:
- Wenn das Element gefunden wurde, gibst Du das Element zurück
- Wenn es kein Folge-Element gibt, gibst du NULL zurück
- Und recursiver Aufruf ist halt auf dem nächsten Element.
Und das hast Du auch schon umgesetzt. Das was mir auffällt ist nur: search und recSearch haben die gleichen Parameter und den gleichen Rückgabewert und search ruft nur recSearch auf. Warum also nicht search löschen und recSearch zu search umbenennen?

 

[ocsme]

Ich Poste mal meine ganze Liste:

revl.c

#include <stdlib.h>
#include <stdio.h>
#include "revl.h"

void recInsert(node *anfang, node *einfuegen);
void recPrint(node *anfang);
void recKill(node *anfang);
node *recSearch(node *anfang, double x);
node *recDelete(node *anfang, node *vorgaenger, double x);

list init() {
    list erg = { NULL };
    return erg;
}

int isEmpty(list *l) {
    return l->anfang == NULL ? 0 : 1;
}

void print(list l) {
    printf("Liste: ");
    recPrint(l.anfang);
}

void recPrint(node *s) {
    if (s) {
        printf("%f ", s->value);
        recPrint(s->next);
    }
}

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

void recInsert(node *anfang, node *einfuegen) {
    if (anfang->next == NULL)
        anfang->next = einfuegen;
    else
        recInsert(anfang->next, einfuegen);
}

//  search Iterativ!
//node *search(list *l, int x) {
//    node *tmp = l->anfang;
//    while (tmp != NULL) {
//        if (tmp->value == x)
//            return tmp;
//        tmp = tmp->next;
//    }
//    return NULL;
//}

//node *search(list *l, double x) {
//    return recSearch(l->anfang, x);
//}
//
//node *recSearch(node *anfang, double x) {
//    if (anfang != NULL) {
//        if (anfang->value == x)
//            return anfang;
//        return recSearch(anfang->next, x);
//    }
//    return NULL;
//}

//void delete(list *l, double x) {
//    l->anfang = recDelete(l->anfang, NULL, x);
//}
//
//node *recDelete(node *anfang, node *vorgaenger, double x) {
//    if(anfang != NULL) {
//        vorgaenger = anfang;
//        if(anfang->value == x) {
//            vorgaenger->next = anfang->next;
//            free(anfang);
//            return vorgaenger;
//        }
//    }
//    return anfang;
//}

void kill(list *l) {
    recKill(l->anfang);
    l->anfang = NULL;
}

void recKill(node *anfang) {
    if (anfang != NULL) {
        recKill(anfang->next);
        free(anfang);
    }
}

revl.h

#ifndef REVL_H_
#define REVL_H_

typedef struct Node {
    double value;
    struct List *next;
}node;

typedef struct List {
    node *anfang;
}list;

list init();
void print(list l);
void insert(list *l, double x);
void delete(list *l, double x);
void kill(list *l);

#endif /* REVL_H_ */

 

[kneitzel]

Also der Compiler meckert da gleich etwas rum ... und das zu Recht:

Schauen wir einmal deine Typen an:
List ist ein struct mit einem pointer auf ein node - ok.
Node ist ein struct mit
- einem value - ok.
- einem Zeiger auf eine List? Das stimmt so doch nicht und wird daher bei rekursiven Aufrufen angemeckert: Der Typ stimmt nicht, denn Du hast da ja nicht eine List sondern ein Node in next. (Mag aber sein, dass das egal ist - die Warnungen ignorierst du und so lange du da immer Nodes rein packst, ist es egal, dass du da gesagt hast, dass das List rein gehören. C prüft das ja nicht im Gegensatz zu Java

==> Bitte Warnungen immer ernst nehmen und prüfen!

Und da habe ich dann vorher auch nicht richtig geschaut: search und recSearch haben unterschiedliche Parameter - einmal List und einmal Node. Daher natürlich 2 Funktionen!

Ich habe Deinen Code genommen und:
- in revl.h lediglich den Node angepasst:

typedef struct Node {
    double value;
    struct Node *next;
}node;

- Deine Main habe ich mit in revl.c getan (Bei dir evtl. in einer separaten Datei - alles ok!) und die Ausgabe war bisher alles auf einer Zeile. Daher einfach leicht angepasst:

int main(void) {

    list test = init();
    insert(&test, 2.3);
    insert(&test, 2.4);
    insert(&test, 2.5);
    insert(&test, 2.6);
    print(test);
    printf("\n");
    node *t;
    t  = search(&test,2.4);
    printf("Found: %f\n", t->value);

    return 0;
}

Und natürlich fehlte die search Funktion - da habe ich einfach einmal deine Rekursive Implementation wieder aus den Kommentaren befreit (Hatte ja schon gesagt, dass diese gut aussehen würde):
nobody@hpzbook:~/tmp$ gcc -o revl revl.c
nobody@hpzbook:~/tmp$ ./revl
Liste: 2.300000 2.400000 2.500000 2.600000
Found: 2.400000
nobody@hpzbook:~/tmp$

Sieht doch soweit gut aus würde ich sagen. Also an Problemen habe ich nur das mit der Definition von Node gesehen ....

 

[kneitzel]

Und bezüglich der Node Definition - meine Aussage mit den Warnungen, die Du einfach ignorieren konntest wollte ich auch noch einmal verifizieren:
Also revl.h wieder geändert mit List *next und dann übersetzt, kurz geschaut, dass auch wirklich ein neues Executable da liegt und dann den Aufruf getestet:

nobody@hpzbook:~/tmp$ gcc -o revl revl.c
revl.c: In function ‘recPrint’:
revl.c:28:18: warning: passing argument 1 of ‘recPrint’ from incompatible pointer type [-Wincompatible-pointer-types]
         recPrint(s->next);
                  ^
revl.c:25:6: note: expected ‘node * {aka struct Node *}’ but argument is of type ‘struct List *’
 void recPrint(node *s) {
      ^~~~~~~~
revl.c: In function ‘recInsert’:
revl.c:48:22: warning: assignment from incompatible pointer type [-Wincompatible-pointer-types]
         anfang->next = einfuegen;
                      ^
revl.c:50:19: warning: passing argument 1 of ‘recInsert’ from incompatible pointer type [-Wincompatible-pointer-types]
         recInsert(anfang->next, einfuegen);
                   ^~~~~~
revl.c:46:6: note: expected ‘node * {aka struct Node *}’ but argument is of type ‘struct List *’
 void recInsert(node *anfang, node *einfuegen) {
      ^~~~~~~~~
revl.c: In function ‘recSearch’:
revl.c:72:26: warning: passing argument 1 of ‘recSearch’ from incompatible pointer type [-Wincompatible-pointer-types]
         return recSearch(anfang->next, x);
                          ^~~~~~
revl.c:68:7: note: expected ‘node * {aka struct Node *}’ but argument is of type ‘struct List *’
 node *recSearch(node *anfang, double x) {
       ^~~~~~~~~
revl.c: In function ‘recKill’:
revl.c:100:17: warning: passing argument 1 of ‘recKill’ from incompatible pointer type [-Wincompatible-pointer-types]
         recKill(anfang->next);
                 ^~~~~~
revl.c:98:6: note: expected ‘node * {aka struct Node *}’ but argument is of type ‘struct List *’
 void recKill(node *anfang) {
      ^~~~~~~
nobody@hpzbook:~/tmp$ ls -l
insgesamt 24
-rwxrwxr-x 1 konrad konrad 12936 Nov 14 13:42 revl
-rw-rw-r-- 1 konrad konrad  2397 Nov 14 13:37 revl.c
-rw-rw-r-- 1 konrad konrad   291 Nov 14 13:42 revl.h
nobody@hpzbook:~/tmp$ ./revl
Liste: 2.300000 2.400000 2.500000 2.600000
Found: 2.400000
nobody@hpzbook:~/tmp$

Aber natürlich sind das Prüfungen auf korrekte Typen und die ignoriert man nicht. Das es klappt liegt einfach nur daran, dass Du im Code immer ein Node in next legst und erwartest und nur die Definition falsch ist.

 

[ocsme]

so ein misst! Ja da habe ich in der .h nicht meine Gedanken zusammen gehabt
Das ist mir alles nicht mal aufgefallen. Die Warnung schaue ich mir immer als letztes an wenn ich Ehrlich bin
Zuerst sehe ich mal zu das die grobe Funktionalität funktioniert.

mhhh... Ich bekomme nur bei keinen von beiden search Funktionen eine Ausgabe. Somit kann ich nicht mal sicher sein das eine von beiden wirklich laufen :/

 

[ocsme]

Also 2 Dinge noch:
1. bekomme ich einfach keine Ausgabe egal welche Search-Funktion ich nutze
2. Wieso bekomme ich bei delete immer wieder die ganze Liste zurück?

void delete(list *l, double x) {
    if(l->anfang == NULL)
        return;
    l->anfang = recDelete(l->anfang, NULL, x);
}

node *recDelete(node *anfang, node *vorgaenger, double x) {
    if(anfang != NULL) {
        vorgaenger = anfang;
        if(anfang->value == x) {
            vorgaenger->next = anfang->next;
            free(anfang);
            return vorgaenger;
        }
    }
    return anfang;
}

 

[kneitzel]

Hmm, also ich habe es bei mir getestet und es hat bei mir funktioniert. Daher wundert mich, dass Du keine Ausgabe bekommst. Warnungen bekommst Du keine mehr? Und die beschriebenen Änderungen hast Du durchgeführt?

Ansonsten bau noch ein paar printf ein, damit Du mehr Ausgaben bekommst.

Oder vielleicht auch interessant: Wie startest Du es? Evtl. auch mal paar fflush() Aufrufe einfügen, es auf der Kommandozeile probieren, ...

 

[ocsme]

Haha, was war vorhin den schon wieder los mit mir
Hab in der Rekursion die Rekursionsaufruf vergessen
Doof!

void delete(list *l, double x) {
    if(l->anfang == NULL)
        return;
    l->anfang = recDelete(l->anfang, NULL, x);
}

node *recDelete(node *anfang, node *vorgaenger, double x) {
    if(anfang != NULL) {
        if(anfang->value == x) {
            vorgaenger->next = anfang->next;
            free(anfang);
            return vorgaenger;
        }
        vorgaenger = anfang;
        return recDelete(anfang->next,vorgaenger,x);
    }
    return anfang;
}

 

[ocsme]

Oder vielleicht auch interessant: Wie startest Du es? Evtl. auch mal paar fflush() Aufrufe einfügen, es auf der Kommandozeile probieren, ...

Ich starte es in Eclipse und nutze den gcc mit Ubuntu. Deswegen sollte ich dieses fflush() nicht brauchen!
Versetehe das selbst schon wieder nicht. Wo verschluckt der Sack meine Ausgabe

Gut delete hab ich hin bekommen wenn auch wieder mal nicht so schön

 

[kneitzel]

Deine Löschroutine sieht auch nicht korrekt aus:
Du setzt vorgaenger = anfang. Danach ist ein vorgaenger->next = anfang->next zumindest wirkungslos.

Edit: Ok, hast es ja schon geändert gehabt ... hatte mir mein Browser nur nicht angezeigt - erst beim Posten habe ich Deine Posts gesehen .... daher hat sich das überschnitten ....

Probier den Aufruf auf der Kommandozeile ... hast Du da die Ausgaben korrekt? Und ja - unter Linux brauchst du keine fflush Aufrufe. Da funktioniert es (wie ich es bei mir ja sehe).

 

[ocsme]

Du setzt vorgaenger = anfang. Danach ist ein vorgaenger->next = anfang->next zumindest wirkungslos.

Ja das war der erste Versuch. Schau mal den Code vor ein paar Minuten an
Diesen hier:

void delete(list *l, double x) {
    if(l->anfang == NULL)
        return;
    l->anfang = recDelete(l->anfang, NULL, x);
}

node *recDelete(node *anfang, node *vorgaenger, double x) {
    if(anfang != NULL) {
        if(anfang->value == x) {
            vorgaenger->next = anfang->next;
            free(anfang);
            return vorgaenger;
        }
        vorgaenger = anfang;
        return recDelete(anfang->next,vorgaenger,x);
    }
    return anfang;
}

Was ich nur einfach nicht verstehe ist das ich keine Ausgabe bei search raus bekomme

 

[ocsme]

So heute ist es Offiziell ich hab was an den Augen!!!
Mein search kann so nicht gehen. Ich hab in der Funktionssignatur int drin stehen. Vergleich dann aber auf double.
int == double mhhh... also 2 == 2.4 gibt sicherlich nie ein Treffer also kommt NULL zurück. Somit Fehlerhafte Ausgabe bzw. Programm Absturz
UFFFF.... sry!!!!

So nun klappt das alles so weiter Könntet Ihr mir vielleicht noch verraten wie ich die delete schöner hin bekomme?

 

[mihe7]

Könntet Ihr mir vielleicht noch verraten wie ich die delete schöner hin bekomme?

Genauso wie die void recInsert-Methode

 

[ocsme]

also geht das auch ohne mein Nachfolger Element das ich in der Rekursion mit schleife?
Geht das den Überhaupt also ohne das Nachfolger Element

 

[mihe7]

Momentan prüfst Du, ob Du das aktuelle Element löschen musst. Daher brauchst Du Zugriff auf den Vorgänger. Du könntest aber auch prüfen, ob das nachfolgende Element gelöscht werden muss, dann ist das aktuelle Element bereits der Vorgänger...

 

[kneitzel]

Also ich sehe zwei Möglichkeiten, die beide gehen würden aber alle Vor- und Nachteile haben.

a) Wie von mihe7 gesagt: Du prüfst, ob Du den Nachfolger löschen musst. Dies setzt aber voraus, dass Du beim ersten Aufruf auf der Liste zwei Fälle abprüfen musst: a) Liste leer? b) Muss erstes Element gelöscht werden?
Und dann ist da halt die Überprüfung etwas weniger leserlich, weil halt auf aktuell->next->value statt einfach auf aktuell->value operiert werden muss.

b) Man könnte beim rekursiven Aufruf aber auch das Element zurückgeben, das als Nachfolger eingetragen werden soll. Das macht den Code kürzer und übersichtlicher, aber dafür hast Du unter dem Strich viele Zuweisungen mehr.
Sprich: Der Aufruf auf der Liste ruft einfach anfang=recursiverAufruf(anfang, ...) auf.
Der rekursive Code prüft:
Aktuelles Element zu löschen? Dann löschen und return next;
aktuell->next nicht null? dann aktuell->next = recursiverAufruf(aktuell->next);
return aktuell;

Was man also sieht: Auf der ganzen Kette wird next neu gesetzt, auch wenn es unverändert ist. Das ist etwas, das ich nicht so mag, aber bezüglich sauberem Code mag der eine oder andere evtl. b) bevorzugen.

 

[Barista]

Sind eine Menge Postings hier.

Also von Löschen stand in der ursprünglichen Aufgabe nichts.

Eigentlich ist es recht einfach

neue_liste = function(neuer_wert, alte_liste);

In der Funktion gibt es drei Fälle:

if (alte_liste == NULL)
{
entry kopf;
kopf.wert = neuer_wert;
return kopf
}

if (neuer_wert >= alte_list.wert)
{
entry neuer_kopf;
neuer_kopf.wert = neuer_wert;
neuer_kopf.next = alte_liste;
return neuer_kopf;
}

if (alte_liste.next == NULL)
{
entry neues_ende;
neues_ende.wert = neuer_wert;
alte_liste.next = neues_ende;
return alte_liste;
}

// else

// jetzt wird es rekursiv

alte_liste.next =
function(
neuer_wert,
alte_liste.next);

return alte_liste;

Ist doch gar nicht so schwer.

 

[mihe7]

Wenn ich @ocsme richtig verstanden habe, soll er den gelöschten Wert zurückgeben. Daraus entstand erst meine Frage, ob er denn das Einfügen, das er zu diesem Zeitpunkt schon hatte, so umschreiben kann, dass er eben nicht den neuen Kopf zurückgibt. Damit hatte ich die Hoffnung verknüpft, dass er daran die grundsätzliche Funktionsweise erkennt und den gelöschten Wert einfach zurückgeben kann.

 

[ocsme]

Danke dafür erst einmal werde mir das morgen genauer anschauen Lieben Dank.

Naja in Java hatte ich bei den Binärbäumen zumindest was insert, delete, find anging keine Probleme. Gut ich denke wenn ich den Code Poste schüttelt Ihr mit dem Kopf aber naja er funktioniert
Vielleicht liegt es auch daran das ich mir die Listen selbst rekursiv aneigne. Denn bei den Binärbäumen wurde uns das echt super anschaulich erklärt.
Auch wenn @mihe7 sich so viel Mühe gegeben hat es so schön anschaulich zu erklären fehlt mir irgendwie etwas!

Nochmals Danke für die Hilfe. Morgen schau ich dann das ich die Liste soweit fertig bekomme. Dann wollte ich eine Doppelt Verkettete Liste so machen und danach dann noch ein Binärbaum. Denke da kommen sicherlich wieder ein paar Fragen auf auch wenn der Baum in Java läuft in C noch lange nicht

 

[mihe7]

Denn bei den Binärbäumen wurde uns das echt super anschaulich erklärt.

Wenn Du in einen binären Suchbaum die Werte in sortierter Reihenfolge einfügst, entartet der Baum zur verketteten Liste, weil immer nur rechts eingefügt wird Vielleicht hilft Dir das weiter.

 

[ocsme]

Hallo,
ich hab schon wieder ein Problem. Wollte eine Mehrdiminsionale Liste erstellen.
Die Header-Datei sieht so aus:

typedef struct Node {
    char value[16];
    struct Node *next;
    struct Node *prev;
    struct Node *firstSon;
    struct Node *father;
}node;

typedef struct List {
    node *root;
}list;

list init();
node *suche(list *root,char *name);
void einfuegen(list *root, char *vater, char *name);

und das was ich versucht habe sieht so aus:

node *greatNode(char *name) {
    node *p;
    p = (node *) malloc(sizeof(node));
    if (p == NULL)
        puts("Nicht genug Speicher!"), exit(1);
    strcpy(p->value, name);
    p->next = p->prev = p->firstSon = p->father = NULL;
    return p;
}

list init(char *name){
        list v;
        v.root = greatNode(name);
        return v;
    }

node *rekSuche(node *p, char *name) {
    if (p != NULL) {
        if (!strcmp(p->value, name))
            return p;

        return rekSuche(p->firstSon, name);
        return rekSuche(p->next, name);
    }

    return NULL;
}

node *suche(list *l, char *name) {
    return rekSuche(l->root, name);
}

void rekEinfuegenListe(node *anfang, node *einfuegen) {
    if (anfang->next == NULL) {
        anfang->next = einfuegen;
        einfuegen->prev = anfang;
    } else
        rekEinfuegenListe(anfang->next, einfuegen);
}

void einfuegen(list *l, char *vater, char *name) {
    if (!suche(l, vater)) {
        printf("Der Vater ist nicht vorhanden!");
        return;
    }
    node *new = greatNode(name);
    node *gefundenVater = suche(l, vater);
    if (gefundenVater->firstSon != NULL)
        rekEinfuegenListe(gefundenVater->firstSon, new);
    else {
        gefundenVater->firstSon = new;
        new->father = gefundenVater;
    }
}

Mein Problem ist schon die suche!
Hab mir das ganze 100 mal aufgemalt und bin auch jetzt mit meinem Latein am ende. Sitze seit über 3 Stunden an gerade mal diesen 3 Funktionen/Prozeduren und kann nicht mehr!

Ich hoffe ihr versteht was ich da versuche.
Würde eben gerne eine Liste erstellen die weitere Ebenen hat also so ähnlich wie ein mehrdiminsionales Array. Ich habe einen Vater dieser Vater hat auch keine next oder prev Elemente. Auf den Vater wollte ich aufbauen Also dieser Vater hat einen Sohn. Dieser Sohn kann wieder mehrere Söhne haben oder eben der Vater hat mehrere Söhne, diese Söhne stehen dann in einer Liste neben dem ersten Sohn
Dann sollen aber auch wieder sämtlich Söhne zu Väter werden können. Ich hoffe es ist halbwegs verständlich.

Vielleicht könnt Ihr ja weiter helfen falls Ihr Lust habt

fg

 

[mihe7]

Du meinst einen Baum?

 

[ocsme]

Ja einen Baum mit einer Liste aber kein Binärer Baum
Ich verstehe nur nicht wieso die Rekursion bei suche so nicht klappt wenn ich es aufmale und im Kopf durchgehe sollte er jeden Knoten mal besuchen. Doch ich glaube das tut er nicht denn das Einfügen klappt nicht

LG