基本介紹
- 中文名：單鍊表
- 外文名：Singly Linked List
- 類型：數據結構元素
- 實質：一種鏈式存取的數據結構
- 簡介：地址任意的存儲單元存放數據元素
- 建立過程：申請空間、得到數據、建立連結
單鍊表簡介,概念介紹,連結存儲方法,結點結構,頭指針head和終端結點,單鍊表定義,C語言結構定義,指針變數和結點變數,單鍊表的建立,頭插法,尾插法,動態存儲,
單鍊表簡介
概念介紹
以“結點的序列”表示線性表稱作線性鍊表（單鍊表），單鍊表是鏈式存取的結構。
連結存儲方法
連結方式存儲的線性表簡稱為鍊表（Linked List）。
鍊表的具體存儲表示為：
① 用一組任意的存儲單元來存放線性表的結點（這組存儲單元既可以是連續的，也可以是不連續的）
② 鍊表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關係，在存儲每個結點值的同時，還必須存儲指示其後繼結點的地址（或位置）信息（稱為指針（pointer）或鏈(link)）
鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數據結構。
結點結構
┌───┬───┐
│data │next │
└───┴───┘
data域--存放結點值的數據域
next域--存放結點的直接後繼的地址（位置）的指針域（鏈域）
鍊表通過每個結點的鏈域將線性表的n個結點按其邏輯順序連結在一起的，每個結點只有一個鏈域的鍊表稱為單鍊表（Single Linked List）。
頭指針head和終端結點
單鍊表中每個結點的存儲地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。鍊表由頭指針唯一確定，單鍊表可以用頭指針的名字來命名。
終端結點無後繼，故終端結點的指針域為空，即NULL。
單鍊表定義
C語言結構定義
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表示它是指向某一結點的指針
指針變數和結點變數
指針變數 | 結點變數 | |
定義 | 在變數說明部分顯式定義 | 在程式執行時，通過標準函式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來訪問結點就意味著訪問一個不存在的變數，從而引起程式的錯誤。
② 有關指針類型的意義和說明方式的詳細解釋
可見，在鍊表中插入結點只需要修改指針。但同時，若要在第 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。
