鏈表各類操作詳解 .
分類： C/C++ 數(shù)據(jù)結(jié)構(gòu) 2011-07-07 22:44 2625人閱讀 評(píng)論(24) 收藏 舉報(bào)
鏈表概述
鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。它是動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)。它可以根據(jù)需要開辟內(nèi)存單元。鏈表有一個(gè)“頭指針”變量，以head表示，它存放一個(gè)地址。該地址指向一個(gè)元素。鏈表中每一個(gè)元素稱為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都應(yīng)包括兩個(gè)部分：一為用戶需要用的實(shí)際數(shù)據(jù)，二為下一個(gè)結(jié)點(diǎn)的地址。因此，head指向第一個(gè)元素：第一個(gè)元素又指向第二個(gè)元素；……，直到最后一個(gè)元素，該元素不再指向其它元素，它稱為“表尾”，它的地址部分放一個(gè)“NULL”（表示“空地址”），鏈表到此結(jié)束。
鏈表的各類操作包括：學(xué)習(xí)單向鏈表的創(chuàng)建、刪除、 插入（無(wú)序、有序）、輸出、 排序（選擇、插入、冒泡）、反序等等。
單向鏈表的圖示：
---->[NULL]
head
圖1：空鏈表
---->[p1]---->[p2]...---->[pn]---->[NULL]
head p1->next p2->next pn->next
圖2：有N個(gè)節(jié)點(diǎn)的鏈表
創(chuàng)建n個(gè)節(jié)點(diǎn)的鏈表的函數(shù)為：
[cpp] view plaincopyprint?
01.#include "stdlib.h"
02.#include "stdio.h"
03.
04.#define NULL 0
05.#define LEN sizeof(struct student)
06.
07.struct student
08.{
09. int num; //學(xué)號(hào)
10. float score; //分?jǐn)?shù)，其他信息可以繼續(xù)在下面增加字段
11. struct student *next; //指向下一節(jié)點(diǎn)的指針
12.};
13.
14.int n; //節(jié)點(diǎn)總數(shù)
15./*
16.==========================
17.功能：創(chuàng)建n個(gè)節(jié)點(diǎn)的鏈表
18.返回：指向鏈表表頭的指針
19.==========================
20.*/
21.struct student *Create()
22.{
23. struct student *head; //頭節(jié)點(diǎn)
24. struct student *p1 = NULL; //p1保存創(chuàng)建的新節(jié)點(diǎn)的地址
25. struct student *p2 = NULL; //p2保存原鏈表最后一個(gè)節(jié)點(diǎn)的地址
26.
27. n = 0; //創(chuàng)建前鏈表的節(jié)點(diǎn)總數(shù)為0：空鏈表
28. p1 = (struct student *) malloc (LEN); //開辟一個(gè)新節(jié)點(diǎn)
29. p2 = p1; //如果節(jié)點(diǎn)開辟成功，則p2先把它的指針保存下來(lái)以備后用
30.
31. if(p1==NULL) //節(jié)點(diǎn)開辟不成功
32. {
33. printf ("\nCann't create it, try it again in a moment!\n");
34. return NULL;
35. }
36. else //節(jié)點(diǎn)開辟成功
37. {
38. head = NULL; //開始head指向NULL
39. printf ("Please input %d node -- num,score: ", n + 1);
40. scanf ("%d %f", &(p1->num), &(p1->score)); //錄入數(shù)據(jù)
41. }
42. while(p1->num != 0) //只要學(xué)號(hào)不為0，就繼續(xù)錄入下一個(gè)節(jié)點(diǎn)
43. {
44. n += 1; //節(jié)點(diǎn)總數(shù)增加1個(gè)
45. if(n == 1) //如果節(jié)點(diǎn)總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點(diǎn)p1
46. {
47. head = p1;
48. p2->next = NULL; //此時(shí)的p2就是p1,也就是p1->next指向NULL。
49. }
50. else
51. {
52. p2->next = p1; //指向上次下面剛剛開辟的新節(jié)點(diǎn)
53. }
54.
55. p2 = p1; //把p1的地址給p2保留，然后p1產(chǎn)生新的節(jié)點(diǎn)
56.
57. p1 = (struct student *) malloc (LEN);
58. printf ("Please input %d node -- num,score: ", n + 1);
59. scanf ("%d %f", &(p1->num), &(p1->score));
60. }
61. p2->next = NULL; //此句就是根據(jù)單向鏈表的最后一個(gè)節(jié)點(diǎn)要指向NULL
62.
63. free(p1); //p1->num為0的時(shí)候跳出了while循環(huán)，并且釋放p1
64. p1 = NULL; //特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針
65. return head; //返回創(chuàng)建鏈表的頭指針
66.}
#include "stdlib.h"
#include "stdio.h"
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
int num; //學(xué)號(hào)
float score; //分?jǐn)?shù)，其他信息可以繼續(xù)在下面增加字段
struct student *next; //指向下一節(jié)點(diǎn)的指針
};
int n; //節(jié)點(diǎn)總數(shù)
/*
==========================
功能：創(chuàng)建n個(gè)節(jié)點(diǎn)的鏈表
返回：指向鏈表表頭的指針
==========================
*/
struct student *Create()
{
struct student *head; //頭節(jié)點(diǎn)
struct student *p1 = NULL; //p1保存創(chuàng)建的新節(jié)點(diǎn)的地址
struct student *p2 = NULL; //p2保存原鏈表最后一個(gè)節(jié)點(diǎn)的地址
n = 0; //創(chuàng)建前鏈表的節(jié)點(diǎn)總數(shù)為0：空鏈表
p1 = (struct student *) malloc (LEN); //開辟一個(gè)新節(jié)點(diǎn)
p2 = p1; //如果節(jié)點(diǎn)開辟成功，則p2先把它的指針保存下來(lái)以備后用
if(p1==NULL) //節(jié)點(diǎn)開辟不成功
{
printf ("\nCann't create it, try it again in a moment!\n");
return NULL;
}
else //節(jié)點(diǎn)開辟成功
{
head = NULL; //開始head指向NULL
printf ("Please input %d node -- num,score: ", n + 1);
scanf ("%d %f", &(p1->num), &(p1->score)); //錄入數(shù)據(jù)
}
while(p1->num != 0) //只要學(xué)號(hào)不為0，就繼續(xù)錄入下一個(gè)節(jié)點(diǎn)
{
n += 1; //節(jié)點(diǎn)總數(shù)增加1個(gè)
if(n == 1) //如果節(jié)點(diǎn)總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點(diǎn)p1
{
head = p1;
p2->next = NULL; //此時(shí)的p2就是p1,也就是p1->next指向NULL。
}
else
{
p2->next = p1; //指向上次下面剛剛開辟的新節(jié)點(diǎn)
}
p2 = p1; //把p1的地址給p2保留，然后p1產(chǎn)生新的節(jié)點(diǎn)
p1 = (struct student *) malloc (LEN);
printf ("Please input %d node -- num,score: ", n + 1);
scanf ("%d %f", &(p1->num), &(p1->score));
}
p2->next = NULL; //此句就是根據(jù)單向鏈表的最后一個(gè)節(jié)點(diǎn)要指向NULL
free(p1); //p1->num為0的時(shí)候跳出了while循環(huán)，并且釋放p1
p1 = NULL; //特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針
return head; //返回創(chuàng)建鏈表的頭指針
} 輸出鏈表中節(jié)點(diǎn)的函數(shù)為：
[cpp] view plaincopyprint?
01./*
02.===========================
03. 功能：輸出節(jié)點(diǎn)
04. 返回： void
05.===========================
06.*/
07.void Print(struct student *head)
08.{
09. struct student *p;
10. printf ("\nNow , These %d records are:\n", n);
11. p = head;
12. if(head != NULL) //只要不是空鏈表，就輸出鏈表中所有節(jié)點(diǎn)
13. {
14. printf("head is %o\n", head); //輸出頭指針指向的地址
15. do
16. {
17. /*
18. 輸出相應(yīng)的值：當(dāng)前節(jié)點(diǎn)地址、各字段值、當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)地址。
19. 這樣輸出便于讀者形象看到一個(gè)單向鏈表在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)，和我們
20. 設(shè)計(jì)的圖示是一模一樣的。
21. */
22. printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);
23. p = p->next; //移到下一個(gè)節(jié)點(diǎn)
24. }
25. while (p != NULL);
26. }
27.}
/*
===========================
功能：輸出節(jié)點(diǎn)
返回： void
===========================
*/
void Print(struct student *head)
{
struct student *p;
printf ("\nNow , These %d records are:\n", n);
p = head;
if(head != NULL) //只要不是空鏈表，就輸出鏈表中所有節(jié)點(diǎn)
{
printf("head is %o\n", head); //輸出頭指針指向的地址
do
{
/*
輸出相應(yīng)的值：當(dāng)前節(jié)點(diǎn)地址、各字段值、當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)地址。
這樣輸出便于讀者形象看到一個(gè)單向鏈表在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)，和我們
設(shè)計(jì)的圖示是一模一樣的。
*/
printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);
p = p->next; //移到下一個(gè)節(jié)點(diǎn)
}
while (p != NULL);
}
} 單向鏈表的刪除圖示：
---->[NULL]
head
圖3：空鏈表
從圖3可知，空鏈表顯然不能刪除
---->[1]---->[2]...---->[n]---->[NULL]（原鏈表）
head 1->next 2->next n->next
---->[2]...---->[n]---->[NULL]（刪除后鏈表）
head 2->next n->next
圖4：有N個(gè)節(jié)點(diǎn)的鏈表，刪除第一個(gè)節(jié)點(diǎn)
結(jié)合原鏈表和刪除后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
1、你要明白head就是第1個(gè)節(jié)點(diǎn)，head->next就是第2個(gè)節(jié)點(diǎn)；
2、刪除后head指向第2個(gè)節(jié)點(diǎn)，就是讓head=head->next,OK這樣就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原鏈表）
head 1->next 2->next 3->next n->next
---->[1]---->[3]...---->[n]---->[NULL]（刪除后鏈表）
head 1->next 3->next n->next
圖5：有N個(gè)節(jié)點(diǎn)的鏈表，刪除中間一個(gè)（這里圖示刪除第2個(gè)）
結(jié)合原鏈表和刪除后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
1、你要明白head就是第1個(gè)節(jié)點(diǎn)，1->next就是第2個(gè)節(jié)點(diǎn)，2->next就是第3個(gè)節(jié)點(diǎn)；
2、刪除后2，1指向第3個(gè)節(jié)點(diǎn)，就是讓1->next=2->next。
刪除指定學(xué)號(hào)的節(jié)點(diǎn)的函數(shù)為：
[cpp] view plaincopyprint?
01./*
02.==========================
03. 功能：刪除指定節(jié)點(diǎn)
04. (此例中是刪除指定學(xué)號(hào)的節(jié)點(diǎn))
05. 返回：指向鏈表表頭的指針
06.==========================
07.*/
08.struct student *Del (struct student *head, int num)
09.{
10. struct student *p1; //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址
11. struct student *p2; //p2保存當(dāng)前檢查過(guò)的節(jié)點(diǎn)的地址
12. if (head == NULL) //是空鏈表（結(jié)合圖3理解）
13. {
14. printf ("\nList is null!\n");
15. return head;
16. }
17.
18. //定位要?jiǎng)h除的節(jié)點(diǎn)
19. p1 = head;
20. while (p1->num != num && p1->next != NULL) //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，就繼續(xù)往下找
21. {
22. p2 = p1; //保存當(dāng)前節(jié)點(diǎn)的地址
23. p1 = p1->next; //后移一個(gè)節(jié)點(diǎn)
24. }
25.
26. if(p1->num==num) //找到了。（結(jié)合圖4、5理解）
27. {
28. if (p1 == head) //如果要?jiǎng)h除的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)
29. {
30. head = p1->next; //頭指針指向第一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，也就是第二個(gè)節(jié)點(diǎn)。這樣第一個(gè)節(jié)點(diǎn)就不在鏈表中，即刪除
31. }
32. else //如果是其它節(jié)點(diǎn)，則讓原來(lái)指向當(dāng)前節(jié)點(diǎn)的指針，指向它的下一個(gè)節(jié)點(diǎn)，完成刪除
33. {
34. p2->next = p1->next;
35. }
36.
37. free (p1); //釋放當(dāng)前節(jié)點(diǎn)
38. p1 = NULL;
39. printf ("\ndelete %ld success!\n", num);
40. n -= 1; //節(jié)點(diǎn)總數(shù)減1個(gè)
41. }
42. else //沒(méi)有找到
43. {
44. printf ("\n%ld not been found!\n", num);
45. }
46.
47. return head;
48.}
/*
==========================
功能：刪除指定節(jié)點(diǎn)
(此例中是刪除指定學(xué)號(hào)的節(jié)點(diǎn))
返回：指向鏈表表頭的指針
==========================
*/
struct student *Del (struct student *head, int num)
{
struct student *p1; //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址
struct student *p2; //p2保存當(dāng)前檢查過(guò)的節(jié)點(diǎn)的地址
if (head == NULL) //是空鏈表（結(jié)合圖3理解）
{
printf ("\nList is null!\n");
return head;
}
//定位要?jiǎng)h除的節(jié)點(diǎn)
p1 = head;
while (p1->num != num && p1->next != NULL) //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，就繼續(xù)往下找
{
p2 = p1; //保存當(dāng)前節(jié)點(diǎn)的地址
p1 = p1->next; //后移一個(gè)節(jié)點(diǎn)
}
if(p1->num==num) //找到了。（結(jié)合圖4、5理解）
{
if (p1 == head) //如果要?jiǎng)h除的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)
{
head = p1->next; //頭指針指向第一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，也就是第二個(gè)節(jié)點(diǎn)。這樣第一個(gè)節(jié)點(diǎn)就不在鏈表中，即刪除
}
else //如果是其它節(jié)點(diǎn)，則讓原來(lái)指向當(dāng)前節(jié)點(diǎn)的指針，指向它的下一個(gè)節(jié)點(diǎn)，完成刪除
{
p2->next = p1->next;
}
free (p1); //釋放當(dāng)前節(jié)點(diǎn)
p1 = NULL;
printf ("\ndelete %ld success!\n", num);
n -= 1; //節(jié)點(diǎn)總數(shù)減1個(gè)
}
else //沒(méi)有找到
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
單向鏈表的插入圖示：
---->[NULL]（原鏈表）
head
---->[1]---->[NULL]（插入后的鏈表）
head 1->next
圖7 空鏈表插入一個(gè)節(jié)點(diǎn)
結(jié)合原鏈表和插入后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
1、你要明白空鏈表head指向NULL就是head=NULL；
2、插入后head指向第1個(gè)節(jié)點(diǎn)，就是讓head=1,1->next=NULL,OK這樣就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原鏈表）
head 1->next 2->next 3->next n->next
---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL]（插入后的鏈表）
head 1->next 2->next x->next 3->next n->next
圖8：有N個(gè)節(jié)點(diǎn)的鏈表，插入一個(gè)節(jié)點(diǎn)（這里圖示插入第2個(gè)后面）
結(jié)合原鏈表和插入后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
1、你要明白原1->next就是節(jié)點(diǎn)2，2->next就是節(jié)點(diǎn)3；
2、插入后x指向第3個(gè)節(jié)點(diǎn),2指向x，就是讓x->next=2->next,1->next=x。
插入指定節(jié)點(diǎn)的后面的函數(shù)為：
[cpp] view plaincopyprint?
01./*
02.==========================
03. 功能：插入指定節(jié)點(diǎn)的后面
04. (此例中是指定學(xué)號(hào)的節(jié)點(diǎn))
05. 返回：指向鏈表表頭的指針
06.==========================
07.*/
08.struct student *Insert (struct student *head, int num, struct student *node)
09.{
10. struct student *p1; //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址
11. if (head == NULL) //（結(jié)合圖示7理解）
12. {
13. head = node;
14. node->next = NULL;
15. n += 1;
16. return head;
17. }
18.
19. p1 = head;
20. while(p1->num != num && p1->next != NULL) //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，繼續(xù)往下找
21. {
22. p1 = p1->next; //后移一個(gè)節(jié)點(diǎn)
23. }
24.
25. if (p1->num==num) //找到了（結(jié)合圖示8理解）
26. {
27. node->next = p1->next; //顯然node的下一節(jié)點(diǎn)是原p1的next
28. p1->next = node; //插入后，原p1的下一節(jié)點(diǎn)就是要插入的node
29. n += 1; //節(jié)點(diǎn)總數(shù)增加1個(gè)
30. }
31. else
32. {
33. printf ("\n%ld not been found!\n", num);
34. }
35. return head;
36.}
/*
==========================
功能：插入指定節(jié)點(diǎn)的后面
(此例中是指定學(xué)號(hào)的節(jié)點(diǎn))
返回：指向鏈表表頭的指針
==========================
*/
struct student *Insert (struct student *head, int num, struct student *node)
{
struct student *p1; //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址
if (head == NULL) //（結(jié)合圖示7理解）
{
head = node;
node->next = NULL;
n += 1;
return head;
}
p1 = head;
while(p1->num != num && p1->next != NULL) //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，繼續(xù)往下找
{
p1 = p1->next; //后移一個(gè)節(jié)點(diǎn)
}
if (p1->num==num) //找到了（結(jié)合圖示8理解）
{
node->next = p1->next; //顯然node的下一節(jié)點(diǎn)是原p1的next
p1->next = node; //插入后，原p1的下一節(jié)點(diǎn)就是要插入的node
n += 1; //節(jié)點(diǎn)總數(shù)增加1個(gè)
}
else
{
printf ("\n%ld not been found!\n", num);
}
return head;
} 單向鏈表的反序圖示：
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原鏈表）
head 1->next 2->next 3->next n->next
[NULL]<----[1]<----[2]<----[3]<----...[n]<----（反序后的鏈表）
1->next 2->next 3->next n->next head
圖9：有N個(gè)節(jié)點(diǎn)的鏈表反序
結(jié)合原鏈表和插入后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
1、我們需要一個(gè)讀原鏈表的指針p2,存反序鏈表的p1=NULL（剛好最后一個(gè)節(jié)點(diǎn)的next為NULL）,還有一個(gè)臨時(shí)存儲(chǔ)變量p；
2、p2在原鏈表中讀出一個(gè)節(jié)點(diǎn)，我們就把它放到p1中，p就是用來(lái)處理節(jié)點(diǎn)放置順序的問(wèn)題；
3、比如，現(xiàn)在我們?nèi)〉靡粋€(gè)2,為了我們繼續(xù)往下取節(jié)點(diǎn)，我們必須保存它的next值，由原鏈表可知p=2->next;
4、然后由反序后的鏈表可知，反序后2->next要指向1，則2->next=1;
5、好了，現(xiàn)在已經(jīng)反序一個(gè)節(jié)點(diǎn)，接著處理下一個(gè)節(jié)點(diǎn)就需要保存此時(shí)的信息：
p1變成剛剛加入的2，即p1=2;p2要變成它的下一節(jié)點(diǎn)，就是上面我們保存的p,即p2=p。
反序鏈表的函數(shù)為：
[cpp] view plaincopyprint?
01./*
02.==========================
03. 功能：反序節(jié)點(diǎn)
04. (鏈表的頭變成鏈表的尾，鏈表的尾變成頭)
05. 返回：指向鏈表表頭的指針
06.==========================
07.*/
08.
09.struct student *Reverse (struct student *head)
10.{
11. struct student *p; //臨時(shí)存儲(chǔ)
12. struct student *p1; //存儲(chǔ)返回結(jié)果
13. struct student *p2; //源結(jié)果節(jié)點(diǎn)一個(gè)一個(gè)取
14.
15. p1 = NULL; //開始顛倒時(shí)，已顛倒的部分為空
16. p2 = head; //p2指向鏈表的頭節(jié)點(diǎn)
17. while(p2 != NULL)
18. {
19. p = p2->next;
20. p2->next = p1;
21. p1 = p2;
22. p2 = p;
23. }
24. head = p1;
25. return head;
26.}
/*
==========================
功能：反序節(jié)點(diǎn)
(鏈表的頭變成鏈表的尾，鏈表的尾變成頭)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Reverse (struct student *head)
{
struct student *p; //臨時(shí)存儲(chǔ)
struct student *p1; //存儲(chǔ)返回結(jié)果
struct student *p2; //源結(jié)果節(jié)點(diǎn)一個(gè)一個(gè)取
p1 = NULL; //開始顛倒時(shí)，已顛倒的部分為空
p2 = head; //p2指向鏈表的頭節(jié)點(diǎn)
while(p2 != NULL)
{
p = p2->next;
p2->next = p1;
p1 = p2;
p2 = p;
}
head = p1;
return head;
} 對(duì)鏈表進(jìn)行選擇排序的基本思想就是反復(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,然后它變成其尾指針；
對(duì)鏈表進(jìn)行選擇排序的函數(shù)為：
[cpp] view plaincopyprint?
01./*
02.==========================
03. 功能：選擇排序(由小到大)
04. 返回：指向鏈表表頭的指針
05.==========================
06.*/
07.struct student *SelectSort (struct student *head)
08.{
09. struct student *first; //排列后有序鏈的表頭指針
10. struct student *tail; //排列后有序鏈的表尾指針
11. struct student *p_min; //保留鍵值更小的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針
12. struct student *min; //存儲(chǔ)最小節(jié)點(diǎn)
13. struct student *p; //當(dāng)前比較的節(jié)點(diǎn)
14.
15. first = NULL;
16. while(head != NULL) //在鏈表中找鍵值最小的節(jié)點(diǎn)
17. {
18. //注意：這里for語(yǔ)句就是體現(xiàn)選擇排序思想的地方
19. for (p = head, min = head; p->next != NULL; p = p->next) //循環(huán)遍歷鏈表中的節(jié)點(diǎn)，找出此時(shí)最小的節(jié)點(diǎn)
20. {
21. if (p->next->num < min->num) //找到一個(gè)比當(dāng)前min小的節(jié)點(diǎn)
22. {
23. p_min = p; //保存找到節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)：顯然p->next的前驅(qū)節(jié)點(diǎn)是p
24. min = p->next; //保存鍵值更小的節(jié)點(diǎn)
25. }
26. }
27.
28. //上面for語(yǔ)句結(jié)束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應(yīng)的條件判斷，安排它離開原來(lái)的鏈表
29.
30. //第一件事
31. if (first == NULL) //如果有序鏈表目前還是一個(gè)空鏈表
32. {
33. first = min; //第一次找到鍵值最小的節(jié)點(diǎn)
34. tail = min; //注意：尾指針讓它指向最后的一個(gè)節(jié)點(diǎn)
35. }
36. else //有序鏈表中已經(jīng)有節(jié)點(diǎn)
37. {
38. tail->next = min; //把剛找到的最小節(jié)點(diǎn)放到最后，即讓尾指針的next指向它
39. tail = min; //尾指針也要指向它
40. }
41.
42. //第二件事
43. if (min == head) //如果找到的最小節(jié)點(diǎn)就是第一個(gè)節(jié)點(diǎn)
44. {
45. head = head->next; //顯然讓head指向原h(huán)ead->next,即第二個(gè)節(jié)點(diǎn)，就OK
46. }
47. else //如果不是第一個(gè)節(jié)點(diǎn)
48. {
49. p_min->next = min->next; //前次最小節(jié)點(diǎn)的next指向當(dāng)前min的next,這樣就讓min離開了原鏈表
50. }
51. }
52.
53. if (first != NULL) //循環(huán)結(jié)束得到有序鏈表first
54. {
55. tail->next = NULL; //單向鏈表的最后一個(gè)節(jié)點(diǎn)的next應(yīng)該指向NULL
56. }
57. head = first;
58. return head;
59.}
/*
==========================
功能：選擇排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
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)的條件判斷，安排它離開原來(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離開了原鏈表
}
}
if (first != NULL) //循環(huán)結(jié)束得到有序鏈表first
{
tail->next = NULL; //單向鏈表的最后一個(gè)節(jié)點(diǎn)的next應(yīng)該指向NULL
}
head = first;
return head;
} 對(duì)鏈表進(jìn)行直接插入排序的基本思想就是假設(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)橛行蜴湵怼?/P>
單向鏈表的直接插入排序圖示：
---->[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)為它和上面的選擇排序法一樣了。
對(duì)鏈表進(jìn)行直接插入排序的函數(shù)為：
[cpp] view plaincopyprint?
01./*
02.==========================
03. 功能：直接插入排序(由小到大)
04. 返回：指向鏈表表頭的指針
05.==========================
06.*/
07.struct student *InsertSort (struct student *head)
08.{
09. struct student *first; //為原鏈表剩下用于直接插入排序的節(jié)點(diǎn)頭指針
10. struct student *t; //臨時(shí)指針變量：插入節(jié)點(diǎn)
11. struct student *p,*q; //臨時(shí)指針變量
12.
13. first = head->next; //原鏈表剩下用于直接插入排序的節(jié)點(diǎn)鏈表：可根據(jù)圖12來(lái)理解
14. head->next = NULL; //只含有一個(gè)節(jié)點(diǎn)的鏈表的有序鏈表：可根據(jù)圖11來(lái)理解
15.
16. while(first != NULL) //遍歷剩下無(wú)序的鏈表
17. {
18. //注意：這里for語(yǔ)句就是體現(xiàn)直接插入排序思想的地方
19. for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next); //無(wú)序節(jié)點(diǎn)在有序鏈表中找插入的位置
20.
21. //退出for循環(huán)，就是找到了插入的位置，應(yīng)該將t節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，q節(jié)點(diǎn)之前
22. //注意：按道理來(lái)說(shuō)，這句話可以放到下面注釋了的那個(gè)位置也應(yīng)該對(duì)的，但是就是不能。原因：你若理解了上面的第3條，就知道了
23. //下面的插入就是將t節(jié)點(diǎn)即是first節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，已經(jīng)改變了first節(jié)點(diǎn)，所以first節(jié)點(diǎn)應(yīng)該在被修改之前往后移動(dòng)，不能放到下面注釋的位置上去
24. first = first->next; //無(wú)序鏈表中的節(jié)點(diǎn)離開，以便它插入到有序鏈表中
25.
26. if (q == head) //插在第一個(gè)節(jié)點(diǎn)之前
27. {
28. head = t;
29. }
30. else //p是q的前驅(qū)
31. {
32. p->next = t;
33. }
34. t->next = q; //完成插入動(dòng)作
35. //first = first->next;
36. }
37. return head;
38.}
/*
==========================
功能：直接插入排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *InsertSort (struct student *head)
{
struct student *first; //為原鏈表剩下用于直接插入排序的節(jié)點(diǎn)頭指針
struct student *t; //臨時(shí)指針變量：插入節(jié)點(diǎn)
struct student *p,*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)，就是找到了插入的位置，應(yīng)該將t節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，q節(jié)點(diǎn)之前
//注意：按道理來(lái)說(shuō)，這句話可以放到下面注釋了的那個(gè)位置也應(yīng)該對(duì)的，但是就是不能。原因：你若理解了上面的第3條，就知道了
//下面的插入就是將t節(jié)點(diǎn)即是first節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，已經(jīng)改變了first節(jié)點(diǎn)，所以first節(jié)點(diǎn)應(yīng)該在被修改之前往后移動(dòng)，不能放到下面注釋的位置上去
first = first->next; //無(wú)序鏈表中的節(jié)點(diǎn)離開，以便它插入到有序鏈表中
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ì)鏈表進(jìn)行冒泡排序的基本思想就是對(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)是排好序的了。
對(duì)鏈表進(jìn)行冒泡排序的函數(shù)為：
[cpp] view plaincopyprint?
01./*
02.==========================
03. 功能：冒泡排序(由小到大)
04. 返回：指向鏈表表頭的指針
05.==========================
06.*/
07.struct student *BubbleSort (struct student *head)
08.{
09. struct student *endpt; //控制循環(huán)比較
10. struct student *p; //臨時(shí)指針變量
11. struct student *p1,*p2;
12.
13. p1 = (struct student *) malloc (LEN);
14. p1->next = head; //注意理解：我們?cè)黾右粋€(gè)節(jié)點(diǎn)，放在第一個(gè)節(jié)點(diǎn)的前面，主要是為了便于比較。因?yàn)榈谝粋€(gè)節(jié)點(diǎn)沒(méi)有前驅(qū)，我們不能交換地址
15. head = p1; //讓head指向p1節(jié)點(diǎn)，排序完成后，我們?cè)侔裵1節(jié)點(diǎn)釋放掉
16.
17. for (endpt = NULL; endpt != head; endpt = p) //結(jié)合第6點(diǎn)理解
18. {
19. for (p = p1 = head; p1->next->next != endpt; p1 = p1->next)
20. {
21. if (p1->next->num > p1->next->next->num) //如果前面的節(jié)點(diǎn)鍵值比后面節(jié)點(diǎn)的鍵值大，則交換
22. {
23. p2 = p1->next->next; //結(jié)合第1點(diǎn)理解
24. p1->next->next = p2->next; //結(jié)合第2點(diǎn)理解
25. p2->next = p1->next; //結(jié)合第3點(diǎn)理解
26. p1->next = p2; //結(jié)合第4點(diǎn)理解
27. p = p1->next->next; //結(jié)合第6點(diǎn)理解
28. }
29. }
30. }
31.
32. p1 = head; //把p1的信息去掉
33. head = head->next; //讓head指向排序后的第一個(gè)節(jié)點(diǎn)
34. free (p1); //釋放p1
35. p1 = NULL; //p1置為NULL，保證不產(chǎn)生“野指針”，即地址不確定的指針變量
36.
37. return head;
38.}
/*
==========================
功能：冒泡排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *BubbleSort (struct student *head)
{
struct student *endpt; //控制循環(huán)比較
struct student *p; //臨時(shí)指針變量
struct student *p1,*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;
} 有序鏈表插入節(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
插入有序鏈表的函數(shù)為：
[cpp] view plaincopyprint?
01./*
02.==========================
03. 功能：插入有序鏈表的某個(gè)節(jié)點(diǎn)的后面(從小到大)
04. 返回：指向鏈表表頭的指針
05.==========================
06.*/
07.
08.struct student *SortInsert (struct student *head, struct student *node)
09.{
10. struct student *p; //p保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址
11. struct student *t; //臨時(shí)指針變量
12.
13. if (head == NULL) //處理空的有序鏈表
14. {
15. head = node;
16. node->next = NULL;
17. n += 1; //插入完畢，節(jié)點(diǎn)總數(shù)加
18. return head;
19. }
20.
21. p = head; //有序鏈表不為空
22. while(p->num < node->num && p != NULL) //p指向的節(jié)點(diǎn)的學(xué)號(hào)比插入節(jié)點(diǎn)的學(xué)號(hào)小，并且它不等于NULL
23. {
24. t = p; //保存當(dāng)前節(jié)點(diǎn)的前驅(qū)，以便后面判斷后處理
25. p = p->next; //后移一個(gè)節(jié)點(diǎn)
26. }
27.
28. if (p == head) //剛好插入第一個(gè)節(jié)點(diǎn)之前
29. {
30. node->next = p;
31. head = node;
32. }
33. else //插入其它節(jié)點(diǎn)之后
34. {
35. t->next = node; //把node節(jié)點(diǎn)加進(jìn)去
36. node->next = p;
37. }
38. n += 1; //插入完畢，節(jié)點(diǎn)總數(shù)加1
39.
40. return head;
41.}
/*
==========================
功能：插入有序鏈表的某個(gè)節(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ù)加
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;
}綜上所述，鏈表的各類操作函數(shù)的完整代碼如下：
[cpp] view plaincopyprint?
01.#include "stdlib.h"
02.#include "stdio.h"
03.
04.#define NULL 0
05.#define LEN sizeof(struct student)
06.
07.struct student
08.{
09. int num; //學(xué)號(hào)
10. float score; //分?jǐn)?shù)，其他信息可以繼續(xù)在下面增加字段
11. struct student *next; //指向下一節(jié)點(diǎn)的指針
12.};
13.
14.int n; //節(jié)點(diǎn)總數(shù)
15./*
16.==========================
17.功能：創(chuàng)建n個(gè)節(jié)點(diǎn)的鏈表
18.返回：指向鏈表表頭的指針
19.==========================
20.*/
21.struct student *Create()
22.{
23. struct student *head; //頭節(jié)點(diǎn)
24. struct student *p1 = NULL; //p1保存創(chuàng)建的新節(jié)點(diǎn)的地址
25. struct student *p2 = NULL; //p2保存原鏈表最后一個(gè)節(jié)點(diǎn)的地址
26.
27. n = 0; //創(chuàng)建前鏈表的節(jié)點(diǎn)總數(shù)為0：空鏈表
28. p1 = (struct student *) malloc (LEN); //開辟一個(gè)新節(jié)點(diǎn)
29. p2 = p1; //如果節(jié)點(diǎn)開辟成功，則p2先把它的指針保存下來(lái)以備后用
30.
31. if(p1==NULL) //節(jié)點(diǎn)開辟不成功
32. {
33. printf ("\nCann't create it, try it again in a moment!\n");
34. return NULL;
35. }
36. else //節(jié)點(diǎn)開辟成功
37. {
38. head = NULL; //開始head指向NULL
39. printf ("Please input %d node -- num,score: ", n + 1);
40. scanf ("%d %f", &(p1->num), &(p1->score)); //錄入數(shù)據(jù)
41. }
42. while(p1->num != 0) //只要學(xué)號(hào)不為0，就繼續(xù)錄入下一個(gè)節(jié)點(diǎn)
43. {
44. n += 1; //節(jié)點(diǎn)總數(shù)增加1個(gè)
45. if(n == 1) //如果節(jié)點(diǎn)總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點(diǎn)p1
46. {
47. head = p1;
48. p2->next = NULL; //此時(shí)的p2就是p1,也就是p1->next指向NULL。
49. }
50. else
51. {
52. p2->next = p1; //指向上次下面剛剛開辟的新節(jié)點(diǎn)
53. }
54.
55. p2 = p1; //把p1的地址給p2保留，然后p1產(chǎn)生新的節(jié)點(diǎn)
56.
57. p1 = (struct student *) malloc (LEN);
58. printf ("Please input %d node -- num,score: ", n + 1);
59. scanf ("%d %f", &(p1->num), &(p1->score));
60. }
61. p2->next = NULL; //此句就是根據(jù)單向鏈表的最后一個(gè)節(jié)點(diǎn)要指向NULL
62.
63. free(p1); //p1->num為0的時(shí)候跳出了while循環(huán)，并且釋放p1
64. p1 = NULL; //特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針
65. return head; //返回創(chuàng)建鏈表的頭指針
66.}
67.
68.
69./*
70.===========================
71. 功能：輸出節(jié)點(diǎn)
72. 返回： void
73.===========================
74.*/
75.void Print(struct student *head)
76.{
77. struct student *p;
78. printf ("\nNow , These %d records are:\n", n);
79. p = head;
80. if(head != NULL) //只要不是空鏈表，就輸出鏈表中所有節(jié)點(diǎn)
81. {
82. printf("head is %o\n", head); //輸出頭指針指向的地址
83. do
84. {
85. /*
86. 輸出相應(yīng)的值：當(dāng)前節(jié)點(diǎn)地址、各字段值、當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)地址。
87. 這樣輸出便于讀者形象看到一個(gè)單向鏈表在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)，和我們
88. 設(shè)計(jì)的圖示是一模一樣的。
89. */
90. printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);
91. p = p->next; //移到下一個(gè)節(jié)點(diǎn)
92. }
93. while (p != NULL);
94. }
95.}
96.
97./*
98.==========================
99. 功能：刪除指定節(jié)點(diǎn)
100. (此例中是刪除指定學(xué)號(hào)的節(jié)點(diǎn))
101. 返回：指向鏈表表頭的指針
102.==========================
103.*/
104.struct student *Del (struct student *head, int num)
105.{
106. struct student *p1; //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址
107. struct student *p2; //p2保存當(dāng)前檢查過(guò)的節(jié)點(diǎn)的地址
108. if (head == NULL) //是空鏈表（結(jié)合圖3理解）
109. {
110. printf ("\nList is null!\n");
111. return head;
112. }
113.
114. //定位要?jiǎng)h除的節(jié)點(diǎn)
115. p1 = head;
116. while (p1->num != num && p1->next != NULL) //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，就繼續(xù)往下找
117. {
118. p2 = p1; //保存當(dāng)前節(jié)點(diǎn)的地址
119. p1 = p1->next; //后移一個(gè)節(jié)點(diǎn)
120. }
121.
122. if(p1->num==num) //找到了。（結(jié)合圖4、5理解）
123. {
124. if (p1 == head) //如果要?jiǎng)h除的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)
125. {
126. head = p1->next; //頭指針指向第一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，也就是第二個(gè)節(jié)點(diǎn)。這樣第一個(gè)節(jié)點(diǎn)就不在鏈表中，即刪除
127. }
128. else //如果是其它節(jié)點(diǎn)，則讓原來(lái)指向當(dāng)前節(jié)點(diǎn)的指針，指向它的下一個(gè)節(jié)點(diǎn)，完成刪除
129. {
130. p2->next = p1->next;
131. }
132.
133. free (p1); //釋放當(dāng)前節(jié)點(diǎn)
134. p1 = NULL;
135. printf ("\ndelete %ld success!\n", num);
136. n -= 1; //節(jié)點(diǎn)總數(shù)減1個(gè)
137. }
138. else //沒(méi)有找到
139. {
140. printf ("\n%ld not been found!\n", num);
141. }
142.
143. return head;
144.}
145.
146.//銷毀鏈表
147.void DestroyList(struct student *head)
148.{
149. struct student *p;
150. if(head==NULL)
151. return 0;
152. while(head)
153. {
154. p=head->next;
155. free(head);
156. head=p;
157. }
158. return 1;
159.}
160.
161./*
162.==========================
163. 功能：插入指定節(jié)點(diǎn)的后面
164. (此例中是指定學(xué)號(hào)的節(jié)點(diǎn))
165. 返回：指向鏈表表頭的指針
166.==========================
167.*/
168.struct student *Insert (struct student *head, int num, struct student *node)
169.{
170. struct student *p1; //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址
171. if (head == NULL) //（結(jié)合圖示7理解）
172. {
173. head = node;
174. node->next = NULL;
175. n += 1;
176. return head;
177. }
178.
179. p1 = head;
180. while(p1->num != num && p1->next != NULL) //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，繼續(xù)往下找
181. {
182. p1 = p1->next; //后移一個(gè)節(jié)點(diǎn)
183. }
184.
185. if (p1->num==num) //找到了（結(jié)合圖示8理解）
186. {
187. node->next = p1->next; //顯然node的下一節(jié)點(diǎn)是原p1的next
188. p1->next = node; //插入后，原p1的下一節(jié)點(diǎn)就是要插入的node
189. n += 1; //節(jié)點(diǎn)總數(shù)增加1個(gè)
190. }
191. else
192. {
193. printf ("\n%ld not been found!\n", num);
194. }
195. return head;
196.}
197.
198./*
199.==========================
200. 功能：反序節(jié)點(diǎn)
201. (鏈表的頭變成鏈表的尾，鏈表的尾變成頭)
202. 返回：指向鏈表表頭的指針
203.==========================
204.*/
205.
206.struct student *Reverse (struct student *head)
207.{
208. struct student *p; //臨時(shí)存儲(chǔ)
209. struct student *p1; //存儲(chǔ)返回結(jié)果
210. struct student *p2; //源結(jié)果節(jié)點(diǎn)一個(gè)一個(gè)取
211.
212. p1 = NULL; //開始顛倒時(shí)，已顛倒的部分為空
213. p2 = head; //p2指向鏈表的頭節(jié)點(diǎn)
214. while(p2 != NULL)
215. {
216. p = p2->next;
217. p2->next = p1;
218. p1 = p2;
219. p2 = p;
220. }
221. head = p1;
222. return head;
223.}
224./*
225.==========================
226. 功能：選擇排序(由小到大)
227. 返回：指向鏈表表頭的指針
228.==========================
229.*/
230.struct student *SelectSort (struct student *head)
231.{
232. struct student *first; //排列后有序鏈的表頭指針
233. struct student *tail; //排列后有序鏈的表尾指針
234. struct student *p_min; //保留鍵值更小的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針
235. struct student *min; //存儲(chǔ)最小節(jié)點(diǎn)
236. struct student *p; //當(dāng)前比較的節(jié)點(diǎn)
237.
238. first = NULL;
239. while(head != NULL) //在鏈表中找鍵值最小的節(jié)點(diǎn)
240. {
241. //注意：這里for語(yǔ)句就是體現(xiàn)選擇排序思想的地方
242. for (p = head, min = head; p->next != NULL; p = p->next) //循環(huán)遍歷鏈表中的節(jié)點(diǎn)，找出此時(shí)最小的節(jié)點(diǎn)
243. {
244. if (p->next->num < min->num) //找到一個(gè)比當(dāng)前min小的節(jié)點(diǎn)
245. {
246. p_min = p; //保存找到節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)：顯然p->next的前驅(qū)節(jié)點(diǎn)是p
247. min = p->next; //保存鍵值更小的節(jié)點(diǎn)
248. }
249. }
250.
251. //上面for語(yǔ)句結(jié)束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應(yīng)的條件判斷，安排它離開原來(lái)的鏈表
252.
253. //第一件事
254. if (first == NULL) //如果有序鏈表目前還是一個(gè)空鏈表
255. {
256. first = min; //第一次找到鍵值最小的節(jié)點(diǎn)
257. tail = min; //注意：尾指針讓它指向最后的一個(gè)節(jié)點(diǎn)
258. }
259. else //有序鏈表中已經(jīng)有節(jié)點(diǎn)
260. {
261. tail->next = min; //把剛找到的最小節(jié)點(diǎn)放到最后，即讓尾指針的next指向它
262. tail = min; //尾指針也要指向它
263. }
264.
265. //第二件事
266. if (min == head) //如果找到的最小節(jié)點(diǎn)就是第一個(gè)節(jié)點(diǎn)
267. {
268. head = head->next; //顯然讓head指向原h(huán)ead->next,即第二個(gè)節(jié)點(diǎn)，就OK
269. }
270. else //如果不是第一個(gè)節(jié)點(diǎn)
271. {
272. p_min->next = min->next; //前次最小節(jié)點(diǎn)的next指向當(dāng)前min的next,這樣就讓min離開了原鏈表
273. }
274. }
275.
276. if (first != NULL) //循環(huán)結(jié)束得到有序鏈表first
277. {
278. tail->next = NULL; //單向鏈表的最后一個(gè)節(jié)點(diǎn)的next應(yīng)該指向NULL
279. }
280. head = first;
281. return head;
282.}
283.
284.
285./*
286.==========================
287. 功能：直接插入排序(由小到大)
288. 返回：指向鏈表表頭的指針
289.==========================
290.*/
291.struct student *InsertSort (struct student *head)
292.{
293. struct student *first; //為原鏈表剩下用于直接插入排序的節(jié)點(diǎn)頭指針
294. struct student *t; //臨時(shí)指針變量：插入節(jié)點(diǎn)
295. struct student *p,*q; //臨時(shí)指針變量
296.
297. first = head->next; //原鏈表剩下用于直接插入排序的節(jié)點(diǎn)鏈表：可根據(jù)圖12來(lái)理解
298. head->next = NULL; //只含有一個(gè)節(jié)點(diǎn)的鏈表的有序鏈表：可根據(jù)圖11來(lái)理解
299.
300. while(first != NULL) //遍歷剩下無(wú)序的鏈表
301. {
302. //注意：這里for語(yǔ)句就是體現(xiàn)直接插入排序思想的地方
303. for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next); //無(wú)序節(jié)點(diǎn)在有序鏈表中找插入的位置
304.
305. //退出for循環(huán)，就是找到了插入的位置，應(yīng)該將t節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，q節(jié)點(diǎn)之前
306. //注意：按道理來(lái)說(shuō)，這句話可以放到下面注釋了的那個(gè)位置也應(yīng)該對(duì)的，但是就是不能。原因：你若理解了上面的第3條，就知道了
307. //下面的插入就是將t節(jié)點(diǎn)即是first節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，已經(jīng)改變了first節(jié)點(diǎn)，所以first節(jié)點(diǎn)應(yīng)該在被修改之前往后移動(dòng)，不能放到下面注釋的位置上去
308. first = first->next; //無(wú)序鏈表中的節(jié)點(diǎn)離開，以便它插入到有序鏈表中
309.
310. if (q == head) //插在第一個(gè)節(jié)點(diǎn)之前
311. {
312. head = t;
313. }
314. else //p是q的前驅(qū)
315. {
316. p->next = t;
317. }
318. t->next = q; //完成插入動(dòng)作
319. //first = first->next;
320. }
321. return head;
322.}
323.
324./*
325.==========================
326. 功能：冒泡排序(由小到大)
327. 返回：指向鏈表表頭的指針
328.==========================
329.*/
330.struct student *BubbleSort (struct student *head)
331.{
332. struct student *endpt; //控制循環(huán)比較
333. struct student *p; //臨時(shí)指針變量
334. struct student *p1,*p2;
335.
336. p1 = (struct student *) malloc (LEN);
337. p1->next = head; //注意理解：我們?cè)黾右粋€(gè)節(jié)點(diǎn)，放在第一個(gè)節(jié)點(diǎn)的前面，主要是為了便于比較。因?yàn)榈谝粋€(gè)節(jié)點(diǎn)沒(méi)有前驅(qū)，我們不能交換地址
338. head = p1; //讓head指向p1節(jié)點(diǎn)，排序完成后，我們?cè)侔裵1節(jié)點(diǎn)釋放掉
339.
340. for (endpt = NULL; endpt != head; endpt = p) //結(jié)合第6點(diǎn)理解
341. {
342. for (p = p1 = head; p1->next->next != endpt; p1 = p1->next)
343. {
344. if (p1->next->num > p1->next->next->num) //如果前面的節(jié)點(diǎn)鍵值比后面節(jié)點(diǎn)的鍵值大，則交換
345. {
346. p2 = p1->next->next; //結(jié)合第1點(diǎn)理解
347. p1->next->next = p2->next; //結(jié)合第2點(diǎn)理解
348. p2->next = p1->next; //結(jié)合第3點(diǎn)理解
349. p1->next = p2; //結(jié)合第4點(diǎn)理解
350. p = p1->next->next; //結(jié)合第6點(diǎn)理解
351. }
352. }
353. }
354.
355. p1 = head; //把p1的信息去掉
356. head = head->next; //讓head指向排序后的第一個(gè)節(jié)點(diǎn)
357. free (p1); //釋放p1
358. p1 = NULL; //p1置為NULL，保證不產(chǎn)生“野指針”，即地址不確定的指針變量
359.
360. return head;
361.}
362.
363./*
364.==========================
365. 功能：插入有序鏈表的某個(gè)節(jié)點(diǎn)的后面(從小到大)
366. 返回：指向鏈表表頭的指針
367.==========================
368.*/
369.
370.struct student *SortInsert (struct student *head, struct student *node)
371.{
372. struct student *p; //p保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址
373. struct student *t; //臨時(shí)指針變量
374.
375. if (head == NULL) //處理空的有序鏈表
376. {
377. head = node;
378. node->next = NULL;
379. n += 1; //插入完畢，節(jié)點(diǎn)總數(shù)加
380. return head;
381. }
382.
383. p = head; //有序鏈表不為空
384. while(p->num < node->num && p != NULL) //p指向的節(jié)點(diǎn)的學(xué)號(hào)比插入節(jié)點(diǎn)的學(xué)號(hào)小，并且它不等于NULL
385. {
386. t = p; //保存當(dāng)前節(jié)點(diǎn)的前驅(qū)，以便后面判斷后處理
387. p = p->next; //后移一個(gè)節(jié)點(diǎn)
388. }
389.
390. if (p == head) //剛好插入第一個(gè)節(jié)點(diǎn)之前
391. {
392. node->next = p;
393. head = node;
394. }
395. else //插入其它節(jié)點(diǎn)之后
396. {
397. t->next = node; //把node節(jié)點(diǎn)加進(jìn)去
398. node->next = p;
399. }
400. n += 1; //插入完畢，節(jié)點(diǎn)總數(shù)加1
401.
402. return head;
403.}
404.
405./*
406.以上函數(shù)的測(cè)試程序：
407.提示：根據(jù)測(cè)試函數(shù)的不同注釋相應(yīng)的程序段，這也是一種測(cè)試方法。
408.*/
409.int main(void)
410.{
411. struct student *head;
412. struct student *stu;
413. int thenumber;
414.
415. // 測(cè)試Create()、Print()
416. head = Create();
417. Print(head);
418.
419. //測(cè)試Del()
420. printf("\nWhich one delete: ");
421. scanf("%d",&thenumber);
422. head = Del(head,thenumber);
423. Print(head);
424.
425. //測(cè)試Insert()
426. stu = (struct student *)malloc(LEN);
427. printf("\nPlease input insert node -- num,score: ");
428. scanf("%d %f",&stu->num,&stu->score);
429. printf("\nInsert behind num: ");
430. scanf("%d",&thenumber);
431. head = Insert(head,thenumber,stu);
432. Print(head);
433.
434. //測(cè)試Reverse()
435. printf("\nReverse the LinkList: \n");
436. head = Reverse(head);
437. Print(head);
438.
439. //測(cè)試SelectSort()
440. printf("\nSelectSort the LinkList: \n");
441. head = SelectSort(head);
442. Print(head);
443.
444. //測(cè)試InsertSort()
445. printf("\nInsertSort the LinkList: \n");
446. head = InsertSort(head);
447. Print(head);
448.
449. //測(cè)試BubbleSort()
450. printf("\nBubbleSort the LinkList: \n");
451. head = BubbleSort(head);
452. Print(head);
453.
454. printf("\nSortInsert the LinkList: \n");
455. //測(cè)試SortInsert():上面創(chuàng)建鏈表，輸入節(jié)點(diǎn)時(shí)請(qǐng)注意學(xué)號(hào)num從小到大的順序
456. stu = (struct student *)malloc(LEN);
457. printf("\nPlease input insert node -- num,score: ");
458. scanf("%d %f",&stu->num,&stu->score);
459. head = SortInsert(head,stu);
460. Print(head);
461.
462. //銷毀鏈表
463. DestroyList(head);
464.
465. printf ("\n");
466. system ("pause");
467.}
