Как динамически заполнять Связанный список с помощью серии Фибоначчи

Question

У меня есть связанный список, который я хотел бы заполнить до определенного номера цикла. У меня есть мой код ниже, показывает серию Фибоначчи, используя список C Linked.

Вот мой код без цикла:

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

Теперь я хочу сделать это с помощью цикла. Как мне это сделать?

Answer 1

Для этого ответа я проигнорирую проблемы вычислительной эффективности, возникающие при пересчете всех чисел Фибоначчи до заданного числа, которое вы получаете при каждом вызове до fibo(n).

Связанные списки обычно не представляют собой структуры данных «произвольного доступа», которые позволяют получить доступ к произвольному элементу с индексом. При использовании связанного списка с указателями вам нужно только указать указатель на головку (первый элемент) связанного списка. Затем вы перемещаете список, начиная с головы, используя петлю, проходящую через каждую ссылку next. Если список пуст, ваша голова обычно равна NULL.

Вы можете применить это здесь. Один из способов (есть несколько), чтобы определить функцию распределения и установить одну запись:

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

, а затем в главном:

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

В вашем примере, узлы автоматические переменные main. Они не распределяются динамически и живут до тех пор, пока вы не вернетесь с main. Вы можете расширить эту концепцию с автоматическим набором узлов:

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

Это не ясно, однако, почему вам нужен ряд Фибоначчи, как связанный список. Кроме того, слово предупреждения: Не смешивайте узлы в стеке (например, здесь) и узлы в куче (как в ответе lurker) в списке. Этот ответ просто расширяет ваш ответ на многие узлы, тогда как ответ lurker показывает более общую концепцию связанных списков.

Answer 3

Вот как я думаю, вы можете это сделать. Вы можете использовать массив для узлов.

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

Хотя на вопрос уже был дан ответ, я хотел бы добавить что-то относительно аспекта эффективности вашего кода. Как указывалось выше, вам не нужно вычислять значение фибо, начиная с самого начала, так как вы сохранили последние результаты в одиночном списке. Итак, у вас есть следующий список 1-1-2-3-5-, вы можете легко вычислить значение фибо нового узла, просто добавив фибо-значение двух элементов ламелей (то есть и 5). Следовательно, значение фибо-значения нового узла должно быть 8.

Учитывая указатель второго последнего элемента, эта функция добавит добавить новый узел в список и установить правильное значение фибо:

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

Для того, чтобы использовать эту функцию, вы должны создать первые два узла в списке:

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; 

Если теперь вы хотите добавить - позволяет сказать, 10 - новые узлы, вы просто сделать:

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

Если вы хотите распечатать записи всех узлов в списке, просто перейдите по списку, пока не достигнете NULL.

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

Пожалуйста, имейте в виду, что вам необходимо вручную освобождать динамически распределенные элементы!