数据结构学习笔记(3.线性表之循环链表)

本节知识点：

1.为什么选择循环链表：因为有很多生活中结构是循环的，是单链表解决不了的，比如星期、月份、24小时，对于这些循环的数据，循环链表就体现出它的优势了。

2.循环链表的结构：

循环链表就是从头结点后面开始，尾节点的next不再是NULL了，而是头结点后面的第一个链表元素，如上图。

3.如何创建一个循环链表：

步骤一：

步骤二：

无论是头插法，还是尾插法都没有关系，都可以创建完成这个循环链表。

4.如何将一个单向链表改写成一个循环链表：

第一步 (改写插入函数)：

a.把插入位置pos的允许范围改成0~~~无穷大

	ret=( NULL != node) && ( NULL != Node) && (pos >= 0);

b.把两种方式的头插法情况加入程序，第一种是pos值为0和1的情况，如图：

这种情况分为两部：先把node插入到head和第一个元素直接，然后再把链表尾指向node元素(node表示插入元素)。

代码如下：

if(node == (CircleListNode* )head) 
{
	Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length); //获得链表最后一个元素 
	Last->next = Node; //把头插法的数据连接到 链表的最后一个元素的后面 
}

头插法的第二种情况，是循环链表，循环了一圈回来了，与第一种不同的是此时插入的相对位置和第一种的相对位置不一样。(其实这种方法跟普通插入是一样的) 如图：

第二步(改写删除函数)：

a.也是把pos值的取值范围改成0 到 无穷大，但是同时记得判断length要大于0 ，要保证链表中有数据，不然删什么呀~~~~

 if(( NULL != lhead) && (pos > 0) && (lhead->length>0))

b.对于删除第一个元素有两种情况 这里是难点：首先要在删除链表元素的 前面 判断是否要删除第一个元素(此时的情况是pos为1的情况)，然后删除链表元素，再判断是否是删除第一个元素的第二种情况(链表循环一圈后，到达链表第一个元素，此时元素的前一个链表不再是head头结点了)。如图：

代码如下：

if(node == (CircleListNode* )head)
{
	Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length);
}
		
ret = node->next;
node->next = ret->next;	
/*判断是不是循环了一圈后回来的情况 */
if((first == ret) &&(NULL == Last))
{
	Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length);
}
/*判断是否要删除链表中的第一个元素*/
if( Last != NULL )
{
	Last->next = ret->next; 
	lhead->head.next = ret->next;
}

图中红笔的代码是：

 ret = node->next;
 node->next = ret->next;	

图中蓝笔的代码是：

if( Last != NULL )
{
	Last->next = ret->next; 
	lhead->head.next = ret->next;
}

c.当length为0的是，即链表长度为0的时候，记得给头结点的next赋值为NULL

第三步 (改写获得链表元素函数)

a.记得把pos给成 0 到 无穷大，然后判断length链表长度是否为0 ，如果为0 就不能获取。

5.游标的引入：

在循环链表中一般可以定义一个游标，对于这样一个封装好的可复用循环链表，定义一个游标是十分方便的。例如：如果想依次获得链表中的每一个元素，利用get函数，太过低效了O(n2)，想想利用这样一个游标去遍历的话，复杂度仅仅是O(n)。还有就是在循环链表中，游标可以在链表中进行转圈，例如：可以解决约瑟夫环问题。

6.指定删除链表中某一个元素的函数CircleListNode* CircleList_Del(CircleList* head,CircleListNode* node)，其实也不是很高效，获得了当前游标的值的时候，再去调用CircleList_Del函数，这个轮询函数获得了pos，再去调用Del_CircleListNode然后又遍历了一边，把复杂的搞到了O(n2)。其实完全可以在找到pos的时候直接删除掉这个链表元素，这样的复杂度是O(n)。

7.我还觉得获得当前游标得值的函数CircleList_Slider的返回值有些问题，我觉得如果返回的是当前游标的上一个链表元素的值会更好，因为这个是一个单向链表，如果得到了上一个链表元素的值，就可以通过游标实现，删除啊，插入啊等高效的操作了。

本节代码：

