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 ;

尾插流程如下：

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

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

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

删除节点的函数原型可定义如下：
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);
			}
		}

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