立此存照(8)[C++]循环链表类模板和双向链表类模板

//1.循环链表
#include<iostream>
using namespace std;

//每个类模板或函数模板对应一个template关键字
template <typename T>
class Node{
	public:
		T val;
		Node* next;
		Node(T val){
			this->val = val;
			this->next = NULL;
		}
		Node(T val, Node* next){
			this->val = val;
			this->next = next;			
		}
};

//循环链表
template <typename T>
class CLinkedList{
	private:
		Node<T> *head;
		int len;
	public:
		CLinkedList(){
			head = NULL;
			len = 0;
		}
		~CLinkedList(){
			if(head != NULL){
				Node<T> *p1 = head->next;
				Node<T> *p2 = NULL;//p2保存即将释放的p1指向的下一个节点
				head->next = NULL;//将循环链表由第0，第1个元素处断开
				for(;p1 != NULL;p1 = p2){
					p2 = p1->next;
					delete p1;
				}
			}
		}
		int length(){
			return this->len;
		}
		//在循环链表的第pos个位置(pos从0开始)处插入节点
		bool insert(Node<T> *p, int pos){
			if(pos < 0 || pos > len){
				return false;
			}else {
				if(pos == 0){
					if(len == 0){
						p->next = p;//只有一个节点时,节点指向它自己
					}else{
						p->next = head;
					}
					head = p;
				}else{
					Node<T> *tmp = head;
					for(int i=1;i < pos;i++){
						tmp = tmp->next;
					}
					p->next = tmp->next;
					tmp->next = p;
				}
				len++;
				return true;
			}
		}
		//返回被删除的元素
		Node<T>* remove(int pos){
			if(pos < 0 || pos >= len){
				return NULL;
			}else{
				Node<T> *p = NULL;
				if(pos == 0){//考虑删除首元素的情况
					p = head;	
					head = head->next;
				}else{
					Node<T> *tmp = head;
					for(int i=1;i < pos;i++){
						tmp = tmp->next;
					}
					p = tmp->next;
					tmp->next = tmp->next->next;
				}
				len--;
				return p;//返回被删除的元素
			}
		}
		//定位某个元素在循环链表中的首次出现的位置
		int getPos(Node<T> *p){
			if(len <= 0)
				return -1;
			else{
				Node<T>* pt = head;
				for(int i=0;i < len;i++){
					if(pt->val == p->val)
						return i;
					pt = pt->next;
				}
			}
			return -1;//未找到该元素
		}
		//打印输出整个链表中元素的值等操作
		void prtMe(){
			Node<T> *p = head;
			cout<<"CList:";
			for(int i=0;i < len;i++){
				cout<<p->val;
				p = p->next;
				cout<<(i == len-1 ? "\n" : " ");
			}
		}
};

int main()
{	

	CLinkedList<int> CList;
	for(int i=0;i < 10;i++){
		Node<int> *p = new Node<int>(i);//动态创建链表
		CList.insert(p, CList.length());
	}
	CList.prtMe();
	//插入元素
	CList.insert(new Node<int>(111), 5);
	CList.prtMe();
	
	//删除元素
	CList.remove(0);
	CList.prtMe();

	//获取元素索引
	Node<int> n(6);//
	cout<<"len="<<CList.length()<<endl<<"getPos()="<<CList.getPos(&n)<<endl;//

return (0);
} 



//2.双向链表
#include<iostream>
using namespace std;

//每个类模板或函数模板对应一个template关键字
template <typename T>
class Node{
	public:
		T val;
		Node* last;
		Node* next;
		Node(T val){
			this->val = val;
			this->last = NULL;
			this->next = NULL;
		}
		Node(T val, Node* last, Node* next){
			this->val = val;
			this->last = last;
			this->next = next;
		}
};

//双向链表
template<typename T>
class DLinkedList{
	private:
		Node<T> *head;
		Node<T> *tail;
		int len;
	public:
		DLinkedList(){
			this->head = NULL;
			this->tail = NULL;
			len = 0;
		}
		~DLinkedList(){
			Node<T> *p1 = head;
			Node<T> *p2 = NULL;
			for(;p1 != NULL;p1 = p2){
				p2 = p1->next;
				delete p1;
			}
		}
		int length(){
			return this->len;
		}
		//在循环链表的第pos个位置(pos从0开始)处插入节点
		bool insert(Node<T> *p, int pos){
			if(pos < 0 || pos > len){
				return false;
			}else {
				if(pos == 0){//插入位置为0
					if(len == 0){
						p->last = NULL;
						p->next = NULL;
						head = tail = p;
					}else{
						p->next = head;
						head->last = p;
						head = p;
						p->last = NULL;
					}
				}else if(pos == len){//插入位置为len处(最后一个元素后面)
					p->last = tail;
					p->next = NULL;
					tail->next = p;
					tail = p;
				}else{//插入到其他位置
					Node<T> *pt = head;
					for(int i=1;i < pos;i++){
						pt = pt->next;
					}
					p->last = pt;
					p->next = pt->next;
					pt->next->last = p;
					pt->next = p;
				}
				len++;
				return true;
			}
		}
		//返回被删除的元素
		Node<T>* remove(int pos){
			if(pos < 0 || pos >= len){
				return NULL;
			}else{
				Node<T> *p = NULL;
				if(len == 1){//仅有一个元素
					p = head;
					tail = head = NULL;
					return p;
				}

				if(pos == 0){//考虑删除首元素的情况
					p = head;
					head = head->next;
				}else if(pos == len-1){//考虑删除最后一个元素的情况
					p = tail;
					tail = p->last;
					p->last->next = NULL;
					p->last = NULL;
				}else{
					Node<T> *tmp = head;
					for(int i=1;i < pos;i++){
						tmp = tmp->next;
					}
					p = tmp->next;
					tmp->next = p->next;
					p->next->last = tmp;
					p->next = p->last = NULL;
				}
				len--;
				return p;//返回被删除的元素
			}
		}
		//定位某个元素在循环链表中的首次出现的位置
		int getPos(Node<T> *p){
			if(len <= 0)
				return -1;
			else{
				Node<T>* pt = head;
				for(int i=0;i < len;i++){
					if(pt->val == p->val)
						return i;
					pt = pt->next;
				}
			}
			return -1;//未找到该元素
		}		
		//打印输出整个链表中元素的值等操作
		void prtMe(){
			Node<T> *p = head;
			cout<<"DList:";
			for(int i=0;i < len;i++){
				cout<<p->val;
				p = p->next;
				cout<<(i == len-1 ? "\n" : " ");
			}
		}

};


int main()
{	

	DLinkedList<int> DList;
	for(int i=0;i < 10;i++){
		Node<int> *p = new Node<int>(i);//动态创建链表节点
		DList.insert(p, DList.length());
	}
	DList.prtMe();
	//插入元素
	DList.insert(new Node<int>(111), 5);
	DList.insert(new Node<int>(1000), DList.length());
	DList.prtMe();
	
	//删除元素
	DList.remove(0);
	DList.remove(DList.length()-1);
	DList.prtMe();

	//获取元素索引
	Node<int> n(6);//
	cout<<"len="<<DList.length()<<endl<<"getPos()="<<DList.getPos(&n)<<endl;//

return (0);
}