1、C語(yǔ)言鏈表排序=功能：選擇排序(由小到大 )返回：指向鏈表表頭的指針=*/*選擇排序的基本思想就是反復(fù)從還未排好序的那些節(jié)點(diǎn)中，選出鍵值（就是用它排序的字段，我們?nèi)W(xué)號(hào)num 為鍵值）最小的節(jié)點(diǎn)，依次重新組合成一個(gè)鏈表。我認(rèn)為寫(xiě)鏈表這類(lèi)程序，關(guān)鍵是理解：head存儲(chǔ)的是第一個(gè)節(jié)點(diǎn)的地址，head->next存儲(chǔ)的是第二個(gè)節(jié)點(diǎn)的地址；任意一個(gè)節(jié)點(diǎn)p 的地址，只能通過(guò)它前一個(gè)節(jié)點(diǎn)的next來(lái)求得。單向鏈表的選擇排序圖示：->1->3->2.->n->NULL（原鏈表）head1->next 3->next 2->nextn->next-&

2、gt;NULL （空鏈表）firsttail->1->2->3.->n->NULL（排序后鏈表）first1->next 2->next 3->nexttail->next圖 10：有N 個(gè)節(jié)點(diǎn)的鏈表選擇排序1、先在原鏈表中找最小的，找到一個(gè)后就把它放到另一個(gè)空的鏈表中；2、空鏈表中安放第一個(gè)進(jìn)來(lái)的節(jié)點(diǎn)，產(chǎn)生一個(gè)有序鏈表,并且讓它在原鏈表中分離出來(lái)（此時(shí)要注意原鏈表中出來(lái)的是第一個(gè)節(jié)點(diǎn)還是中間其它節(jié)點(diǎn)）；3、繼續(xù)在原鏈表中找下一個(gè)最小的，找到后把它放入有序鏈表的尾指針的next, 然后它變成其尾指針；*/struct student *Se

3、lectSort(struct student *head)struct student *first; /*排列后有序鏈的表頭指針*/struct student *tail; /*排列后有序鏈的表尾指針*/struct student *p_min; /*保留鍵值更小的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針*/struct student *min; /*存儲(chǔ)最小節(jié)點(diǎn)*/struct student *p; /*當(dāng)前比較的節(jié)點(diǎn)*/first = NULL;while (head != NULL) /*在鏈表中找鍵值最小的節(jié)點(diǎn)。*/*注意：這里for 語(yǔ)句就是體現(xiàn)選擇排序思想的地方*/for (p=head,

4、min=head; p->next!=NULL; p=p->next) /*循環(huán)遍歷鏈表中的節(jié)點(diǎn)，找出此時(shí)最小的節(jié)點(diǎn)。 */if (p->next->num < min->num) /*找到一個(gè)比當(dāng)前min 小的節(jié)點(diǎn)。 */p_min = p; /*保存找到節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)：顯然p->next 的前驅(qū)節(jié)點(diǎn)是p。 */min = p->next; /*保存鍵值更小的節(jié)點(diǎn)。*/*上面 for 語(yǔ)句結(jié)束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應(yīng)的條件判斷，安排它離開(kāi)原來(lái)的鏈表。 */*第一件事 */if (first = NULL) /*如果

5、有序鏈表目前還是一個(gè)空鏈表*/first = min; /*第一次找到鍵值最小的節(jié)點(diǎn)。*/tail = min; /* 注意：尾指針讓它指向最后的一個(gè)節(jié)點(diǎn)。*/else /* 有序鏈表中已經(jīng)有節(jié)點(diǎn)*/tail->next = min; /*把剛找到的最小節(jié)點(diǎn)放到最后，即讓尾指針的next 指向它。 */tail = min; /* 尾指針也要指向它。*/*第二件事 */if (min = head) /*如果找到的最小節(jié)點(diǎn)就是第一個(gè)節(jié)點(diǎn)*/head = head->next; /*顯然讓 head 指向原 head->next, 即第二個(gè)節(jié)點(diǎn)，就OK*/else /* 如果不

6、是第一個(gè)節(jié)點(diǎn)*/p_min->next = min->next; /* 前次最小節(jié)點(diǎn)的 next 指向當(dāng)前 min 的 next, 這樣就讓 min 離開(kāi)了原鏈表。 */if (first != NULL) /*循環(huán)結(jié)束得到有序鏈表first*/tail->next = NULL; /*單向鏈表的最后一個(gè)節(jié)點(diǎn)的next 應(yīng)該指向 NULL*/head = first;return head;/*=功能：直接插入排序(由小到大 )返回：指向鏈表表頭的指針=*/*直接插入排序的基本思想就是假設(shè)鏈表的前面n-1 個(gè)節(jié)點(diǎn)是已經(jīng)按鍵值（就是用它排序的字段，我們?nèi)W(xué)號(hào)num 為鍵值）排好

