已知一个带有表头结点的单链表,结点结构为:
data | link |
假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
1)描述算法的基本设计思想。
2)描述算法的详细实现步骤。
3)根据设计思想和实现步骤,采用程序设计语言描述算法(使用C、C++或Java语言实现),关键之处请给出简要注释。
1)算法的基本设计思想:
问题的关键是设计一个尽可能高效的算法,通过链表的一趟遍历,找到倒数第k个结点的位置。算法的基本设计思想:定义两个指针变量p和q,初始时均指向头结点的下一个结点(链表的第一个结点)。p指针沿链表移动,当p指针移动到第k个结点时,q指针开始与p指针同步移动;当p指针移动到最后一个结点时,q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。
2)算法的详细实现步骤:
① count=0,p和q指向链表表头结点的下一个结点;
② 若p为空,转⑤;
③ 若count等于k,则q指向下一个结点;否则,count=count+1;
④ p指向下一个结点,转②;
⑤ 若count等于k,则查找成功,输出该结点的data域的值,返回1;否则,说明k值超过了线性表的长度,查找失败,返回0;
⑥ 算法结束。
提示:算法程序题,如果能够写出数据结构类型定义,正确的算法思想都会至少给一半以上分数,如果能用伪代码写出自然更好,比较复杂的地方可以直接用文字表达。
【评分说明】①若所给出的算法采用一遍扫描方式就能得到正确结果,可给满分15分;若采用两遍或多遍扫描才能得到正确结果的,最高给10分;若采用递归算法得到正确结果的,最高给10分;若实现算法的空间复杂度过高(使用了大小与k有关的辅助数组),但结果正确,最高给10分;若实现的算法的空间复杂度过高(使用了大小与k有关的辅助数组),但结果正确,最高给10分。
② 若在算法基本思想描述和算法步骤描述中因文字表达没有非常清晰地反映出算法的思路,但在算法实现中能够清晰看出算法思想和步骤且正确,按照①的标准给分。
③ 若考生的答案中算法基本思想描述、算法步骤描述或算法实现中部分正确,可酌情给分。