CricleList.c：

/*******************************************************************************************************
文件名：CircleList.c
头文件：CircleList.h 
时间： 2013/08/17
作者： Hao
功能:  可以复用 带有增 删 改 查 功能的循环链表
难道： 1.typedef struct Str_CircleList CircleListNode;  //这个结构体是链表的真身 
		struct Str_CircleList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型 
		{                     //转换成(CircleListNode* )的时候  其实就是要开始对每个元素中的 CircleListNode进行赋值了 
			CircleListNode* next;
		}; 
		这个链表结构在链表元素中起到的作用 是本节的难点 
		2.切记一个问题  就是已经是链表中元素的 千万不要再往链表中添加了 否则链表一定出现无穷的错误 
		3.对于pos值的问题  add、get、del三个函数中 的链表都是 从1开始的到length  0是链表头 
						  在add函数中pos为0的时候是和pos为1的情况是一样的  都是头插法  0~~~~~无穷大 
		                  在get函数中pos为0的时候是获得链表头 地址      0~~~~~length 
						  在del函数中pos为0的时候是无效的 del失败       1~~~~~length 
*******************************************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "CircleList.h"
 
typedef struct str_list_head  //这个是链表头 其实也可以当作一个没有前驱的 链表元素 元素的内容是链表长度 
{
	//CircleListNode* next;
	CircleListNode head; //这个参数要特别重视 每一个链表元素结构的第一个参数一定是 CircleListNode
	                   //因为在寻找链表元素后继的时候 其实就是将链表元素强制类型转换成 CircleListNode*  然后给next进行赋值 其实就是给 CircleListNode变量赋值 
	CircleListNode* slider; 
	int length; //链表长度 
}list_head;
 
/*******************************************************************************************************
函数名： Creat_CircleListHead
函数功能：创建一个链表的链表头 并给链表头分配空间
参数： void
返回值：ret 成功返回链表头地址  失败返回NULL 
*******************************************************************************************************/
CircleList* Creat_CircleListHead(void)
{
	list_head* ret = NULL;
	ret = (list_head* )malloc( sizeof(list_head)*1 );
	if(NULL != ret) //malloc分配成功 
	{
		ret->length = 0;
		//ret -> next = NULL;
		ret->head.next = NULL;
		ret->slider = NULL;
	}
	return (CircleList* )ret; 
}
 
/*******************************************************************************************************
函数名：Destroy_CircleListHead
函数功能：释放一个链表头指针 
参数：CircleList* head 链表头指针 
返回值： ret 释放成功返回1  释放失败返回0 
*******************************************************************************************************/
int Destroy_CircleListHead(CircleList* head)
{
	int ret = 0; 
	list_head* lhead = (list_head* )head;
	if( NULL != lhead )
	{
		free(lhead);
		ret = 1;
	}
	return ret;
}
 
/*******************************************************************************************************
函数名:Get_Length
函数功能：获得链表的长度 
参数: CircleList* head 链表头指针 
返回值： ret 成功返回链表长度  失败返回0 
*******************************************************************************************************/
int Get_Length(CircleList* head) 
{
	int ret = 0;
	list_head* lhead = (list_head* )head;
	if( NULL != lhead )
	{
		ret = lhead -> length;
	}	
	return ret;
}
 
/*******************************************************************************************************
函数名：Clean_CircleListHead
函数功能：	清空链表 
参数： CircleList* head 链表头指针 
返回值：ret 成功返回1 失败返回0 
*******************************************************************************************************/
int Clean_CircleListHead(CircleList* head) 
{
	int ret = 0;
	list_head* lhead = (list_head* )head;
	if( NULL != lhead )
	{
		lhead -> length = 0;
		//lhead	 -> next = NULL;
		lhead -> head.next = NULL;
		lhead->slider = NULL;
		ret = 1;
	}	
	return ret;
}
 
