数据结构考研分类复习真题 第二章 答案[21]

．[题目分析]本题实质上是一个排序问题要求不得使用除该链表结点以外的任何链结点空间链表上的排序采用直接插入排序比较方便即首先假定第一个结点有序然后从第二个结点开始依次插入到前面有序链表中最终达到整个链表有序

LinkedList LinkListSort(LinkedList list)∥list是不带头结点的线性链表链表结点构造为data和link两个域data是数据域link是指针域本算法将该链表按结点数据域的值的大小从小到大重新链接

{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>data<p>data)q=q>link;

p>link=q>link;∥将当前排序结点链入有序链表中

q>link=p;}

p=r;∥p指向下个待排序结点

}

}

[算法讨论]算法时间复杂度的分析与用顺序存储结构时的情况相同但顺序存储结构将第i(i>)个元素插入到前面第至第i个元素的有序表时是将第i个元素先与第i个元素比较而在链表最佳情况均是和第一元素比较两种存储结构下最佳和最差情况的比较次数相同在链表情况下不移动元素而是修改结点指针

另一说明是本题中线性链表list不带头结点而且要求不得使用除该链表以外的任何链结点空间所以处理复杂需要考虑当前结点元素值比有序链表第一结点的元素值还小的情况这时要修改链表指针list如果list是头结点的指针则相应处理要简单些其算法片段如下

p=list>link;∥p指向第一元素结点

list>link=null;∥有序链表初始化为空

while(p!=null)

{r=p>link;∥保存后继

q=list;

while(q>link!=null && q>link>data<p>data)q=q>link;

p>link=q>link;

q>link=p;

q=r;

}

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []