问题的关键是设计一个尽可能高效的算法,通过链表的一趟遍历,找到倒数第 k 个结点的位置。算法的基本设计思想是:定义两个指针变量 p 和 q,初始时均指向头结点的下一个结点(链表的第一个结点)。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
登录后提交答案