# Sortierte Liste in C



## ocsme (8. Nov 2019)

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



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 (8. Nov 2019)

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 (8. Nov 2019)

mihe7 hat doch wieder zu viel Zeit.


----------



## mihe7 (9. Nov 2019)

@insanezulu Tobias?!? 

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


----------



## ocsme (9. Nov 2019)

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 (9. Nov 2019)

ocsme hat gesagt.:


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



ocsme hat gesagt.:


> 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 (10. Nov 2019)

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 (10. Nov 2019)

```
#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 (10. Nov 2019)

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 (10. Nov 2019)

Vergleich ihn mal mit Deinem Ursprungscode


----------



## kneitzel (10. Nov 2019)

@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 (12. Nov 2019)

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 (13. Nov 2019)

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 (13. Nov 2019)

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 (13. Nov 2019)

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 (13. Nov 2019)

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 (13. Nov 2019)

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


----------



## ocsme (13. Nov 2019)

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 (13. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

ocsme hat gesagt.:


> 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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

JustNobody hat gesagt.:


> 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 (14. Nov 2019)

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 (14. Nov 2019)

JustNobody hat gesagt.:


> 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 (14. Nov 2019)

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 (14. Nov 2019)

ocsme hat gesagt.:


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


Genauso wie die void recInsert-Methode


----------



## ocsme (14. Nov 2019)

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 (14. Nov 2019)

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 (14. Nov 2019)

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 (15. Nov 2019)

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 (15. Nov 2019)

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 (15. Nov 2019)

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 (15. Nov 2019)

ocsme hat gesagt.:


> 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 (16. Nov 2019)

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 (16. Nov 2019)

Du meinst einen Baum?


----------



## ocsme (16. Nov 2019)

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


----------



## mihe7 (16. Nov 2019)

Wenn ich Dich richtig verstehe, sieht Dein Baum also so aus:

```
next
  A1 --------> A2
   |             \____
   | son           son\      next
   v     next          A2.1 -----> A2.2
  A1.1 --------> A1.2
   |
   | son
   |
   v       next
  A1.1.1 --------> A1.1.2
```

Effizient Suchen ist da aber nicht drin...

Um im Baum k den Wert w zu finden, sollte folgender Pseudocode funktionieren:

```
suche(k, w) {
    if (k == null || k.wert == w) { return k; }
    ergebnis = suche(k.son, w); // durchsuche Sohn
    if (ergebnis == null) {
        ergebnis = suche(k.next, w); // durchsuche nächsten Knoten
    }
    return ergebnis;
}
```


----------



## ocsme (16. Nov 2019)

Das werde ich morgen mal ausprobieren.
Ich hab oben 2x return gehabt statt es einer Variablen zu zuordnen und diese zurück zu geben grrr... was hab ich da wieder für ein Käse gemacht. Naja werd es morgen Probieren bin jetzt zu Müde.

Eine Frage hätte ich noch zu C. Wenn ich ein Array der größe [16] in der struct vereinbare, die Eingabe des Strings aber größer später ist als 16 dann printet der mir ja komische Zeichen.
Hatte versucht das weg zu bekommen mit if(MAX_SIZE(16)-1 > strlen(string))array[15] = '\0';
Doch dann bekomme ich gar keine Ausgabe mehr 
Wenn nicht muss ich es morgen mal wieder hinfrickeln das ganze habe ich nämlich wieder gelöscht gehabt und dachte mir dann naja darf man eben nichts eingaben was größer als 15 Zeichen ist 

PS:
Also die suche und das einfügen scheinen jetzt zu klappen  Danke.
Hab es mal probiert werde es morgen aber nochmal Testen


----------



## mihe7 (17. Nov 2019)

ocsme hat gesagt.:


> Wenn ich ein Array der größe [16] in der struct vereinbare, die Eingabe des Strings aber größer später ist als 16 dann printet der mir ja komische Zeichen.


Du meinst bei printf("%s")? Ggf. ja  

Das ist ganz einfach: in C wird eine Zeichenkette durch ein 0-char beendet. Wenn Du eine Zeichenkette haben willst, die 16 Zeichen aufnimmt, muss für ein Zeichen (0-char) mehr Platz reserviert werden. 

Schreibst Du ein Array voll, dann wird der 0-char hinter dem Array im Speicher platziert, bei einer Struktur im nächsten Element:

```
#include <stdio.h>
#include <memory.h>

