第十二章 利用结构和指针

这章就是链表。先单链表，后双向链表。

总结：

单链表是一种使用指针来存储值的数据结构。链表中的每一个节点包括一个字段，用于指向链表的下一个节点。

有一个独立的根指针指向链表的第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;

		}

	}

}