c-如何打印链表的fibonacci节点?例如，我们打印链接列表中的第一、第二、第三、第五、第八等节点

Question

我正在努力寻找最有效的方法。以下代码用于打印前十个元素的斐波那契级数(使用记忆(

int main()
{
int arrayWithFibIndices[100] = {0}; //Explanation for this array comes later
int series[10] = {0}; //array to store the fibonacci values for last two iterations
series[0] = 1; //hard coding the first two elements of the fib series
series[1] = 2;
for (int i = 0; i < 10; i++)
{   
if (series[i] != 0)
{   
printf ("series[%d]=%d.n", i, series[i]);
}   
else 
{   
series[i] = series[i - 1] + series[i - 2]; 
printf ("series[%d]=%d.n", i, series[i]);
}
arrayWithFibIndices[series[i]] = 1;
}   
}

我还有以下逻辑来迭代打印链表。

void printLL(struct node *temp)
{
int i  = 0;
while(temp != NULL)
{   
if (arrayWithFibIndices[i] != 0) //reason explained later below
{
printf("data:%d ", temp->data);
temp = temp->next;
}
i++;
}   
printf("n");
}

我正试图找出最有效的方法是什么？我想到的第一件事是创建一个新的数组arrayWithFibIndices[]，并将该数组的所有元素初始化为0。每当我们遇到一个fibonacci值时，我们都会用1填充arrayWithFibIndices[]中的索引。我们可以稍后在打印链表的值之前检查arrayWithFibIndices[]的每个索引。

我想到的第二个想法是创建一个队列。我会将所有Fibonacci元素排队，当涉及到打印链表时，我会在成功匹配时出列(匹配是队列元素与链表的第I个元素匹配。

你们还有其他建议吗？

Answer 1

您在描述中建议的解决方案将起作用。然而，你不需要做一个通行证就可以得到所有菲巴努奇数字的列表。您可以只跟踪上一个数字，并使用来偏移列表中的当前节点。

这里有一个简单的例子来演示它的工作原理。

#include <stdio.h>
#include <malloc.h>
struct node {
int data;
struct node *next;
};
void create_linked_list(struct node **root_ptr, int count) {
struct node **curr_ptr = root_ptr;
struct node *curr = NULL;
for (int i = 0; i < count; i++) {
*curr_ptr = (struct node *)malloc(sizeof(struct node *));
curr = *curr_ptr;
curr->data = i + 1;
curr->next = NULL;
curr_ptr = &(curr->next);
}
}
void print_linked_list(struct node *root) {
for(struct node *curr = root; curr != NULL; curr = curr->next) {
printf("%dn", curr->data);
}
}
void print_linked_list_fib(struct node *root) {
struct node *curr = root;
// Print the root node twice because of 1,1
// 1
printf("%dn", curr->data);
int old_val = 1;
// 1
printf("%dn", curr->data);
int curr_val = 1;
int offset = old_val;
while (true) {
// Keep moving until the next fibonacci node.
for (int i = 0; i < offset; i++) {
if (curr == NULL) return;
curr = curr->next;
}
if (curr == NULL) return;
printf("%dn", curr->data);
old_val = curr_val;
curr_val = curr_val + offset;
offset = old_val;
}
}
int main() {
struct node *root = NULL;
const int count = 20;
create_linked_list(&root, count);
printf("nnList of all nodesn");
print_linked_list(root);
printf("nnList of fibonacci nodesn");
print_linked_list_fib(root);
return 0;
}

这是样本输出

List of all nodes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

List of fibonacci nodes
1
1
2
3
5
8
13

EDIT:为fibonacci节点编写打印函数的另一种方法。这将上一个实现中的两个循环扁平化为一个循环。

void print_linked_list_fib_loop(struct node *root) {
struct node *curr = root;
// Print the root node twice because of 1,1
// 1
printf("%dn", curr->data);
int old_val = 1;
// 1
printf("%dn", curr->data);
int curr_val = 1;
int i = 0;
curr = curr->next;
for(struct node *curr = root; curr != NULL; curr = curr->next) {
if (i == old_val) {
old_val = curr_val;
curr_val = curr_val + i;
i = 0;
printf("%dn", curr->data);
}
i++;
}
}

Answer 2

如果您也在设计和构建列表，那么在构建过程中，您可以将fibonacci节点的地址复制到单独的struct node*数组中。为了管理节点的任何重新排序，您将在每个节点中存储列表位置(例如，如果添加或删除了一个节点，则会对其进行更改(。如果经常操作列表，这是一种开销，但打印fibonacci节点会变得非常高效：只需遍历指针数组，根本不遍历链表。