Wie verknüpfte Liste mit Fibonacci-Serie dynamisch bevölkern

Question

Ich habe eine verknüpfte Liste, die ich bis zu einer bestimmten Loop-Nummer auffüllen wollte. Ich habe meinen Code unten zeigt eine Fibonacci-Serie mit einer C-Liste verknüpft.

Hier ist mein Code ohne Schleife:

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

typedef struct Node 
{ 
    int count; 
    int fibo;  
    struct Node* next; 

}node; 

int 
fibo(int val){ 
     if(val == 1 || val == 2) { 
       return 1; 
     } 
     return fibo(val - 1) + fibo(val - 2); 
} 

int 
main (void) 
{ 
    node f1, f2, f3; 

    f1.count = 1; 
    f1.fibo = fibo(1); 

    f2.count = 2; 
    f2.fibo = fibo(2); 

    f3.count = 3; 
    f3.fibo = fibo(3); 

    f1.next = &f2; 
    f2.next = &f3; 
    f3.next = NULL; 


    printf("f1 fibo : %i\n", f1.fibo); 
    printf("f2 fibo : %i\n", f2.fibo); 
    printf("f3 fibo : %i\n", f3.fibo); 

    return (0); 
} 

Jetzt möchte ich über eine Schleife, dies zu tun. Wie würde ich das tun?

Answer 1

Für diese Antwort werde ich die Bedenken hinsichtlich der Effizienz der Berechnung ignorieren, die sich aus der Neuberechnung aller Fibonacci-Nummern bis zu der angegebenen Zahl bei jedem Aufruf von fibo(n) ergeben.

Verknüpfte Listen sind normalerweise keine "Direktzugriff" -Datenstrukturen, mit denen Sie auf ein beliebiges Element mit einem Index zugreifen können. Wenn Sie eine verkettete Liste mit Zeigern verwenden, müssen Sie nur den Zeiger auf den Kopf (erstes Element) der verknüpften Liste haben. Dann durchqueren Sie die Liste beginnend am Kopf mit einer Schleife, die durch jede next Verbindung geht. Wenn eine Liste leer ist, ist Ihr Kopf normalerweise NULL.

Sie können dies hier anwenden. Eine Möglichkeit (es gibt mehrere) ist eine Funktion zu definieren zuzuweisen und einen einzelnen Eintrag eingestellt:

node *set_fibo(int n) 
{ 
    node *fibo_entry = malloc(sizeof(node)); 

    if (fibo_entry == NULL) { 
     // error 
    } 

    fibo_entry->count = n; 
    fibo_entry->fibo = fibo(n); 
    fibo_entry->next = NULL; 
    return fibo_entry; 
} 

Und dann in der Haupt:

node *fibo_list = NULL; 
node *last_fibo = NULL; 

// Assume n_fibo is the number of Fibonacci numbers you want to store in order 
for (int n = 1; n <= n_fibo; n++) { 
    if (n == 1) 
     fibo_list = last_fibo = set_fibo(1); 
    else { 
     last_fibo->next = set_fibo(n); 
     last_fibo = last_fibo->next; 
    } 
} 

Answer 2

In Ihrem Beispiel sind die Knoten automatische Variablen in main. Sie werden nicht dynamisch zugewiesen und sie leben so lange, wie Sie nicht von main zurückkehren. Sie können dieses Konzept mit einer automatischen Anordnung von Knoten erweitern:

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

typedef struct Node Node; 

struct Node { 
    int count; 
    int fibo;  
    Node* next; 
}; 

#define N 30 

int main (void) 
{ 
    Node fibo[N]; 
    Node *head = NULL; 
    Node **p = &head; 

    int f1 = 0; 
    int f2 = 0; 

    for (size_t i = 0; i < N; i++) { 
     Node *nd = &fibo[i]; 

     nd->count = i + 1; 
     nd->fibo = f2 + f1 ? f2 + f1 : 1; 

     f1 = f2; 
     f2 = nd->fibo; 

     *p = nd; 
     p = &(*p)->next; 
    } 
    *p = NULL; 

    Node *nd = head; 

    while (nd) { 
     printf("fib(%d) == %d\n", nd->count, nd->fibo); 
     nd = nd->next; 
    } 

    return (0); 
} 

Es ist nicht klar, aber warum Sie die Fibonacci-Reihe als verkettete Liste benötigen. Auch ein Wort der Warnung: Mischen Sie nicht Knoten auf dem Stapel (wie hier) und Knoten auf dem Haufen (wie in lurkers Antwort) in einer Liste. Diese Antwort erweitert Ihre Antwort auf viele Knoten, während lurkers Antwort ein allgemeineres Konzept von verknüpften Listen zeigt.

Answer 3

Hier ist, wie ich denke, Sie können es tun. Sie können ein Array für die Knoten verwenden.

node f[3]; 
int i; 

for (i = 0 ; i < 3 ; i++) 
{ 
    f[i].count = i+1; 
    f[i].fibo = fibo (i+1); 
    if (i == 2) 
    { 
     f[i].next = NULL; 
    } 
    else 
    { 
     f[i].next = &f[i+1]; 
    } 
} 

Answer 4

Obwohl die Frage bereits beantwortet wurde, möchte ich etwas in Bezug auf den Effizienzaspekt Ihres Codes hinzufügen. Wie bereits erwähnt, müssen Sie den Fibo-Wert nicht von Anfang an berechnen, da Sie die letzten Ergebnisse in der einfach verknüpften Liste gespeichert haben. Wenn Sie also die folgende Liste 1-1-2-3-5- haben, können Sie den Fibo-Wert des neuen Knotens leicht berechnen, indem Sie einfach den Fibo-Wert der beiden letzten Elemente (d. H. 3 und 5) hinzufügen. Daher sollte der Wert des Fibo-Werts des neuen Knotens 8 sein.

die Zeiger auf das zweite letzte Element gegeben, fügt diese Funktion einen neuen Knoten in die Liste aufnehmen und stellen Sie den richtigen fibo Wert:

void addNode(struct Node* node){ 
    struct Node* n = malloc(sizeof(struct Node)); 
    n->next = NULL; 
    n->count = node->next->count + 1; 
    n->fibo = node->fibo + node->next->fibo;  
    node->next->next = n; 
} 

Um diese Funktion zu nutzen, müssen Sie die erstellen ersten beiden Knoten in der Liste:

struct Node* n2 = malloc(sizeof(struct Node)); 
n2->count = 2; 
n2->fibo = 1; 
n2->next = NULL; 
struct Node* n1 = malloc(sizeof(struct Node)); 
n1->count = 1; 
n1->fibo = 1; 
n1->next = n2; 

Wenn Sie jetzt hinzufügen möchten - können 10 sagen - neue Knoten, tun Sie einfach:

struct Node* ptr = n1; 
int i; 
for(i=0; i<10;i++) { 
    addNode(ptr); 
    ptr = ptr->next; 
} 

Wenn Sie nun die Einträge aller Knoten in der Liste drucken möchten, iterieren Sie einfach über die Liste, bis Sie NULL erreichen.

ptr = n1; 
while(ptr != NULL) { 
    printf("fib(%d) = %d\n ", ptr->count, ptr->fibo); 
    ptr = ptr->next; 
} 

Bitte beachten Sie, dass Sie dynamisch zugewiesene Artikel manuell freigeben müssen!