一、鏈表的定義
1嘿辟、定義
（1）n個(gè)結(jié)點(diǎn)離散分配
（2）彼此通過(guò)指針相連
（3）每個(gè)結(jié)點(diǎn)只有1個(gè)前驅(qū)結(jié)點(diǎn)舆瘪，每個(gè)結(jié)點(diǎn)只有1個(gè)后續(xù)結(jié)點(diǎn)。首結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)红伦，尾結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)英古。
2、一些概念
結(jié)點(diǎn)：類(lèi)似數(shù)組的元素色建，單個(gè)的邏輯上具有獨(dú)立意義的個(gè)體哺呜。
每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)都相同。有效結(jié)點(diǎn)：存放有效數(shù)據(jù)的結(jié)點(diǎn)
首結(jié)點(diǎn)：第一個(gè)有效結(jié)點(diǎn)
尾結(jié)點(diǎn)：最后一個(gè)有效結(jié)點(diǎn)
頭結(jié)點(diǎn)：不存放任何有效數(shù)據(jù)箕戳；它指向首結(jié)點(diǎn)某残；它的數(shù)據(jù)類(lèi)型與其它結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型相同国撵。
加頭結(jié)點(diǎn)的目的：對(duì)鏈表進(jìn)行操作時(shí)，在前面添加沒(méi)有實(shí)際含義的頭結(jié)點(diǎn)玻墅，可以方便我們對(duì)鏈表進(jìn)行操作介牙。頭指針：指向頭結(jié)點(diǎn)的指針變量
尾指針：指向尾結(jié)點(diǎn)的指針變量
3、確定一個(gè)鏈表需要幾個(gè)參數(shù)澳厢？
1個(gè)參數(shù)：頭指針环础。
因?yàn)橥ㄟ^(guò)頭指針，可以推算出鏈表的其它所有信息剩拢。
因此线得，如果通過(guò)一個(gè)函數(shù)來(lái)對(duì)鏈表進(jìn)行處理，我們至少需要接收鏈表的頭指針信息徐伐。
4贯钩、每個(gè)結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型該如何表示？（如何模擬/表示一個(gè)結(jié)點(diǎn)）
每個(gè)結(jié)點(diǎn)可以分為2部分：數(shù)據(jù)域和指針域办素。
數(shù)據(jù)域中的數(shù)據(jù)可以非常復(fù)雜角雷；指針域中的指針指向另外一個(gè)和它數(shù)據(jù)類(lèi)型相同的結(jié)點(diǎn)。
（1）
typedef struct Node
{
int data; // 數(shù)據(jù)域
struct Node *pNext; //指針域
} NODE, *PNODE;
（2）
PNODE p = (PNODE)malloc(sizeof(NODE));
// 將動(dòng)態(tài)分配的新結(jié)點(diǎn)的地址賦給p
（3）
free p; // 刪除p指向結(jié)點(diǎn)所占的內(nèi)存
// 不是刪除p本身所占內(nèi)存
（4）
p -> pNext; // p所指向結(jié)構(gòu)體變量中的pNext成員本身
二性穿、鏈表的分類(lèi)
單鏈表
每個(gè)結(jié)點(diǎn)只有一個(gè)指針域勺三，且該指針域只能指向后面的結(jié)點(diǎn)。雙鏈表
每個(gè)結(jié)點(diǎn)有2個(gè)指針域需曾。左邊的指針域指向前面的結(jié)點(diǎn)吗坚，右邊的指針域指向后面的結(jié)點(diǎn)。循環(huán)鏈表
能通過(guò)任何一個(gè)結(jié)點(diǎn)找到其他所有的結(jié)點(diǎn)胯舷。
尾結(jié)點(diǎn)的指針域指向了頭結(jié)點(diǎn)刻蚯。非循環(huán)鏈表
三绊含、單鏈表的操作
創(chuàng)建鏈表
遍歷鏈表
查找
清空
銷(xiāo)毀
判斷是否為空
求長(zhǎng)度
排序
-
刪除結(jié)點(diǎn)：刪除p所指向的結(jié)點(diǎn)后面的結(jié)點(diǎn)
// 錯(cuò)誤：
p->pNext = p->pNext->pNext; // 刪除結(jié)點(diǎn)的內(nèi)存就會(huì)被泄漏// 錯(cuò)誤：
free(p->pNext); // 直接free掉這個(gè)結(jié)點(diǎn)桑嘶，則它指向的結(jié)點(diǎn)也都找不到了。 -
插入結(jié)點(diǎn)：把q所指向的結(jié)點(diǎn)插到p所指向的結(jié)點(diǎn)后面
// 錯(cuò)誤：
p->pNext = q;
q->pNext = p->pNext;// 方法1：先臨時(shí)定義一個(gè)指向p后面結(jié)點(diǎn)的指針r
r = p->pNext; // r指向p后面的那個(gè)結(jié)點(diǎn)
p->pNext = q;
q->pNext = r;// 方法2：
q->pNext = p->pNext;
p->pNext = q;
