排序算法----無表頭鏈表插入排序，算法----

排序算法----無表頭鏈表插入排序，算法----

1. /*  
2. ==========================  
3.  功能：直接插入排序(由小到大)  
4.  返回：指向鏈表表 頭的指針  
5. ==========================  
6. */    
7. /*  
8.  直接插入排序的基本思想就是假設鏈表的前面n-1個節點是已經按鍵值  
9.  （就是用它排序的字段，我們取學號num為鍵值）排好序的，對於節點n在  
10.  這個序列中找插入位置，使得n插入後新序列仍然有序。按照這種思想，依次  
11.  對鏈表從頭到尾執行一遍，就可以使無序鏈表變為有序鏈表。  
12.    
13. 單向鏈表的直接插入排序圖示：  
14. ---->[1]---->[3]----> [2]...---->[n]---->[NULL]（原鏈表）  
15. head   1->next  3->next  2->next   n->next  
16.   
17. ---->[1]---->[NULL]（從原鏈表中取第1個節點作為只有一個節點的有序鏈表）  
18. head  
19. 圖11  
20.   
21. ---->[3]---->[2]...---->[n]---->[NULL]（原鏈表剩下用於直接插入排序的節點）  
22. first   3->next  2->next   n->next  
23. 圖12  
24.   
25. ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序後鏈表）  
26. head   1->next  2->next  3->next   n->next  
27.   
28. 圖13：有N個節點的鏈表直接插入排序  
29.   
30. 1、先在原鏈表中以第一個節點為一個有序鏈表，其余節點為待定節點。  
31. 2、從圖12鏈表中取節點，到圖11鏈表中定位插入。  
32. 3、上面圖示雖說畫了兩條鏈表，其實只有一條鏈表。在排序中，實質只增加了一個用於指向剩下需要排序節點的頭指針first罷了。  
33.    這一點請讀者務必搞清楚，要不然就可能認為它和上面的選擇排序法一樣了。  
34. */    
35. struct student *InsertSort(struct student *head)    
36. {    
37.     struct student *first; /*為原鏈表剩下用於直接插入排序的節點頭指針*/    
38.     struct student *t; /*臨時指針變量：插入節點*/    
39.     struct student *p; /*臨時指針變量*/    
40.     struct student *q; /*臨時指針變量*/    
41.     
42.     first = head->next; /*原鏈表剩下用於直接插入排序的節點鏈表：可根據圖12來理解。*/    
43.     head->next = NULL; /*只含有一個節點的鏈表的有序鏈表：可根據圖11來理解。*/    
44.     
45.     while (first != NULL) /*遍歷剩下無序的鏈表*/    
46.     {    
47.         /*注意：這裡for語句就是體現直接插入排序思想的地方*/    
48.         for (t = first, q = head; ((q! = NULL) && (q->num < t->num)); p = q, q = q->next); /*無序節點在有序鏈表中找插入的位置*/    
49.         
50.     /*退出for循環，就是找到了插入的位置*/    
51.     /*注意：按道理來說，這句話可以放到下面注釋了的那個位置也應該對的，但是就是不能。原因：你若理解了上面的第3條，就知道了。*/    
52.         first = first->next; /*無序鏈表中的節點離開，以便它插入到有序鏈表中。*/     
53.       
54.         if (q == head) /*插在第一個節點之前*/    
55.         {    
56.             head = t;    
57.         }    
58.         else /*p是q的前驅*/    
59.         {    
60.             p->next = t;    
61.         }    
62.         t->next = q; /*完成插入動作*/    
63.         /*first = first->next;*/    
64.     }    
65.     return head;    
66. }