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

admin2017-01-04  55

问题 已知非空链表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://kaotiyun.com/show/ehRi777K
0

最新回复(0)