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

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;
		}
	}

}