Sortierte Liste in C

Du könntest auch einfach dafür sorgen, dass beim Aufruf von ttest immer anfang != NULL gilt:
C:
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.
 
Nur um Dir einmal zu zeigen, wie so eine Funktion auch aussehen könnte:
C:
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 :)
 
Zuletzt bearbeitet:
o_O 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
 
Ich bringe mal beide Funktionen zusammen (da mir gerade auch aufgefallen ist, dass Du da einen Fehler hattest in test!):
C:
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);
    }
}
 
So sollte es nun halbwegs okay sein:
C:
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);
}
 
Weiter habe ich aber immer noch nicht das Löschen gelöst, wobei ich jetzt dachte naja suchen sollte leichter sein :D
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:
C:
//  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 :D
C:
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:
C:
//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
 
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?
 
Ich Poste mal meine ganze Liste:

revl.c
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
C:
#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_ */
 
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:
C:
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:

C:
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):
[email protected]:~/tmp$ gcc -o revl revl.c
[email protected]:~/tmp$ ./revl
Liste: 2.300000 2.400000 2.500000 2.600000
Found: 2.400000
[email protected]:~/tmp$

Sieht doch soweit gut aus würde ich sagen. Also an Problemen habe ich nur das mit der Definition von Node gesehen ....
 
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:
Code:
[email protected]:~/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) {
      ^~~~~~~
[email protected]:~/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
[email protected]:~/tmp$ ./revl
Liste: 2.300000 2.400000 2.500000 2.600000
Found: 2.400000
[email protected]:~/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.
 
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 :D
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 :/
 
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?

C:
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;
}
 
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, ...
 
Haha, was war vorhin den schon wieder los mit mir :D
Hab in der Rekursion die Rekursionsaufruf vergessen :D
Doof!

C:
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;
}
 
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 :D

Gut delete hab ich hin bekommen wenn auch wieder mal nicht so schön :D
 
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).
 
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:
C:
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 :(
 
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?
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben