==========================
功能：選擇排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
/*
選擇排序的基本思想就是反復(fù)從還未排好序的那些節(jié)點(diǎn)中，
選出鍵值（就是用它排序的字段，我們?nèi)W(xué)號(hào)num為鍵值）最小的節(jié)
點(diǎn)，
依次重新組合成一個(gè)鏈表。
我認(rèn)為寫鏈表這類程序，關(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]（原鏈表）
head 1->next 3->next 2->next
n->next
---->[NULL]（空鏈表）
first
tail
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后鏈表）
first
1->next 2->next 3->next tail->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 *SelectSort(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,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) /*如果有序鏈表目前還是一個(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指向原h(huán)ead->next,即第二個(gè)節(jié)點(diǎn)，就OK*/
}
else /*如果不是第一個(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為鍵值）排好
序的，對(duì)于節(jié)點(diǎn)n在
這個(gè)序列中找插入位置，使得n插入后新序列仍然有序。按照這種思想，依次
對(duì)鏈表從頭到尾執(zhí)行一遍，就可以使無(wú)序鏈
表變?yōu)橛行蜴湵怼?
單向鏈表的直接插入排序圖示：
---->[1]---->[3]---->
[2]...---->[n]---->[NULL]（原鏈表）
head 1->next 3->next
2->next n->next
---->[1]---->[NULL]（從原鏈表中取第1個(gè)節(jié)點(diǎn)作為只有一個(gè)節(jié)點(diǎn)的有序鏈表）
head
圖11
---->[3]---->[2]...---->[n]---->[NULL]（原鏈表剩下用于直接插入排序的節(jié)點(diǎn)）
first
3->next 2->next n->next
圖12
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后鏈表）
head
1->next 2->next 3->next n->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ō)畫了兩條鏈表，其實(shí)只有一條鏈表。在排序中，實(shí)質(zhì)只增加了一個(gè)用于指向剩下需要排序節(jié)點(diǎn)的頭指針first罷了。
這一點(diǎn)請(qǐng)讀者務(wù)必搞清楚，要不然就可能認(rèn)為它和上面的選擇排序法一樣了。
*/
struct student
*InsertSort(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) /*遍歷剩下無(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ō)，這句話可以放到下面注釋了的那個(gè)位置也應(yīng)該對(duì)的，但是就是不能。原因：你若理解了上面的第3條，就知道了。*/
first = first->next; /*無(wú)序鏈表中的節(jié)點(diǎn)離開(kāi)，以便它插入到有序鏈表中。*/
if (q ==
head) /*插在第一個(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í)，
就將它們互換。
單向鏈表的冒泡排序圖示：
---->[1]---->[3]---->[2]...---->
[n]---->[NULL]（原鏈表）
head 1->next 3->next 2->next
n->next
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后鏈表）
head
1->next 2->next 3->next n->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的后繼節(jié)點(diǎn)，我們用p2保存
p1->next->next指針。即：p2=p1->next->next，則
有：
[ ]---->[p]---------->[q]---->[ ]（排序前）
p1->next p1->next->next p2->next
圖15
[ ]---->[q]---------->[p]---->[ ]（排序后）
圖16
1、排序后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,所以
p1->next->next=p2->next;
3、在圖15中p2->next原是q發(fā)出來(lái)的指向，排序后圖16中
q的指向要變?yōu)橹赶騪的，而原來(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)就是記錄了每次最后一
次節(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)的前面，主要是為了便于比較。因?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;
/*結(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)生“野指針”，即地址不確定的指針變量*/
return head;
}
/*
==========================
功能：插入有序鏈表的某個(gè)節(jié)點(diǎn)的后面(從小到大)
返
回：指向鏈表表頭的指針
==========================
*/
/*
有序鏈表插入節(jié)點(diǎn)示意圖：
---->[NULL]（空有序鏈表）
head
圖18：空有序鏈表（空有序鏈表好解決，直接讓head指向它就是了。）
以下討論不為空的有序鏈表。
---->[1]---->[2]---->[3]...---->
[n]---->[NULL]（有序鏈表）
head 1->next 2->next 3->next
n->next
圖18：有N個(gè)節(jié)點(diǎn)的有序鏈表
插入node節(jié)點(diǎn)的位置有兩種情況：一是第一個(gè)節(jié)點(diǎn)前，二是其它節(jié)點(diǎn)前或后。
---->[node]---->[1]---->[2]---->[3]...---->[n]---->[NULL]
head
node->next 1->next 2->next 3->next n->next
圖19：node節(jié)點(diǎn)插在第一個(gè)節(jié)點(diǎn)前
---->[1]---->[2]---->[3]...---->[node]...---->[n]---->[NULL]
head
1->next 2->next 3->next node->next n->next
圖20：node節(jié)點(diǎn)插在其它節(jié)點(diǎn)后
*/
struct student *SortInsert(struct student
*head, struct student *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; /*后移一個(gè)節(jié)點(diǎn)*/
}
if
(p == head) /*剛好插入第一個(gè)節(jié)點(diǎn)之前*/
{
node->next = p;
head =
node;
}
else /*插入其它節(jié)點(diǎn)之后*/
{
t->next = node;
/*把node節(jié)點(diǎn)加進(jìn)去*/
node->next = p;
}
n += 1;
/*插入完畢，節(jié)點(diǎn)總數(shù)加1*/
return head;
}
/*
測(cè)試代碼如下：
*/
/*測(cè)試SelectSort():請(qǐng)編譯時(shí)去掉注釋塊*/
/*
head = SelectSort(head);
Print(head);
*/
/*測(cè)
試InsertSort():請(qǐng)編譯時(shí)去掉注釋塊*/
/*
head = InsertSort(head);
Print(head);
*/
/*測(cè)試BubbleSort():請(qǐng)編譯時(shí)去掉注釋塊*/
/*
head = BubbleSort(head);
Print(head);
*/
/*測(cè)試SortInsert():上面創(chuàng)建鏈表，輸入節(jié)點(diǎn)時(shí)請(qǐng)注意學(xué)號(hào)num從小到大的順序。請(qǐng)編譯時(shí)去掉注釋塊*/
/*
stu = (struct student *)malloc(LEN);
printf("\nPlease
input insert node -- num,score: ");
scanf("%ld,%f",&stu->num,&stu->score);
head
= SortInsert(head,stu);
free(stu);
stu = NULL;
Print(head);
*/