說到鏈表，我們都很熟悉，我們在通常的編碼中或多或少地使用了這種數(shù)據(jù)結(jié)構(gòu)，本文是武林技術(shù)頻道小編帶給大家的深入理解鏈表的各類操作方法，一起來了解一下吧！
鏈表概述鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。它是動態(tài)地進(jìn)行存儲分配的一種結(jié)構(gòu)。它可以根據(jù)需要開辟內(nèi)存單元。鏈表有一個“頭指針”變量，以head表示，它存放一個地址。該地址指向一個元素。鏈表中每一個元素稱為“結(jié)點(diǎn)”，每個結(jié)點(diǎn)都應(yīng)包括兩個部分：一為用戶需要用的實(shí)際數(shù)據(jù)，二為下一個結(jié)點(diǎn)的地址。因此，head指向第一個元素：第一個元素又指向第二個元素；……，直到最后一個元素，該元素不再指向其它元素，它稱為“表尾”，它的地址部分放一個“NULL”（表示“空地址”），鏈表到此結(jié)束。
鏈表的各類操作包括：學(xué)習(xí)單向鏈表的創(chuàng)建、刪除、? 插入（無序、有序）、輸出、? 排序（選擇、插入、冒泡）、反序等等。
單向鏈表的圖示：
?---->[NULL]
head
圖1：空鏈表
---->[p1]---->[p2]...---->[pn]---->[NULL]
????? head?? p1->next? p2->next?? pn->next
圖2：有N個節(jié)點(diǎn)的鏈表
????? 創(chuàng)建n個節(jié)點(diǎn)的鏈表的函數(shù)為：
?
?
?
?
#include "stdlib.h"
#include "stdio.h"
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
?int num;???? //學(xué)號
?float score;?????? //分?jǐn)?shù)，其他信息可以繼續(xù)在下面增加字段
?struct student *next;??//指向下一節(jié)點(diǎn)的指針
};
int n;?//節(jié)點(diǎn)總數(shù)
/*
==========================
功能：創(chuàng)建n個節(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保存原鏈表最后一個節(jié)點(diǎn)的地址
?n = 0;???//創(chuàng)建前鏈表的節(jié)點(diǎn)總數(shù)為0：空鏈表
?p1 = (struct student *) malloc (LEN);?//開辟一個新節(jié)點(diǎn)
?p2 = p1;???//如果節(jié)點(diǎn)開辟成功，則p2先把它的指針保存下來以備后用
?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é)號不為0，就繼續(xù)錄入下一個節(jié)點(diǎn)
?{
??n += 1;???//節(jié)點(diǎn)總數(shù)增加1個
??if(n == 1)??//如果節(jié)點(diǎn)總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點(diǎn)p1
??{
???head = p1;
???p2->next = NULL;? //此時的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ù)單向鏈表的最后一個節(jié)點(diǎn)要指向NULL
?free(p1);???//p1->num為0的時候跳出了while循環(huán)，并且釋放p1
?p1 = NULL;???//特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針
?return head;???? //返回創(chuàng)建鏈表的頭指針
}
?輸出鏈表中節(jié)點(diǎn)的函數(shù)為：
?
?
?
/*
===========================
?功能：輸出節(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)地址。
???這樣輸出便于讀者形象看到一個單向鏈表在計算機(jī)中的存儲結(jié)構(gòu)，和我們
???設(shè)計的圖示是一模一樣的。
???*/
???printf ("%o?? %d?? %5.1f?? %o/n", p, p->num, p->score, p->next);
???p = p->next;??//移到下一個節(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個節(jié)點(diǎn)的鏈表，刪除第一個節(jié)點(diǎn)
????? 結(jié)合原鏈表和刪除后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
????? 1、你要明白head就是第1個節(jié)點(diǎn)，head->next就是第2個節(jié)點(diǎn)；
?????? 2、刪除后head指向第2個節(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個節(jié)點(diǎn)的鏈表，刪除中間一個（這里圖示刪除第2個）
????? 結(jié)合原鏈表和刪除后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
????? 1、你要明白head就是第1個節(jié)點(diǎn)，1->next就是第2個節(jié)點(diǎn)，2->next就是第3個節(jié)點(diǎn)；
????? 2、刪除后2，1指向第3個節(jié)點(diǎn)，就是讓1->next=2->next。
????? 刪除指定學(xué)號的節(jié)點(diǎn)的函數(shù)為：
?
?
?
/*
==========================
?功能：刪除指定節(jié)點(diǎn)
? (此例中是刪除指定學(xué)號的節(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)前檢查過的節(jié)點(diǎn)的地址
?if (head == NULL)??//是空鏈表（結(jié)合圖3理解）
?{
??printf ("/nList is null!/n");
??return head;
?}
?//定位要刪除的節(jié)點(diǎn)
?p1 = head;
?while (p1->num != num && p1->next != NULL)?//p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個節(jié)點(diǎn)，就繼續(xù)往下找
?{
??p2 = p1;???//保存當(dāng)前節(jié)點(diǎn)的地址
??p1 = p1->next;??//后移一個節(jié)點(diǎn)
?}
?if(p1->num==num)??//找到了。（結(jié)合圖4、5理解）
?{
??if (p1 == head)??//如果要刪除的節(jié)點(diǎn)是第一個節(jié)點(diǎn)
??{
???head = p1->next;?//頭指針指向第一個節(jié)點(diǎn)的后一個節(jié)點(diǎn)，也就是第二個節(jié)點(diǎn)。這樣第一個節(jié)點(diǎn)就不在鏈表中，即刪除
??}
??else???//如果是其它節(jié)點(diǎn)，則讓原來指向當(dāng)前節(jié)點(diǎn)的指針，指向它的下一個節(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個
?}
?else????//沒有找到
?{
??printf ("/n%ld not been found!/n", num);
?}
?return head;
}
?????? 單向鏈表的插入圖示：
?????? ---->[NULL]（原鏈表）
????? head
????? ---->[1]---->[NULL]（插入后的鏈表）
????? head?? 1->next
????? 圖7 空鏈表插入一個節(jié)點(diǎn)
????? 結(jié)合原鏈表和插入后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
???? 1、你要明白空鏈表head指向NULL就是head=NULL；
???? 2、插入后head指向第1個節(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個節(jié)點(diǎn)的鏈表，插入一個節(jié)點(diǎn)（這里圖示插入第2個后面）
???? 結(jié)合原鏈表和插入后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
??? 1、你要明白原1->next就是節(jié)點(diǎn)2，2->next就是節(jié)點(diǎn)3；
??? 2、插入后x指向第3個節(jié)點(diǎn),2指向x，就是讓x->next=2->next,1->next=x。
??? 插入指定節(jié)點(diǎn)的后面的函數(shù)為：
?
?
?
/*
==========================
?功能：插入指定節(jié)點(diǎn)的后面
? (此例中是指定學(xué)號的節(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)不是所要查找的，并且它不是最后一個節(jié)點(diǎn)，繼續(xù)往下找
?{
??p1 = p1->next;??//后移一個節(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個
?}
?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é)點(diǎn)的鏈表反序
????????? 結(jié)合原鏈表和插入后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
????????? 1、我們需要一個讀原鏈表的指針p2,存反序鏈表的p1=NULL（剛好最后一個節(jié)點(diǎn)的next為NULL）,還有一個臨時存儲變量p；
????????? 2、p2在原鏈表中讀出一個節(jié)點(diǎn)，我們就把它放到p1中，p就是用來處理節(jié)點(diǎn)放置順序的問題；
????????? 3、比如，現(xiàn)在我們?nèi)〉靡粋€2,為了我們繼續(xù)往下取節(jié)點(diǎn)，我們必須保存它的next值，由原鏈表可知p=2->next;
????????? 4、然后由反序后的鏈表可知，反序后2->next要指向1，則2->next=1;
????????? 5、好了，現(xiàn)在已經(jīng)反序一個節(jié)點(diǎn)，接著處理下一個節(jié)點(diǎn)就需要保存此時的信息：
????????? p1變成剛剛加入的2，即p1=2;p2要變成它的下一節(jié)點(diǎn)，就是上面我們保存的p,即p2=p。
????????? 反序鏈表的函數(shù)為：
?
?
?
/*
==========================
?功能：反序節(jié)點(diǎn)
? (鏈表的頭變成鏈表的尾，鏈表的尾變成頭)
?返回：指向鏈表表頭的指針
==========================
*/
struct student *Reverse (struct student *head)
{
?struct student *p;??//臨時存儲
?struct student *p1;??//存儲返回結(jié)果
?struct student *p2;??//源結(jié)果節(jié)點(diǎn)一個一個取
?p1 = NULL;???//開始顛倒時，已顛倒的部分為空
?p2 = head;???//p2指向鏈表的頭節(jié)點(diǎn)
?while(p2 != NULL)
?{
??p = p2->next;
??p2->next = p1;
??p1 = p2;
??p2 = p;
?}
?head = p1;
?return head;
}
????????? 對鏈表進(jìn)行選擇排序的基本思想就是反復(fù)從還未排好序的那些節(jié)點(diǎn)中，選出鍵值（就是用它排序的字段，我們?nèi)W(xué)號num為鍵值）最小的節(jié)點(diǎn)，依次重新組合成一個鏈表。
???????? 我認(rèn)為寫鏈表這類程序，關(guān)鍵是理解：head存儲的是第一個節(jié)點(diǎn)的地址，head->next存儲的是第二個節(jié)點(diǎn)的地址；任意一個節(jié)點(diǎn)p的地址，只能通過它前一個節(jié)點(diǎn)的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é)點(diǎn)的鏈表選擇排序
??????? 1、先在原鏈表中找最小的，找到一個后就把它放到另一個空的鏈表中；
??????? 2、空鏈表中安放第一個進(jìn)來的節(jié)點(diǎn)，產(chǎn)生一個有序鏈表,并且讓它在原鏈表中分離出來（此時要注意原鏈表中出來的是第一個節(jié)點(diǎn)還是中間其它節(jié)點(diǎn)）；
??????? 3、繼續(xù)在原鏈表中找下一個最小的，找到后把它放入有序鏈表的尾指針的next,然后它變成其尾指針；
??????? 對鏈表進(jìn)行選擇排序的函數(shù)為：
?
?
?
/*
==========================
?功能：選擇排序(由小到大)
?返回：指向鏈表表頭的指針
==========================
*/
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;??? //存儲最小節(jié)點(diǎn)
?struct student *p;???? //當(dāng)前比較的節(jié)點(diǎn)
?first = NULL;
?while(head != NULL)??? //在鏈表中找鍵值最小的節(jié)點(diǎn)
?{
??//注意：這里for語句就是體現(xiàn)選擇排序思想的地方
??for (p = head, min = head; p->next != NULL; p = p->next)?//循環(huán)遍歷鏈表中的節(jié)點(diǎn)，找出此時最小的節(jié)點(diǎn)
??{
???if (p->next->num < min->num)? //找到一個比當(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語句結(jié)束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應(yīng)的條件判斷，安排它離開原來的鏈表
??//第一件事
??if (first == NULL)??? //如果有序鏈表目前還是一個空鏈表
??{
???first = min;??//第一次找到鍵值最小的節(jié)點(diǎn)
???tail = min;???? //注意：尾指針讓它指向最后的一個節(jié)點(diǎn)
??}
??else???? //有序鏈表中已經(jīng)有節(jié)點(diǎn)
??{
???tail->next = min;?? ?//把剛找到的最小節(jié)點(diǎn)放到最后，即讓尾指針的next指向它
???tail = min;??????? //尾指針也要指向它
??}
??//第二件事
??if (min == head)????? //如果找到的最小節(jié)點(diǎn)就是第一個節(jié)點(diǎn)
??{
???head = head->next;??? //顯然讓head指向原h(huán)ead->next,即第二個節(jié)點(diǎn)，就OK
??}
??else???//如果不是第一個節(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;?//單向鏈表的最后一個節(jié)點(diǎn)的next應(yīng)該指向NULL
?}
?head = first;
?return head;
}
?????????? 對鏈表進(jìn)行直接插入排序的基本思想就是假設(shè)鏈表的前面n-1個節(jié)點(diǎn)是已經(jīng)按鍵值（就是用它排序的字段，我們?nèi)W(xué)號num為鍵值）排好序的，對于節(jié)點(diǎn)n在這個序列中找插入位置，使得n插入后新序列仍然有序。按照這種思想，依次對鏈表從頭到尾執(zhí)行一遍，就可以使無序鏈表變?yōu)橛行蜴湵怼?br>???????? 單向鏈表的直接插入排序圖示：
???????? ---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原鏈表）
??????? head?? 1->next? 3->next? 2->next?? n->next
???????? ---->[1]---->[NULL]（從原鏈表中取第1個節(jié)點(diǎn)作為只有一個節(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個節(jié)點(diǎn)的鏈表直接插入排序
?????? 1、先在原鏈表中以第一個節(jié)點(diǎn)為一個有序鏈表，其余節(jié)點(diǎn)為待定節(jié)點(diǎn)。
?????? 2、從圖12鏈表中取節(jié)點(diǎn)，到圖11鏈表中定位插入。
?????? 3、上面圖示雖說畫了兩條鏈表，其實(shí)只有一條鏈表。在排序中，實(shí)質(zhì)只增加了一個用于指向剩下需要排序節(jié)點(diǎn)的頭指針first罷了。
?????? 這一點(diǎn)請讀者務(wù)必搞清楚，要不然就可能認(rèn)為它和上面的選擇排序法一樣了。
?????? 對鏈表進(jìn)行直接插入排序的函數(shù)為：
?
?
?
/*
==========================
?功能：直接插入排序(由小到大)
?返回：指向鏈表表頭的指針
==========================
*/
struct student *InsertSort (struct student *head)
{
?struct student *first;?? //為原鏈表剩下用于直接插入排序的節(jié)點(diǎn)頭指針
?struct student *t;??? //臨時指針變量：插入節(jié)點(diǎn)
?struct student *p,*q;???? //臨時指針變量
?first = head->next;??//原鏈表剩下用于直接插入排序的節(jié)點(diǎn)鏈表：可根據(jù)圖12來理解
?head->next = NULL;??//只含有一個節(jié)點(diǎn)的鏈表的有序鏈表：可根據(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é)點(diǎn)在有序鏈表中找插入的位置
??//退出for循環(huán)，就是找到了插入的位置，應(yīng)該將t節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，q節(jié)點(diǎn)之前
??//注意：按道理來說，這句話可以放到下面注釋了的那個位置也應(yīng)該對的，但是就是不能。原因：你若理解了上面的第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)該在被修改之前往后移動，不能放到下面注釋的位置上去
??first = first->next;?//無序鏈表中的節(jié)點(diǎn)離開，以便它插入到有序鏈表中
??if (q == head)??//插在第一個節(jié)點(diǎn)之前
??{
???head = t;
??}
??else???//p是q的前驅(qū)
??{
???p->next = t;
??}
??t->next = q;??//完成插入動作
??//first = first->next;
?}
?return head;
}
???????? 對鏈表進(jìn)行冒泡排序的基本思想就是對當(dāng)前還未排好序的范圍內(nèi)的全部節(jié)點(diǎn)，自上而下對相鄰的兩個節(jié)點(diǎn)依次進(jìn)行比較和調(diào)整，讓鍵值（就是用它排 序的字段，我們?nèi)W(xué)號num為鍵值）較大的節(jié)點(diǎn)往下沉，鍵值較小的往上冒。即：每當(dāng)兩相鄰的節(jié)點(diǎn)比較后發(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é)點(diǎn)的鏈表冒泡排序
????? 任意兩個相鄰節(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ā)出來的指向，排序后圖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é)點(diǎn)的順序交換。
????? 6、下面的程序描述改進(jìn)了一點(diǎn)就是記錄了每次最后一次節(jié)點(diǎn)下沉的位置，這樣我們不必每次都從頭到尾的掃描，只需要掃描到記錄點(diǎn)為止。 因?yàn)楹竺娴亩家呀?jīng)是排好序的了。
?????? 對鏈表進(jìn)行冒泡排序的函數(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é)點(diǎn)，放在第一個節(jié)點(diǎn)的前面，主要是為了便于比較。因?yàn)榈谝粋€節(jié)點(diǎn)沒有前驅(qū)，我們不能交換地址
?head = p1;????????? //讓head指向p1節(jié)點(diǎn)，排序完成后，我們再把p1節(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指向排序后的第一個節(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個節(jié)點(diǎn)的有序鏈表
?????? 插入node節(jié)點(diǎn)的位置有兩種情況：一是第一個節(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)插在第一個節(jié)點(diǎn)前
?????? ---->[1]---->[2]---->[3]...---->[node]...---->[n]---->[NULL]
????? head?? 1->next? 2->next? 3->next??? node->next? n->next
?????? 插入有序鏈表的函數(shù)為：
?
?
?
/*
==========================
?功能：插入有序鏈表的某個節(jié)點(diǎn)的后面(從小到大)
?返回：指向鏈表表頭的指針
==========================
*/
struct student *SortInsert (struct student *head, struct student *node)
{
?struct student *p;??//p保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址
?struct student *t;??//臨時指針變量
?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é)號比插入節(jié)點(diǎn)的學(xué)號小，并且它不等于NULL
?{
??t = p;???? //保存當(dāng)前節(jié)點(diǎn)的前驅(qū)，以便后面判斷后處理
??p = p->next;??//后移一個節(jié)點(diǎn)
?}
?if (p == head)??//剛好插入第一個節(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ù)的完整代碼如下：
?
?
?
#include "stdlib.h"
#include "stdio.h"
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
?int num;???? //學(xué)號
?float score;?????? //分?jǐn)?shù)，其他信息可以繼續(xù)在下面增加字段
?struct student *next;??//指向下一節(jié)點(diǎn)的指針
};
int n;?//節(jié)點(diǎn)總數(shù)
/*
==========================
功能：創(chuàng)建n個節(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保存原鏈表最后一個節(jié)點(diǎn)的地址
?n = 0;???//創(chuàng)建前鏈表的節(jié)點(diǎn)總數(shù)為0：空鏈表
?p1 = (struct student *) malloc (LEN);?//開辟一個新節(jié)點(diǎn)
?p2 = p1;???//如果節(jié)點(diǎn)開辟成功，則p2先把它的指針保存下來以備后用
?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é)號不為0，就繼續(xù)錄入下一個節(jié)點(diǎn)
?{
??n += 1;???//節(jié)點(diǎn)總數(shù)增加1個
??if(n == 1)??//如果節(jié)點(diǎn)總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點(diǎn)p1
??{
???head = p1;
???p2->next = NULL;? //此時的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ù)單向鏈表的最后一個節(jié)點(diǎn)要指向NULL
?free(p1);???//p1->num為0的時候跳出了while循環(huán)，并且釋放p1
?p1 = NULL;???//特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針
?return head;???? //返回創(chuàng)建鏈表的頭指針
}
/*
===========================
?功能：輸出節(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)地址。
???這樣輸出便于讀者形象看到一個單向鏈表在計算機(jī)中的存儲結(jié)構(gòu)，和我們
???設(shè)計的圖示是一模一樣的。
???*/
???printf ("%o?? %d?? %5.1f?? %o/n", p, p->num, p->score, p->next);
???p = p->next;??//移到下一個節(jié)點(diǎn)
??}
??while (p != NULL);
?}
}
/*
==========================
?功能：刪除指定節(jié)點(diǎn)
? (此例中是刪除指定學(xué)號的節(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)前檢查過的節(jié)點(diǎn)的地址
?if (head == NULL)??//是空鏈表（結(jié)合圖3理解）
?{
??printf ("/nList is null!/n");
??return head;
?}
?//定位要刪除的節(jié)點(diǎn)
?p1 = head;
?while (p1->num != num && p1->next != NULL)?//p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個節(jié)點(diǎn)，就繼續(xù)往下找
?{
??p2 = p1;???//保存當(dāng)前節(jié)點(diǎn)的地址
??p1 = p1->next;??//后移一個節(jié)點(diǎn)
?}
?if(p1->num==num)??//找到了。（結(jié)合圖4、5理解）
?{
??if (p1 == head)??//如果要刪除的節(jié)點(diǎn)是第一個節(jié)點(diǎn)
??{
???head = p1->next;?//頭指針指向第一個節(jié)點(diǎn)的后一個節(jié)點(diǎn)，也就是第二個節(jié)點(diǎn)。這樣第一個節(jié)點(diǎn)就不在鏈表中，即刪除
??}
??else???//如果是其它節(jié)點(diǎn)，則讓原來指向當(dāng)前節(jié)點(diǎn)的指針，指向它的下一個節(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個
?}
?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é)點(diǎn)的后面
? (此例中是指定學(xué)號的節(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)不是所要查找的，并且它不是最后一個節(jié)點(diǎn)，繼續(xù)往下找
?{
??p1 = p1->next;??//后移一個節(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個
?}
?else
?{
??printf ("/n%ld not been found!/n", num);
?}
?return head;
}
/*
==========================
?功能：反序節(jié)點(diǎn)
? (鏈表的頭變成鏈表的尾，鏈表的尾變成頭)
?返回：指向鏈表表頭的指針
==========================
*/
struct student *Reverse (struct student *head)
{
?struct student *p;??//臨時存儲
?struct student *p1;??//存儲返回結(jié)果
?struct student *p2;??//源結(jié)果節(jié)點(diǎn)一個一個取
?p1 = NULL;???//開始顛倒時，已顛倒的部分為空
?p2 = head;???//p2指向鏈表的頭節(jié)點(diǎn)
?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é)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針
?struct student *min;??? //存儲最小節(jié)點(diǎn)
?struct student *p;???? //當(dāng)前比較的節(jié)點(diǎn)
?first = NULL;
?while(head != NULL)??? //在鏈表中找鍵值最小的節(jié)點(diǎn)
?{
??//注意：這里for語句就是體現(xiàn)選擇排序思想的地方
??for (p = head, min = head; p->next != NULL; p = p->next)?//循環(huán)遍歷鏈表中的節(jié)點(diǎn)，找出此時最小的節(jié)點(diǎn)
??{
???if (p->next->num < min->num)? //找到一個比當(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語句結(jié)束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應(yīng)的條件判斷，安排它離開原來的鏈表
??//第一件事
??if (first == NULL)??? //如果有序鏈表目前還是一個空鏈表
??{
???first = min;??//第一次找到鍵值最小的節(jié)點(diǎn)
???tail = min;???? //注意：尾指針讓它指向最后的一個節(jié)點(diǎn)
??}
??else???? //有序鏈表中已經(jīng)有節(jié)點(diǎn)
??{
???tail->next = min;?? ?//把剛找到的最小節(jié)點(diǎn)放到最后，即讓尾指針的next指向它
???tail = min;??????? //尾指針也要指向它
??}
??//第二件事
??if (min == head)????? //如果找到的最小節(jié)點(diǎn)就是第一個節(jié)點(diǎn)
??{
???head = head->next;??? //顯然讓head指向原h(huán)ead->next,即第二個節(jié)點(diǎn)，就OK
??}
??else???//如果不是第一個節(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;?//單向鏈表的最后一個節(jié)點(diǎn)的next應(yīng)該指向NULL
?}
?head = first;
?return head;
}
/*
==========================
?功能：直接插入排序(由小到大)
?返回：指向鏈表表頭的指針
==========================
*/
struct student *InsertSort (struct student *head)
{
?struct student *first;?? //為原鏈表剩下用于直接插入排序的節(jié)點(diǎn)頭指針
?struct student *t;??? //臨時指針變量：插入節(jié)點(diǎn)
?struct student *p,*q;???? //臨時指針變量
?first = head->next;??//原鏈表剩下用于直接插入排序的節(jié)點(diǎn)鏈表：可根據(jù)圖12來理解
?head->next = NULL;??//只含有一個節(jié)點(diǎn)的鏈表的有序鏈表：可根據(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é)點(diǎn)在有序鏈表中找插入的位置
??//退出for循環(huán)，就是找到了插入的位置，應(yīng)該將t節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，q節(jié)點(diǎn)之前
??//注意：按道理來說，這句話可以放到下面注釋了的那個位置也應(yīng)該對的，但是就是不能。原因：你若理解了上面的第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)該在被修改之前往后移動，不能放到下面注釋的位置上去
??first = first->next;?//無序鏈表中的節(jié)點(diǎn)離開，以便它插入到有序鏈表中
??if (q == head)??//插在第一個節(jié)點(diǎn)之前
??{
???head = t;
??}
??else???//p是q的前驅(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é)點(diǎn)，放在第一個節(jié)點(diǎn)的前面，主要是為了便于比較。因?yàn)榈谝粋€節(jié)點(diǎn)沒有前驅(qū)，我們不能交換地址
?head = p1;????????? //讓head指向p1節(jié)點(diǎn)，排序完成后，我們再把p1節(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指向排序后的第一個節(jié)點(diǎn)
?free (p1);???//釋放p1
?p1 = NULL;???//p1置為NULL，保證不產(chǎn)生“野指針”，即地址不確定的指針變量
?return head;
}
/*
==========================
?功能：插入有序鏈表的某個節(jié)點(diǎn)的后面(從小到大)
?返回：指向鏈表表頭的指針
==========================
*/
struct student *SortInsert (struct student *head, struct student *node)
{
?struct student *p;??//p保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址
?struct student *t;??//臨時指針變量
?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é)號比插入節(jié)點(diǎn)的學(xué)號小，并且它不等于NULL
?{
??t = p;???? //保存當(dāng)前節(jié)點(diǎn)的前驅(qū)，以便后面判斷后處理
??p = p->next;??//后移一個節(jié)點(diǎn)
?}
?if (p == head)??//剛好插入第一個節(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ù)的測試程序：
提示：根據(jù)測試函數(shù)的不同注釋相應(yīng)的程序段，這也是一種測試方法。
*/
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é)點(diǎn)時請注意學(xué)號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");
}
以上就是關(guān)于深入理解鏈表的各類操作方法，提醒大家操作的時候要謹(jǐn)慎，更多的專業(yè)信息，請大家關(guān)注武林技術(shù)頻道，一定會對你有很大的幫助。
