單鏈表
1、鏈接存儲方法
鏈接方式存儲的線性表簡稱為鏈表（Linked List）。
鏈表的具體存儲表示為：
① 用一組任意的存儲單元來存放線性表的結點（這組存儲單元既可以是連續的，也可以是不連續的）
② 鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其後繼結點的地址（或位置）信息（稱為指針（pointer）或鏈(link)）
注意：
鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數據結構。
2、鏈表的結點結構
┌──┬──┐
│data│next│
└──┴──┘
data域--存放結點值的數據域
next域--存放結點的直接後繼的地址（位置）的指針域（鏈域）
注意：
①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的。
②每個結點只有一個鏈域的鏈表稱為單鏈表（Single Linked List）。
3、頭指針head和終端結點指針域的表示
單鏈表中每個結點的存儲地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。
注意：
鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。
【例】頭指針名是head的鏈表可稱為表head。
終端結點無後繼，故終端結點的指針域為空，即NULL。
4、單鏈表的一般圖示法
由於我們常常只注重結點間的邏輯順序，不關心每個結點的實際位置，可以用箭頭來表示鏈域中的指針，線性表（bat，cat，fat，hat，jat，lat，mat）的單鏈表就可以表示為下圖形式。
5、單鏈表類型描述
typedef char DataType; //假設結點的數據域類型為字符
typedef struct node{ //結點類型定義
DataType data; //結點的數據域
struct node *next;//結點的指針域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
注意：
①LinkList和ListNode *是不同名字的同一個指針類型（命名的不同是為了概念上更明確）
②LinkList類型的指針變量head表示它是單鏈表的頭指針
③ListNode *類型的指針變量p表示它是指向某一結點的指針
6、指針變量和結點變量
┌────┬────────────┬─────────────┐
│ │ 指針變量 │ 結點變量 │
├────┼────────────┼─────────────┤
│ 定義 │在變量說明部分顯式定義 │在程序執行時，通過標准 │
│ │ │函數malloc生成 │
├────┼────────────┼─────────────┤
│ 取值 │ 非空時，存放某類型結點 │實際存放結點各域內容 │
│ │的地址 │ │
├────┼────────────┼─────────────┤
│操作方式│ 通過指針變量名訪問 │ 通過指針生成、訪問和釋放 │
└────┴────────────┴─────────────┘
①生成結點變量的標准函數
p=( ListNode *)malloc(sizeof(ListNode))；
//函數malloc分配一個類型為ListNode的結點變量的空間,並將其首地址放入指針變量p中
②釋放結點變量空間的標准函數
free(p)；//釋放p所指的結點變量空間
③結點分量的訪問
利用結點變量的名字*p訪問結點分量
方法一：(*p).data和(*p).next
方法二：p-﹥data和p-﹥next
④指針變量p和結點變量*p的關系
指針變量p的值——結點地址
結點變量*p的值——結點內容
(*p).data的值——p指針所指結點的data域的值
(*p).next的值——*p後繼結點的地址
*((*p).next)——*p後繼結點
注意：
① 若指針變量p的值為空（NULL），則它不指向任何結點。此時，若通過*p來訪問結點就意味著訪問一個不存在的變量，從而引起程序的錯誤。
② 有關指針類型的意義和說明方式的詳細解釋，【參考C語言的有關資料】。
