Question

数据结构 算法（求高手解答）有一个由自然数构成的序列采用单链表存储,试编写算法判断该序列是否是fibonacci序列（f

Answer 1

用C语言给你写了一个,其他语言的话再说,算法思想基本就是从表头开始遍历,按照fibonacci的特性进行检验

按单链表的特点,节点命名为node,

一个节点有long int型的data和节点指针型的next两个属性,以下是判断方法

bool Check(node head)

{

//a为当前遍历的节点,b为a之后的节点

node *a, *b;

bool isFibonacci;

//初始化

a = head;

b = head -> next;

//验证最初的两个数

if(!(a->data == 1) && (b->data == 1))

isFibonacci = false;

else

{

isFibonacci = true;

//根据特性,遍历检查

while(b->next != NULL)

{

if((b->next->data) == a->data + b->data)

{

a = b;

b = b->next;

}

else

{

isFibonacci = false;

break;

}

}

}

return isFibonacci;

}