//LinkList.cpp
#include "LinkList.h"
/*
*前置條件：單鏈表不存在
*輸    入：無
*功    能：構建一個單鏈表
*輸    出：無
*后置條件：構建一個單鏈表
*/
template <class T>
LinkList<T>:: LinkList( )
{
 first=new Node<T>; first->next=NULL;
}
/*
*前置條件：單鏈表不存在
*輸    入：順序表信息的數組形式a[],單鏈表長度n
*功    能：將數組a[]中元素建為長度為n的單鏈表
*輸    出：無
*后置條件：構建一個單鏈表
*/
 
template <class T>  
LinkList<T>:: LinkList(T a[ ], int n)
 {
    first=new Node<T>;   //生成頭結點
	Node<T> *r,*s;
     r=first;          //尾指針初始化
    for (int i=0; i<n; i++)
	{ 
      s=new Node<T>; s->data=a[i];  //為每個數組元素建立一個結點
      r->next=s; r=s;      //插入到終端結點之后
	}
    r->next=NULL;    //單鏈表建立完畢，將終端結點的指針域置空
 }


/*
*前置條件：無
*輸    入：無
*功    能：無
*輸    出：無
*后置條件：無
*/
template <class T>
LinkList<T>:: ~LinkList()
{
}
/*
*前置條件：單鏈表存在
*輸    入：查詢元素位置i
*功    能：按位查找位置為i的元素并輸出值
*輸    出：查詢元素的值
*后置條件：單鏈表不變
*/
template <class T>
T LinkList<T>::Get(int i) 
{   
  Node<T> *p; int j;
  p=first->next;  j=1;  //或p=first;  j=0;
  while (p && j<i)    
  {
    p=p->next;       //工作指針p后移
    j++;
  }
  if (!p) throw "位置";
  else return p->data;
}

/*
*前置條件：單鏈表存在
*輸    入：查詢元素值x
*功    能：按值查找值的元素并輸出位置
*輸    出：查詢元素的位置
*后置條件：單鏈表不變
*/
template <class T> 
int LinkList<T>::Locate(T x)
{
	Node<T> *p; int j;
	p=first->next; j=1;
	if(p&&p->next){
	  while(p->data!=x)
	  {
		 p=p->next;
	     j++;
	  }
	return j;
	}
	else throw "位置";
	
}

/*
*前置條件：單鏈表存在
*輸    入：插入元素x,插入位置i
*功    能：將元素x插入到單鏈表中位置i處
*輸    出：無
*后置條件：單鏈表插入新元素
*/
template <class T>  
void LinkList<T>::Insert(int i, T x)
{  
   Node<T> *p; int j;
   p=first ; j=0;    //工作指針p初始化
   while (p && j<i-1)
   {
     p=p->next;   //工作指針p后移
     j++;
   }
   if (!p) throw "位置";
    else { 
	  Node<T> *s;
      s=new Node<T>; 
	  s->data=x;  //向內存申請一個結點s，其數據域為x
      s->next=p->next;       //將結點s插入到結點p之后
      p->next=s;
	}
}

/*
*前置條件：單鏈表存在
*輸    入：無
*功    能：輸出單鏈表長度
*輸    出：單鏈表長度
*后置條件：單鏈表不變
*/
template <class T> 
int LinkList<T>::Length( )
{
  Node <T> *p = first->next;
  int i = 0;
  while(p)
  {
    p = p->next;
    i++;
  }
  return i;
}
/*
*前置條件：單鏈表存在
*輸    入：要刪除元素位置i
*功    能：刪除單鏈表中位置為i的元素
*輸    出：無
*后置條件：單鏈表刪除元素
*/
template <class T>  
T LinkList<T>::Delete(int i)
{ 
  Node<T> *p; int j;
  p=first ; j=0;  //工作指針p初始化
  while (p && j<i-1)  //查找第i-1個結點
  {
    p=p->next;
    j++;
  }
  if (!p || !p->next) throw "位置";  //結點p不存在或結點p的后繼結點不存在
    else {
		  Node<T> *q; int x;
          q=p->next; x=q->data;  //暫存被刪結點
          p->next=q->next;  //摘鏈
          delete q; 
          return x;
	}
}
/*
*前置條件：單鏈表存在
*輸    入：無
*功    能：單鏈表遍歷
*輸    出：輸出所有元素
*后置條件：單鏈表不變
*/
template <class T> 
void LinkList<T>::PrintList( )
{
	Node<T> *p;
	p=first->next;
	while (p)
	{
	  cout<<p->data<<endl;
	  p=p->next;
	}
	
}