## 問題描述 > 有一個帶頭結點的單鏈表對其排序，使之遞增有序。 ## 算法思想 > 本題是僅僅要求完成排序，因此我們很容易的想到使用插入排序算法完成單鏈表的排序。 首先將單鏈表的頭結點拆下，用指針p指向剩余的不帶頭結點的那部分鏈表的的第一個結點，指針q指向指針p指向的結點的下一個結點。然后將指針p指向的結點摘下，使用指針pre對帶有頭結點的那部分鏈表進行遍歷，如果指針pre所指結點的下一個結點的數據域值比指針p所指結點的數據域的值大，則將指針p所指結點插入到指針pre所指結點的后面，這樣便完成了一次排序過程。重新讓指針p指向不帶頭節點的那部分鏈表的第一個結點，指針q指向指針p所指結點的下一個結點，重新開始一次排序。 如圖所示：  ## 算法描述 ~~~ void Sort(LNode *head) { LNode *pre=head; LNode *p=pre->next; LNode *q=p->next; p->next=NULL; p=q; while(q){ q=p->next; pre=head; while(pre->next!=NULL&&pre->next->data<p->data){ pre=pre->next; } p->next=pre->next; pre->next=p; p=q; } } ~~~ 具體代碼見附件 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(LNode*); void Sort(LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head; head=(LNode*)malloc(sizeof(LNode)); head->next=NULL; head=CreatList(head); Print(head); Sort(head); Print(head); return 0; } //頭插法創建單鏈表 LinkList CreatList(LNode* head) { LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; L->next=head->next; head->next=L; scanf("%d",&x); } return head; } //直接插入排序 void Sort(LNode *head) { LNode *pre=head; LNode *p=pre->next; LNode *q=p->next; p->next=NULL; p=q; while(q){ q=p->next; pre=head; while(pre->next!=NULL&&pre->next->data<p->data){ pre=pre->next; } p->next=pre->next; pre->next=p; p=q; } } //打印全部結點 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~