数据结构 | 每日一练（59）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．已知一个单链表中每个结点存放一个整数，并且结点数不少于 2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方

正确答案

ps：||代表注释

1. [题目分析] 本题要求对单链表结点的元素值进行运算，判断元素值是否等于其序号的平方减去其前驱的值。这里主要技术问题是结点的序号和前驱及后继指针的正确指向。

int Judge（LinkedList la）∥la是结点的元素为整数的单链表。本算法判断从第二结点开始，每个元素值是否等于其序号的平方减去其前驱的值，如是返回true；否则，返回false。

{p=la->next->next；∥p是工作指针，初始指向链表的第二项。

pre=la->next； ∥pre是p所指结点的前驱指针。

i=2； ∥i是la链表中结点的序号，初始值为2。

while（p!=null）

if（p->data==i*i-pre->data）{i++；pre=p；p=p->next；} ∥结点值间的关系符合题目要求

else break； ∥当前结点的值不等于其序号的平方减去前驱的值。

if（p!=null） return（false）； ∥未查到表尾就结束了。

else return（true）； ∥成功返回。

}∥算法结束。

[算法讨论]本题不设头结点也无影响。另外，算法中还可节省前驱指针pre，其算法片段如下：

p=la；∥假设无头结点，初始p指向第一元素结点。

i=2；

while（p->next!=null） ∥初始p->next指向第二项。

if（p->next->data= =i*i-p->data）

{i++；p=p->next；}

if（p->next!=null） return（false）；∥失败

else return（true）； ∥成功

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-