C语言数据结构单链表之温故而知新

抛弃繁杂的定义，以实用，实战的角度来学习数据结构，这将使得数据结构的学习非常的简单。

前面已经学习了单链表的创建操作：http://blog.csdn.net/morixinguan/article/details/68951912

这节，将单链表温习的笔记共享出来，然后写一个例子，以防自己忘记。

1、单链表的数据结构的定义:

创建节点函数原型可定义如下：

struct list *create_node(int data) ;
如何创建单链表的节点，主要分以下步骤:
(1)给当前的每个节点的数据结构配置定量的空间大小
   ep : struct list *node = malloc(sizeof(struct list));
(2)清节点数据(由于结构体变量在未初始化的时候，数据是脏的)
   ep : memset(node,0,sizeof(struct list));
(3)给节点初始化数据
   ep : node->id = data ;
(4)将该节点的指针域设置为NULL
   ep : node->next = NULL ;

3、单链表的尾插：
尾插节点函数原型可定义如下：

如何将当前链表和新的节点相连接？只要实现：
header->next = new 

尾插流程如下：

(1)获取当前节点的位置，也就是访问头节点
   ep : struct list *p = header ;
(2)判断是否为最后一个节点，如果不是，移动到下一个节点，如果是，将数据插入尾部。
   ep : while(NULL != p->next) p = p->next ;
	    p->next = new ;

4、单链表的头插

很好理解，头插就是把新的节点插在原来的节点和原来节点的下一个节点之间的一个节点。如图，新的节点插在头节点和节点1。
所以可以推出头插流程如下：

(1)获取当前节点的位置，也就是访问头节点
	ep : struct list *p = header ;
(2)新的节点的下一个节点设置为原来头节点的下一个节点(第一个节点)
    ep : new->next = p->next ;
(3)原来的头节点的下一个节点设置为现在新插入的头节点
	ep : p->next = new ;

5、单向链表的遍历

      如图为一条单向链表的模型，看图知道该链表由头节点和若干个节点组成，最后一个节点(尾节点)为NULL 。
从图中可以得出信息，如果我们要打印出各个节点的数据，要考虑以下问题：

(1)需要打印头节点吗？(头节点肯定是不用打印的，因为这是我们为了操作方便而设置的一个节点)。
(2)这条链表有多少个节点我们怎么知道？(通过判断该链表是否已经到达了尾节点，标志就是NULL)

那么可以得到流程如下：

(1)获取当前节点的位置，也就是访问头节点
	ep : struct list *p = header ;
(2)由于头节点我们不需要去打印它，这时候，初始化打印的节点需要从第一个节点开始。
	ep : p = p->next ;
(3)判断是否为最后一个节点，如果不是，先打印第一个节点的数据(1)，然后移动到下一个节点(2),重复这两个步骤。
   如果是最后一个节点，直接打印数据即可。
	while(NULL != p->next){ printf("node:%d\n",p->data) ; p = p->next ;}
	printf("node:%d\n",p->data);
	当然还可以一句代码解决，这样就达到了先偏移，后取数据。
	while(NULL != p->next){ p = p->next ; printf("node:%d\n",p->data) ; }

6、单向链表的删除

删除节点的函数原型可定义如下：
int detele_list_node(struct list *pH , int data);
单向链表的删除要考虑两种情况，一种的普通节点的删除(当然，头节点不能算)
还有一种是尾节点的前一个节点的删除情况，注意，删除完节点还需要释放对应节点的内存空间。

删除节点的设计流程：

(1)先定义两个指针，一个表示当前的节点，另一个表示当前节点的上一个节点。
	ep : struct list *p = header ;  //当前节点
		 struct list *prev = NULL ; //当前节点的上一个节点
(2)遍历整个链表，同时保存当前节点的前一个节点
    ep : while(NULL != p->next)
		{
		  //保存了当前的节点的前一个节点
		  prev = p ;
		  //保存当前偏移的节点
		  p = p->next ;
		  return 0 ;
		}
(3)在遍历的过程中查找要删除的数据
	ep : while(NULL != p->next)
		{
		  //保存了当前的节点的前一个节点
		  prev = p ;
		  //保存当前偏移的节点
		  p = p->next ;
		  //查找到了数据
		  if(p->id == data)
		  {

		  }
		  return 0 ;
		}
