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

admin2015-12-30  45

问题 已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。
要求:
根据设计思想和实现步骤,采用程序设计语言描述算法(使用C、C++或Java语言实现),关键之处请给出简要注释。

选项

答案算法实现: 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

解析 考查链表的查找操作,查找链表中倒数第k个结点。
转载请注明原文地址:https://kaotiyun.com/show/ZKxi777K
0

最新回复(0)