/*******************************************************************************************************
函数名:Add_CircleList
函数功能：往链表里面添加一个链表元素 如果pos的值是0(就是链表头)和1(链表的第一元素 链表元素个数是从1开始算的)都是头插法
          pos的值大于链表长度是尾插法  这里面pos值得注意的是 i=1 pos为a的时候 是把链表元素插入第a个元素的位置 
          当i=0 pos为a的时候 是把链表元素插入 第a个元素位置的后面    切忌：这里面0位置是链表头指针 从1开始是链表元素 
参数：   CircleList* head链表头指针    CircleListNode* Node插入元素的指针(被强制类型转化成CircleListNode*)  int pos 插入位置 
         pos的有效值范围是 从0到无穷大  
返回值： ret 插入成功返回1  插入失败返回0 
*******************************************************************************************************/
int Add_CircleList(CircleList* head, CircleListNode* Node, int pos)
{
	int ret = 0;
	int i = 0;
	list_head* lhead = (list_head* )head;
	CircleListNode* node = (CircleListNode* )head;
	CircleListNode* Last = NULL;
	ret=( NULL != node) && ( NULL != Node) && (pos >= 0);
	if(1 == ret)
	{
		for(i=1; ( (i<pos) && (node->next != NULL) ); i++)
		{
			node = node->next;
		}
		Node -> next = node -> next;
		node -> next = Node;
		if(lhead->length == 0)//第一次插入元素的时候把游标 指向这个元素  
		{
			lhead->slider = Node;
		}
		lhead -> length++; //这个一定要在后面调用 lhead->length值的前面更新 
		/*判断是否为头插法  所谓头插法 就是pos为0和1的情况 其实也就是没有进for循环的情况  剩下的无论pos为多少  进入多少次循环都没有头插法*/
		if(node == (CircleListNode* )head) 
		{
			Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length); //获得链表最后一个元素 
			Last->next = Node; //把头插法的数据连接到 链表的最后一个元素的后面 
		}
		
	}
	return ret;
}
 
/*******************************************************************************************************
函数名：Get_CircleListNode
函数功能：获得链表中第pos个元素位置的链表元素 链表是从1开始的  0是链表头   pos为0的时候表示get链表头 
参数： CircleList* head链表头指针    int pos获得链表元素的位置  pos的有效取值范围是 1 到  length  0是链表头 
返回值： CircleListNode*类型 第pos个链表元素的地址 
*******************************************************************************************************/
CircleListNode* Get_CircleListNode(CircleList* head, int pos)
{
	int ret = 0;
	int i = 0;
	list_head* lhead = (list_head* )head;
	/*本来pos应该是有上限的  但是变成了循环链表pos理论上说就可以无穷大了  但是get函数应该是在链表中有值的情况下才成立的 即(lhead->length>0)*/ 
	ret=( NULL != lhead) && (pos >= 0) && (lhead->length>0); 
	if(1 == ret)
	{
		CircleListNode* node = (CircleListNode* )head;
		for(i=0; i<pos; i++) //执行 pos次   得到的是第pos位置的node 
		{
			node = node->next;
		}	
		return (CircleListNode*)node;
	}
	return NULL;
}
 