typedef struct {
    char z1[4];
    char z2[4];
} struktur;

int main()
{
    struktur x;
    memset(&x, 'X', sizeof(struktur));
    x.z1[3] = 0;
    x.z2[3] = 0;
    printf("%s\n%s\n", x.z1, x.z2);

    scanf("%s", x.z1);
    printf("%s\n%s\n", x.z1, x.z2);
}
```

Wenn Du das ausführst, hast Du Platz für zwei Strings der Länge 3. Am Anfang werden beide mit XXX initialisiert.

Gibst Du nun drei Zeichen ein, z. B. AAA ein, ist alles so, wie es sein soll, und es wird

```
AAA
XXX
```
ausgegeben.

Gibst Du dagegen vier Zeichen ein, z. B. AAAA, dann wird nur noch AAAA ausgegeben. Der zweite String ist "leer". Warum? 

Der Speicher sieht in etwa so aus:

```
z1   z2 
0123 0123 Indizes
------------------------------
XXX0 XXX0 Initialzustand
AAA0 XXX0 Nach Eingabe von 3 A
AAAA 0XX0 Nach Eingabe von 4 A
AAAA A0X0 Nach Eingabe von 5 A
```
Wenn Du jetzt überlegst, dass printf() bis zum Erreichen des 0-Zeichens ausgibt, dann wird die Sache klar. Kannst Du anhand des Programms überprüfen. Du solltest aber nicht mehr als 7 Zeichen eingeben, denn sonst wird einfach der aktuelle Inhalt Deines Speichers in Form von Zeichen ausgegeben, bis eine 0 erreicht wird oder das Betriebssystem einen Seitenzugriff verhindert.


----------



## ocsme (17. Nov 2019)

Danke @mihe7  super erklärt und das auch noch um diese Uhrzeit 

Eine Doofe frage hätte ich noch dazu. Es geht hier mehr um das Thema Sicherheit. Sagen wir mal wie hätten so eine Struktur:

```
struct Test {
    char value[16];
};

struct Test init(char *name) {
    struct Test erg;
    strcpy(erg.value, name);
    return erg;
}

int main(void) {

    struct Test a = init("Hallo");
    printf("%s\n", a.value);
    struct Test b = init("So und jetzt mehr"); //Hier würden mehr als 16 Zeichen gelesen werden was ein Überlauf provoziert
    printf("%s\n", b.value);

    return 0;
}
```

Diesen Überlauf kann ich doch dann so z. B. in der init() Methode verhindern oder ist daran auch etwas Falsch?

```
struct Test init(char *name) {
    struct Test erg;
    int i = strlen(name); //zählt ohne den '\0'
    strcpy(erg.value, name);
    if (i > 16 - 1)
        erg.value[15] = '\0';
    return erg;
}
```

Natürlich würde dadurch der rest des Strings verloren gehen bzw. der rest würde zwar fürs erst noch im Speicher hinten dran stehen doch sicherlich nicht sehr lange, oder könnte man dadurch schon die Software angreifen?

Dann hätte ich noch diese Variante die mir eingefallen ist als ich diesen Beitrag geschrieben habe:

```
struct Test init(char *name) {
    struct Test erg;
    int i = strlen(name); //zählt ohne den '\0'
    strncpy(erg.value, name, 15);
    if (i < 15)
        erg.value[i] = '\0';
    return erg;
}
```

Das letzte gefällt mir am besten 
Da dort gleich von vorne rein verhindert wird das mehr Zeichen als gewollt geschrieben werden dürfen


----------



## mihe7 (17. Nov 2019)

ocsme hat gesagt.:


> Natürlich würde dadurch der rest des Strings verloren gehen bzw. der rest würde zwar fürs erst noch im Speicher hinten dran stehen doch sicherlich nicht sehr lange, oder könnte man dadurch schon die Software angreifen?


Die bleiben ja im Speicher stehen  Das Schreiben der 0 "kürzt" ja nichts, sondern sorgt nur dafür, dass dort eine 0 steht. Was vorher geschrieben wurde, bleibt im Speicher und genau so entstehen dann Sicherheitslücken. Beispielsweise kann auf diese Weise die Rücksprungadresse eines Funktionsaufrufs verändert werden. Moderne Compiler haben Gegenmaßnahmen dafür.



ocsme hat gesagt.:


> Da dort gleich von vorne rein verhindert wird das mehr Zeichen als gewollt geschrieben werden dürfen


So ist das richtig.


----------



## ocsme (18. Nov 2019)

Guten Abend, 
ich sitze schon wieder an einem String Problem 
Was ich versuche ist eine Methode zu schreiben die ein String (char *string) übergeben bekommt und diesen String dann Wort weiße als Liste abspeichert.

Die Strukturen sehen so aus:

```
typedef struct Node {
    char value[WORD_SIZE];
    struct Node *next;
    struct Node *prev;
}node;

typedef struct List {
    node *anfang, *ende;
    int anzahl;
}list;
```

Und meine Methode derzeit so:

```
list createListFromArray(char *array) {
    int i, j = strlen(array);
    char string[j];
    strcpy(string, "");
    list erg = createEmptyList();
    for (i = 0; i < j; i++) {
        if (array[i] == ' ') {
            insertWordAtFront(&erg, string);
        }
        string[i] = array[i];
    }
    return erg;
}
```

Mit dieser Murks Methode habe ich aber 2 Probleme. 
1. Ich bekomme viel misst ausgegeben da ich den char string ja so groß mache wie den übergebenen Array-String. Weiß leider nicht wie ich den char string[j] in jedem durchlauf auf Null setzen kann bzw. bräuchte ich für jeden Satz durchlauf ein neuen String mit der passenden größe des einzelnen Wort ein Beispiel:

Das ist das Haus vom Nikolaus.
Bräuchte ich 6 einzelne Knoten mit den größen 3, 3, 3, 4, 3, 9 bzw. 10 hier ist der Satz zu ende also '\0'

2. läuft derzeit die Methode nur bis zu einem 'Leerzeichen'. Wie erkenne ich hierbei in C das ich an einem ende eines Wortes wäre.

Vielleicht könnt Ihr mir hierbei nochmals unter die Arme greifen 

Danke im voraus

mfg


----------



## mihe7 (18. Nov 2019)

ocsme hat gesagt.:


> Die Strukturen sehen so aus:


Wenn Du die Werte nicht aus die Länge des char-Arrays (value) begrenzen willst, mach aus value einen Zeiger:

```
typedef struct Node {
    char *value;
    struct Node *next;
    struct Node *prev;
}node;
```
Wenn Du von einem gegebenen char* eine Kopie ablegen willst, reservierst Du für value ausreichend Speicher (malloc) und kopierst mittels strncpy.


----------



## ocsme (18. Nov 2019)

mhhh... ich wollte in der Struktur das Array eigentlich drin lassen  
Denn durch den Satz muss ich ja eh immer laufen um herauszufinden wieviele Wörter im Satz stehen und wie lang diese dann sind mhhh...
Wie bekomme ich den einzelne Strings in der Länge erstellt wie lang eben ein einzelnes Wort ist?

Also nehmen wir mein Beispiel von oben:
Das ist das Haus ...
Dann wäre der erste String ja 3 Wörter lang. 
Kann ich dann nicht irgendwie über strncpy es machen? 
Man erstellt zwei string Variablen die eine nutzt man als tmp und übertragt den ganzen Satz nach und nach in tmp. Die andere String Variable nimmt man dann sobald man auf ein ' ' kommt benutzt man strncpy(string, tmp, i) <- wobei ich jetzt wieder nicht weiß welche Reihenfolge hier wo rein kopiert wird müsste ich mir anschauen wie die strncpy dokumentiert ist. Was ich noch gerade nicht weiß ist die Rechenformschrift denn das i wandert ja weiter doch ich muss den alten i Wert ja abziehen damit ich nicht wie oben immer wieder den ersten Anfang mit Kopiere

 ob das klappen könnte falls man es hier versteht?
LG


----------



## ocsme (19. Nov 2019)

Nö so bekomme ich nur eine Endlosschleife  Bekomme es so nicht hin! Das lasse ich erst einmal. Man die Strings in C sind ja mal mega anstrengend 


```
char word[] = "Das sollte ein Test werden.";
    list erg = createListFromArray(word);
    printList(erg);
```


```
list createListFromArray(char array[]) {
    list erg = createEmptySentence();
    char delimiter[] = " ";
    char *ptr = NULL;
    ptr = strtok(array,delimiter);
    while(ptr != NULL) {
        insertWordAtFront(&erg, ptr);
        ptr = strtok(array,delimiter);
    }
    return erg;
}
```


----------



## kneitzel (19. Nov 2019)

Also array ist ja unverändert - daher wird `strtok(array,delimiter);` immer NULL oder eben kein NULL zurück geben.

Daher ist in der while Scheife das array als Parameter nicht korrekt.

http://www.c-howto.de/tutorial/strings-zeichenketten/string-funktionen/string-zerteilen/  ist evtl. hilfreich.


----------



## ocsme (19. Nov 2019)

Danke für die schnelle Antwort.

also jetzt geht es. Wieso verstehe ich zwar noch nicht so ganz  aber es geht 
Eine Frage habe ich aber noch. Wenn ich der Methode einen char *ptr übergebe geht es nur wenn ich in meiner main ein char string[] = "Kurt Kanns 555678 DE"; erstelle. Wieso geht es nicht so: char *k = "Kurt Kanns";?

list createListFromArray(char *array) <- so sieht der Methodenkopf aus wieso geht dann nicht das hier? char *k = "Kurt Kanns"


----------



## kneitzel (19. Nov 2019)

Ich nehme einmal an, dass Du einfach den Aufruf in der while Schleife angepasst hast und Du nicht mehr array sondern NULL übergeben hast.

Und der Link, den ich gegeben habe, erläutert es doch auch:


> Beim ersten Aufruf muss *strtok* mit einem String initialisiert werden. Die Rückgabe ist hierbei der erste Abschnitt. Bei Folgeaufrufen wird statt *string* der *NULL* Wert übergeben, da *strtok* bereits initialisiert ist und intern einen Zeiger auf *string* gespeichert hat.





ocsme hat gesagt.:


> list createListFromArray(char *array) <- so sieht der Methodenkopf aus wieso geht dann nicht das hier? char *k = "Kurt Kanns"



Wieso sollte das nicht gehen? https://www.prismnet.com/~mcmahon/Notes/strings.html gibt das als Beispiel an, aber wir probieren es noch einmal:
test.c:

```
#include <stdio.h>

void main() {
   char *k = "Kurt kanns";
   printf(k);
}
```
dann noch:
gcc -o test test.c
./test

Und schon steht da "Kurt kanns".


----------



## ocsme (19. Nov 2019)

Bei mir geht das nicht. Er gibt dann mal wieder nichts mehr aus. Ich muss aufhören denn bin wieder total verwirrt 

Also erst einmal hier die wie es bei mir aussieht. Vielleicht geht es bei dir ja 

```
char string[] = "Kurt Kanns 555678 DE";
    char *k = "Kurt Kanns";
    list erg = createSentenceFromArray(string);
    printList(erg);
    printf("\n");
    list tmp = createSentenceFromArray(k);
    printList(tmp); //wird nicht gedruckt!!!
```

so sieht die Methode ja dazu aus:

```
//list createSentenceFromArray(char *array) {
//    list erg = createEmptySentence();
//    char delimiter[] = " ";
//    char *ptr = NULL;
//    ptr = strtok(array,delimiter);
//    while(ptr != NULL) {
//        insertWordAtFront(&erg, ptr);
//        ptr = strtok(NULL,delimiter);
//    }
//    return erg;
//}
```

Denn ich habe eine weitere Methode dazu geschrieben um ein Array von node zu übergeben und diese node dann in meine Liste einzufügen. 
Erstes Problem daran ich hab 20 Minuten gebraucht bis ich das node[] initialiserit bekommen habe. Wollte es per for Schleife machen doch das hat nicht geklappt 
Zweites Problem wieso muss hier an der Stelle der Punkt hin? 

```
list createSentenceFromArray(node word[], int pos) {
    list erg = createEmptySentence(); int i;
    for(i = 0; i < pos; i++)
        insertWordAtEnd(&erg, word[i].value); //warum kommt hier der Punkt hin?

    return erg;
}
```

Ein Array ist doch nichts weiter als ein Pointer oder?
node *word sollte oben im Methodenkopf also auch funktionieren. Wieso muss man dann word_.value schreiben hab es versucht so umzuschreiben das geht aber nicht! *(word+i)->value geht auch nicht so *(word+i).value!
Das hier hat mich mehr verwirrt als es mir etwas gebracht hat so ein misst aber auch 

So habe ich es dann Initialisiert am Ende da ich nicht mehr weiter kam 


		C:In die Zwischenablage kopieren


node a[2];
    node test = {"Test", NULL, NULL};
    node test2 = {"Test2", NULL, NULL};
    a[0] = test;
    a[1] = test2;
    list t = createSentenceFromArray(a, 2);
    printList(t);

_


----------



## kneitzel (19. Nov 2019)

Zugriff auf Elemente:
a) wenn du einen Pointer hast, also z.B. node *pnNode: pnNode->element
b) wenn du eine instanz hast: node nNode: nNode.element
Also bei pointer -> und bei instanz .

Bezüglich der Ausgabe:
Hast du es wieder aus eclipse gestartet? Mach es dann direkt von der Kommandozeile! Oder besorg Dir eine andere IDE, wenn eclipse so spinnt.


----------



## ocsme (19. Nov 2019)

JustNobody hat gesagt.:


> a) wenn du einen Pointer hast, also z.B. node *pnNode: pnNode->element
> b) wenn du eine instanz hast: node nNode: nNode.element



Ja das ist mir irgendwie klar 
Doch ein Array ist doch eigentlich auch ein Pointer deswegen dachte ich dort muss auch der -> hin 



JustNobody hat gesagt.:


> Hast du es wieder aus eclipse gestartet? Mach es dann direkt von der Kommandozeile! Oder besorg Dir eine andere IDE, wenn eclipse so spinnt.


Ja hab es wieder wie alles aus Eclipse gestartet. Dann sollte ich das mal ausprobieren ohne Eclipse.

Danke nochmals

Achso weisst du wie ich mein node word[] besser initialisieren kann?

LG


----------



## kneitzel (19. Nov 2019)

ocsme hat gesagt.:


> Ja das ist mir irgendwie klar
> Doch ein Array ist doch eigentlich auch ein Pointer deswegen dachte ich dort muss auch der -> hin



Also word ist das Array und damit wäre es ein Pointer. Das `word[i]` ist dann aber ein konkretes Element. Also der Pointer aufgelöst. Das `word[i]` ist nichts anderes als ein *(word+i), was dann ja zeigt: Das ist nicht mehr der Pointer sondern das Element.

Und auf das (word+i) noch einmal zurück kommen:
word ist ein pointer auf das erste Element eines Arrays.
(word+i) ist ein Zeiger auf das ite Element des Arrays.
Nun kannst Du auf Elemente zugreifen. Bei einem Pointer wäre dies dann z.B. (word+i)->value
Wenn Du einen Pointer hast, dann kannst Du mit * das Element dahinter bekommen, also ist *(word+i) das Element des Arrays.
Wenn Du da nun .value anhängen willst, dann geht das nicht *(word+i).value ist für den Compiler *((word+i).value), d.h. er würde da den Pointer nehmen und Zugriff als Element -> Das wird nichts. Aber wir können da natürlich Klammern setzen: 
(*(word+i)).value.
Aber das ist natürlich Quatsch - da nutzt man natürlich entweder word_.value oder von mir aus noch (word+i)->value, was ich aber unleserlich finde.



ocsme hat gesagt.:



			Ja hab es wieder wie alles aus Eclipse gestartet. Dann sollte ich das mal ausprobieren ohne Eclipse.
		
Zum Vergrößern anklicken....

Ich habe keine Ahnung, was da mit Deinem Eclipse los ist, aber ich habe Eclipse auch noch nie mit C oder C++ genutzt. Da hatte ich damals unter Windows Visual Studio und unter Linux KDevelop oder Anjuta im Einsatz. Aber es gibt auch noch einige andere IDEs, die gerade für Anfänger gut sein könnten, da sie nicht so überladen sind. CodeBlocks fällt mir da z.B. gerade ein....



ocsme hat gesagt.:



			Achso weisst du wie ich mein node word[] besser initialisieren kann?
		
Zum Vergrößern anklicken....

Wie initialisierst Du das derzeit? Ich habe gerade keinen wirklichen Überblick, was Du da wie machst. Ich habe aber da mal noch paar Aussagen / Fragen von Dir aufgearbeitet, auf die ich vorher noch nicht eingegangen bin._


----------



## ocsme (19. Nov 2019)

JustNobody hat gesagt.:


> Also word ist das Array und damit wäre es ein Pointer. Das `word[i]` ist dann aber ein konkretes Element. Also der Pointer aufgelöst. Das `word[i]` ist nichts anderes als ein *(word+i), was dann ja zeigt: Das ist nicht mehr der Pointer sondern das Element.



Stimmt deswegen auch der . 

Was mit meinem Eclipse dann los ist weis ich auch nicht. Vielleicht sollte ich die  Programme öfters dann über die Konsole laufen lassen. 

Derzeit Initialisierie ich das node word[] so:
in meiner main:

```
node a[2];
    node test = {"Test", NULL, NULL};
    node test2 = {"Test2", NULL, NULL};
    a[0] = test;
    a[1] = test2;
    list t = createSentenceFromArray(a, 2);
    printList(t);
```

Mein Node sieht so aus:

```
typedef struct word {
    char value[WORD_SIZE];
    struct word *next;
    struct word *prev;
}node;
```

Ich wollte es in einer Schleife Initialisieren geht das Überhaut in C*?*

*Danke.*


----------



## kneitzel (19. Nov 2019)

Also bezüglich des Initialisierens habe ich noch immer Probleme, Dich so richtig zu verstehen, aber das liegt evtl. daran, dass ich derzeit nicht den Überblick habe, was Du erreichen möchtest....

Aber natürlich kann man auch in C ein Array in einer Schleife initialisieren. (Generell geht alles, was in Java und Co geht, auch in C/C++. Aber natürlich ist dies ggf. etwas umständlicher. Aber Java ist ja auch irgendwie entwickelt worden und das was Java Compiler und JVM machen, geht natürlich auch in C ... Egal wie Du etwas schreibst: Am Ende ist es der Computer der irgendwas macht ... Aber das heißt natürlich nicht, dass etwas einfach ist ... )

Also ein Beispiel, wie ein node Array in einer Schleife initialisiert wird:

```
#include <stdio.h>
 
typedef struct Node {
    char value[100];
    struct Node *next;
    struct Node *prev;
}node;

void main() {
        node array[10];

        for (int i=0; i<10; i++) {
                sprintf(array[i].value, "Element %d", i);
                array[i].next = NULL;
                array[i].prev = NULL;
        }
}
```

Also Node ist klein bisschen geändert - statt deiner Constante habe ich eine Magic Number ... hab beim Copy & Paste nicht aufgepasst und dann zu faul, erneut zum Browser zu wechseln ...


----------



## mihe7 (20. Nov 2019)

ocsme hat gesagt.:


> Eine Frage habe ich aber noch. Wenn ich der Methode einen char *ptr übergebe geht es nur wenn ich in meiner main ein char string[] = "Kurt Kanns 555678 DE"; erstelle. Wieso geht es nicht so: char *k = "Kurt Kanns";?


Erstmal sind

```
char string[] = "ABCD";
char *k = "ABCD";
```
zwei unterschiedliche Dinge.

Im ersten Fall erzeugst Du ein Array, das mit den Zeichen aus dem Literal (inkl. der abschließenden 0) initialisiert wird. Im zweiten Fall erzeugst Du einen Zeiger auf ein Literal.

Das Verhalten beim Versuch, ein Literal zu verändern, ist nicht definiert. Der GCC legt das Literal in ein Read-Only-Segment ab, so dass Versuche, das Literal zu verändern, mit einem Speicherzugriffsfehler quittiert werden.

Zur Veranschaulichung:

```
#include <stdio.h>

