2. 考研
  3. 已知非空链表A，其指针是list，链表中的结点由两部分组成：数据域data和指针域link。设计一个算法，将链表中数据域值最小的那个链结点移到链表的最前面，在不额外申请新的链结点的情况下，使得算法时间复杂度和空间复杂度尽可能低。要求： (1)给出算

已知非空链表A，其指针是list，链表中的结点由两部分组成：数据域data和指针域link。设计一个算法，将链表中数据域值最小的那个链结点移到链表的最前面，在不额外申请新的链结点的情况下，使得算法时间复杂度和空间复杂度尽可能低。要求： (1)给出算

admin2017-01-04  102
问题 已知非空链表A，其指针是list，链表中的结点由两部分组成：数据域data和指针域link。设计一个算法，将链表中数据域值最小的那个链结点移到链表的最前面，在不额外申请新的链结点的情况下，使得算法时间复杂度和空间复杂度尽可能低。要求：
    (1)给出算法的基本设计思想。
    (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
选项
答案(1)算法的基本设计思想：首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链：上摘下(不是删除并回收空间)，再插入到链表的最前面。 (2)算法的实现如下： typedef struct LNode{ char data； struct LNode*link； }*Linkedlist； LinkedList delinsert(LinkedList list){ ／／将链表中数据域值最小的那个结点移到链表的最前面 Linkedlist*P，*pre，*q； P=list一＞link： ／／p是链表的工作指针 pre=list； ／／pre指向链表中数据域最小值结点的前驱 q=P； ／／q指向数据域最小值结点，初始假定是第一结点 while(p一＞link!=null){ if(p一＞link一＞data＜q一＞data){pre=P；q=p一＞link；} ／／找到新的最小值结点 p=p一＞link； } if(q!=list一＞link){ ／／若最小值是第一元素结点，则不需再操作 pre一＞link=q一＞link：／／将最小值结点从链表上摘下 q一＞link=list一＞link； ／／将q结点插到链表最前面 list一＞link=q； } }／／算法结束
解析
转载请注明原文地址:https://www.kaotiyun.com/show/ehRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)