问答题
已知非空线性链表由list指出,链结点的构造为(data,link)。请写一算法,将链表中数据域值最小的那个链结点移到链表的最前面(要求:不得额外申请新的链结点)。【北京航空航天大学2007年】
【正确答案】正确答案:算法的基本设计思想:首先耍查找最小值结点,然后将该结点从链表上摘下,再插入到链表的最前面。算法的代码: LinkList Delinsert(LinkList 1ist){ //本算法将链表中数据域值最小的那个结点移到链表的最前面 p=list一>next; //p为链表的工作指针 pre=list; //pre指向链表中数据域最小值结点的前驱 q=p; //q指向数据域最小值结点,初始假定是第一结点 while(P一>next!=NULL) { if(p一>next一>datadata)//找到新的最小值结点 { Pre=p; q=P一>next; } P=P一>next; } if(q!=list一>next) //若最小值是第一元素结点-则不需再操作 { pre一>next=q->next; //将最小值结点从链表上摘下 q一>next=list一>next; //将q结点插到链表最前面 list一>next=q; } return 1ist; }//Delinsert 本算法中假定list带有头结点,否则,插入操作变为q->next=list;list=q。
【答案解析】