/*******************************************************************************************************
函数名：Del_CircleListNode
函数功能：删除链表中第pos位置的链表元素 
参数： CircleList* head链表头指针    int pos删除链表元素的位置  pos是删除的链表元素的位置 跟get和add中的
       pos是配套的  有效取值范围依然是 1到 length  在这个函数里面由于不能删除链表头 所以pos为0的时候无效 
返回值： CircleListNode* ret这个返回值很重要 因为这个删除仅仅是把链表元素踢出了链表 并没有free开辟的内存
         应该通过这个返回的地址free  释放内存
		 删除成功返回 删除链表元素的地址   删除失败返回 NULL 
*******************************************************************************************************/
CircleListNode* Del_CircleListNode(CircleList* head, int pos)
{
	CircleListNode* ret = NULL;
	CircleListNode* Last = NULL;
	int i = 0;
	list_head* lhead = (list_head* )head;
	CircleListNode* first = lhead->head.next;
	
	if(( NULL != lhead) && (pos > 0) && (lhead->length>0))
	{
		CircleListNode* node = (CircleListNode* )head;
		for(i=1; i<pos; i++)//执行 pos次   得到的是第pos位置的node  这个方法行不通 
		{                   //因为要想删除第pos位置的node 应该先找到它上一个链表元素 
			node = node->next; //所以这里面i=1 比get函数少执行了一次  得到第pos-1位置的node 
		}
		/*判断是不是 pos为1的 情况删除头节点后面的第一个元素(这个是没有进入for循环的)  跟循环一圈后的情况不一样  */
		/*循环一圈的是进入for循环的情况   此时的node不再是head了 而是链表最后一个元素*/ 
		if(node == (CircleListNode* )head)
		{
			Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length);
		}
		
		ret = node->next;
		node->next = ret->next;	
		/*判断是不是循环了一圈后回来的情况 */
		if((first == ret) &&(NULL == Last))
		{
			Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length);
		}
		/*判断是否要删除链表中的第一个元素*/
		if( Last != NULL )
		{
			Last->next = ret->next; 
			lhead->head.next = ret->next;
		}
		if( lhead->slider == ret)//如果删除的元素恰恰就是游标指向的元素  要把游标往后面移动一位 
		{
			lhead->slider = ret->next;
		}
		lhead->length--; //这个一定要写在 Get_CircleListNode 后面 不然的话 pos就为0了 
		/*判断链表是否 减到了空  如果链表中不再有元素 就把head.next赋值为NULL*/
		/*单向链表不需要这个的原因 是因为单向链表的最后一个元素的next就是NULL 而双向链表没有NULL的了*/
		if(0 == lhead->length)
		{
			lhead->head.next = NULL;
			lhead->slider = NULL; 
		}
		
	}
	return (CircleListNode*)ret;
}
 
/*******************************************************************************************************
函数名： CircleList_Slider
函数功能：获得当前游标指向的数据
参数： CircleList* head
返回值：成功返回 CircleListNode* ret  失败返回NULL 
*******************************************************************************************************/
CircleListNode* CircleList_Slider(CircleList* head)
{
	CircleListNode* ret = NULL;
	list_head* lhead = (list_head* )head;
	if( (NULL != lhead)&&(NULL != lhead->slider) )//保证slider是有效的 
	{
		ret = lhead->slider;
	}
	return ret;
}
 
/*******************************************************************************************************
函数名： CircleList_Reset
函数功能：重置游标 让游标指向head头节点后面的第一个元素 
参数： CircleList* head
返回值：成功返回 当前游标的指向CircleListNode* ret  失败返回NULL 
*******************************************************************************************************/
CircleListNode* CircleList_Reset(CircleList* head)
{
	CircleListNode* ret = NULL;
	list_head* lhead = (list_head* )head;
	if(NULL != lhead)
	{
		lhead->slider = lhead->head.next;
		ret = lhead->slider;
	}
	return ret;
}
 
/*******************************************************************************************************
函数名： CircleList_Next
函数功能：使游标指向下一个元素 
参数： CircleList* head
返回值：成功返回 前游标的指向CircleListNode* ret  失败返回NULL 
*******************************************************************************************************/
CircleListNode* CircleList_Next(CircleList* head)
{
	CircleListNode* ret = NULL;
	list_head* lhead = (list_head* )head;
	if((NULL != lhead)&&(NULL != lhead->slider)) //保证游标是有效的 
	{
		ret = lhead->slider;
		lhead->slider = ret->next; 
	}
	return ret;
}
 
/*******************************************************************************************************
函数名： CircleList_Del
函数功能：删除链表中的某个指定元素 
参数： CircleList* head   CircleListNode* node为指定的元素 
返回值：成功返回 删除的链表元素  失败返回NULL 
*******************************************************************************************************/
CircleListNode* CircleList_Del(CircleList* head,CircleListNode* node)
{	//这个函数主要是用来删除游标的返回值的 
 
	CircleListNode* ret = NULL;
	list_head* lhead = (list_head* )head;
	int i=0; 
	if((NULL != head)&&(NULL != node))
	{
		CircleListNode* current = (CircleListNode*)lhead;
		for(i=1; i<=lhead->length; i++)
		{
			if(node == current->next)
			{
				ret = current->next;
				break; 
			} 
			current = current->next;
		}
		
		if(NULL == ret)  //说明没有找到node 
		{
			printf("put error!!!\n"); 
		}
		else //找到了node 
		{
			Del_CircleListNode(lhead,i); 
		} 
	}	
	return ret;//返回删除的链表元素 
}
 
 
 
 
 

