template <class T> class LinList;			//前視定義,否則友元無法定義
template <class T>							//模板類型為T
class ListNode
{
	friend class LinList<T>;					//定義類LinList<T>為友元
	friend void LinListSort(LinList<T> &L);
private:
	ListNode<T> *next;	    				//指向下一結點的指針
	T data;								//定義為公有成員方便使用
public:
	//構造函數1,用于構造頭結點
	ListNode(ListNode<T> *ptrNext = NULL)
		{next = ptrNext;}

	//構造函數2,用于構造其他結點
	ListNode(const T& item, ListNode<T> *ptrNext = NULL)
		{data = item;	next = ptrNext;}

	~ListNode(void){}				//析構函數
};

//單鏈表類的定義
template <class T>
class LinList
{
	friend void LinListSort(LinList<T> &L);
private:
	ListNode<T> *head;				//頭指針
	int size;							//當前的數據元素個數

	ListNode<T> *Index(int i);			//定位
public:
	LinList(void);						//構造函數
	~LinList(void);					//析構函數

	int ListSize(void) const;				//取當前數據元素個數
	void Insert(const T& item, int i);		//前插
	T Delete(int i);						//刪除
	T GetData(int i);					//取元素

	void OrderInsert(T x);
	void Converse(void);
};
 
//單鏈表類的實現  
template <class T> 
LinList<T>::LinList(void)					//構造函數
{
	head = new ListNode<T>();			//頭指針指向頭結點
	size = 0;							//size的初值為0
}

template <class T>
LinList<T>::~LinList(void)				//析構函數
{ 
	ListNode<T> *p, *q;
	p = head;						//p指向第一個結點
	while(p != NULL)				//循環釋放結點空間直至初始化狀態
	{
   		q = p;
		p = p->next;
		delete q;
	}
	size = 0;							//結點個數置為初始化值0
	head = NULL;
}

template <class	T>	
ListNode<T> *LinList<T>::Index(int i)		//定位
//返回指向第i個數據元素結點的指針
//參數i的取值范圍為：-1≤i≤size-1；i=-1時返回頭指針
{
	if(i < -1 || i > size-1)
	{
		cout << "參數i越界出錯！" << endl;
		exit(0);
	}

	if(i == -1) return head;					//i為-1時返回頭指針head
	ListNode<T> *p = head->next;			//p指向第一個數據元素結點
	int j = 0;								//從0開始計數
	while(p != NULL && j < i)				//尋找第i個結點
	{
		p = p->next;
		j++;
	}
	return p;								//返回第i個結點的指針
}

template <class T>
int LinList<T>::ListSize(void) const			//取當前數據元素個數并返回
{
	return size;
}

template <class T>
void LinList<T>::Insert(const T& item, int i)				//插入
//在第i個結點后插入一個元素值為item的新結點
//參數i的取值范圍為：0≤i≤size
{
	if(i < 0 || i > size)
	{
		cout << "參數i越界出錯！"  << endl;
		exit(0);
	}

	ListNode<T> *p = Index(i - 1);			//p為指向第i-1個結點的指針

	//構造新結點p，p的data域值為item，next域值為 p->next
	ListNode<T> *q = new ListNode<T>(item, p->next);

	p->next = q;								//新結點插入第i個結點前
	size++;									//元素個數加1
}

template <class T>
T LinList<T>::Delete(int i)				//刪除
//刪除第i個數據元素并返回。參數i的取值范圍為：0≤i≤size-1
{
	if(size == 0) 
	{
		cout << "鏈表已空無元素可刪！" << endl;
		exit(0);
	}

	if(i < 0 || i > size-1)
	{
		cout << "參數i越界出錯！" << endl;
		exit(0);
	}

	
	ListNode<T> *s, *p = Index(i - 1);		//p為指向第i-1個結點指針

	s = p->next;								//s指向第i個結點
	p->next = p->next->next;					//第i個結點脫鏈
	T x = s->data;
	delete s;								//釋放第i個結點空間
	size--;									//結點個數減1
	return x;								//返回第i個結點的data域值
}

template <class T>
T LinList<T>::GetData(int i)				//取數據元素
//取第i個數據元素并返回。參數i的取值范圍為：0≤i≤size-1
{
	if(i < 0 || i > size-1)
	{
		cout << "參數i越界出錯！" << endl;
		exit(0);
	}

	ListNode<T> *p = Index(i);				//p指向第i個結點
	return p->data;
}

template <class T>
void LinList<T>::OrderInsert(T x)
//數據元素x有序插入
{
	ListNode<T> *curr, *pre;
	//循環初始化
	curr = head->next;					//curr指向第一個數據元素結點
	pre = head;							//pre指向頭結點

	//定位插入位置
	while(curr != NULL && curr->data <= x)
	{
		pre = curr;
		curr = curr->next;
	}

	//申請一個結點并賦值
	ListNode<T> *q = new ListNode<T>(x, pre->next);

	pre->next = q;					//把新結點插入pre所指結點后
	size++;
}

template <class T>
void LinList<T>::Converse(void)
{
	ListNode<T> *p, *q;

	p = head->next;
	head->next = NULL;
	while(p != NULL)
	{
		q = p;
		p = p->next;
		q->next = head->next;
		head->next = q;;
	}
}