数据结构考研分类复习真题 第二章 答案[37]

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

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

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

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

i=;∥i是la链表中结点的序号初始值为

while(p!=null)

if(p>data==i*ipre>data){i++;pre=p;p=p>next;}∥结点值间的关系符合题目要求

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

if(p!=null)return(false);∥未查到表尾就结束了

else return(true);∥成功返回

}∥算法结束

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

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

i=;

while(p>next!=null)∥初始p>next指向第二项

if(p>next>data= =i*ip>data)

{i++;p=p>next;}

if(p>next!=null)return(false);∥失败

else return(true);∥成功

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []