42. （5分）已知一个带有表头结点的单链表，结点结构为 Data/link 假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法;查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回1∶否则，只返回0。要求∶ 1）描述算法的基本设计思想。 2）描述算法的详细实现步骤。 3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或 Java 语言实现），关键之处请给出简要注释。
【参考答案及解析】
（1）算法的基本设计思想（5分）： 问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k 个结点的位置。算法的基本设计思想是∶定义两个指针变量p和g，初始时均指向头结点的下一个结点（链表的第一个结点）。p指针沿链表移动;当p指针移动到第k个结点时，q指针开始与p指针同步移动;当p指针移动到最后一个结点时，q 指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。 （2）算法的详细实现步骤（5分）： ①count=0，p和 q 指向链表表头结点的下一个结点; ②若p为空，转⑤; ③若count 等于k，则 q指向下一个结点;否则，count=count+1; ④ p指向下一个结点，转②; ⑤若 count 等于k，则查找成功，输出该结点的 data 域的值，返回 1;否则，说明 k 值超过了线性表的长度，查找失败，返回 0; ⑥算法结束。 （3）算法实现（5分）： typedef int ElemType; //链表数据的类型定义 typedef struct LNode { //链表结点的结构定义 ElemType data; //结点数据 Struct Lnode *Link; //结点链接指针 }*LinkList; int Search_k (LinkList list, int k){ //查找链表list倒数第k个结点，并输出该结点data 域的值 LinkList 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
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
（1）算法的基本设计思想（5分）： 问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k 个结点的位置。算法的基本设计思想是∶定义两个指针变量p和g，初始时均指向头结点的下一个结点（链表的第一个结点）。p指针沿链表移动;当p指针移动到第k个结点时，q指针开始与p指针同步移动;当p指针移动到最后一个结点时，q 指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。 （2）算法的详细实现步骤（5分）： ①count=0，p和 q 指向链表表头结点的下一个结点; ②若p为空，转⑤; ③若count 等于k，则 q指向下一个结点;否则，count=count+1; ④ p指向下一个结点，转②; ⑤若 count 等于k，则查找成功，输出该结点的 data 域的值，返回 1;否则，说明 k 值超过了线性表的长度，查找失败，返回 0; ⑥算法结束。 （3）算法实现（5分）： typedef int ElemType; //链表数据的类型定义 typedef struct LNode { //链表结点的结构定义 ElemType data; //结点数据 Struct Lnode *Link; //结点链接指针 }*LinkList; int Search_k (LinkList list, int k){ //查找链表list倒数第k个结点，并输出该结点data 域的值 LinkList 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
正在整理中,欢迎在文下评论区提供答案解析,谢谢！