|
试题 【年真题】 （分）己知一个带有表头结点的单链表夕结点结构为{data…link假设该链表只给出了头指针list在不改变链表的前提下请设计一个尽可能高效的算法查找链表中倒数第k个位置上的结点（k为正整数）若查找成功算法输出该结点的data值并返回否则只返回要求 （）描述算法的基本设计思想 （）描述算法的详细实现步骤 （）根据设计思想和实现步骤采用程序设计语言描述算法（使用C或C++或JAVA语言实现）关键之处请给出简要注释 参考答案: （）算法基本思想如下:从头至尾遍历单链表并用指针p指向当前结点的前k个结点当遍历到链表的最后一个结点时指针p所指向的结点即为所查找的结点 （）详细实现步骤增加两个指针变量和一个整型变量从链表头向后遍历其中指针p指向当前遍历的结点指针p指向p所指向结点的前k个结点如果pl之前没有k个结点那么p指问表头结点整型变量i表示当前遍历了多少个结点当i>k时指针p随着每次遍历也问前移动一个结点当遍历完成时p或者指向表头结点或者指向链表中倒数第k个位置上的结点 （）算法描述 int LocateElement(Linklist istint k) { p=list>link; p=list; i=; while(p) { pl=pl>link; i++; if(i>k)p=p>next; //如果i>k则p也往后移 } if(p==list) return ; //说明链表没有k个结点 else { printf(%d\np>data); return ; } } 返回《数据结构》考研复习精编 [] [] [] [] [] |