int main(int argc, char *argv[]) {
    char string[] = "ABCD";
    char *k = "ABCD";
    char *m = "ABCD";

    printf("%p\n%p\n%p\n", string, k, m);
    return 0;
}
```
Wenn Du das mit dem GCC übersetzt, wirst Du vermutlich feststellen, dass k und m auf die gleiche Adresse zeigen. Das Literal wird also nur einmal für die beiden Zeiger abgelegt. Jetzt wäre es ziemlich ungünstig, wenn Du über m das Literal ändern könntest, denn dann würde sich automatisch auch k verändern. Insofern macht es durchaus Sinn, dass der Compiler für Literale ein RO-Segment verwendet.

Da strtok die übergebene Zeichenkette verändert, muss die Angabe eines Zeigers auf ein Literal zu einem Speicherzugriffsfehler führen.


----------



## kneitzel (20. Nov 2019)

Also da macht es evtl. Sinn, das noch einmal ganz ausführlich zu bringen: http://www.lysator.liu.se/c/c-faq/c-2.html

Da werden viele Punkte durchgesprochen und erläutert, die evtl. beim Verständnis des ganzen Sachverhaltes helfen.


----------



## ocsme (20. Nov 2019)

Nochmals Danke an euch beide 
Muss mir die Strings, Arrays und Pointer noch einmal anschauen. Bei der ganzen Sache jetzt habe ich mich wieder total verwirrt 

Des weiteren war ich wohl etwas vorlaut das ich Bäume rekursiv hin bekomme  grr.... ich dachte ich hätte es verstanden :'(


----------



## kneitzel (20. Nov 2019)

Evtl. einmal den Link von mir ansehen? Der zeigt das alles recht anschaulich finde ich... Und dann evtl. daran etwas entlang hangeln? Ich habe im Augenblick keinen Ansatz, wo wir für Verwirrung gesorgt haben ....

Ansonsten kann ich dir ggf. auch einmal ein direktes Gespräch anbieten. Das hilft evtl. mehr wie schreiben....


----------



## ocsme (20. Nov 2019)

JustNobody hat gesagt.:


> ? Ich habe im Augenblick keinen Ansatz, wo wir für Verwirrung gesorgt haben ....



 Ohhh.. nicht falsch verstehen. Ihr habt euch ja super nette Mühe gegeben  Das ganze liegt an mir! 

Bin ja schon einmal froh das wenigstens die paar Listen Algorithmen nun laufen  Der Rest ist erst einmal neben Sache.

Ich hätte aber noch ein kleines Problem aber zum Thema Suchbaum. Soll ich ein neues Thema erstellen da es hier ja um die Liste geht und falls jemand auch so ein Problem hat es auch finden kann?
Wollte bei einem Suchbaum eine Methode schreiben die mir den Vaterknoten sucht für den Wert den ich gerne einfügen möchte. Doch irgendwie klappt es Rekursiv mal wieder überhaupt nicht  bzw. hab es sogar wieder komplett gelöscht. 
Es ist echt zum Haare raufen.


----------



## mihe7 (20. Nov 2019)

ocsme hat gesagt.:


> Soll ich ein neues Thema erstellen


Ja, besser ist das.


----------

