数据结构【二】:循环链表和双向链表(C++)

循环链表

---

#include<iostream>
using namespace std;
template<class T>
struct LinkNode
{
	LinkNode *next=NULL;
	T data;
};
template<class T>
class List
 {
 	public:
 		List();//构造函数 
		List(const T& x);//构造函数 
		List( List<T>& L);//复制构造函数 
		~List(){makeEmpty();}; 
		void makeEmpty();//置空表 
		int getLength()const;//获取表长 
		LinkNode<T> *getHead()const{return head;};//获取头节点地址 
		LinkNode<T> *Search(T x);// 查询含有数据x节点的地址 失败返回NULL 
		LinkNode<T> *Locate(int i);// 查询第i个 数据的地址 失败返回NULL 
		bool getData(int i,T&x);//用x获取第i个数据
		bool setData(int i,T &x);//用x替换第i个位替上的数据
		bool Insert(int i,T &x);//在第i个元素后插入数据x
		bool Remove(int i,T &x);//删除第i个数据并用x返回
		bool isEmpyty()const; //判断表空
		bool isFull()const ;//判断表满
		void inputQianCha();//清空链表，输入结束标志，根据标志判断来输入数据  
		void inputHouCha();//清空链表，输入结束标志，根据标志判断来输入数据  
		void output();//输出 
		List<T>&operator=(List<T> &L); 
	protected:
		LinkNode<T> *head;
 };
