首页 26考研 在职考研 直播好课 大纲冲刺

新东方在线 > 考研 > 计算机 > 考研计算机真题 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

42.(15分)已知一个带有表头结点的单链表，结点结构为 data link

2021-06-27 07:07:00来源：新东方在线

　　【题目】

　　42.(15分)已知一个带有表头结点的单链表，结点结构为 data link，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1;否则， 只返回0。要求：

　　(1)描述算法的基本设计思想; (2)描述算法的详细实现步骤;

　　(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C、C++或Java语言实现)，关键之处请给出简要注释。

　　【答案要点】

　　(1) 算法的基本设计思想：

　　定义两个指针变量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;否则，查找失败，返回0：

　　⑥算法结束。

　　(3) 算 法 实 现 ： typedef struct LNode{ int data：

　　struct LNode*link;

　　}*LinkList;

　　int SearchN(LinkList list，int k){

　　LinkList p，q;

　　int count=0： /*计数器赋初值*/

　　p=q=list->link; /*p和q指向链表表头结点的下一个结点*/ while(p!=NULL){

　　if(count

　　else q=q->link; /*q移到下一个结点*/ p=p->link; /*p移到下一个结点*/

　　}

　　if(countdata);/*查找成功*/

　　return(1);

　　}

　　}


考研公开课小程序

本文关键字: 已知一个带有表头结点的单链表

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
看课程 MBA 优惠券 0元学 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

名师试听

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10