查找带有头结点的单链表的倒数第k个位置上的结点
问题描述:
已知一个带有表头结点的单链表,结点结构为假设该链表只给出了头指针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。
⑥算法结束。
3)算法实现
typedef int ElemType; //链表数据的类型定义 typedef struct LNode{ //链表结点的结构定义 ElemType data; //结点数据 struct Lnode *link; //结点链接指针 }LNode, *LinkList; int Search_k(LinkList list,int k) { //查找链表list倒数第k个结点,并输出该结点data域的值 LNode *p = list->link, *q=list->link; //指计;p、q 指示第一个结点 int count=0; while (p!=NULL) { //遍历链表直到最后一个结点 if (count<k) count++; //计数,若 count<k 只移动 p else q=q->link; p-p->link; //之后让p、q同步移动 } //while if(count<k) return 0; //查找失败返回0 else{ //否则打印并返回1 printf("%d", q->data); return 1; } } //Search_k注意:若所给出的算法采用一遍扫描方式就能得到正确结果,可给满分15分;若采用两遍或多遍扫描才能得到正确结果的,最高分为10分。若采用递归算法得到正确结果的,最高给10分;若实现算法的空间复杂度过高(使用了大小与k有关的辅助数组),但结果正确,最高给10分。