7、序的，對(duì)于節(jié)點(diǎn)n 在這個(gè)序列中找插入位置，使得n 插入后新序列仍然有序。按照這種思想，依次對(duì)鏈表從頭到尾執(zhí)行一遍，就可以使無(wú)序鏈表變?yōu)橛行蜴湵?。單向鏈表的直接插入排序圖示：->1->3->2.->n->NULL（原鏈表）head1->next 3->next 2->nextn->next->1->NULL（從原鏈表中取第1 個(gè)節(jié)點(diǎn)作為只有一個(gè)節(jié)點(diǎn)的有序鏈表）head圖 11->3->2.->n->NULL（原鏈表剩下用于直接插入排序的節(jié)點(diǎn)）first3->next 2->nextn->n

8、ext圖 12->1->2->3.->n->NULL（排序后鏈表）head1->next 2->next 3->nextn->next圖 13 ：有 N 個(gè)節(jié)點(diǎn)的鏈表直接插入排序1、先在原鏈表中以第一個(gè)節(jié)點(diǎn)為一個(gè)有序鏈表，其余節(jié)點(diǎn)為待定節(jié)點(diǎn)。2、從圖 12 鏈表中取節(jié)點(diǎn)，到圖11 鏈表中定位插入。3、上面圖示雖說(shuō)畫(huà)了兩條鏈表，其實(shí)只有一條鏈表。在排序中，實(shí)質(zhì)只增加了一個(gè)用于指向剩下需要排序節(jié)點(diǎn)的頭指針first 罷了。這一點(diǎn)請(qǐng)讀者務(wù)必搞清楚，要不然就可能認(rèn)為它和上面的選擇排序法一樣了。*/struct student *InsertSort

9、(struct student *head)struct student *first; /*為原鏈表剩下用于直接插入排序的節(jié)點(diǎn)頭指針*/struct student *t; /*臨時(shí)指針變量：插入節(jié)點(diǎn)*/struct student *p; /*臨時(shí)指針變量 */struct student *q; /*臨時(shí)指針變量 */first = head->next; /*原鏈表剩下用于直接插入排序的節(jié)點(diǎn)鏈表：可根據(jù)圖12 來(lái)理解。 */head->next = NULL; /*只含有一個(gè)節(jié)點(diǎn)的鏈表的有序鏈表：可根據(jù)圖11 來(lái)理解。 */while (first != NULL) /*遍

10、歷剩下無(wú)序的鏈表*/*注意：這里for 語(yǔ)句就是體現(xiàn)直接插入排序思想的地方*/for (t=first, q=head; (q!=NULL) && (q->num < t->num); p=q, q=q->next); /*無(wú)序節(jié)點(diǎn)在有序鏈表中找插入的位置*/*退出 for 循環(huán)，就是找到了插入的位置*/*注意：按道理來(lái)說(shuō)，這句話(huà)可以放到下面注釋了的那個(gè)位置也應(yīng)該對(duì)的，但是就是不能。原因：你若理解了上面的第3 條，就知道了。*/first = first->next; /*無(wú)序鏈表中的節(jié)點(diǎn)離開(kāi)，以便它插入到有序鏈表中。*/if (q = head)

11、 /*插在第一個(gè)節(jié)點(diǎn)之前*/head = t;else /*p 是 q 的前驅(qū) */p->next = t;t->next = q; /* 完成插入動(dòng)作*/*first = first->next;*/return head;/*=功能：冒泡排序(由小到大 )返回：指向鏈表表頭的指針=*/*直接插入排序的基本思想就是對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部節(jié)點(diǎn)，自上而下對(duì)相鄰的兩個(gè)節(jié)點(diǎn)依次進(jìn)行比較和調(diào)整，讓鍵值（就是用它排序的字段，我們?nèi)W(xué)號(hào)num 為鍵值）較大的節(jié)點(diǎn)往下沉，鍵值較小的往上冒。即：每當(dāng)兩相鄰的節(jié)點(diǎn)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。單向鏈表的冒泡排序圖示

12、：->1->3->2.->n->NULL（原鏈表）head1->next 3->next 2->nextn->next->1->2->3.->n->NULL（排序后鏈表）head1->next 2->next 3->nextn->next圖 14 ：有 N 個(gè)節(jié)點(diǎn)的鏈表冒泡排序任意兩個(gè)相鄰節(jié)點(diǎn) p、 q 位置互換圖示 :假設(shè) p1->next 指向 p，那么顯然p1->next->next就指向 q,p1->next->next->next就指向 q

13、的后繼節(jié)點(diǎn)，我們用p2 保存p1->next->next指針。即： p2=p1->next->next，則有： ->p->q-> （排序前）p1->next p1->next->next p2->next圖 15 ->q->p-> （排序后）圖 161、排序后q 節(jié)點(diǎn)指向p 節(jié)點(diǎn)，在調(diào)整指向之前，我們要保存原p 的指向節(jié)點(diǎn)地址，即：p2=p1->next->next；2、順著這一步一步往下推 ,排序后圖 16 中 p1->next->next 要指的是 p2->next, 所以 p

