單鏈表

鏈接方式存儲的線性表簡稱為鏈表（Linked List）。

鏈表的具體存儲表示為：

① 用一組任意的存儲單元來存放線性表的結點（這組存儲單元既可以是連續的，也可以是不連續的）

② 鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關係，在存儲每個結點值的同時，還必須存儲指示其後繼結點的地址（或位置）信息（稱為指針（pointer）或鏈(link)）

鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數據結構。

┌───┬───┐

│data │next │

└───┴───┘

data域--存放結點值的數據域

next域--存放結點的直接後繼的地址（位置）的指針域（鏈域）

鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的，每個結點只有一個鏈域的鏈表稱為單鏈表（Single Linked List）。

單鏈表中每個結點的存儲地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。

終端結點無後繼，故終端結點的指針域為空，即NULL。

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表示它是指向某一結點的指針

①生成結點變數的標準函數

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來訪問結點就意味著訪問一個不存在的變數，從而引起程序的錯誤。

② 有關指針類型的意義和說明方式的詳細解釋

可見，在鏈表中插入結點只需要修改指針。但同時，若要在第 i 個結點之前插入元素，修改的是第 i-1 個結點的指針。

因此，在單鏈表中第 i 個結點之前進行插入的基本操作為:

找到線性表中第i-1個結點，然後修改其指向後繼的指針。

單鏈表的建立有頭插法、尾插法兩種方法。

單鏈表是用戶不斷申請存儲單元和改變鏈接關係而得到的一種特殊數據結構，將鏈表的左邊稱為鏈頭，右邊稱為鏈尾。頭插法建單鏈表是將鏈表右端看成固定的，鏈表不斷向左延伸而得到的。頭插法最先得到的是尾結點。

由於鏈表的長度是隨機的，故用一個while循環來控制鏈表中結點個數。假設每個結點的值都大於O，則循環條件為輸入的值大於o。申請存儲空間可使用malloc()函數實現，需設立一申請單元指針，但malloc()函數得到的指針並不是指向結構體的指針，需使用強制類型轉換，將其轉換成結構體型指針。剛開始時，鏈表還沒建立，是一空鏈表，head指針為NULL。

鏈表建立的過程是申請空間、得到數據、建立鏈接的循環處理過程。

若將鏈表的左端固定，鏈表不斷向右延伸，這種建立鏈表的方法稱為尾插法。尾插法建立鏈表時，頭指針固定不動，故必須設立一個搜索指針，向鏈表右邊延伸，則整個演演算法中應設立三個鏈表指針，即頭指針head、搜索指針p2、申請單元指針pl。尾插法最先得到的是頭結點。

鏈表操作中動態存儲分配要使用標準函數，先介紹一下這些函數。

(1)malloc(size)

在內存的動態存儲區申請一個長度為size位元組的連續空間。

(2)calloc(n，size)

在內存的動態存儲區申請n個長度為size位元組的連續空間，函數返回值為分配空間的首地址。若此函數未被成功執行，函數返回值為0。

(3)free(p)

釋放由指針p所指向的存儲單元，而存儲單元的大小是最近一次調用malloc()或calloc()函數時所申請的存儲空間。

在頭文件\"stdlib．h”中包含了這些函數的信息，使用這些函數時需在程序開頭用文件包含指令#include“stdlib．h”指明。

調用動態存儲分配函數返回的指針是指向void類型或char類型的指針，在具體使用時，要根據所指向的數據進行強制類型轉換。