立此存照(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);
}