有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)

admin2019-01-16  31

问题 有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求:
    (1)给出算法的基本设计思想。
    (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。

选项

答案(1)算法的基本设计思想:本题实质上是一个排序问题。链表上的排序采用直接插入排序比较方便,即首先假定第一个结点有序,然后,从第二个结点开始,依次插入到前面有序链表中,最终达到整个链表有序。 (2)算法设计如下: typedef struct LNode{ int data; struct LNode*link; }*linkedlist; LinkedList LinkListSort(LinkedList list){ Lnode*p,*q: P=list->link: //p是工作指针,指向待排序的当前元素 list一>link=null: //假定第一个元素有序,即链表中现只有一个结点 while(P!=null){ r=p->link; //r是P的后继 q=list; if(q->data>p->data){ //处理待排序结点P比第一个元素结点小的情况 p一>link=list; list=P: //链表指针指向最小元素 } else{ //查找元素值最小的结点 while(q一>link==null&&q一>link一>datadata)q=q一>link; p->link=q->link; //将当前排序结点链入有序链表中 q一>link=P; } P=r; //p指向下个待排序结点 } }

解析
转载请注明原文地址:https://kaotiyun.com/show/6aRi777K
0

随机试题
最新回复(0)