#include<iostream>
using namespace std;

/*
*节点类
*/
struct DCNode
{
  int data;
  DCNode * prior;
  DCNode * next;
};
/*
*链表类
*/
struct DCList
{
	DCList()
	{
		size = 0;
	}
	size_t size;//记录节点数的个数
	DCNode * head;//指向链表的头结点
};

/*
*分配一个节点，并给该节点的数据域赋值，默认值为0；
*/
DCNode * MakeNode(int t=0)
{
	DCNode * p = (DCNode *)malloc(sizeof(DCNode));
	p->data = t;
	return p;
}

//初始化一个空的双向循环链表
void InitDCList(DCList &list)
{
	//分配一个头结点
	DCNode * p = MakeNode();
	list.head = p;
	list.size = 0;
	p->next = p;
	p->prior = p;
}

//释放所指向的节点
void FreeNode(DCNode * p)
{
	delete p;
}

//清空一个线性表
void clear(DCList &list)
{
	DCNode * p = list.head;
	p = p->next;
	while(p!= list.head)
	{  
		DCNode * p1 = p->next;
		delete p;
		p = p1;
	}
	list.size = 0;
}

//将s所指向的节点插入到链表的第一个节点之前
bool InsFirst(DCList &list,DCNode * s)
{
	
	s->next = list.head->next;
	list.head->next->prior = s;
	list.head->next = s;
	s->prior = list.head;
	list.size++;
	return true;
}

//删除链表中的第一个节点并以q指针返回
bool DelFirst(DCList &list,DCNode *  & q)
{
	if(list.head->next==list.head)//如果链表为空
	{
		q = 0;
		return false;
	}
	q = list.head->next;
	list.head->next->next->prior = list.head;
	list.head->next = list.head->next->next;
	list.size--;
	return true;
}

//将s所指向的节点串接在链表的最后一个节点之后
bool Append(DCList &list,DCNode * s)
{
	s->prior = list.head->prior;
	s->next = list.head;
	list.head->prior->next = s;
	list.head->prior = s;
	list.size++;
	return true;
}

//删除链表中的尾节点,并以指针q返回
bool Remove(DCList &list,DCNode * & q)
{
	if(list.head->next==list.head)//如果链表为空
	{
		q = 0;
		return false;
	}
	q = list.head->prior;
	list.head->prior->prior->next = list.head;
	list.head->prior = list.head->prior->prior;
	list.size--;
	return true;
}

//将s所指向的节点插入链表中p所指向的节点之前
bool InsBefore(DCList &list,DCNode * p,DCNode * s)
{
	DCNode * p1 = list.head->next;
	while(p1!=list.head)
	{
	 if(p1==p)//找到该链表中是否存在p所指向的节点
	 {
		 s->next = p;
		 s->prior = p->prior;
		 p->prior->next = s;
		 p->prior = s;
		 list.size++;
	     return true;
	 }
	  p1 = p1->next;
	}
	//没找到
	return false;
}

//将s所指向的节点插入链表中p所指向的节点之后
bool InsAfter(DCList &list,DCNode * p,DCNode * s)
{
	DCNode * p1 = list.head->next;
	while(p1!=list.head)
	{
	 if(p1==p)//找到该链表中是否存在p所指向的节点
	 {
		 s->next = p->next;
		 s->prior = p;
		 p->next->prior = s;
		 p->next = s;
		 list.size++;
	     return true;
	 }
	 p1 = p1->next;
	}
	//没找到
	return false;
}

//判断链表是否为空
bool Empty(DCList &list)
{
	if(list.size==0)
	return  true;
	else
	return false;

}

//返回链表的长度
int GetLength(DCList &list)
{
	return list.size;
}

//返回链表中第i个节点的指针
DCNode * LocatePos(DCList &list,int i)
{
	if(i<=0&&i>(int)list.size ) return 0;//如果不存在第i个节点则返回一个0指针
	int n = 0;
	DCNode * p1 = list.head->next;
	while(p1!=list.head)
	{
	 n++;
	 if(n==i)//找到
	 {
		return p1;
	 }
	 p1 = p1->next;
	}
	return 0;
}

//在链表中查找第一个元素值与t相等的节点指针
DCNode * LocateElem(DCList &list,int t)
{
	if(list.head->next==list.head)//如果链表为空
	{
		return 0;
	}
	DCNode * p1 = list.head->next;
	while(p1!=list.head)
	{
		if(p1->data==t)//找到
	 {
		return p1;
	 }
	 p1 = p1->next;
	}
	return 0;
}

//在链表中查找第一个元素值与t满足compare函数关系的节点指针
DCNode * LocateElem(DCList &list,int t,bool (* compare)(int ,int))
{
	if(list.head->next==list.head)//如果链表为空
	{
		return 0;
	}
	DCNode * p1 = list.head->next;
	while(p1!=list.head)
	{
		if((*compare)(p1->data,t))//找到了
	 {
		return p1;
	 }
	 p1 = p1->next;
	}
	return 0;
}

//依次对链表中的每一个元素调用visit函数，一旦visit函数调用失败，则整个操作失败
bool ListTraverse(DCList &list,bool (*visit)(int &))
{

	DCNode * p1 = list.head->next;
	while(p1!=list.head)
	{
		if(!(*visit)(p1->data))//找到了
	 {
		return false;
	 }
	 p1 = p1->next;
	}
	return true;
}