(4)查找到了数据后，分两种情况删除
	ep : 普通节点的删除
		if(p->id == data)
		{
			prev->next = p->next ;
			free(p);
		}
	ep : 考虑尾节点的下一个节点为NULL的节点删除
		if(p->id == data)
		{
			if(p->next == NULL)
			{
				prev->next = NULL ;
				free(p);
			}
		}

5、单向链表的逆序操作

逆序步骤：

流程咱们基本搞懂了，下面写一个程序，这将会变得非常非常的简单。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct slist
{
	int id ;
	struct slist *next ;
}L;

//创建一个节点
L *create_node(int data)
{
	//给每个节点分配结构体一样的空间大小
	L *p = malloc(sizeof(L));
	if(NULL == p)
	{
		printf("malloc error!\n");
		return NULL ;
	}
	//由于结构体在未初始化的时候一样是脏数据，所以要清
	memset(p,0,sizeof(L));
	//初始化第一个节点
	p->id = data ;
	//将节点的后继指针设置为NULL
	p->next = NULL ;
}

//链表的尾插
void tail_insert(L *pH , L *new)
{
	//获取当前的位置
	L *p = pH ;
	//如果当前位置的下一个节点不为空
	while(NULL != p->next)
	{
		//移动到下一个节点
		p = p->next ;
	}
	//如果跳出以上循环，所以已经到了NULL的这个位置
	//此时直接把新插入的节点赋值给NULL这个位置
	p->next = new ;
}

//链表的头插
void top_insert(L *pH , L *new)
{
	L *p = pH ;
	new->next = p->next ;
	p->next = new ;
}

//链表的遍历
void Print_node(L *pH)
{
	//获取当前的位置
	L *p = pH ;
	//获取第一个节点的位置
	p = p->next ;
	//如果当前位置的下一个节点不为空
	while(NULL != p->next)
	{
		//(1)打印节点的数据
		printf("id:%d\n",p->id);
		//(2)移动到下一个节点,如果条件仍为真，则重复(1)，再(2)
		p = p->next ;
	}
	//如果当前位置的下一个节点为空，则打印数据
	//说明只有一个节点
	printf("id:%d\n",p->id);
}

//删除链表中的节点
int detele_list_node(L * pH , int data)
{
	//获取当前头节点的位置
	L *p = pH ;
	L *prev = NULL;
	while(NULL != p->next)
	{
		//保存当前节点的前一个节点的指针
		prev = p ;
		//然后让当前的指针继续往后移动
		p = p->next ;
		//判断，找到了要删除的数据
		if(p->id == data)
		{
			//两种情况，一种是普通节点，还有一种是尾节点
			if(p->next != NULL)  //普通节点的情况
			{
				prev->next = p->next ;
				free(p);
			}
			else //尾节点的情况
			{
				prev->next = NULL ; //将这个尾节点的上一个节点的指针域指向空
				free(p);
			}
			return 0  ;
		}
	}
	printf("没有要删除的节点\n");
	return -1 ;
}

void trave_list(L * pH)
{
	//保存第一个节点的位置
	L *p = pH->next;
	L *pBack;
	int i = 0 ;
	if(p->next == NULL || p == NULL)
		return ;

	while(NULL != p->next) //遍历链表
	{
		//保存第一个节点的下一个节点
		pBack = p->next ;
		//找到第一个有效节点,其实就是头指针的下一个节点
		if(p == pH->next)
		{
			//第一个有效节点就是最后一个节点，所以要指向NULL
			p->next = NULL ;
		}
		else
		{
			/*
			new->next = p->next ;
			p->next = new ;
			*/
			p->next = pH->next ; //尾部连接
		}
		pH->next = p ; //头部连接
		p = pBack ; //走下一个节点
	}
	top_insert(pH,p); //插入最后一个节点
}

int main(int argc , char **argv)
{
	//创建第一个节点
	int i ;
	L *header = create_node(0);
	for(i = 1 ; i < 10 ; i++)
	{
		tail_insert(header,create_node(i));
	}
	Print_node(header);
	detele_list_node(header,5);
	putchar('\n');
	Print_node(header);
	putchar('\n');
	trave_list(header);
	Print_node(header);
	return 0 ;
}

运行结果：