不含头结点的单链表

template <class T>
class Node
{
public:
	T data;
	Node<T> *next;
	Node()
	{
		this->next = NULL;
	}
			
	Node(T data,Node<T>*next = NULL)
	{
		this->data = data;
		this->next = next;
	}
};

#include <iostream>
#include "Node.h"
using namespace std;
template <class T>
class SinglyLinkedList
{
public:
	Node<T> *head;

	SinglyLinkedList();                   //构造空单链表
	SinglyLinkedList(T valur[],int n);    //构造有指定数组提供元素的单链表
	void outPut();                        //声明输出链表函数
	~SinglyLinkedList();
	bool isEmpty();
	int length();
	Node<T>*getNode(int i);
	T get(int i);
	bool set(int i,T x);
	void insert(int i,T x);
	bool remove(int i);
	void clear();
	void concat(SinglyLinkedList<T>&list);
//	void sort();
};


//空构造函数的定义
template <class T>
SinglyLinkedList<T>::SinglyLinkedList()
{
	this->head = NULL;
}


//构造函数的定义
template <class T>
SinglyLinkedList<T>::SinglyLinkedList(T value[],int n)
{
	head = NULL;
	if(n>0)
	{
		head = new Node<T>(value[0]);
		Node<T> *temp = head;
		int i = 1;
		while(i<n)
		{
			temp->next = new Node<T>(value[i++]);
			temp = temp->next;
		}
	}

}


//定义输出链表函数
template <class T>
void SinglyLinkedList<T>::outPut()
{
	Node<T> *temp = head;
	while(temp != NULL)
	{
		cout<<setw(5)<<temp->data;
		temp = temp->next;
	}
	cout<<endl;
}

template <class T>
bool SinglyLinkedList<T>::isEmpty()
{
	return head == NULL;
}

template <class T>
int SinglyLinkedList<T>::length()
{
	Node<T> *temp = head;
	int Number = 0;
	while(temp != NULL)
	{
		Number++;
		temp = temp->next;
	}
	return Number;
}


//函数有问题带改进，应该在加入判断i的值的程序
template <class T>
Node<T>* SinglyLinkedList<T>::getNode(int i)
{
	if(i < 0)
		return NULL;
	Node<T> *temp = head;
	int Number = 1;
	while(Number != i)
	{
		Number++;
		temp = temp->next;
	}

	return temp;
}

template <class T>
T SinglyLinkedList<T>::get(int i)
{
	Node<T> *temp = getNode(i);
	try{
	if(temp != NULL)
		return temp->data;
	else throw "对不起得到的数字不是所希望的！";
	}
	catch(const char str[])
	{
		cout<<endl<<str<<endl;
	}
}

template <class T>
bool SinglyLinkedList<T>::set(int i,T x)
{
	Node<T> *temp = getNode(i);
	if(temp != NULL)
	{
		temp->data = x;
		return true;
	}
	else return false;
}


template <class T>
void SinglyLinkedList<T>::insert(int i,T x)
{
	Node<T> *temp = NULL;
	if(head == NULL)
	{
		temp = new Node<T>(x,head);
		head = temp;
	}
	else
	{
		Node<T> *temp_1 = head;
		int Number = 0;
		while(temp_1->next !=NULL&&Number < i-1)
		{
			Number++;
			temp_1 = temp_1->next;
		}
		temp = new Node<T>(x,temp_1->next);
		temp_1->next = temp;
	}
	//return temp;
}

template <class T>
bool SinglyLinkedList<T>::remove(int i)
{
	if(i <=0||i>length())
	{
		cout<<"i的值输入的有误，请检查后再重新输入"<<endl;
			return false;
	}
	else 
	{
		Node<T> *temp = getNode(i -1);
		Node<T> *ptr  = temp->next;
		temp->next = ptr->next;
		delete ptr;
		return true;
	}
}

template <class T>
void SinglyLinkedList<T>::clear()
{
	head = NULL;
}

template <class T>
SinglyLinkedList<T>::~SinglyLinkedList()
{
	clear();
}

template <class T>
void SinglyLinkedList<T>::concat(SinglyLinkedList<T> &list)
{
	if(head == NULL)
		head =list.head;
	else
	{
		Node<T> *temp = head;
		while(temp->next != NULL)
			temp = temp->next;
		temp->next = list.head;
	}
}