//合并两个双向循环链表
DCList & MergeList(DCList &list1,DCList &list2)
{
	if(Empty(list1))
	{
		return list2;
	}
	if(Empty(list2))
	{
		return list1;
	}
	list1.head->prior->next = list2.head->next;
	list2.head->next->prior = list1.head->prior;
	list1.head->prior = list2.head->prior;
	list2.head->prior->next = list1.head;
	return list1;
}

//判断是否一个数为偶数
bool judge(int a,int b)
{
	if(a%b==0) return true;
	return false;
}

bool visit(int & t)
{
	t = t+1;
	return true;
}

int main()
{
//创建并初始化一个空的双向循环链表
	DCList myList;
	InitDCList(myList);

//在链表的尾端添加元素
	//现分配一个节点
	DCNode * s = MakeNode(1);
	Append(myList,s);
	s = MakeNode(3);
	Append(myList,s);
	s = MakeNode(5);
	Append(myList,s);
	s = MakeNode(7);
	Append(myList,s);

//遍历该链表，并输出该链表的元素个数
	DCNode * p1 = myList.head->next;
	cout<<"新建一个双向链表，并初始化元素值为1，3，5，7"<<endl;
	while(p1!=myList.head)
	{
		cout<<p1->data<<"  ";
	 p1 = p1->next;
	}
	cout<<endl;
	cout<<"链表的元素个数为:"<<GetLength(myList)<<endl;

//在链表的第一个数据节点之前插入两个元素

	s = MakeNode(9);
	InsFirst(myList,s);
	s = MakeNode(0);
	InsFirst(myList,s);
	 cout<<"在链表的第一个数据节点之前插入两个元素值为0，9的节点:"<<endl;
	 p1 = myList.head->next;
	while(p1!=myList.head)
	{
		cout<<p1->data<<"  ";
	 p1 = p1->next;
	}
	cout<<endl;

//删除链表中的第一个节点和尾节点 
	 cout<<"删除的第一个节点"<<endl;
	 if(DelFirst(myList,s))
	 {
		 cout<<"被删除的第一个节点数据为："<<s->data<<endl;
	 }
	  p1 = myList.head->next;
	while(p1!=myList.head)
	{
		cout<<p1->data<<"  ";
	 p1 = p1->next;
	}
	cout<<endl;
	//释放被删除的节点空间
	 FreeNode(s);
	 cout<<"删除的尾节点"<<endl;
	if( Remove(myList,s) )
	{
		 cout<<"被删除的尾节点数据为："<<s->data<<endl;
	}
	 p1 = myList.head->next;
	while(p1!=myList.head)
	{
		cout<<p1->data<<"  ";
	 p1 = p1->next;
	}
	cout<<endl;
	//释放被删除的节点空间
	FreeNode(s);

//在第二个节点之前插入元素
	 p1 = LocatePos(myList,2);
	 cout<<"第二个节点数据为："<<p1->data<<endl;
	 s = MakeNode(11);
	 InsBefore(myList,p1,s);
	 cout<<"在第二个节点之前插入一个元素值为11的新节点:"<<endl;
	 p1 = myList.head->next;
	 while(p1!=myList.head)
	 {
		cout<<p1->data<<"  ";
	 p1 = p1->next;
	 }
	 cout<<endl;

//在第二个节点之后插入元素
	 s = MakeNode(16);
	 p1 = LocatePos(myList,2);
	 InsAfter(myList,p1,s);
	 cout<<"再在第二个节点之后插入一个元素值为16的新节点:"<<endl;
	 p1 = myList.head->next;
	 while(p1!=myList.head)
	 {
		cout<<p1->data<<"  ";
	 p1 = p1->next;
	 }
	 cout<<endl;

//查找第一个元素值为4的倍数的节点
	 p1 = LocateElem(myList,4,judge);
	 cout<<"找到第一个元素值为4的倍数的节点数据为："<<p1->data<<endl;

//将链表中所有的元素值都增加1
	 ListTraverse(myList,visit);
	 cout<<"将链表中所有的元素值都增加1:"<<endl;
	 p1 = myList.head->next;
	 while(p1!=myList.head)
	 {
		cout<<p1->data<<"  ";
	 p1 = p1->next;
	 }
	 cout<<endl;

//新建一个元素值为1，3，9的链表
	 DCList myList2;
	InitDCList(myList2);

//在链表的尾端添加元素
	//现分配一个节点
	 s = MakeNode(1);
	Append(myList2,s);
	s = MakeNode(3);
	Append(myList2,s);
	s = MakeNode(9);
	Append(myList2,s);

//遍历该链表，并输出该链表的元素个数
	 cout<<"新建一个元素值为1，3，9的链表:"<<endl;
    p1 = myList2.head->next;
	while(p1!=myList2.head)
	{
		cout<<p1->data<<"  ";
	 p1 = p1->next;
	}
	cout<<endl;

//合并两个链表
	 myList = MergeList(myList,myList2);
	 cout<<"合并两个链表:"<<endl;
	 p1 = myList.head->next;
	 while(p1!=myList.head)
	 {
		cout<<p1->data<<"  ";
	    p1 = p1->next;
	 }
	 cout<<endl;
	 cout<<"最后清空myList链表！"<<endl;
	 clear(myList);
}

双向循环链表C++实现（完整版）,布布扣,bubuko.com

双向循环链表C++实现（完整版）