14、1->next->next=p2->next;3、在圖 15 中 p2->next 原是 q 發(fā)出來(lái)的指向，排序后圖 16 中 q 的指向要變?yōu)橹赶?p 的，而原來(lái) p1->next 是指向 p 的，所以 p2->next=p1->next;4、在圖 15 中 p1->next 原是指向 p 的，排序后圖 16 中 p1->next 要指向 q, 原來(lái) p1->next->next （即 p2) 是指向 q 的，所以 p1->next=p2;5、至此，我們完成了相鄰兩節(jié)點(diǎn)的順序交換。6、下面的程序描述改進(jìn)了一點(diǎn)就是記錄了每

15、次最后一次節(jié)點(diǎn)下沉的位置，這樣我們不必每次都從頭到尾的掃描，只需要掃描到記錄點(diǎn)為止。因?yàn)楹竺娴亩家呀?jīng)是排好序的了。*/struct student *BubbleSort(struct student *head)struct student *endpt; /*控制循環(huán)比較*/struct student *p; /*臨時(shí)指針變量 */struct student *p1;struct student *p2;p1 = (struct student *)malloc(LEN);p1->next = head; /*注意理解：我們?cè)黾右粋€(gè)節(jié)點(diǎn)，放在第一個(gè)節(jié)點(diǎn)的前面，主要是為了便于比較。

16、因?yàn)榈谝粋€(gè)節(jié)點(diǎn)沒(méi)有前驅(qū)，我們不能交換地址。*/head = p1; /* 讓 head 指向 p1 節(jié)點(diǎn)，排序完成后，我們?cè)侔裵1 節(jié)點(diǎn)釋放掉 */for (endpt=NULL; endpt!=head; endpt=p) /*結(jié)合第 6 點(diǎn)理解 */for (p=p1=head; p1->next->next!=endpt; p1=p1->next)if (p1->next->num > p1->next->next->num) /*如果前面的節(jié)點(diǎn)鍵值比后面節(jié)點(diǎn)的鍵值大，則交換*/p2 = p1->next->next; /

17、*結(jié)合第1 點(diǎn)理解*/p1->next->next = p2->next; /*結(jié)合第2 點(diǎn)理解*/p2->next = p1->next; /*結(jié)合第3 點(diǎn)理解*/p1->next = p2; /*結(jié)合第4 點(diǎn)理解 */p = p1->next->next; /*結(jié)合第6 點(diǎn)理解*/p1 = head; /* 把 p1 的信息去掉 */head = head->next; /*讓 head 指向排序后的第一個(gè)節(jié)點(diǎn)*/free(p1); /* 釋放 p1*/p1 = NULL; /*p1置為 NULL ，保證不產(chǎn)生“野指針 ”，即地址不確定

18、的指針變量*/return head;/*=功能：插入有序鏈表的某個(gè)節(jié)點(diǎn)的后面(從小到大 )返回：指向鏈表表頭的指針=*/*有序鏈表插入節(jié)點(diǎn)示意圖：->NULL （空有序鏈表）head圖 18 ：空有序鏈表（空有序鏈表好解決，直接讓head 指向它就是了。）以下討論不為空的有序鏈表。->1->2->3.->n->NULL（有序鏈表）head1->next 2->next 3->nextn->next圖 18 ：有 N 個(gè)節(jié)點(diǎn)的有序鏈表插入 node 節(jié)點(diǎn)的位置有兩種情況：一是第一個(gè)節(jié)點(diǎn)前，二是其它節(jié)點(diǎn)前或后。->node->

19、;1->2->3.->n->NULLhead node->next 1->next 2->next 3->nextn->next圖 19 ： node 節(jié)點(diǎn)插在第一個(gè)節(jié)點(diǎn)前->1->2->3.->node.->n->NULLhead1->next 2->next 3->nextnode->next n->next圖 20 ： node 節(jié)點(diǎn)插在其它節(jié)點(diǎn)后*/struct student *SortInsert(struct student *head, struct stud

20、ent *node)struct student *p; /*p保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址*/struct student *t; /*臨時(shí)指針變量*/if (head = NULL) /*處理空的有序鏈表*/head = node;node->next = NULL;n += 1; /* 插入完畢，節(jié)點(diǎn)總數(shù)加1*/return head;p = head; /* 有序鏈表不為空*/while (p->num < node->num && p != NULL) /*p 指向的節(jié)點(diǎn)的學(xué)號(hào)比插入節(jié)點(diǎn)的學(xué)號(hào)小，并且它不等于 NULL*/t = p; /* 保存當(dāng)前節(jié)點(diǎn)的前驅(qū)，以便后面判斷后處理*/p = p->next; /*