template <class T>
List<T>::List()
{
	head=new LinkNode<T>;
	head->next=head;			//增加 
}
template <class T>
List<T>::List(const T& x)
{
	head=new LinkNode<T>(x);
	head->next=head; 			//增加 
}
template <class T>
List<T>::List(List<T>& L)
{
	LinkNode<T> *p1,*p2,*newNode,*Lhead;
	p1=L.getHead()->next;
	Lhead=L.getHead();			//增加 
	p2=head=new LinkNode<T>;  //p2=head=new LinkNode<T>;必须要有 new LinkNode<T>，因为此时head还没有构造出来。 
	while(p1!=Lhead)
	{
		newNode=new LinkNode<T>;
		newNode->data=p1->data;
		p2->next=newNode;
		p2=newNode;
		p1=p1->next;
	}
	p2->next=head; 				//增加 
}
template <class T>
void List<T>::makeEmpty()
{
	LinkNode<T> *p=head->next;
	while(head->next!=head)    //改变 
	{
		head->next=p->next;
		delete p;
		p=head->next;
	}
}
template <class T>
int List<T>::getLength()const
{
	LinkNode<T> *p=head->next;
	int num=0;
	while(p!=head)     //改变 
	 {
	 	num++;
	 	p=p->next;
	 }
	 return num;
}
template <class T>
LinkNode<T>* List<T>::Search(T x)
{
	LinkNode<T> *p=head->next;
	while(p!=head)				//修改 
	{
		if(p->data==x)
		return p;
		p=p->next;
	}	
	return NULL;            //修改为NULL，因为循环链表最后元素的下一个指向为head. 
	
} 
template <class T>
LinkNode<T>* List<T>::Locate(int i)
{
	if(i<=0) return NULL;
	int num=1; 		
	LinkNode<T> *p=head->next;
	while(i!=num&&p!=head)		//修改 
	{
		num++;
		p=p->next; 
	 } 
	 if(p==head) 
	 return NULL;		//添加为NULL，因为循环链表最后元素的下一个指向为head. 没找到必须返回NULL 
	 else
	 return p;
}
template <class T>
bool List<T>::getData(int i,T&x)
{
	LinkNode<T> *p=Locate(i);
	if(p==NULL)
	return false;
	else
	{
		x=p->data;
		return	true;		
	}
}
template <class T>
bool List<T>::setData(int i,T &x)
{
	LinkNode<T> *p=Locate(i);
	if(p==NULL)
	return false;
	else
	{
		p->data=x;
		return	true;		
	}
}
template <class T>
bool List<T>::Insert(int i,T &x)
{
	LinkNode<T> *p1=Locate(i),*p2;
		if(p1==NULL)
	return false;
	else
	{
		p2=new LinkNode<T>(x);
		if(p2==NULL)
		{
			cerr<<"储存分配错误"<<endl;
			exit(1); 
		}
		p2->next=p1->next;
		p1->next=p2; 
		return true;
	}
}
template <class T>
bool List<T>::Remove(int i,T &x)
{
	LinkNode<T> *p1=Locate(i-1),*p2;
	if(p1==NULL||p1->next==head)		//修改 
	return false;
	else
	{
		p2=p1->next;
		p1->next=p2->next;
		x=p2->data;
		delete p2;
		return true;
	} 
} 
template <class T>
bool List<T>::isEmpyty()const
{
	if(head->next==head)
	return true;
	else
	return
	false;
}
template <class T>
bool List<T>::isFull()const 
{
	return false;
}
template <class T>
void List<T>::inputQianCha()
{
	makeEmpty(); 
	T endTag,val;
	LinkNode<T> *newNode;
	cout<<"请输入结束标志";
	cin>>endTag;
	while(1)
	{
		cin>>val;
		if(val==endTag)
		break;
		newNode=new LinkNode<T>;
		newNode->data=val;
		if(newNode==NULL)
		{
			cerr<<"储存分配错误"<<endl;
			exit(1); 
		}
		newNode->next=head->next;
		head->next=newNode;
	}	 
}
template <class T>
void List<T>::inputHouCha()
{
	makeEmpty(); 
	T endTag,val;
	LinkNode<T> *newNode,*p=head;
	cout<<"请输入结束标志";
	cin>>endTag;
	while(1)
	{
		cin>>val;
		if(val==endTag)
		break;
		newNode=new LinkNode<T>;
		newNode->data=val;
		if(newNode==NULL)
		{
			cerr<<"储存分配错误"<<endl;
			exit(1); 
		}
		p->next=newNode;
		p=p->next;
	}
	p->next=head;	 //增加 
}
template <class T>
void List<T>::output()
{
	LinkNode<T> *p=head->next;
	while(p!=head)
	{
		cout<<p->data<<",";
		p=p->next;
	}
	cout<<endl;
}
template <class T>
List<T>& List<T>::operator=(List<T> &L)
{
	makeEmpty();						//先清空原有的数据 
	LinkNode<T> *p1,*p2,*newNode,*Lhead;
	p1=L.getHead()->next;
	Lhead=L.getHead();
	p2=head;
	while(p1!=Lhead)
	{
		newNode=new LinkNode<T>;
		newNode->data=p1->data;
		p2->next=newNode;
		p2=newNode;
		p1=p1->next;
	}
	p2->next=head; 
	return *this;	 
}
int main()
{
List<int> test1,test2;
	int a,len,i;
	test1.inputHouCha();
	test2.inputQianCha();
	test1.output();
	test2.output();
	test2=test1;
	test2.output();
}
/*
和单链表区别:
主要是构造的时候进行尾部连接头部: 
1、构造函数中 添加head->next=head;
2、复制构造函数和重载=号函数中增加Lhead=L.getHead();用while(p1!=Lhead)来判别循环表结束 最后增加p2->next=head; 为末尾添加head连接； 
3、 前插法构造不需要变化，后插法需要在最后增加p2->next=head; 为末尾添加head连接；  
其他函数有需要遍历的，判断结束条件改变为！+head即可: 
4、置空函数makeEmpty()获取表长函数getLength()查询数据函数Search(T x)获取第i个元素的地址函数Locate(int i)删除元素函数Remove(int i,T &x)判空函数isEmpyty() 
输出函数output()只需要变化判断结束条件head->next!=head
5、返回指针类若遍历后找不到，则返回NULL，因为循环链表最后元素的下一个指向为head而不是NULL 不能用最后的指向代替 。若不修改，会影响调用的判断 
6、 其他函数不需要改变 
*/

和单链表区别:
主要是构造的时候进行尾部连接头部:
1、构造函数中 添加head->next=head;
2、复制构造函数和重载=号函数中增加Lhead=L.getHead();用while(p1!=Lhead)来判别循环表结束 最后增加p2->next=head; 为末尾添加head连接；
3、 前插法构造不需要变化，后插法需要在最后增加p2->next=head; 为末尾添加head连接；
其他函数有需要遍历的，判断结束条件改变为！=head即可:
4、置空函数makeEmpty()获取表长函数getLength()查询数据函数Search(T x)获取第i个元素的地址函数Locate(int i)删除元素函数Remove(int i,T &x)判空函数isEmpyty()
输出函数output()只需要变化判断结束条件head->next!=head
5、 返回指针类若遍历后找不到，则返回NULL，因为循环链表最后元素的下一个指向为head而不是NULL 不能用最后的指向代替 。若不修改，会影响调用的判断

双向链表（带附加头结点的循环链表形式 ）

---

