．[題目分析]本題實質上是一個排序問題要求不得使用除該鏈表結點以外的任何鏈結點空間鏈表上的排序采用直接插入排序比較方便即首先假定第一個結點有序然後從第二個結點開始依次插入到前面有序鏈表中最終達到整個鏈表有序
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;
}
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23351.html
