深入理解鏈表的各類操作詳解
更新時間：2013年05月24日 17:25:40 作者：
本篇文章是對鏈表的各類操作進行了詳細的分析介紹，需要的朋友參考下
鏈表概述
鏈表是一種常見的重要的數(shù)據(jù)結構。它是動態(tài)地進行存儲分配的一種結構。它可以根據(jù)需要開辟內存單元。鏈表有一個“頭指針”變量，以head表示，它存放一個地址。該地址指向一個元素。鏈表中每一個元素稱為“結點”，每個結點都應包括兩個部分：一為用戶需要用的實際數(shù)據(jù)，二為下一個結點的地址。因此，head指向第一個元素：第一個元素又指向第二個元素；……，直到最后一個元素，該元素不再指向其它元素，它稱為“表尾”，它的地址部分放一個“NULL”（表示“空地址”），鏈表到此結束。
鏈表的各類操作包括：學習單向鏈表的創(chuàng)建、刪除、 插入（無序、有序）、輸出、 排序（選擇、插入、冒泡）、反序等等。
單向鏈表的圖示：
---->[NULL]
head
圖1：空鏈表
---->[p1]---->[p2]...---->[pn]---->[NULL]
head p1->next p2->next pn->next
圖2：有N個節(jié)點的鏈表
創(chuàng)建n個節(jié)點的鏈表的函數(shù)為：
#include "stdlib.h"
#include "stdio.h"
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
int num; //學號
float score; //分數(shù)，其他信息可以繼續(xù)在下面增加字段
struct student *next; //指向下一節(jié)點的指針
};
int n; //節(jié)點總數(shù)
/*
==========================
功能：創(chuàng)建n個節(jié)點的鏈表
返回：指向鏈表表頭的指針
==========================
*/
struct student *Create()
{
struct student *head; //頭節(jié)點
struct student *p1 = NULL; //p1保存創(chuàng)建的新節(jié)點的地址
struct student *p2 = NULL; //p2保存原鏈表最后一個節(jié)點的地址
n = 0; //創(chuàng)建前鏈表的節(jié)點總數(shù)為0：空鏈表
p1 = (struct student *) malloc (LEN); //開辟一個新節(jié)點
p2 = p1; //如果節(jié)點開辟成功，則p2先把它的指針保存下來以備后用
if(p1==NULL) //節(jié)點開辟不成功
{
printf ("\nCann't create it, try it again in a moment!\n");
return NULL;
}
else //節(jié)點開辟成功
{
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) //只要學號不為0，就繼續(xù)錄入下一個節(jié)點
{
n += 1; //節(jié)點總數(shù)增加1個
if(n == 1) //如果節(jié)點總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點p1
{
head = p1;
p2->next = NULL; //此時的p2就是p1,也就是p1->next指向NULL。
}
else
{
p2->next = p1; //指向上次下面剛剛開辟的新節(jié)點
}
p2 = p1; //把p1的地址給p2保留，然后p1產生新的節(jié)點
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ù)單向鏈表的最后一個節(jié)點要指向NULL
free(p1); //p1->num為0的時候跳出了while循環(huán)，并且釋放p1
p1 = NULL; //特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針
return head; //返回創(chuàng)建鏈表的頭指針
}
輸出鏈表中節(jié)點的函數(shù)為：
/*
===========================
功能：輸出節(jié)點
返回： void
===========================
*/
void Print(struct student *head)
{
struct student *p;
printf ("\nNow , These %d records are:\n", n);
p = head;
if(head != NULL) //只要不是空鏈表，就輸出鏈表中所有節(jié)點
{
printf("head is %o\n", head); //輸出頭指針指向的地址
do
{
/*
輸出相應的值：當前節(jié)點地址、各字段值、當前節(jié)點的下一節(jié)點地址。
這樣輸出便于讀者形象看到一個單向鏈表在計算機中的存儲結構，和我們
設計的圖示是一模一樣的。
*/
printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);
p = p->next; //移到下一個節(jié)點
}
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個節(jié)點的鏈表，刪除第一個節(jié)點
結合原鏈表和刪除后的鏈表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白head就是第1個節(jié)點，head->next就是第2個節(jié)點；
2、刪除后head指向第2個節(jié)點，就是讓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個節(jié)點的鏈表，刪除中間一個（這里圖示刪除第2個）
結合原鏈表和刪除后的鏈表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白head就是第1個節(jié)點，1->next就是第2個節(jié)點，2->next就是第3個節(jié)點；
2、刪除后2，1指向第3個節(jié)點，就是讓1->next=2->next。
刪除指定學號的節(jié)點的函數(shù)為：
/*
==========================
功能：刪除指定節(jié)點
(此例中是刪除指定學號的節(jié)點)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Del (struct student *head, int num)
{
struct student *p1; //p1保存當前需要檢查的節(jié)點的地址
struct student *p2; //p2保存當前檢查過的節(jié)點的地址
if (head == NULL) //是空鏈表（結合圖3理解）
{
printf ("\nList is null!\n");
return head;
}
//定位要刪除的節(jié)點
p1 = head;
while (p1->num != num && p1->next != NULL) //p1指向的節(jié)點不是所要查找的，并且它不是最后一個節(jié)點，就繼續(xù)往下找
{
p2 = p1; //保存當前節(jié)點的地址
p1 = p1->next; //后移一個節(jié)點
}
if(p1->num==num) //找到了。（結合圖4、5理解）
{
if (p1 == head) //如果要刪除的節(jié)點是第一個節(jié)點
{
head = p1->next; //頭指針指向第一個節(jié)點的后一個節(jié)點，也就是第二個節(jié)點。這樣第一個節(jié)點就不在鏈表中，即刪除
}
else //如果是其它節(jié)點，則讓原來指向當前節(jié)點的指針，指向它的下一個節(jié)點，完成刪除
{
p2->next = p1->next;
}
free (p1); //釋放當前節(jié)點
p1 = NULL;
printf ("\ndelete %ld success!\n", num);
n -= 1; //節(jié)點總數(shù)減1個
}
else //沒有找到
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
單向鏈表的插入圖示：
---->[NULL]（原鏈表）
head
---->[1]---->[NULL]（插入后的鏈表）
head 1->next
圖7 空鏈表插入一個節(jié)點
結合原鏈表和插入后的鏈表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白空鏈表head指向NULL就是head=NULL；
2、插入后head指向第1個節(jié)點，就是讓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個節(jié)點的鏈表，插入一個節(jié)點（這里圖示插入第2個后面）
結合原鏈表和插入后的鏈表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白原1->next就是節(jié)點2，2->next就是節(jié)點3；
2、插入后x指向第3個節(jié)點,2指向x，就是讓x->next=2->next,1->next=x。
插入指定節(jié)點的后面的函數(shù)為：
/*
==========================
功能：插入指定節(jié)點的后面
(此例中是指定學號的節(jié)點)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Insert (struct student *head, int num, struct student *node)
{
struct student *p1; //p1保存當前需要檢查的節(jié)點的地址
if (head == NULL) //（結合圖示7理解）
{
head = node;
node->next = NULL;
n += 1;
return head;
}
p1 = head;
while(p1->num != num && p1->next != NULL) //p1指向的節(jié)點不是所要查找的，并且它不是最后一個節(jié)點，繼續(xù)往下找
{
p1 = p1->next; //后移一個節(jié)點
}
if (p1->num==num) //找到了（結合圖示8理解）
{
node->next = p1->next; //顯然node的下一節(jié)點是原p1的next
p1->next = node; //插入后，原p1的下一節(jié)點就是要插入的node
n += 1; //節(jié)點總數(shù)增加1個
}
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個節(jié)點的鏈表反序
結合原鏈表和插入后的鏈表，就很容易寫出相應的代碼。操作方法如下：
1、我們需要一個讀原鏈表的指針p2,存反序鏈表的p1=NULL（剛好最后一個節(jié)點的next為NULL）,還有一個臨時存儲變量p；
2、p2在原鏈表中讀出一個節(jié)點，我們就把它放到p1中，p就是用來處理節(jié)點放置順序的問題；
3、比如，現(xiàn)在我們取得一個2,為了我們繼續(xù)往下取節(jié)點，我們必須保存它的next值，由原鏈表可知p=2->next;
4、然后由反序后的鏈表可知，反序后2->next要指向1，則2->next=1;
5、好了，現(xiàn)在已經反序一個節(jié)點，接著處理下一個節(jié)點就需要保存此時的信息：
p1變成剛剛加入的2，即p1=2;p2要變成它的下一節(jié)點，就是上面我們保存的p,即p2=p。
反序鏈表的函數(shù)為：
/*
==========================
功能：反序節(jié)點
(鏈表的頭變成鏈表的尾，鏈表的尾變成頭)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Reverse (struct student *head)
{
struct student *p; //臨時存儲
struct student *p1; //存儲返回結果
struct student *p2; //源結果節(jié)點一個一個取
p1 = NULL; //開始顛倒時，已顛倒的部分為空
p2 = head; //p2指向鏈表的頭節(jié)點
while(p2 != NULL)
{
p = p2->next;
p2->next = p1;
p1 = p2;
p2 = p;
}
head = p1;
return head;
}
對鏈表進行選擇排序的基本思想就是反復從還未排好序的那些節(jié)點中，選出鍵值（就是用它排序的字段，我們取學號num為鍵值）最小的節(jié)點，依次重新組合成一個鏈表。
我認為寫鏈表這類程序，關鍵是理解：head存儲的是第一個節(jié)點的地址，head->next存儲的是第二個節(jié)點的地址；任意一個節(jié)點p的地址，只能通過它前一個節(jié)點的next來求得。
單向鏈表的選擇排序圖示：
---->[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個節(jié)點的鏈表選擇排序
1、先在原鏈表中找最小的，找到一個后就把它放到另一個空的鏈表中；
2、空鏈表中安放第一個進來的節(jié)點，產生一個有序鏈表,并且讓它在原鏈表中分離出來（此時要注意原鏈表中出來的是第一個節(jié)點還是中間其它節(jié)點）；
3、繼續(xù)在原鏈表中找下一個最小的，找到后把它放入有序鏈表的尾指針的next,然后它變成其尾指針；
對鏈表進行選擇排序的函數(shù)為：
/*
==========================
功能：選擇排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *SelectSort (struct student *head)
{
struct student *first; //排列后有序鏈的表頭指針
struct student *tail; //排列后有序鏈的表尾指針
struct student *p_min; //保留鍵值更小的節(jié)點的前驅節(jié)點的指針
struct student *min; //存儲最小節(jié)點
struct student *p; //當前比較的節(jié)點
first = NULL;
while(head != NULL) //在鏈表中找鍵值最小的節(jié)點
{
//注意：這里for語句就是體現(xiàn)選擇排序思想的地方
for (p = head, min = head; p->next != NULL; p = p->next) //循環(huán)遍歷鏈表中的節(jié)點，找出此時最小的節(jié)點
{
if (p->next->num < min->num) //找到一個比當前min小的節(jié)點
{
p_min = p; //保存找到節(jié)點的前驅節(jié)點：顯然p->next的前驅節(jié)點是p
min = p->next; //保存鍵值更小的節(jié)點
}
}
//上面for語句結束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應的條件判斷，安排它離開原來的鏈表
//第一件事
if (first == NULL) //如果有序鏈表目前還是一個空鏈表
{
first = min; //第一次找到鍵值最小的節(jié)點
tail = min; //注意：尾指針讓它指向最后的一個節(jié)點
}
else //有序鏈表中已經有節(jié)點
{
tail->next = min; //把剛找到的最小節(jié)點放到最后，即讓尾指針的next指向它
tail = min; //尾指針也要指向它
}
//第二件事
if (min == head) //如果找到的最小節(jié)點就是第一個節(jié)點
{
head = head->next; //顯然讓head指向原h(huán)ead->next,即第二個節(jié)點，就OK
}
else //如果不是第一個節(jié)點
{
p_min->next = min->next; //前次最小節(jié)點的next指向當前min的next,這樣就讓min離開了原鏈表
}
}
if (first != NULL) //循環(huán)結束得到有序鏈表first
{
tail->next = NULL; //單向鏈表的最后一個節(jié)點的next應該指向NULL
}
head = first;
return head;
}
對鏈表進行直接插入排序的基本思想就是假設鏈表的前面n-1個節(jié)點是已經按鍵值（就是用它排序的字段，我們取學號num為鍵值）排好序的，對于節(jié)點n在這個序列中找插入位置，使得n插入后新序列仍然有序。按照這種思想，依次對鏈表從頭到尾執(zhí)行一遍，就可以使無序鏈表變?yōu)橛行蜴湵怼?BR> 單向鏈表的直接插入排序圖示：
---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原鏈表）
head 1->next 3->next 2->next n->next
---->[1]---->[NULL]（從原鏈表中取第1個節(jié)點作為只有一個節(jié)點的有序鏈表）
head
圖11
---->[3]---->[2]...---->[n]---->[NULL]（原鏈表剩下用于直接插入排序的節(jié)點）
first 3->next 2->next n->next
圖12
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后鏈表）
head 1->next 2->next 3->next n->next
圖13：有N個節(jié)點的鏈表直接插入排序
1、先在原鏈表中以第一個節(jié)點為一個有序鏈表，其余節(jié)點為待定節(jié)點。
2、從圖12鏈表中取節(jié)點，到圖11鏈表中定位插入。
3、上面圖示雖說畫了兩條鏈表，其實只有一條鏈表。在排序中，實質只增加了一個用于指向剩下需要排序節(jié)點的頭指針first罷了。
這一點請讀者務必搞清楚，要不然就可能認為它和上面的選擇排序法一樣了。
對鏈表進行直接插入排序的函數(shù)為：
/*
==========================
功能：直接插入排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *InsertSort (struct student *head)
{
struct student *first; //為原鏈表剩下用于直接插入排序的節(jié)點頭指針
struct student *t; //臨時指針變量：插入節(jié)點
struct student *p,*q; //臨時指針變量
first = head->next; //原鏈表剩下用于直接插入排序的節(jié)點鏈表：可根據(jù)圖12來理解
head->next = NULL; //只含有一個節(jié)點的鏈表的有序鏈表：可根據(jù)圖11來理解
while(first != NULL) //遍歷剩下無序的鏈表
{
//注意：這里for語句就是體現(xiàn)直接插入排序思想的地方
for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next); //無序節(jié)點在有序鏈表中找插入的位置
//退出for循環(huán)，就是找到了插入的位置，應該將t節(jié)點插入到p節(jié)點之后，q節(jié)點之前
//注意：按道理來說，這句話可以放到下面注釋了的那個位置也應該對的，但是就是不能。原因：你若理解了上面的第3條，就知道了
//下面的插入就是將t節(jié)點即是first節(jié)點插入到p節(jié)點之后，已經改變了first節(jié)點，所以first節(jié)點應該在被修改之前往后移動，不能放到下面注釋的位置上去
first = first->next; //無序鏈表中的節(jié)點離開，以便它插入到有序鏈表中
if (q == head) //插在第一個節(jié)點之前
{
head = t;
}
else //p是q的前驅
{
p->next = t;
}
t->next = q; //完成插入動作
//first = first->next;
}
return head;
}
對鏈表進行冒泡排序的基本思想就是對當前還未排好序的范圍內的全部節(jié)點，自上而下對相鄰的兩個節(jié)點依次進行比較和調整，讓鍵值（就是用它排 序的字段，我們取學號num為鍵值）較大的節(jié)點往下沉，鍵值較小的往上冒。即：每當兩相鄰的節(jié)點比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。
單向鏈表的冒泡排序圖示：
---->[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個節(jié)點的鏈表冒泡排序
任意兩個相鄰節(jié)點p、q位置互換圖示:
假設p1->next指向p，那么顯然p1->next->next就指向q,
p1->next->next->next就指向q的后繼節(jié)點，我們用p2保存
p1->next->next指針。即：p2=p1->next->next，則有：
[ ]---->[p]---------->[q]---->[ ]（排序前）
p1->next p1->next->next p2->next
圖15
[ ]---->[q]---------->[p]---->[ ]（排序后）
圖16
1、排序后q節(jié)點指向p節(jié)點，在調整指向之前，我們要保存原p的指向節(jié)點地址，即：p2=p1->next->next；
2、順著這一步一步往下推,排序后圖16中p1->next->next要指的是p2->next,所以p1->next->next=p2->next;
3、在圖15中p2->next原是q發(fā)出來的指向，排序后圖16中q的指向要變?yōu)橹赶騪的，而原來p1->next是指向p的，所以p2->next=p1->next;
4、在圖15中p1->next原是指向p的，排序后圖16中p1->next要指向q,原來p1->next->next（即p2)是指向q的，所以p1->next=p2;
5、至此，我們完成了相鄰兩節(jié)點的順序交換。
6、下面的程序描述改進了一點就是記錄了每次最后一次節(jié)點下沉的位置，這樣我們不必每次都從頭到尾的掃描，只需要掃描到記錄點為止。 因為后面的都已經是排好序的了。
對鏈表進行冒泡排序的函數(shù)為：
/*
==========================
功能：冒泡排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *BubbleSort (struct student *head)
{
struct student *endpt; //控制循環(huán)比較
struct student *p; //臨時指針變量
struct student *p1,*p2;
p1 = (struct student *) malloc (LEN);
p1->next = head; //注意理解：我們增加一個節(jié)點，放在第一個節(jié)點的前面，主要是為了便于比較。因為第一個節(jié)點沒有前驅，我們不能交換地址
head = p1; //讓head指向p1節(jié)點，排序完成后，我們再把p1節(jié)點釋放掉
for (endpt = NULL; endpt != head; endpt = p) //結合第6點理解
{
for (p = p1 = head; p1->next->next != endpt; p1 = p1->next)
{
if (p1->next->num > p1->next->next->num) //如果前面的節(jié)點鍵值比后面節(jié)點的鍵值大，則交換
{
p2 = p1->next->next; //結合第1點理解
p1->next->next = p2->next; //結合第2點理解
p2->next = p1->next; //結合第3點理解
p1->next = p2; //結合第4點理解
p = p1->next->next; //結合第6點理解
}
}
}
p1 = head; //把p1的信息去掉
head = head->next; //讓head指向排序后的第一個節(jié)點
free (p1); //釋放p1
p1 = NULL; //p1置為NULL，保證不產生“野指針”，即地址不確定的指針變量
return head;
}
有序鏈表插入節(jié)點示意圖：
---->[NULL]（空有序鏈表）
head
圖18：空有序鏈表（空有序鏈表好解決，直接讓head指向它就是了。）
以下討論不為空的有序鏈表。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（有序鏈表）
head 1->next 2->next 3->next n->next
圖18：有N個節(jié)點的有序鏈表
插入node節(jié)點的位置有兩種情況：一是第一個節(jié)點前，二是其它節(jié)點前或后。
---->[node]---->[1]---->[2]---->[3]...---->[n]---->[NULL]
head node->next 1->next 2->next 3->next n->next
圖19：node節(jié)點插在第一個節(jié)點前
---->[1]---->[2]---->[3]...---->[node]...---->[n]---->[NULL]
head 1->next 2->next 3->next node->next n->next
插入有序鏈表的函數(shù)為：
/*
==========================
功能：插入有序鏈表的某個節(jié)點的后面(從小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *SortInsert (struct student *head, struct student *node)
{
struct student *p; //p保存當前需要檢查的節(jié)點的地址
struct student *t; //臨時指針變量
if (head == NULL) //處理空的有序鏈表
{
head = node;
node->next = NULL;
n += 1; //插入完畢，節(jié)點總數(shù)加
return head;
}
p = head; //有序鏈表不為空
while(p->num < node->num && p != NULL) //p指向的節(jié)點的學號比插入節(jié)點的學號小，并且它不等于NULL
{
t = p; //保存當前節(jié)點的前驅，以便后面判斷后處理
p = p->next; //后移一個節(jié)點
}
if (p == head) //剛好插入第一個節(jié)點之前
{
node->next = p;
head = node;
}
else //插入其它節(jié)點之后
{
t->next = node; //把node節(jié)點加進去
node->next = p;
}
n += 1; //插入完畢，節(jié)點總數(shù)加1
return head;
}
綜上所述，鏈表的各類操作函數(shù)的完整代碼如下：
#include "stdlib.h"
#include "stdio.h"
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
int num; //學號
float score; //分數(shù)，其他信息可以繼續(xù)在下面增加字段
struct student *next; //指向下一節(jié)點的指針
};
int n; //節(jié)點總數(shù)
/*
==========================
功能：創(chuàng)建n個節(jié)點的鏈表
返回：指向鏈表表頭的指針
==========================
*/
struct student *Create()
{
struct student *head; //頭節(jié)點
struct student *p1 = NULL; //p1保存創(chuàng)建的新節(jié)點的地址
struct student *p2 = NULL; //p2保存原鏈表最后一個節(jié)點的地址
n = 0; //創(chuàng)建前鏈表的節(jié)點總數(shù)為0：空鏈表
p1 = (struct student *) malloc (LEN); //開辟一個新節(jié)點
p2 = p1; //如果節(jié)點開辟成功，則p2先把它的指針保存下來以備后用
if(p1==NULL) //節(jié)點開辟不成功
{
printf ("\nCann't create it, try it again in a moment!\n");
return NULL;
}
else //節(jié)點開辟成功
{
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) //只要學號不為0，就繼續(xù)錄入下一個節(jié)點
{
n += 1; //節(jié)點總數(shù)增加1個
if(n == 1) //如果節(jié)點總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點p1
{
head = p1;
p2->next = NULL; //此時的p2就是p1,也就是p1->next指向NULL。
}
else
{
p2->next = p1; //指向上次下面剛剛開辟的新節(jié)點
}
p2 = p1; //把p1的地址給p2保留，然后p1產生新的節(jié)點
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ù)單向鏈表的最后一個節(jié)點要指向NULL
free(p1); //p1->num為0的時候跳出了while循環(huán)，并且釋放p1
p1 = NULL; //特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針
return head; //返回創(chuàng)建鏈表的頭指針
}
/*
===========================
功能：輸出節(jié)點
返回： void
===========================
*/
void Print(struct student *head)
{
struct student *p;
printf ("\nNow , These %d records are:\n", n);
p = head;
if(head != NULL) //只要不是空鏈表，就輸出鏈表中所有節(jié)點
{
printf("head is %o\n", head); //輸出頭指針指向的地址
do
{
/*
輸出相應的值：當前節(jié)點地址、各字段值、當前節(jié)點的下一節(jié)點地址。
這樣輸出便于讀者形象看到一個單向鏈表在計算機中的存儲結構，和我們
設計的圖示是一模一樣的。
*/
printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);
p = p->next; //移到下一個節(jié)點
}
while (p != NULL);
}
}
/*
==========================
功能：刪除指定節(jié)點
(此例中是刪除指定學號的節(jié)點)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Del (struct student *head, int num)
{
struct student *p1; //p1保存當前需要檢查的節(jié)點的地址
struct student *p2; //p2保存當前檢查過的節(jié)點的地址
if (head == NULL) //是空鏈表（結合圖3理解）
{
printf ("\nList is null!\n");
return head;
}
//定位要刪除的節(jié)點
p1 = head;
while (p1->num != num && p1->next != NULL) //p1指向的節(jié)點不是所要查找的，并且它不是最后一個節(jié)點，就繼續(xù)往下找
{
p2 = p1; //保存當前節(jié)點的地址
p1 = p1->next; //后移一個節(jié)點
}
if(p1->num==num) //找到了。（結合圖4、5理解）
{
if (p1 == head) //如果要刪除的節(jié)點是第一個節(jié)點
{
head = p1->next; //頭指針指向第一個節(jié)點的后一個節(jié)點，也就是第二個節(jié)點。這樣第一個節(jié)點就不在鏈表中，即刪除
}
else //如果是其它節(jié)點，則讓原來指向當前節(jié)點的指針，指向它的下一個節(jié)點，完成刪除
{
p2->next = p1->next;
}
free (p1); //釋放當前節(jié)點
p1 = NULL;
printf ("\ndelete %ld success!\n", num);
n -= 1; //節(jié)點總數(shù)減1個
}
else //沒有找到
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
//銷毀鏈表
void DestroyList(struct student *head)
{
struct student *p;
if(head==NULL)
return 0;
while(head)
{
p=head->next;
free(head);
head=p;
}
return 1;
}
/*
==========================
功能：插入指定節(jié)點的后面
(此例中是指定學號的節(jié)點)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Insert (struct student *head, int num, struct student *node)
{
struct student *p1; //p1保存當前需要檢查的節(jié)點的地址
if (head == NULL) //（結合圖示7理解）
{
head = node;
node->next = NULL;
n += 1;
return head;
}
p1 = head;
while(p1->num != num && p1->next != NULL) //p1指向的節(jié)點不是所要查找的，并且它不是最后一個節(jié)點，繼續(xù)往下找
{
p1 = p1->next; //后移一個節(jié)點
}
if (p1->num==num) //找到了（結合圖示8理解）
{
node->next = p1->next; //顯然node的下一節(jié)點是原p1的next
p1->next = node; //插入后，原p1的下一節(jié)點就是要插入的node
n += 1; //節(jié)點總數(shù)增加1個
}
else
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
/*
==========================
功能：反序節(jié)點
(鏈表的頭變成鏈表的尾，鏈表的尾變成頭)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Reverse (struct student *head)
{
struct student *p; //臨時存儲
struct student *p1; //存儲返回結果
struct student *p2; //源結果節(jié)點一個一個取
p1 = NULL; //開始顛倒時，已顛倒的部分為空
p2 = head; //p2指向鏈表的頭節(jié)點
while(p2 != NULL)
{
p = p2->next;
p2->next = p1;
p1 = p2;
p2 = p;
}
head = p1;
return head;
}
/*
==========================
功能：選擇排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *SelectSort (struct student *head)
{
struct student *first; //排列后有序鏈的表頭指針
struct student *tail; //排列后有序鏈的表尾指針
struct student *p_min; //保留鍵值更小的節(jié)點的前驅節(jié)點的指針
struct student *min; //存儲最小節(jié)點
struct student *p; //當前比較的節(jié)點
first = NULL;
while(head != NULL) //在鏈表中找鍵值最小的節(jié)點
{
//注意：這里for語句就是體現(xiàn)選擇排序思想的地方
for (p = head, min = head; p->next != NULL; p = p->next) //循環(huán)遍歷鏈表中的節(jié)點，找出此時最小的節(jié)點
{
if (p->next->num < min->num) //找到一個比當前min小的節(jié)點
{
p_min = p; //保存找到節(jié)點的前驅節(jié)點：顯然p->next的前驅節(jié)點是p
min = p->next; //保存鍵值更小的節(jié)點
}
}
//上面for語句結束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應的條件判斷，安排它離開原來的鏈表
//第一件事
if (first == NULL) //如果有序鏈表目前還是一個空鏈表
{
first = min; //第一次找到鍵值最小的節(jié)點
tail = min; //注意：尾指針讓它指向最后的一個節(jié)點
}
else //有序鏈表中已經有節(jié)點
{
tail->next = min; //把剛找到的最小節(jié)點放到最后，即讓尾指針的next指向它
tail = min; //尾指針也要指向它
}
//第二件事
if (min == head) //如果找到的最小節(jié)點就是第一個節(jié)點
{
head = head->next; //顯然讓head指向原h(huán)ead->next,即第二個節(jié)點，就OK
}
else //如果不是第一個節(jié)點
{
p_min->next = min->next; //前次最小節(jié)點的next指向當前min的next,這樣就讓min離開了原鏈表
}
}
if (first != NULL) //循環(huán)結束得到有序鏈表first
{
tail->next = NULL; //單向鏈表的最后一個節(jié)點的next應該指向NULL
}
head = first;
return head;
}
/*
==========================
功能：直接插入排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *InsertSort (struct student *head)
{
struct student *first; //為原鏈表剩下用于直接插入排序的節(jié)點頭指針
struct student *t; //臨時指針變量：插入節(jié)點
struct student *p,*q; //臨時指針變量
first = head->next; //原鏈表剩下用于直接插入排序的節(jié)點鏈表：可根據(jù)圖12來理解
head->next = NULL; //只含有一個節(jié)點的鏈表的有序鏈表：可根據(jù)圖11來理解
while(first != NULL) //遍歷剩下無序的鏈表
{
//注意：這里for語句就是體現(xiàn)直接插入排序思想的地方
for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next); //無序節(jié)點在有序鏈表中找插入的位置
//退出for循環(huán)，就是找到了插入的位置，應該將t節(jié)點插入到p節(jié)點之后，q節(jié)點之前
//注意：按道理來說，這句話可以放到下面注釋了的那個位置也應該對的，但是就是不能。原因：你若理解了上面的第3條，就知道了
//下面的插入就是將t節(jié)點即是first節(jié)點插入到p節(jié)點之后，已經改變了first節(jié)點，所以first節(jié)點應該在被修改之前往后移動，不能放到下面注釋的位置上去
first = first->next; //無序鏈表中的節(jié)點離開，以便它插入到有序鏈表中
if (q == head) //插在第一個節(jié)點之前
{
head = t;
}
else //p是q的前驅
{
p->next = t;
}
t->next = q; //完成插入動作
//first = first->next;
}
return head;
}
/*
==========================
功能：冒泡排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *BubbleSort (struct student *head)
{
struct student *endpt; //控制循環(huán)比較
struct student *p; //臨時指針變量
struct student *p1,*p2;
p1 = (struct student *) malloc (LEN);
p1->next = head; //注意理解：我們增加一個節(jié)點，放在第一個節(jié)點的前面，主要是為了便于比較。因為第一個節(jié)點沒有前驅，我們不能交換地址
head = p1; //讓head指向p1節(jié)點，排序完成后，我們再把p1節(jié)點釋放掉
for (endpt = NULL; endpt != head; endpt = p) //結合第6點理解
{
for (p = p1 = head; p1->next->next != endpt; p1 = p1->next)
{
if (p1->next->num > p1->next->next->num) //如果前面的節(jié)點鍵值比后面節(jié)點的鍵值大，則交換
{
p2 = p1->next->next; //結合第1點理解
p1->next->next = p2->next; //結合第2點理解
p2->next = p1->next; //結合第3點理解
p1->next = p2; //結合第4點理解
p = p1->next->next; //結合第6點理解
}
}
}
p1 = head; //把p1的信息去掉
head = head->next; //讓head指向排序后的第一個節(jié)點
free (p1); //釋放p1
p1 = NULL; //p1置為NULL，保證不產生“野指針”，即地址不確定的指針變量
return head;
}
/*
==========================
功能：插入有序鏈表的某個節(jié)點的后面(從小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *SortInsert (struct student *head, struct student *node)
{
struct student *p; //p保存當前需要檢查的節(jié)點的地址
struct student *t; //臨時指針變量
if (head == NULL) //處理空的有序鏈表
{
head = node;
node->next = NULL;
n += 1; //插入完畢，節(jié)點總數(shù)加
return head;
}
p = head; //有序鏈表不為空
while(p->num < node->num && p != NULL) //p指向的節(jié)點的學號比插入節(jié)點的學號小，并且它不等于NULL
{
t = p; //保存當前節(jié)點的前驅，以便后面判斷后處理
p = p->next; //后移一個節(jié)點
}
if (p == head) //剛好插入第一個節(jié)點之前
{
node->next = p;
head = node;
}
else //插入其它節(jié)點之后
{
t->next = node; //把node節(jié)點加進去
node->next = p;
}
n += 1; //插入完畢，節(jié)點總數(shù)加1
return head;
}
/*
以上函數(shù)的測試程序：
提示：根據(jù)測試函數(shù)的不同注釋相應的程序段，這也是一種測試方法。
*/
int main(void)
{
struct student *head;
struct student *stu;
int thenumber;
// 測試Create()、Print()
head = Create();
Print(head);
//測試Del()
printf("\nWhich one delete: ");
scanf("%d",&thenumber);
head = Del(head,thenumber);
Print(head);
//測試Insert()
stu = (struct student *)malloc(LEN);
printf("\nPlease input insert node -- num,score: ");
scanf("%d %f",&stu->num,&stu->score);
printf("\nInsert behind num: ");
scanf("%d",&thenumber);
head = Insert(head,thenumber,stu);
Print(head);
//測試Reverse()
printf("\nReverse the LinkList: \n");
head = Reverse(head);
Print(head);
//測試SelectSort()
printf("\nSelectSort the LinkList: \n");
head = SelectSort(head);
Print(head);
//測試InsertSort()
printf("\nInsertSort the LinkList: \n");
head = InsertSort(head);
Print(head);
//測試BubbleSort()
printf("\nBubbleSort the LinkList: \n");
head = BubbleSort(head);
Print(head);
printf("\nSortInsert the LinkList: \n");
//測試SortInsert():上面創(chuàng)建鏈表，輸入節(jié)點時請注意學號num從小到大的順序
stu = (struct student *)malloc(LEN);
printf("\nPlease input insert node -- num,score: ");
scanf("%d %f",&stu->num,&stu->score);
head = SortInsert(head,stu);
Print(head);
//銷毀鏈表
DestroyList(head);
printf ("\n");
system ("pause");
}
鏈表是一種常見的重要的數(shù)據(jù)結構。它是動態(tài)地進行存儲分配的一種結構。它可以根據(jù)需要開辟內存單元。鏈表有一個“頭指針”變量，以head表示，它存放一個地址。該地址指向一個元素。鏈表中每一個元素稱為“結點”，每個結點都應包括兩個部分：一為用戶需要用的實際數(shù)據(jù)，二為下一個結點的地址。因此，head指向第一個元素：第一個元素又指向第二個元素；……，直到最后一個元素，該元素不再指向其它元素，它稱為“表尾”，它的地址部分放一個“NULL”（表示“空地址”），鏈表到此結束。
鏈表的各類操作包括：學習單向鏈表的創(chuàng)建、刪除、 插入（無序、有序）、輸出、 排序（選擇、插入、冒泡）、反序等等。
單向鏈表的圖示：
---->[NULL]
head
圖1：空鏈表
---->[p1]---->[p2]...---->[pn]---->[NULL]
head p1->next p2->next pn->next
圖2：有N個節(jié)點的鏈表
創(chuàng)建n個節(jié)點的鏈表的函數(shù)為：
復制代碼 代碼如下:
#include "stdlib.h"
#include "stdio.h"
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
int num; //學號
float score; //分數(shù)，其他信息可以繼續(xù)在下面增加字段
struct student *next; //指向下一節(jié)點的指針
};
int n; //節(jié)點總數(shù)
/*
==========================
功能：創(chuàng)建n個節(jié)點的鏈表
返回：指向鏈表表頭的指針
==========================
*/
struct student *Create()
{
struct student *head; //頭節(jié)點
struct student *p1 = NULL; //p1保存創(chuàng)建的新節(jié)點的地址
struct student *p2 = NULL; //p2保存原鏈表最后一個節(jié)點的地址
n = 0; //創(chuàng)建前鏈表的節(jié)點總數(shù)為0：空鏈表
p1 = (struct student *) malloc (LEN); //開辟一個新節(jié)點
p2 = p1; //如果節(jié)點開辟成功，則p2先把它的指針保存下來以備后用
if(p1==NULL) //節(jié)點開辟不成功
{
printf ("\nCann't create it, try it again in a moment!\n");
return NULL;
}
else //節(jié)點開辟成功
{
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) //只要學號不為0，就繼續(xù)錄入下一個節(jié)點
{
n += 1; //節(jié)點總數(shù)增加1個
if(n == 1) //如果節(jié)點總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點p1
{
head = p1;
p2->next = NULL; //此時的p2就是p1,也就是p1->next指向NULL。
}
else
{
p2->next = p1; //指向上次下面剛剛開辟的新節(jié)點
}
p2 = p1; //把p1的地址給p2保留，然后p1產生新的節(jié)點
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ù)單向鏈表的最后一個節(jié)點要指向NULL
free(p1); //p1->num為0的時候跳出了while循環(huán)，并且釋放p1
p1 = NULL; //特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針
return head; //返回創(chuàng)建鏈表的頭指針
}
輸出鏈表中節(jié)點的函數(shù)為：
復制代碼 代碼如下:
/*
===========================
功能：輸出節(jié)點
返回： void
===========================
*/
void Print(struct student *head)
{
struct student *p;
printf ("\nNow , These %d records are:\n", n);
p = head;
if(head != NULL) //只要不是空鏈表，就輸出鏈表中所有節(jié)點
{
printf("head is %o\n", head); //輸出頭指針指向的地址
do
{
/*
輸出相應的值：當前節(jié)點地址、各字段值、當前節(jié)點的下一節(jié)點地址。
這樣輸出便于讀者形象看到一個單向鏈表在計算機中的存儲結構，和我們
設計的圖示是一模一樣的。
*/
printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);
p = p->next; //移到下一個節(jié)點
}
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個節(jié)點的鏈表，刪除第一個節(jié)點
結合原鏈表和刪除后的鏈表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白head就是第1個節(jié)點，head->next就是第2個節(jié)點；
2、刪除后head指向第2個節(jié)點，就是讓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個節(jié)點的鏈表，刪除中間一個（這里圖示刪除第2個）
結合原鏈表和刪除后的鏈表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白head就是第1個節(jié)點，1->next就是第2個節(jié)點，2->next就是第3個節(jié)點；
2、刪除后2，1指向第3個節(jié)點，就是讓1->next=2->next。
刪除指定學號的節(jié)點的函數(shù)為：
復制代碼 代碼如下:
/*
==========================
功能：刪除指定節(jié)點
(此例中是刪除指定學號的節(jié)點)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Del (struct student *head, int num)
{
struct student *p1; //p1保存當前需要檢查的節(jié)點的地址
struct student *p2; //p2保存當前檢查過的節(jié)點的地址
if (head == NULL) //是空鏈表（結合圖3理解）
{
printf ("\nList is null!\n");
return head;
}
//定位要刪除的節(jié)點
p1 = head;
while (p1->num != num && p1->next != NULL) //p1指向的節(jié)點不是所要查找的，并且它不是最后一個節(jié)點，就繼續(xù)往下找
{
p2 = p1; //保存當前節(jié)點的地址
p1 = p1->next; //后移一個節(jié)點
}
if(p1->num==num) //找到了。（結合圖4、5理解）
{
if (p1 == head) //如果要刪除的節(jié)點是第一個節(jié)點
{
head = p1->next; //頭指針指向第一個節(jié)點的后一個節(jié)點，也就是第二個節(jié)點。這樣第一個節(jié)點就不在鏈表中，即刪除
}
else //如果是其它節(jié)點，則讓原來指向當前節(jié)點的指針，指向它的下一個節(jié)點，完成刪除
{
p2->next = p1->next;
}
free (p1); //釋放當前節(jié)點
p1 = NULL;
printf ("\ndelete %ld success!\n", num);
n -= 1; //節(jié)點總數(shù)減1個
}
else //沒有找到
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
單向鏈表的插入圖示：
---->[NULL]（原鏈表）
head
---->[1]---->[NULL]（插入后的鏈表）
head 1->next
圖7 空鏈表插入一個節(jié)點
結合原鏈表和插入后的鏈表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白空鏈表head指向NULL就是head=NULL；
2、插入后head指向第1個節(jié)點，就是讓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個節(jié)點的鏈表，插入一個節(jié)點（這里圖示插入第2個后面）
結合原鏈表和插入后的鏈表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白原1->next就是節(jié)點2，2->next就是節(jié)點3；
2、插入后x指向第3個節(jié)點,2指向x，就是讓x->next=2->next,1->next=x。
插入指定節(jié)點的后面的函數(shù)為：
復制代碼 代碼如下:
/*
==========================
功能：插入指定節(jié)點的后面
(此例中是指定學號的節(jié)點)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Insert (struct student *head, int num, struct student *node)
{
struct student *p1; //p1保存當前需要檢查的節(jié)點的地址
if (head == NULL) //（結合圖示7理解）
{
head = node;
node->next = NULL;
n += 1;
return head;
}
p1 = head;
while(p1->num != num && p1->next != NULL) //p1指向的節(jié)點不是所要查找的，并且它不是最后一個節(jié)點，繼續(xù)往下找
{
p1 = p1->next; //后移一個節(jié)點
}
if (p1->num==num) //找到了（結合圖示8理解）
{
node->next = p1->next; //顯然node的下一節(jié)點是原p1的next
p1->next = node; //插入后，原p1的下一節(jié)點就是要插入的node
n += 1; //節(jié)點總數(shù)增加1個
}
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個節(jié)點的鏈表反序
結合原鏈表和插入后的鏈表，就很容易寫出相應的代碼。操作方法如下：
1、我們需要一個讀原鏈表的指針p2,存反序鏈表的p1=NULL（剛好最后一個節(jié)點的next為NULL）,還有一個臨時存儲變量p；
2、p2在原鏈表中讀出一個節(jié)點，我們就把它放到p1中，p就是用來處理節(jié)點放置順序的問題；
3、比如，現(xiàn)在我們取得一個2,為了我們繼續(xù)往下取節(jié)點，我們必須保存它的next值，由原鏈表可知p=2->next;
4、然后由反序后的鏈表可知，反序后2->next要指向1，則2->next=1;
5、好了，現(xiàn)在已經反序一個節(jié)點，接著處理下一個節(jié)點就需要保存此時的信息：
p1變成剛剛加入的2，即p1=2;p2要變成它的下一節(jié)點，就是上面我們保存的p,即p2=p。
反序鏈表的函數(shù)為：
復制代碼 代碼如下:
/*
==========================
功能：反序節(jié)點
(鏈表的頭變成鏈表的尾，鏈表的尾變成頭)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Reverse (struct student *head)
{
struct student *p; //臨時存儲
struct student *p1; //存儲返回結果
struct student *p2; //源結果節(jié)點一個一個取
p1 = NULL; //開始顛倒時，已顛倒的部分為空
p2 = head; //p2指向鏈表的頭節(jié)點
while(p2 != NULL)
{
p = p2->next;
p2->next = p1;
p1 = p2;
p2 = p;
}
head = p1;
return head;
}
對鏈表進行選擇排序的基本思想就是反復從還未排好序的那些節(jié)點中，選出鍵值（就是用它排序的字段，我們取學號num為鍵值）最小的節(jié)點，依次重新組合成一個鏈表。
我認為寫鏈表這類程序，關鍵是理解：head存儲的是第一個節(jié)點的地址，head->next存儲的是第二個節(jié)點的地址；任意一個節(jié)點p的地址，只能通過它前一個節(jié)點的next來求得。
單向鏈表的選擇排序圖示：
---->[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個節(jié)點的鏈表選擇排序
1、先在原鏈表中找最小的，找到一個后就把它放到另一個空的鏈表中；
2、空鏈表中安放第一個進來的節(jié)點，產生一個有序鏈表,并且讓它在原鏈表中分離出來（此時要注意原鏈表中出來的是第一個節(jié)點還是中間其它節(jié)點）；
3、繼續(xù)在原鏈表中找下一個最小的，找到后把它放入有序鏈表的尾指針的next,然后它變成其尾指針；
對鏈表進行選擇排序的函數(shù)為：
復制代碼 代碼如下:
/*
==========================
功能：選擇排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *SelectSort (struct student *head)
{
struct student *first; //排列后有序鏈的表頭指針
struct student *tail; //排列后有序鏈的表尾指針
struct student *p_min; //保留鍵值更小的節(jié)點的前驅節(jié)點的指針
struct student *min; //存儲最小節(jié)點
struct student *p; //當前比較的節(jié)點
first = NULL;
while(head != NULL) //在鏈表中找鍵值最小的節(jié)點
{
//注意：這里for語句就是體現(xiàn)選擇排序思想的地方
for (p = head, min = head; p->next != NULL; p = p->next) //循環(huán)遍歷鏈表中的節(jié)點，找出此時最小的節(jié)點
{
if (p->next->num < min->num) //找到一個比當前min小的節(jié)點
{
p_min = p; //保存找到節(jié)點的前驅節(jié)點：顯然p->next的前驅節(jié)點是p
min = p->next; //保存鍵值更小的節(jié)點
}
}
//上面for語句結束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應的條件判斷，安排它離開原來的鏈表
//第一件事
if (first == NULL) //如果有序鏈表目前還是一個空鏈表
{
first = min; //第一次找到鍵值最小的節(jié)點
tail = min; //注意：尾指針讓它指向最后的一個節(jié)點
}
else //有序鏈表中已經有節(jié)點
{
tail->next = min; //把剛找到的最小節(jié)點放到最后，即讓尾指針的next指向它
tail = min; //尾指針也要指向它
}
//第二件事
if (min == head) //如果找到的最小節(jié)點就是第一個節(jié)點
{
head = head->next; //顯然讓head指向原h(huán)ead->next,即第二個節(jié)點，就OK
}
else //如果不是第一個節(jié)點
{
p_min->next = min->next; //前次最小節(jié)點的next指向當前min的next,這樣就讓min離開了原鏈表
}
}
if (first != NULL) //循環(huán)結束得到有序鏈表first
{
tail->next = NULL; //單向鏈表的最后一個節(jié)點的next應該指向NULL
}
head = first;
return head;
}
對鏈表進行直接插入排序的基本思想就是假設鏈表的前面n-1個節(jié)點是已經按鍵值（就是用它排序的字段，我們取學號num為鍵值）排好序的，對于節(jié)點n在這個序列中找插入位置，使得n插入后新序列仍然有序。按照這種思想，依次對鏈表從頭到尾執(zhí)行一遍，就可以使無序鏈表變?yōu)橛行蜴湵怼?BR> 單向鏈表的直接插入排序圖示：
---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原鏈表）
head 1->next 3->next 2->next n->next
---->[1]---->[NULL]（從原鏈表中取第1個節(jié)點作為只有一個節(jié)點的有序鏈表）
head
圖11
---->[3]---->[2]...---->[n]---->[NULL]（原鏈表剩下用于直接插入排序的節(jié)點）
first 3->next 2->next n->next
圖12
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后鏈表）
head 1->next 2->next 3->next n->next
圖13：有N個節(jié)點的鏈表直接插入排序
1、先在原鏈表中以第一個節(jié)點為一個有序鏈表，其余節(jié)點為待定節(jié)點。
2、從圖12鏈表中取節(jié)點，到圖11鏈表中定位插入。
3、上面圖示雖說畫了兩條鏈表，其實只有一條鏈表。在排序中，實質只增加了一個用于指向剩下需要排序節(jié)點的頭指針first罷了。
這一點請讀者務必搞清楚，要不然就可能認為它和上面的選擇排序法一樣了。
對鏈表進行直接插入排序的函數(shù)為：
復制代碼 代碼如下:
/*
==========================
功能：直接插入排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *InsertSort (struct student *head)
{
struct student *first; //為原鏈表剩下用于直接插入排序的節(jié)點頭指針
struct student *t; //臨時指針變量：插入節(jié)點
struct student *p,*q; //臨時指針變量
first = head->next; //原鏈表剩下用于直接插入排序的節(jié)點鏈表：可根據(jù)圖12來理解
head->next = NULL; //只含有一個節(jié)點的鏈表的有序鏈表：可根據(jù)圖11來理解
while(first != NULL) //遍歷剩下無序的鏈表
{
//注意：這里for語句就是體現(xiàn)直接插入排序思想的地方
for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next); //無序節(jié)點在有序鏈表中找插入的位置
//退出for循環(huán)，就是找到了插入的位置，應該將t節(jié)點插入到p節(jié)點之后，q節(jié)點之前
//注意：按道理來說，這句話可以放到下面注釋了的那個位置也應該對的，但是就是不能。原因：你若理解了上面的第3條，就知道了
//下面的插入就是將t節(jié)點即是first節(jié)點插入到p節(jié)點之后，已經改變了first節(jié)點，所以first節(jié)點應該在被修改之前往后移動，不能放到下面注釋的位置上去
first = first->next; //無序鏈表中的節(jié)點離開，以便它插入到有序鏈表中
if (q == head) //插在第一個節(jié)點之前
{
head = t;
}
else //p是q的前驅
{
p->next = t;
}
t->next = q; //完成插入動作
//first = first->next;
}
return head;
}
對鏈表進行冒泡排序的基本思想就是對當前還未排好序的范圍內的全部節(jié)點，自上而下對相鄰的兩個節(jié)點依次進行比較和調整，讓鍵值（就是用它排 序的字段，我們取學號num為鍵值）較大的節(jié)點往下沉，鍵值較小的往上冒。即：每當兩相鄰的節(jié)點比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。
單向鏈表的冒泡排序圖示：
---->[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個節(jié)點的鏈表冒泡排序
任意兩個相鄰節(jié)點p、q位置互換圖示:
假設p1->next指向p，那么顯然p1->next->next就指向q,
p1->next->next->next就指向q的后繼節(jié)點，我們用p2保存
p1->next->next指針。即：p2=p1->next->next，則有：
[ ]---->[p]---------->[q]---->[ ]（排序前）
p1->next p1->next->next p2->next
圖15
[ ]---->[q]---------->[p]---->[ ]（排序后）
圖16
1、排序后q節(jié)點指向p節(jié)點，在調整指向之前，我們要保存原p的指向節(jié)點地址，即：p2=p1->next->next；
2、順著這一步一步往下推,排序后圖16中p1->next->next要指的是p2->next,所以p1->next->next=p2->next;
3、在圖15中p2->next原是q發(fā)出來的指向，排序后圖16中q的指向要變?yōu)橹赶騪的，而原來p1->next是指向p的，所以p2->next=p1->next;
4、在圖15中p1->next原是指向p的，排序后圖16中p1->next要指向q,原來p1->next->next（即p2)是指向q的，所以p1->next=p2;
5、至此，我們完成了相鄰兩節(jié)點的順序交換。
6、下面的程序描述改進了一點就是記錄了每次最后一次節(jié)點下沉的位置，這樣我們不必每次都從頭到尾的掃描，只需要掃描到記錄點為止。 因為后面的都已經是排好序的了。
對鏈表進行冒泡排序的函數(shù)為：
復制代碼 代碼如下:
/*
==========================
功能：冒泡排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *BubbleSort (struct student *head)
{
struct student *endpt; //控制循環(huán)比較
struct student *p; //臨時指針變量
struct student *p1,*p2;
p1 = (struct student *) malloc (LEN);
p1->next = head; //注意理解：我們增加一個節(jié)點，放在第一個節(jié)點的前面，主要是為了便于比較。因為第一個節(jié)點沒有前驅，我們不能交換地址
head = p1; //讓head指向p1節(jié)點，排序完成后，我們再把p1節(jié)點釋放掉
for (endpt = NULL; endpt != head; endpt = p) //結合第6點理解
{
for (p = p1 = head; p1->next->next != endpt; p1 = p1->next)
{
if (p1->next->num > p1->next->next->num) //如果前面的節(jié)點鍵值比后面節(jié)點的鍵值大，則交換
{
p2 = p1->next->next; //結合第1點理解
p1->next->next = p2->next; //結合第2點理解
p2->next = p1->next; //結合第3點理解
p1->next = p2; //結合第4點理解
p = p1->next->next; //結合第6點理解
}
}
}
p1 = head; //把p1的信息去掉
head = head->next; //讓head指向排序后的第一個節(jié)點
free (p1); //釋放p1
p1 = NULL; //p1置為NULL，保證不產生“野指針”，即地址不確定的指針變量
return head;
}
有序鏈表插入節(jié)點示意圖：
---->[NULL]（空有序鏈表）
head
圖18：空有序鏈表（空有序鏈表好解決，直接讓head指向它就是了。）
以下討論不為空的有序鏈表。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（有序鏈表）
head 1->next 2->next 3->next n->next
圖18：有N個節(jié)點的有序鏈表
插入node節(jié)點的位置有兩種情況：一是第一個節(jié)點前，二是其它節(jié)點前或后。
---->[node]---->[1]---->[2]---->[3]...---->[n]---->[NULL]
head node->next 1->next 2->next 3->next n->next
圖19：node節(jié)點插在第一個節(jié)點前
---->[1]---->[2]---->[3]...---->[node]...---->[n]---->[NULL]
head 1->next 2->next 3->next node->next n->next
插入有序鏈表的函數(shù)為：
復制代碼 代碼如下:
/*
==========================
功能：插入有序鏈表的某個節(jié)點的后面(從小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *SortInsert (struct student *head, struct student *node)
{
struct student *p; //p保存當前需要檢查的節(jié)點的地址
struct student *t; //臨時指針變量
if (head == NULL) //處理空的有序鏈表
{
head = node;
node->next = NULL;
n += 1; //插入完畢，節(jié)點總數(shù)加
return head;
}
p = head; //有序鏈表不為空
while(p->num < node->num && p != NULL) //p指向的節(jié)點的學號比插入節(jié)點的學號小，并且它不等于NULL
{
t = p; //保存當前節(jié)點的前驅，以便后面判斷后處理
p = p->next; //后移一個節(jié)點
}
if (p == head) //剛好插入第一個節(jié)點之前
{
node->next = p;
head = node;
}
else //插入其它節(jié)點之后
{
t->next = node; //把node節(jié)點加進去
node->next = p;
}
n += 1; //插入完畢，節(jié)點總數(shù)加1
return head;
}
綜上所述，鏈表的各類操作函數(shù)的完整代碼如下：
復制代碼 代碼如下:
#include "stdlib.h"
#include "stdio.h"
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
int num; //學號
float score; //分數(shù)，其他信息可以繼續(xù)在下面增加字段
struct student *next; //指向下一節(jié)點的指針
};
int n; //節(jié)點總數(shù)
/*
==========================
功能：創(chuàng)建n個節(jié)點的鏈表
返回：指向鏈表表頭的指針
==========================
*/
struct student *Create()
{
struct student *head; //頭節(jié)點
struct student *p1 = NULL; //p1保存創(chuàng)建的新節(jié)點的地址
struct student *p2 = NULL; //p2保存原鏈表最后一個節(jié)點的地址
n = 0; //創(chuàng)建前鏈表的節(jié)點總數(shù)為0：空鏈表
p1 = (struct student *) malloc (LEN); //開辟一個新節(jié)點
p2 = p1; //如果節(jié)點開辟成功，則p2先把它的指針保存下來以備后用
if(p1==NULL) //節(jié)點開辟不成功
{
printf ("\nCann't create it, try it again in a moment!\n");
return NULL;
}
else //節(jié)點開辟成功
{
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) //只要學號不為0，就繼續(xù)錄入下一個節(jié)點
{
n += 1; //節(jié)點總數(shù)增加1個
if(n == 1) //如果節(jié)點總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點p1
{
head = p1;
p2->next = NULL; //此時的p2就是p1,也就是p1->next指向NULL。
}
else
{
p2->next = p1; //指向上次下面剛剛開辟的新節(jié)點
}
p2 = p1; //把p1的地址給p2保留，然后p1產生新的節(jié)點
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ù)單向鏈表的最后一個節(jié)點要指向NULL
free(p1); //p1->num為0的時候跳出了while循環(huán)，并且釋放p1
p1 = NULL; //特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針
return head; //返回創(chuàng)建鏈表的頭指針
}
/*
===========================
功能：輸出節(jié)點
返回： void
===========================
*/
void Print(struct student *head)
{
struct student *p;
printf ("\nNow , These %d records are:\n", n);
p = head;
if(head != NULL) //只要不是空鏈表，就輸出鏈表中所有節(jié)點
{
printf("head is %o\n", head); //輸出頭指針指向的地址
do
{
/*
輸出相應的值：當前節(jié)點地址、各字段值、當前節(jié)點的下一節(jié)點地址。
這樣輸出便于讀者形象看到一個單向鏈表在計算機中的存儲結構，和我們
設計的圖示是一模一樣的。
*/
printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);
p = p->next; //移到下一個節(jié)點
}
while (p != NULL);
}
}
/*
==========================
功能：刪除指定節(jié)點
(此例中是刪除指定學號的節(jié)點)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Del (struct student *head, int num)
{
struct student *p1; //p1保存當前需要檢查的節(jié)點的地址
struct student *p2; //p2保存當前檢查過的節(jié)點的地址
if (head == NULL) //是空鏈表（結合圖3理解）
{
printf ("\nList is null!\n");
return head;
}
//定位要刪除的節(jié)點
p1 = head;
while (p1->num != num && p1->next != NULL) //p1指向的節(jié)點不是所要查找的，并且它不是最后一個節(jié)點，就繼續(xù)往下找
{
p2 = p1; //保存當前節(jié)點的地址
p1 = p1->next; //后移一個節(jié)點
}
if(p1->num==num) //找到了。（結合圖4、5理解）
{
if (p1 == head) //如果要刪除的節(jié)點是第一個節(jié)點
{
head = p1->next; //頭指針指向第一個節(jié)點的后一個節(jié)點，也就是第二個節(jié)點。這樣第一個節(jié)點就不在鏈表中，即刪除
}
else //如果是其它節(jié)點，則讓原來指向當前節(jié)點的指針，指向它的下一個節(jié)點，完成刪除
{
p2->next = p1->next;
}
free (p1); //釋放當前節(jié)點
p1 = NULL;
printf ("\ndelete %ld success!\n", num);
n -= 1; //節(jié)點總數(shù)減1個
}
else //沒有找到
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
//銷毀鏈表
void DestroyList(struct student *head)
{
struct student *p;
if(head==NULL)
return 0;
while(head)
{
p=head->next;
free(head);
head=p;
}
return 1;
}
/*
==========================
功能：插入指定節(jié)點的后面
(此例中是指定學號的節(jié)點)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Insert (struct student *head, int num, struct student *node)
{
struct student *p1; //p1保存當前需要檢查的節(jié)點的地址
if (head == NULL) //（結合圖示7理解）
{
head = node;
node->next = NULL;
n += 1;
return head;
}
p1 = head;
while(p1->num != num && p1->next != NULL) //p1指向的節(jié)點不是所要查找的，并且它不是最后一個節(jié)點，繼續(xù)往下找
{
p1 = p1->next; //后移一個節(jié)點
}
if (p1->num==num) //找到了（結合圖示8理解）
{
node->next = p1->next; //顯然node的下一節(jié)點是原p1的next
p1->next = node; //插入后，原p1的下一節(jié)點就是要插入的node
n += 1; //節(jié)點總數(shù)增加1個
}
else
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
/*
==========================
功能：反序節(jié)點
(鏈表的頭變成鏈表的尾，鏈表的尾變成頭)
返回：指向鏈表表頭的指針
==========================
*/
struct student *Reverse (struct student *head)
{
struct student *p; //臨時存儲
struct student *p1; //存儲返回結果
struct student *p2; //源結果節(jié)點一個一個取
p1 = NULL; //開始顛倒時，已顛倒的部分為空
p2 = head; //p2指向鏈表的頭節(jié)點
while(p2 != NULL)
{
p = p2->next;
p2->next = p1;
p1 = p2;
p2 = p;
}
head = p1;
return head;
}
/*
==========================
功能：選擇排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *SelectSort (struct student *head)
{
struct student *first; //排列后有序鏈的表頭指針
struct student *tail; //排列后有序鏈的表尾指針
struct student *p_min; //保留鍵值更小的節(jié)點的前驅節(jié)點的指針
struct student *min; //存儲最小節(jié)點
struct student *p; //當前比較的節(jié)點
first = NULL;
while(head != NULL) //在鏈表中找鍵值最小的節(jié)點
{
//注意：這里for語句就是體現(xiàn)選擇排序思想的地方
for (p = head, min = head; p->next != NULL; p = p->next) //循環(huán)遍歷鏈表中的節(jié)點，找出此時最小的節(jié)點
{
if (p->next->num < min->num) //找到一個比當前min小的節(jié)點
{
p_min = p; //保存找到節(jié)點的前驅節(jié)點：顯然p->next的前驅節(jié)點是p
min = p->next; //保存鍵值更小的節(jié)點
}
}
//上面for語句結束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應的條件判斷，安排它離開原來的鏈表
//第一件事
if (first == NULL) //如果有序鏈表目前還是一個空鏈表
{
first = min; //第一次找到鍵值最小的節(jié)點
tail = min; //注意：尾指針讓它指向最后的一個節(jié)點
}
else //有序鏈表中已經有節(jié)點
{
tail->next = min; //把剛找到的最小節(jié)點放到最后，即讓尾指針的next指向它
tail = min; //尾指針也要指向它
}
//第二件事
if (min == head) //如果找到的最小節(jié)點就是第一個節(jié)點
{
head = head->next; //顯然讓head指向原h(huán)ead->next,即第二個節(jié)點，就OK
}
else //如果不是第一個節(jié)點
{
p_min->next = min->next; //前次最小節(jié)點的next指向當前min的next,這樣就讓min離開了原鏈表
}
}
if (first != NULL) //循環(huán)結束得到有序鏈表first
{
tail->next = NULL; //單向鏈表的最后一個節(jié)點的next應該指向NULL
}
head = first;
return head;
}
/*
==========================
功能：直接插入排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *InsertSort (struct student *head)
{
struct student *first; //為原鏈表剩下用于直接插入排序的節(jié)點頭指針
struct student *t; //臨時指針變量：插入節(jié)點
struct student *p,*q; //臨時指針變量
first = head->next; //原鏈表剩下用于直接插入排序的節(jié)點鏈表：可根據(jù)圖12來理解
head->next = NULL; //只含有一個節(jié)點的鏈表的有序鏈表：可根據(jù)圖11來理解
while(first != NULL) //遍歷剩下無序的鏈表
{
//注意：這里for語句就是體現(xiàn)直接插入排序思想的地方
for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next); //無序節(jié)點在有序鏈表中找插入的位置
//退出for循環(huán)，就是找到了插入的位置，應該將t節(jié)點插入到p節(jié)點之后，q節(jié)點之前
//注意：按道理來說，這句話可以放到下面注釋了的那個位置也應該對的，但是就是不能。原因：你若理解了上面的第3條，就知道了
//下面的插入就是將t節(jié)點即是first節(jié)點插入到p節(jié)點之后，已經改變了first節(jié)點，所以first節(jié)點應該在被修改之前往后移動，不能放到下面注釋的位置上去
first = first->next; //無序鏈表中的節(jié)點離開，以便它插入到有序鏈表中
if (q == head) //插在第一個節(jié)點之前
{
head = t;
}
else //p是q的前驅
{
p->next = t;
}
t->next = q; //完成插入動作
//first = first->next;
}
return head;
}
/*
==========================
功能：冒泡排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *BubbleSort (struct student *head)
{
struct student *endpt; //控制循環(huán)比較
struct student *p; //臨時指針變量
struct student *p1,*p2;
p1 = (struct student *) malloc (LEN);
p1->next = head; //注意理解：我們增加一個節(jié)點，放在第一個節(jié)點的前面，主要是為了便于比較。因為第一個節(jié)點沒有前驅，我們不能交換地址
head = p1; //讓head指向p1節(jié)點，排序完成后，我們再把p1節(jié)點釋放掉
for (endpt = NULL; endpt != head; endpt = p) //結合第6點理解
{
for (p = p1 = head; p1->next->next != endpt; p1 = p1->next)
{
if (p1->next->num > p1->next->next->num) //如果前面的節(jié)點鍵值比后面節(jié)點的鍵值大，則交換
{
p2 = p1->next->next; //結合第1點理解
p1->next->next = p2->next; //結合第2點理解
p2->next = p1->next; //結合第3點理解
p1->next = p2; //結合第4點理解
p = p1->next->next; //結合第6點理解
}
}
}
p1 = head; //把p1的信息去掉
head = head->next; //讓head指向排序后的第一個節(jié)點
free (p1); //釋放p1
p1 = NULL; //p1置為NULL，保證不產生“野指針”，即地址不確定的指針變量
return head;
}
/*
==========================
功能：插入有序鏈表的某個節(jié)點的后面(從小到大)
返回：指向鏈表表頭的指針
==========================
*/
struct student *SortInsert (struct student *head, struct student *node)
{
struct student *p; //p保存當前需要檢查的節(jié)點的地址
struct student *t; //臨時指針變量
if (head == NULL) //處理空的有序鏈表
{
head = node;
node->next = NULL;
n += 1; //插入完畢，節(jié)點總數(shù)加
return head;
}
p = head; //有序鏈表不為空
while(p->num < node->num && p != NULL) //p指向的節(jié)點的學號比插入節(jié)點的學號小，并且它不等于NULL
{
t = p; //保存當前節(jié)點的前驅，以便后面判斷后處理
p = p->next; //后移一個節(jié)點
}
if (p == head) //剛好插入第一個節(jié)點之前
{
node->next = p;
head = node;
}
else //插入其它節(jié)點之后
{
t->next = node; //把node節(jié)點加進去
node->next = p;
}
n += 1; //插入完畢，節(jié)點總數(shù)加1
return head;
}
/*
以上函數(shù)的測試程序：
提示：根據(jù)測試函數(shù)的不同注釋相應的程序段，這也是一種測試方法。
*/
int main(void)
{
struct student *head;
struct student *stu;
int thenumber;
// 測試Create()、Print()
head = Create();
Print(head);
//測試Del()
printf("\nWhich one delete: ");
scanf("%d",&thenumber);
head = Del(head,thenumber);
Print(head);
//測試Insert()
stu = (struct student *)malloc(LEN);
printf("\nPlease input insert node -- num,score: ");
scanf("%d %f",&stu->num,&stu->score);
printf("\nInsert behind num: ");
scanf("%d",&thenumber);
head = Insert(head,thenumber,stu);
Print(head);
//測試Reverse()
printf("\nReverse the LinkList: \n");
head = Reverse(head);
Print(head);
//測試SelectSort()
printf("\nSelectSort the LinkList: \n");
head = SelectSort(head);
Print(head);
//測試InsertSort()
printf("\nInsertSort the LinkList: \n");
head = InsertSort(head);
Print(head);
//測試BubbleSort()
printf("\nBubbleSort the LinkList: \n");
head = BubbleSort(head);
Print(head);
printf("\nSortInsert the LinkList: \n");
//測試SortInsert():上面創(chuàng)建鏈表，輸入節(jié)點時請注意學號num從小到大的順序
stu = (struct student *)malloc(LEN);
printf("\nPlease input insert node -- num,score: ");
scanf("%d %f",&stu->num,&stu->score);
head = SortInsert(head,stu);
Print(head);
//銷毀鏈表
DestroyList(head);
printf ("\n");
system ("pause");
}
相關文章
在C++11中引入了auto類型說明符，用它就能讓編譯器替我們去分析表達式所屬的類型。當然，auto變量必須有初始值，這樣編譯器才能推斷其類型2016-03-03
這篇文章主要介紹了C語言科學計算入門之矩陣乘法的相關計算,文章中還介紹了矩陣相關的斯特拉森算法的實現(xiàn),需要的朋友可以參考下2015-12-12
這篇文章主要以圖文結合的方式為大家詳細介紹了C語言的操作符知識，感興趣的小伙伴們可以參考一下,希望能給你帶來幫助2021-11-11
這篇文章主要為大家詳細介紹了C++圖書管理系統(tǒng)程序源代碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要為大家介紹了C語言算法練習中數(shù)組元素排序的四種類型，文中的示例代碼講解詳細，對我們學習C語言有一定幫助，需要的可以參考一下2022-12-12
這篇文章主要介紹了C語言編程實例之輸出指定圖形問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-01-01
華為云CodeArts?IDE?Online服務,提供了可隨時隨地編碼的云上開發(fā)環(huán)境,同時具備開放的生態(tài)和獨立插件市場,本文主要介紹了華為云CodeArts?IDE?Online快速入門和使用,具有一定的參考價值,感興趣的可以了解一下2023-08-08
對于多線程來說，這兩個概念有很大部分是重疊的。對于很多人來說，它們的意思沒有什么區(qū)別。其區(qū)別主要在于關注點和意圖方面(差距甚微)。這兩個詞都是用來對硬件在同時執(zhí)行多個任務的方式進行描述的術語，不過并行更加注重性能2023-02-02
這篇文章主要介紹了C語言使用libZPlay錄制聲音并寫到文件的方法,實例分析了C語言操作音頻文件的相關技巧,需要的朋友可以參考下2015-06-06
這篇文章主要介紹了C++中結構體的類型定義和初始化以及變量引用,是C++入門學習中的基礎知識,需要的朋友可以參考下2015-09-09