双向循环带头链表的基础操作(增删改查)

1.定义链表结点的结构

	typedef int CLDataType;
	//结点类型
	typedef struct ListNode
	{
		 CLDataType _data;
		 struct ListNode* _next;
		 struct ListNode* _prev;
	}ListNode;
	//链表的头
	typedef struct List
	{
		 ListNode* _head;
	}List;

2.声明各函数接口

//创建一个双向循环链表结点
ListNode* BuyListNode(CLDataType x);
//初始化双向循环带头链表
void ListInit(List* pcl);
//销毁双向循环带头链表
void ListDestory(List* pcl);
//尾插
void ListPushBack(List* pcl, CLDataType x);
//头插
void ListPushFront(List* pcl, CLDataType x);
//指定位置插入结点 
void ListInsert(ListNode* pos, CLDataType x);
//尾删
void ListPopBack(List* pcl);
//头删
void ListPopFront(List* pcl);
//指定位置删除(不能是头结点)
void ListErase(List* pcl, ListNode* pos);
//遍历打印链表
void ListPrint(List* pcl);
//链表的长度
int ListSize(List* pcl);
//判断链表是否为空(为空返回0，非空返回1)
int ListEmpty(List* pcl);
//寻找指定数据的结点(找到返回地址，找不到返回NULL)
ListNode* FindListNode(List* pcl, CLDataType x);

3.各函数实现

//创建一个双向循环链表结点
ListNode* BuyListNode(CLDataType x)
{
	 ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
	 if (cur == NULL)
	 {
	  	perror("use malloc");
	  	exit(1);
	 }
	 cur->_data = x;
	 cur->_next = NULL;
	 cur->_prev = NULL;	
	return cur;
}
//初始化双向循环带头链表
void ListInit(List* pcl)
{
	 assert(pcl);
	 ListNode* head = BuyListNode(0);
	 pcl->_head = head;
	 pcl->_head->_next = pcl->_head;
	 pcl->_head->_prev = pcl->_head;
}
//销毁双向循环带头链表
void ListDestory(List* pcl)
{
	 assert(pcl);
	 ListNode* cur = pcl->_head->_next;
	 while (cur != pcl->_head)
	 {
		  ListNode* tmp = cur->_next;
		  free(cur);
		  cur = tmp;
	 }
	 free(pcl->_head);
	 pcl->_head = NULL;
}
//尾插
void ListPushBack(List* pcl, CLDataType x)
{
	 assert(pcl);
	 //尾插和在头结点前面插入一个结点一样
	 ListInsert(pcl->_head, x);
}
//头插
void ListPushFront(List* pcl, CLDataType x)
{
	 assert(pcl);
	 //头插和在第一个结点前面插入一样
 	ListInsert(pcl->_head->_next, x);
}
//指定位置前面插入结点 
void ListInsert(ListNode* pos, CLDataType x)
{
	 assert(pos);
	 ListNode* newnode = BuyListNode(x);
	 //保存前面结点(建议这么写，如果直接用指针完会太绕了)
	 ListNode* prev = pos->_prev;
	 //prev-newnode-pos指针连接起来
	 prev->_next = newnode;
	 newnode->_prev = prev;
	 newnode->_next = pos;
	 pos->_prev = newnode;
}
//尾删
void ListPopBack(List* pcl)
{
	 assert(pcl);
	 //尾删和在删除指定最后一个结点一样
	 ListErase(pcl, pcl->_head->_prev);
}
//头删
void ListPopFront(List* pcl)
{
	 assert(pcl);
	 //头删和删除指定第一个结点一样
	 ListErase(pcl, pcl->_head->_next);
}
//指定位置删除结点
void ListErase(List* pcl, ListNode* pos)
{
	 assert(pos);
	 //删除的结点不能是头结点
	 assert(pos != pcl->_head);
	 //保存pos前面结点
	 ListNode* prev = pos->_prev;
	 //保存pos后面结点
	 ListNode* next = pos->_next;
	 //prev pos next(pos为删除结点) 
	 prev->_next = next;
	 next->_prev = prev;
	 free(pos);
	 pos = NULL;
}
//遍历打印链表
void ListPrint(List* pcl)
{
	 assert(pcl);
	 ListNode* cur = pcl->_head->_next;
	 //从头结点的下一个结点开始遍历
	 while (cur != pcl->_head)
	 {
		  printf("%d-->", cur->_data);
		  cur = cur->_next;
	 }
	 printf("over\n");
}
//链表的长度
int ListSize(List* pcl)
{
	 assert(pcl);
	 ListNode* cur = pcl->_head->_next;
	 int count = 0;
	 //遍历一遍链表(不算头结点)
	 while (cur != pcl->_head)
	 {
		  count++;
		  cur = cur->_next;
	 }
	 return count;
}
//判断链表是否为空(为空返回0，非空返回1)
int ListEmpty(List* pcl)
{
	 assert(pcl);
	 //prev和next如果都指向自己，则链表为空
	 return ((pcl->_head->_next == pcl->_head) && (pcl->_head->_prev == pcl->_head)) ? 0 : 1;
}
//寻找指定数据的结点(找到返回地址，找不到返回NULL)
ListNode* FindListNode(List* pcl, CLDataType x)
{
	 assert(pcl);
	 ListNode* cur = pcl->_head->_next;
	 //遍历链表找到相同数据返回地址，找不到则返NULL
	 while (cur != pcl->_head)
	 {
		  if (cur->_data == x)
		  {
		   return cur;
		  }
		  cur = cur->_next;
	 }
	 return NULL;
}