C和指針 （pointers on C）——第十二章：使用結構和指針

第十二章 使用結構和指針

這章就是連結清單。先單連結清單，後雙向連結清單。

總結：

單連結清單是一種使用指針來存儲值的資料結構。連結清單中的每個節點包含一個字段，用于指向連結清單的下一個節點。

有一個獨立的根指針指向連結清單的第1個節點。單連結清單隻能從一個方向周遊。

如何insert單連結清單：1、新節點的link字段必須設定為指向它的後面節點。2、前一個節點的link字段必須指向這個新節點。

為了防止可能會插傳入連結表的起始位置這種情況，在C中，可以儲存一個指向必須進行修改的link字段的指針，而不是儲存一個指向前一個節點的指針。

雙連結清單中的每個節點包含兩個link字段：其中一個指向連結清單的下一個node，另一個指向前一個node。

雙連結清單有兩個根指針，一個指向第一個node，另一個指向最後一個node。是以周遊的過程中可以從任何一端開始，而且在周遊過程中夠可以改變方向。

為了把一個新節點插入到雙連結清單中，我們必須修改4個指針。新節點的前向和後向link字段必需被設定，前一個節點的fwd和後一個節點的bwd也要修改，指向新節點。

警告：

1、落到連結清單尾部的後面。

2、使用指針時應該格外小心，因為C并沒有對他們的使用提供安全網。

3、從if語句中提煉語句可能會改變測試結果。

程式設計提示：

1、消除特殊情況使代碼更易于維護。

2、不要輕易的進行提煉語句，這樣會使你的語句更難維護。

程式設計執行個體：（本章就不再弄習題了，關于資料結構這塊會有大量代碼進行訓練）

1、提煉後的單連結清單插入操作

#include "stdlib.h"

typedef struct NODE
{
	struct NODE *link;
	int			value;
} Node;
int sll_int(register Node **linkp, int new_value)
{
	register Node *current;		//指向目前節點
	register Node *new_node;	//指向插入節點

	/*
	** 尋找正确插入位置，按順序通路連結清單，直到有個值大于或等于新值
	*/
	while ((current = current->link) != NULL && current->value < new_value)
	{
		linkp = ¤t->link; //移動linkp指向下一個Node的link
	}
	/* 配置設定新的記憶體，并存到新節點去 */
	new_node = (NODE *) malloc (sizeof(NODE));
	if (new_node == NULL)
	{
		return 0;
	}
	new_node->value = new_value;
	/* 插入新節點 */
	new_node->link = current;
	*linkp = new_node;
	return 1;
}
           

2、雙連結清單插入操作

#include "stdlib.h"

typedef struct NODE
{
	struct NODE *fwd;
	struct NODE *bwd;
	int value;
}Node;

int dll_insert(Node *rootp, int value)
{
	/* 把一個值插入到一個雙向連結清單中，rootp是一個指向根節點的指針
	   value 是插入的新值
	   傳回值：如果已經存在連結清單中，傳回0
	         如果記憶體不足導緻無法插入，傳回-1，成功傳回1；
	*/
	Node *this_node;
	Node *next_node;
	Node *new_node;

	for (this_node = rootp; next_node != NULL; this_node = next_node )	
	{
		if (next_node->value == value)
			return 0;
		if (next_node->value < value)
			break;
		next_node = next_node->fwd;
	}
	/* 為新節點申請記憶體空間*/
	new_node = (Node *) malloc (sizeof(Node));
	if (new_node == NULL)
		return -1;
	new_node->value = value;
	/*  
		插入節點 
	    if 不在連結清單尾部 then 不在連結清單起始位置 or 位于連結清單起始位置
		else 在連結清單尾部 then 不在連結清單起始位置 or 位于連結清單起始位置（空連結清單）
	*/
	if (next_node->fwd != NULL)
	{
		/*不在連結清單尾部*/
		if (this_node != rootp)
		{
			/* 不在連結清單的頭部 */
			this_node->fwd = new_node;
			next_node->bwd = new_node;
			new_node->bwd = this_node;
			new_node->fwd = next_node;
		}
		else
		{
			/* 在連結清單的頭部*/
			rootp->fwd = new_node;
			next_node->bwd = new_node;
			new_node->bwd = rootp;
			new_node->fwd = next_node;
		}		
	}
	else
	{
		/*在連結清單尾部*/
		if (this_node->bwd != rootp)
		{
			/* 不在連結清單的頭部 */
			new_node->fwd = NULL;
			new_node->bwd = this_node;
			this_node->fwd = new_node;
			rootp->bwd = new_node;
		}
		else
		{
			/* 在連結清單的頭部*/
			new_node->fwd = NULL;
			new_node->bwd = NULL;
			rootp->bwd = new_node;
			rootp->fwd = new_node;
		}
	}

}