c - 如何使用斐波那契数列动态填充链表

Question

我有一个链表，我想将其填充到某个循环编号。下面的代码显示了使用 C 链表的斐波那契数列。

这是我没有任何循环的代码:

#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 链接的循环从头部开始遍历列表。如果列表为空，则您的head 通常为 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;
    }
}