这里主要是为了复习线性结构的重点：链表

收获：

1.复习了头插法、尾插法、节点的插入删除查询

2.复习了只带有头节点的向某节点前插入元素的算法

#include <iostream>
using namespace std;

template<typename T>
struct Node{
	T data;
	Node<T> *Next;
};

template<typename T>
class LinkList{
	private:
		Node<T> *head;
		int size_;
	public:
		LinkList(){
			head = new Node<T>;
			head->Next = NULL;
			size_ = 0;
		}
		
		void CreateList_1(T a[], int n){
			head->Next = NULL;
			for(int i = 0;i < n;i++){
				Node<T> *pNode = new Node<T>;
				pNode->data = a[i];
				pNode->Next = head->Next;
				head->Next = pNode;
				size_++;
			}
		}
		
		void CreateList_1_2(T a[], int n){
			head->Next = NULL;
			Node<T> *pCur = head;
			for(int i = 0;i < n;i++){
				Node<T> *pNode = new Node<T>;
				pNode->data = a[i];
				pCur->Next = pNode;
				pCur = pCur->Next;
				pNode->Next = NULL;
				size_++;
			}
		}
		
		void Display(){
			Node<T> *pNode = head->Next;
			while(pNode != NULL){
				cout << pNode->data << ' ';
				pNode = pNode->Next;
			}
		}
		
		void Destory_all(){
			Node<T> *pNode = head->Next;
			head->Next = NULL;
			while(pNode != NULL){
				Node<T> *pCur = pNode;
				pNode = pNode->Next;
				delete pCur;
			}
			size_ = 0;
		}
		
		int Find(T x){
			Node<T> *pNode = head->Next;
			int pos = -1, cnt = 1;
			while(pNode){
				if(pNode->data == x)
					return cnt;
				pNode = pNode->Next;
				cnt++;
			}
			return pos;
		}
		
		bool Destory_one_1(T x){
			Node<T> *pNode = head, *pCur = head->Next;
			bool book = false;
			while(!book && pCur){
				if(pCur->data == x){
					pNode->Next = pCur->Next;
					delete pCur;
					book = true;
					size_--;
				}
				else{
					pNode = pCur;
					pCur = pCur->Next;
				}
			}
			if(book)
				return true;
			else
				return false;
		}
		
		bool Destory_one_2(int p){
			if(p > size_)
				return false;
			int pos = 0;
			Node<T> *pNode = head, *pCur = head->Next;
			while(pos < p - 1 && pNode != NULL){
				pNode = pCur;
				pCur = pCur->Next;
				pos++;
			}
			pNode->Next = pCur->Next;
			delete pCur;
			size_--;
			return true;
		}
		
		bool Insert_1(int p, T e){
			if(p > size_)
				return false;
			int pos = 0;
			Node<T> *pNode = new Node<T>, *pCur = head;
			pNode->data = e, pNode->Next = NULL;
			while(pos < p - 1){
				pCur = pCur->Next;
				pos++;
			}
			pNode->Next = pCur->Next;
			pCur->Next = pNode;
			size_++;
			return true;
		}
		
		bool Insert_2_after(T pre, T e){
			Node<T> *pNode = new Node<T>, *pCur = head->Next;
			pNode->data = e, pNode->Next = NULL;
			while(pCur){
				if(pCur->data == pre){
					pNode->Next = pCur->Next;
					pCur->Next = pNode;
					size_++;
					return true;
				}
				else
					pCur = pCur->Next;
			}
			return false;
		}
		
		bool Insert_3_before(T after, T e){
			Node<T> *pNode = new Node<T>, *pCur = head->Next;
			pNode->data = e, pNode->Next = NULL;
			while(pCur){
				if(pCur->data == after){
					pNode->Next = pCur->Next;
					pCur->Next = pNode;
					T temp = pCur->data;
					pCur->data = pNode->data;
					pNode->data = temp;
					size_++;
					return true;
				}
				else
					pCur = pCur->Next;
			}
			return false;
		}
		
		int Capasity(){
			return size_;
		}
		
		bool Empty(){
			return 0 == size_;
		}
};

int main(){
	int n;
	char a[50] = {'\0'};
	LinkList<char> LS;
	cin >> n;
	for(int i = 0;i < n;i++)	cin >> a[i];
	//测试头插法 
	LS.CreateList_1(a, n);
	LS.Display();
	cout << endl;
	LS.Destory_all();
	//测试尾插法 
	LS.CreateList_1_2(a, n);
	LS.Display();
	cout << endl;
	//测试链表规模
	cout << LS.Capasity() << endl; 
	char x;
	cin >> x;
	//测试删除一个存在的元素 
	if(LS.Destory_one_1(x)){
		cout << "Success! I will show the LinkList！" << endl;
		LS.Display();
		cout << endl;
	}
	else
		cout << "Failture!" << endl;
	//测试删除后的链表规模
	cout << LS.Capasity() << endl;
	
	cin >> x;
//	cout << LS.Destory_one_1(x) << endl;
	//测试删除一个不存在的元素 
	if(LS.Destory_one_1(x)){
		cout << "Success! I will show the LinkList！" << endl;
		LS.Display();
		cout << endl;
	}
	else
		cout << "Failture!" << endl;
	//测试删除后的链表规模
	cout << LS.Capasity() << endl;
	
	cin >> x;
	//测试查找一个存在的元素 
	cout << LS.Find(x) << endl;
	cin >> x;
	//测试查找一个不存在的元素 
	cout << LS.Find(x) << endl;
	int p;
	cin >> p;
	//测试删除某个位置上的元素 
	if(LS.Destory_one_2(p)){
		cout << "Success! I will show the LinkList！" << endl;
		LS.Display();
		cout << endl;
	}
	else
		cout << "Failture!" << endl;
	//测试删除后的链表规模
	cout << LS.Capasity() << endl;
	
	//测试在确定位置上成功插入某元素
	cin >> p;
	char e;
	cin >> e;
	if(LS.Insert_1(p, e)) {
		cout << "Success! I will show the LinkList！" << endl;
		LS.Display();
		cout << endl;
	}
	else
		cout << "Failture!" << endl;
	
	//测试在确定位置上插入某元素失败 
	cin >> p;
	cin >> e;
	if(LS.Insert_1(p, e)) {
		cout << "Success! I will show the LinkList！" << endl;
		LS.Display();
		cout << endl;
	}
	else
		cout << "Failture!" << endl;
	
	//测试在某元素之后插入元素成功
	char after;
	cin >> after >> e;
	if(LS.Insert_2_after(after, e)){
		cout << "Success! I will show the LinkList！" << endl;
		LS.Display();
		cout << endl;
	}
	else
		cout << "Failture!" << endl;
	
	//测试在某元素之后插入元素失败 
	cin >> after >> e;
	if(LS.Insert_2_after(after, e)){
		cout << "Success! I will show the LinkList！" << endl;
		LS.Display();
		cout << endl;
	}
	else
		cout << "Failture!" << endl;
	
	// 测试在某元素之前插入元素 
	char pre;
	cin >> pre >> e;
	if(LS.Insert_3_before(pre, e)){
		cout << "Success! I will show the LinkList！" << endl;
		LS.Display();
		cout << endl;
	} 
	else
		cout << "Failture!" << endl;
	return 0;
}```