數據結構考研分類復習真題 第二章 答案[22]

　　．[題目分析]本題明確指出單鏈表帶頭結點其結點數據是正整數且不相同要求利用直接插入原則把鏈表整理成遞增有序鏈表這就要求從第二結點開釋將各結點依次插入到有序鏈表中

　　LinkedList LinkListInsertSort(LinkedList la)∥la是帶頭結點的單鏈表其數據域是正整數本算法利用直接插入原則將鏈表整理成遞增的有序鏈表
　　{if(la>next!=null)∥鏈表不為空表
　　{p=la>next>next;∥p指向第一結點的後繼
　　la>next>next=null;∥直接插入原則認為第一元素有序然後從第二元素起依次插入
　　while(p!=null)
　　{r=p>next;∥暫存p的後繼
　　q=la;
　　while(q>next!=null&&q>next>data<p>data)q=q>next;∥查找插入位置
　　p>next=q>next;∥將p結點鏈入鏈表
　　q>next=p;
　　p=r;
　　}

　　與本題有類似敘述的題的解答

　　()本題也是鏈表排序問題雖沒象上題那樣明確要求利用直接插入的原則來排序仍可用上述算法求解這裡不再贅述

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23349.html