鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。

使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由於增加了結點的指針域，空間開銷比較大。鏈表最明顯的好處就是，常規數組排列關聯項目的方式可能不同於這些數據項目在記憶體或磁盤上順序，數據的存取往往要在不同的排列順序中轉換。鏈表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。

鏈表細則：

1)是由結構體和指針構成的。

2)包括兩個部分一個是數據域和指針域。

3)鏈表中的結點分為兩類：頭結點和一般結點。頭結點是沒有數據域的。

4)基本操作有：初始化鏈表，增加結點和刪除結點，求鏈表的長度等等。

鏈表主要包括：單向鏈表，雙向鏈表，循環鏈表。

單向鏈表

含義：

單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始；鏈表是使用指針進行構造的列表；又稱為結點列表，因為鏈表是由一個個結點組裝起來的；其中每個結點都有指針成員變量指向列表中的下一個結點；

列表是由結點構成，head指針指向第一個成為表頭結點，而終止於最後一個指向nuLL的指針。

用法：

typedef struct NODE{
	struct NODE *next;
	int	 data; 

}Node;

單鏈表的指向，鏈表的起始位置我們成為根指針(root)，它指向鏈表的第一個節點。根指針不包含任何數據，它只是一個指針。

Node *root;

下一個節點的訪問通過root->next來實現

1.初始化鏈表：

int InitNodeList(Node **node)
{
	*node=(Node*)malloc(sizeof(Node));//鏈表分配內存空間
	if(!*node)
	{
		return 0;
	}
	(*node)->next=NULL;
 	return 1;
}

2.插入數據：

/*
按值的大小順序進行插入，把值插入到合適的位置
*/
int InsertNodeList(Node **root,int data)
{
 Node *current;
 Node *previous;
 Node *new;
 current = *root;
 previous = NULL; /*用於判斷新插入的值是否在第一個節點*/ 

 
 /*尋找正確的插入位置，按序訪問鏈表，直到到達一個其值大於或等於新值的節點*/
 while(current != NULL && current->data < data)
 {
 previous = current;
 current = current->next;
 }
 
 /*新節點分配內存空間*/
 new = (Node *)malloc(sizeof(Node));
 if(new == NULL)
 {
 return false;
 }
 /*新節點插入鏈表*/
 new->data = data;
 /*如果插入的值在根節點，把新節點指向根節點，否則前一個節點，指向新節點*/
 if (previous == NULL)
 {
 *root = new;
 }
 else
 {
 previous->next = new;
 }
 return true;
}

3.獲取鏈表長度

int LengthNodeList(Node *root)
{
 int i = 0;
 Node *previous;
 previous=root->next;/*p指向鏈表的第一個結點。*/
 /*循環鏈表，直到節點為空*/ 

 while(previous)
 {
 i++;
 previous=previous->next;
 }
 return i;
}

4.刪除節點：

void DestroyNodeList(Node *root)
{
 Node *current,*next;
 current=root;/*current 指向鏈表的根結點*/
 /*當節點指向為空，即到了鏈表末尾，跳出*/
 while(current)
 {
 next = current->next;/*指向當前結點的下一個結點。*/
 free(current);/*釋放當前結點*/
 current = next;/*指向下一個結點*/
 }
}

5.調用：

int main(void)
{
	Node *root;
	int node_length = 0;
	InitNodeList(&root); /*初始化鏈表，得到一個跟節點*/
	InsertNodeList(&root,10); /*向鏈表中插入一個數據*/
	node_length = LengthNodeList(root); /*獲取鏈表長度*/
	DestroyNodeList(root); /*銷燬鏈表*/ 

	return 0;
}

閱讀更多 大貓玩程序 的文章

關鍵字: 技術 結點 指針