CircleList.h：

#ifndef __CircleList_H__
#define __CircleList_H__
 
typedef void CircleList;  //这个是为了 封装方便 
typedef struct Str_CircleList CircleListNode;  //这个结构体是链表的真身 
struct Str_CircleList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型 
{                     //转换成(CircleListNode* )的时候  其实就是要开始对每个元素中的 CircleListNode进行赋值了 
	CircleListNode* next;
};
 
CircleList* Creat_CircleListHead(void);
 
int Destroy_CircleListHead(CircleList* head);
 
int Get_Length(CircleList* head);
 
int Clean_CircleListHead(CircleList* head);
 
int Add_CircleList(CircleList* head, CircleListNode* Node, int pos);
 
CircleListNode* Get_CircleListNode(CircleList* head, int pos);
 
CircleListNode* Del_CircleListNode(CircleList* head, int pos); 
 
CircleListNode* CircleList_Del(CircleList* head,CircleListNode* node);
 
CircleListNode* CircleList_Next(CircleList* head);
 
CircleListNode* CircleList_Reset(CircleList* head);
 
CircleListNode* CircleList_Slider(CircleList* head);
 
#endif

main.c：

#include <stdio.h>
#include <stdlib.h>
#include "CircleList.h"
 
typedef struct _tag_str
{
	CircleListNode head;
	int i;
}str;
int main(int argc, char *argv[]) 
{
	str str1,str2,str3,str4,str5,str6;
	str *strp;
	int i=0;
	str1.i=1;
	str2.i=2;
	str3.i=3;
	str4.i=4;
	str5.i=5;
	str6.i=6;
	CircleList* head;
	head = Creat_CircleListHead();
	
	Add_CircleList(head, (CircleListNode*)&str1, 0);
	Add_CircleList(head, (CircleListNode*)&str2, 0);
	Add_CircleList(head, (CircleListNode*)&str3, 0);
	Add_CircleList(head, (CircleListNode*)&str4, 0);
	Add_CircleList(head, (CircleListNode*)&str5, 5);
	
	for(i=1; i<=2*Get_Length(head); i++)
	{
		strp = (str* )Get_CircleListNode(head, i);
		printf("%d\n",strp->i);
	}
	printf("\n");
	
	printf("%d\n",Get_Length(head));
	strp = (str* )Del_CircleListNode(head, 6);
	printf("%d\n",strp->i);	
	
	printf("%d\n",Get_Length(head));
	printf("\n");
	for(i=1; i<=2*Get_Length(head); i++)
	{
		strp = (str* )Get_CircleListNode(head, i);
		printf("%d\n",strp->i);
	}
	
	printf("\n");
	printf("%d\n",Get_Length(head));
	strp = (str* )Del_CircleListNode(head, 1);
	printf("%d\n",strp->i);	
	
	printf("%d\n",Get_Length(head));
	printf("\n");
	for(i=1; i<=2*Get_Length(head); i++)
	{
		strp = (str* )Get_CircleListNode(head, i);
		printf("%d\n",strp->i);
	}
	
	
	
	
	printf("\n");
	for(i=1; i<=3; i++)
	{
		strp = (str* )Del_CircleListNode(head, 1);
		printf("%d\n",strp->i);
	}
	
	/*CircleList_Reset(head);
	CircleList_Next(head);
	CircleList_Del(head,(CircleListNode*)&str3);
	strp = (str* )CircleList_Slider(head);
	printf("%d\n",strp->i);
	printf("\n");
	
	for(i=1; i<=2*Get_Length(head); i++)
	{
		strp = (str* )Get_CircleListNode(head, i);
		printf("%d\n",strp->i);
	}
	printf("\n");*/
	
 
	
	Destroy_CircleListHead(head);
	return 0;
}