#include<iostream>
using namespace std;
template <class T>
struct LinkNode
{
	LinkNode *left=NULL,*next=NULL;
	T data;
} ;
template<class T>
class List
{
	public:
		List();//构造函数 
		List(const T& x);//构造函数 
		List( List<T>& L);//复制构造函数 
		~List(){makeEmpty();}; 
		void makeEmpty();//置空表 
		int getLength()const;//获取表长 
		LinkNode<T> *getHead()const{return head;};//获取头节点地址 
		LinkNode<T> *Search(T x);// 向后查询含有数据x节点的地址 失败返回NULL 
		LinkNode<T> *Locate(int i,int d);// 查询向右（向左）第i个 数据的地址,d！=0向右查找 d==0向左查找失败返回NULL 
		bool getData(int i,T&x,int d);//用x获取向右（向左）第i个数据， d！=0向右查找 d==0向左查找
		bool setData(int i,T &x,int d);//用x替换向右（向左）第i个数据， d！=0向右查找 d==0向左查找
		bool Insert(int i,T &x,int d);//在向右（向左）第i个元素后插入数据x d！=0向右查找 d==0向左查找
		bool Remove(int i,T &x,int d);//删除第向右（向左）i个数据并用x返回 d！=0向右查找 d==0向左查找
		bool isEmpyty()const; //判断表空 
		bool isFull()const ;//判断表满
		void inputQianCha();//输入结束标志，根据标志判断来输入数据  
		void inputHouCha();//输入结束标志，根据标志判断来输入数据  
		void output();//输出 
		List<T>&operator=(List<T> &L); 
	protected:
		LinkNode<T> *head;
};
template <class T>
List<T>::List()
{
	head=new LinkNode<T>;
	head->next=head;
	head->left=head;

}
template <class T>
List<T>::List(const T& x)
{
	head=new LinkNode<T>(x);
	head->right=head;
	head->left=head;
}
template <class T>
List<T>::List(List<T>& L)
{
	LinkNode<T> *p1,*newNode,*Lhead;
	p1=L.getHead()->next;
	Lhead=L.getHead();
	head=new LinkNode<T>;						//必须要有 new LinkNode<T>，因为此时head还没有构造出来。 
	head->left=head->next=head;					//加上这步构造一个头节点 
	while(p1!=Lhead)
	{
		newNode=new LinkNode<T>;
		newNode->data=p1->data;		
		newNode->next=head;					//后插法四步 ，由于是双向链表，可以直接通过head操作。 
		newNode->left=head->left;
		head->left->next=newNode;
		head->left=newNode;	
		p1=p1->next; 						//别忘了p1需要往后移动 
	}	
}
template <class T>
void List<T>::makeEmpty()			
{
	LinkNode<T> *p=head->next;
	while(head->next!=head)
	{
		head->next=p->next;
		delete p;
		p=head->next;
	}
	head->left=head;         //增添左指向为head 
}
template <class T>
void List<T>::inputQianCha()
{
	makeEmpty();
	T endTag,val;
	LinkNode<T> *newNode;
	cout<<"请输入结束标志";
	cin>>endTag;
	while(1)
	{
		cin>>val;
		if(val==endTag)
		break;
		newNode=new LinkNode<T>;
		newNode->data=val;
		if(newNode==NULL)
		{
			cerr<<"储存分配错误"<<endl;
			exit(1); 
		}							
			newNode->next=head->next;
			head->next=newNode;
			newNode->next->left=newNode;
			newNode->left=head;
	}
}
template <class T>
void List<T>::inputHouCha()
{
	makeEmpty(); 
	T endTag,val;
	LinkNode<T> *newNode,*p=head;
	cout<<"请输入结束标志";
	cin>>endTag;
	while(1)
	{
		cin>>val;
		if(val==endTag)
		break;
		newNode=new LinkNode<T>;
		newNode->data=val;
		if(newNode==NULL)
		{
			cerr<<"储存分配错误"<<endl;
			exit(1); 
		}
		newNode->next=head;
		newNode->left=head->left;
		head->left->next=newNode;
		head->left=newNode;		
	}
}
template <class T>
void List<T>::output()
{
	LinkNode<T> *p=head->next;
	while(p!=head)
	{
		cout<<p->data<<",";
		p=p->next;
	}
	cout<<endl;
}
template <class T>
int List<T>::getLength()const
{
	LinkNode<T> *p=head->next;
	int num=0;
	while(p!=head)
	 {
	 	num++;
	 	p=p->next;
	 }
	 return num;
}
template <class T>
LinkNode<T>* List<T>::Search(T x)
{
	LinkNode<T> *p=head->next;
	while(p!=head)
	{
		if(p->data==x)
		return p;
		p=p->next;
	}	
 	return NULL;  //修改为NULL，因为循环链表最后元素的下一个指向为head. 
}
template <class T>
LinkNode<T>* List<T>::Locate(int i,int d)
{
	if(i<=0) return NULL;
	int num=1; 
	LinkNode<T> *p;
	if(d!=0)					//增加判断语句是左查询还是右查询 
 	p=head->next;
	else
	p=head->left;
	while(i!=num&&p!=head)		//修改 
	{
		num++;
		if(d!=0)				//增加判断语句是左查询还是右查询 
		p=p->next;
		else
		p=p->left;
	 } 
	 if(p==head) 
	 return NULL;		//添加为NULL，因为循环链表最后元素的下一个指向为head. 没找到必须返回NULL 
	 else
	 return p;
}
template <class T>
bool List<T>::getData(int i,T&x,int d)
{
	LinkNode<T> *p=Locate(i,d);
	if(p==NULL)
	return false;
	else
	{
		x=p->data;
		return	true;		
	}
}
template <class T>
bool List<T>::setData(int i,T &x,int d)
{
	LinkNode<T> *p=Locate(i,d);
	if(p==NULL)
	return false;
	else
	{
		p->data=x;
		return	true;		
	}
}
template <class T>
bool List<T>::Insert(int i,T &x,int d)
{
	LinkNode<T> *p1,*newNode;
	if(i!=0)
	p1=Locate(i,d);
	else						//增加一种空表插入判断 
	p1=head;
	if(p1==NULL)
	return false;
	else
	{
		newNode=new LinkNode<T>;
		newNode->data=x;
		if(newNode==NULL)
		{
			cerr<<"储存分配错误"<<endl;
			exit(1); 
		}
		newNode->next=p1->next;
		p1->next=newNode;
		newNode->next->left=newNode;
		newNode->left=p1;
		return true;
	}
}
template <class T>
bool List<T>::Remove(int i,T &x,int d)
{
	LinkNode<T> *p1=Locate(i,d);	//由于是双向链表，所以不用再找第i-1个了 
	if(p1==NULL)						//修改  
	return false;
	else
	{
		p1->left->next=p1->next;
		p1->next->left=p1->left;
		delete p1;
		return true;
	} 
} 
template <class T>
bool List<T>::isEmpyty()const
{
	if(head->next==head)
	return true;
	else
	return
	false;
}
template <class T>
bool List<T>::isFull()const 
{
	return false;
}
template <class T>
List<T>& List<T>::operator=(List<T> &L)
{
	makeEmpty();					//清空链表 ，只剩下头节点 
	LinkNode<T> *p1,*newNode,*Lhead;
	p1=L.getHead()->next;
	Lhead=L.getHead();
	while(p1!=Lhead)
	{
		newNode=new LinkNode<T>;
		newNode->data=p1->data;		
		newNode->next=head;					//后插法四步 ，由于是双向链表，可以直接通过head操作。 
		newNode->left=head->left;
		head->left->next=newNode;
		head->left=newNode;	
		
		p1=p1->next; 						//别忘了p1需要往后移动 
	}
	return *this;	 
}
int main()
{
	List<int> test1;
	int a,len;
	int x;
	test1.inputHouCha();
	test1.output();
	test1.makeEmpty();
	List<int> test2(test1);
	test2.output(); 
} 
/*双向循环链表和单链表的区别:
1、结点中有前驱和后驱两个连接指针
2、构造函数中需要对前指针后指针赋头节点值	head->right=head->left=head;
3、前插法创建和后插法：均需要四步。注意分析。 
4、 置空函数需要添加左指向为head  
5、按顺序查找并返回地址进行判断添加。之后其他函数如获取数据等直接调用即可 
6、插入函数Insert需要多一种第0个元素后插入的条件，即空表插入的条件。 
7、删除函数Remove由于是双向链表，所以不用再找第i-1个了 判断也不需要考虑第i-1个是最后一个了。 
8、复制构造函数和重载=号，需要清空链表，构造使用后插法则4步即可 
 */

双向循环链表和单链表的区别:
1、结点中有前驱和后驱两个连接指针
2、构造函数中需要对前指针后指针赋头节点值 head->right=head->left=head;
3、前插法创建和后插法：均需要四步。注意分析。
4、 置空函数需要添加左指向为head
5、按顺序查找并返回地址进行判断添加。之后其他函数如获取数据等直接调用即可
6、插入函数Insert需要多一种第0个元素后插入的条件，即空表插入的条件。
7、删除函数Remove由于是双向链表，所以不用再找第i-1个了 判断也不需要考虑第i-1个是最后一个了。
8、复制构造函数和重载=号，需要清空链表，构造使用后插法则4步即可