while (p!=NULL)  
        {
            rear->next = new Node<T>(p->data);   //創建結點鏈入rear結點之后
            p = p->next;
            rear = rear->next;                   //rear指向新的鏈尾結點
        }
    }
}

template <class T>
bool SinglyLinkedList<T>::equals(SinglyLinkedList<T> &list)   //比較兩條單鏈表是否相等
{
    Node<T> *p=this->head, *q=list.head;
    while (p!=NULL && q!=NULL && p->data==q->data)
    {
        p = p->next;
        q = q->next;
    }
    return (p==NULL && q==NULL);
}


//以下是第4章例題，遞歸算法
/*
template <class T>
SinglyLinkedList<T>::SinglyLinkedList(T value[], int n)    //構造由指定數組提供元素的單鏈表
{
    head = create(value,n,0);
}

template <class T>
Node<T>* SinglyLinkedList<T>::create(T value[], int n, int i)    //由指定數組構造單鏈表，遞歸算法
{
    Node<T> *p=NULL;
    if (i<n)
    {
        p = new Node<T>(value[i]);
        p->next = create(value, n, i+1);         //遞歸調用         
    }
    return p;
}

template <class T>
int SinglyLinkedList<T>::length()                //返回單鏈表長度
{
    return lengthFrom(head);
}

template <class T>
int SinglyLinkedList<T>::lengthFrom(Node<T>*p)   //返回從p結點開始的單鏈表長度，遞歸算法，私有函數
{
    if (p==NULL)
        return 0;
    return 1+lengthFrom(p->next);                //遞歸調用
}

template <class T>
void SinglyLinkedList<T>::print()                //輸出單鏈表
{
    cout<<"(";
    printFrom(head);
    cout<<")\n";
}

template <class T>
void SinglyLinkedList<T>::printFrom(Node<T>*p)   //輸出從p結點開始的單鏈表，遞歸算法，私有函數
{
    if (p!=NULL)
    {
        cout<<p->data;
        if (p->next!=NULL)
            cout<<", ";
        printFrom(p->next);                      //遞歸調用
    }
}
*/
//以下是第4章習題，遞歸算法
/*
template <class T>
SinglyLinkedList<T>::SinglyLinkedList(SinglyLinkedList<T> &list)   //以單鏈表list構造新的單鏈表，復制單鏈表
{
    this->head = copy(list.head);
}

template <class T>
Node<T>* SinglyLinkedList<T>::copy(Node<T> *p)   //復制單鏈表，遞歸算法，私有函數
{
    Node<T> *q=NULL;
    if (p!=NULL)
    {
        q = new Node<T>(p->data);
        q->next = copy(p->next); 
    }
    return q;
}
   
template <class T>
bool SinglyLinkedList<T>::equals(SinglyLinkedList<T> &list)   //比較兩條單鏈表是否相等
{
    return equals(this->head, list.head);
}

template <class T>
bool SinglyLinkedList<T>::equals(Node<T> *p, Node<T> *q)   //比較兩條單鏈表是否相等，遞歸算法，私有函數
{
    if (p==NULL && q==NULL)
        return true;
    if (p!=NULL && q!=NULL)
        return p->data==q->data && equals(p->next, q->next);
    return false;
}
*/





//以下第8章 8.2.1 順序查找，散列表中用

template <class T>
Node<T>* SinglyLinkedList<T>::search(T value, Node<T>* start)    //從單鏈表start結點開始順序查找指定元素
{                                                 //若查找成功返回結點，否則返回NULL
    if (isEmpty())
        return NULL;

    Node<T>* p=start;
    while (p!=NULL && p->data!=value)
        p = p->next;
    return p;
}

template <class T>
Node<T>* SinglyLinkedList<T>::search(T value)    //順序查找指定元素
{
    return search(value, head); 
}

template <class T>
bool SinglyLinkedList<T>::contain(T value)       //以查找結果判斷單鏈表是否包含指定元素
{
    return search(value)!=NULL;
}

template <class T>
bool SinglyLinkedList<T>::remove(T value)        //移去指定元素首次出現結點
{
    if (isEmpty())
        return false;
    
    Node<T> *p=head;
    if (head->data==value)
    {
        head = head->next;                       //頭刪除
        delete(p);
        return true;
    }
    
    Node<T>* front=head;
    p=front->next;
    while (p!=NULL && p->data!=value)            //中間/尾刪除
    {
        front = p;
        p=p->next;
    }
    if (p!=NULL)
    {
        front->next = p->next;
        delete(p);
        return true;
    }
    return false;
}

/*
//以下是第2章習題
    public boolean replace(Object obj, E value)//將元素值為obj的結點值替換為value，O(n)
    {                                            //若替換成功返回true，否則返回false
        if (obj==null || value==null)
            return false;

        Node<E> p=this.head;
        while (p!=null)
        {
            if (obj.equals(p.data))
            {
                p.data = value;
                return true;
            }
            p = p.next;
        }
        return false;
    }
 
    public boolean replaceAll(Object obj, E value) //將所有元素值為obj的結點值替換為value，O(n)
    {                                            //若替換成功返回true，否則返回false
        boolean done=false;
        if (obj!=null && value!=null)
        {
            Node<E> p=this.head;
            while (p!=null)
            {
                if (obj.equals(p.data))
                {
                    p.data = value;
                    done = true;
                }
                p = p.next;
            }
        }
        return done;
    }
    
    public boolean removeAll(Object obj)         //將所有元素值為obj的結點刪除
    {
        if (this.head==null || obj==null)
            return false;
        
        boolean done=false;
        while (this.head!=null && obj.equals(this.head.data))
        {
            this.head = this.head.next;          //頭刪除
            done = true;
        }
        Node<E> front=this.head, p=front.next;
        while(p!=null)
        {
            if (obj.equals(p.data))
            {
                front.next = p.next;             //刪除p結點
                p = front.next;
                done = true;
            }
            else
            {
                front = p;
                p = p.next;
            }
        }
        return done;
    }


/* 第2章    //可行，但效率低，時間復雜度是O(n*n)。
    public String toString()
    {
        String str="{";
        if (this.length()!=0)
        {
            for(int i=0; i<this.length()-1; i++)
                str += this.get(i).toString()+", ";
            str += this.get(this.length()-1).toString();
        }
        return str+"}";
    }
*/