利用C++模板封装链表

利用C++实现链表模板类

#include <iostream>
#include <stdlib.h>

using namespace std;

template <typename T>
class Node//定义结点类
{
public:
	Node(T data):data(data)
	{
		next = NULL;
	}

	T data;
	Node* next;
};

template <typename T>
class List //定义链表类
{
	Node<T>* head;
	Node<T>* tail;
public:
	List(void)//构造函数
	{
		head = NULL;
		tail = NULL;
	}

	bool empty(void)//判断链表是否为空
	{
		return NULL == head;
	}

	size_t size(void)//获取链表长度
	{
		size_t n = 0;
		for(Node<T>* node=head;node;node=node->next)
		{
			n++;
		}
		return n;
	}

	bool head_del_list(void)//头删除
	{
		if(empty()) return false;
		Node<T>* temp = head;
		head = head->next;
		delete temp;
		return true;
	}
	
	bool tail_del_list(void)//尾删除
	{
		if(empty()) return false;
		
		if(1 == size())
		{
			Node<T>* temp = head;
			delete temp;
			head = NULL;
			tail = NULL;
			return true;
		}
		Node<T>* node=head;
		for(;node->next->next!=NULL;node=node->next);
		node->next = NULL;
		tail = node;
		delete node->next;
		return true;
	}

	bool delete_index_list(int index)//指定位置下标删除
	{
		if(0 > index||index >=size()) return false;
		if(0 == index)
		{
			return head_del_list();
		}
		if(size()-1 == index)
		{
			return tail_del_list();
		}
		Node<T>* node = head;
		for(int i=0;i<index-1;i++)
		{
			node = node->next;
		}
		Node<T>* temp = node->next;
		node->next = node->next->next;
		delete temp;
		return true;
	}

	bool delete_val_list(const T& val)//按值删除
	{
		if(empty()) return false;
		if(head->data == val) return head_del_list();
		if(tail->data == val) return tail_del_list();
		Node<T>* node = NULL;
		for(node=head;NULL!=node;node=node->next)
		{
			if(node->next->data == val)
			{
				Node<T>* temp = node->next;
				node->next = node->next->next;
				delete temp;
				return true;
			}
		}
		return false;
	}

	void head_add_list(const T& data)//头添加
	{
		Node<T>* node = new Node<T>(data);
		if(empty())
		{
			head = node;
			tail = node;
			return ;
		}
		if(head == tail)
		{
			head = node;
			node->next = tail;
			return ;
		}
		node->next = head;
		head = node;
	}

	void tail_add_list(const T& data)//尾添加
	{
		Node<T>* temp = new Node<T>(data);
		if(empty())
		{
			head = temp;
			tail = temp;
			return;
		}
		
		tail->next = temp;
		tail = temp;
	}

	bool insert_list(int index,const T& data)//指定位置添加
	{
		if(0 > index||index >=size()) return false;
		if(0 == index)
		{
			head_add_list(data);
			return true;
		}
		Node<T>* temp = new Node<T>(data);
		Node<T>* node = head;
		for(int i=0;i<index-1;i++)
		{
			node = node->next;
		}
		temp->next = node->next;
		node->next = temp;
		return true;
	}


	void sort_list(void)//排序
	{
		for(Node<T>* node1=head;NULL!=node1->next;node1=node1->next)
		{
			for(Node<T>* node2=node1->next;NULL!=node2;node2=node2->next)
			{
				if(node1->data > node2->data)
				{
					T temp = node1->data;
					node1->data = node2->data;
					node2->data = temp;
				}
			}
		}

	}

	void show_list(void)//遍历
	{
		for(Node<T>* node=head;node;node=node->next)
		{
			cout << node->data << ' ';
		}
		cout << endl;
	}
};

int main()
{
	List<int> s;
	for(int i=0;i<10;i++)
	{
		s.tail_add_list(i);
		//s.tail_add_list(rand()%100);
	}
	cout << "尾添加后：";
	s.show_list();
	s.insert_list(5,186);
	cout << "在下标为5的位置插入数字186后：";
	s.show_list();
	cout << endl;
	s.sort_list();
	cout << "按从小到大排序后：";
	s.show_list();
	cout << endl;
	s.delete_index_list(3);
	cout << "删除原来下标为3的位置数字后：";
	s.show_list();
	cout << endl;
	s.delete_val_list(7);
	cout << "删除值为7的值后：";
	s.show_list();	
}

以下为程序执行后的结果：