//單鏈表類
#include <iostream.h>
#include "Node.h"                                //單鏈表結點類

template <class T>
class SinglyLinkedList                           //單鏈表類
{
  public:
    Node<T> *head;                               //單鏈表的頭指針

    SinglyLinkedList();                          //構造空單鏈表
    SinglyLinkedList(T value[], int n);          //構造由指定數組提供元素的單鏈表
    ~SinglyLinkedList();                         //析構
 
    bool isEmpty();                              //判斷單鏈表是否為空
    int length();                                //返回單鏈表長度 
    Node<T>* getNode(int i);                     //返回第i（i≥0）個結點指針
    T get(int i);                                //返回第i個元素
    bool set(int i, T x);                        //設置第i個元素為x
    friend ostream& operator<<(ostream& out, SinglyLinkedList<T> &list);    //輸出單鏈表所有元素
    Node<T>* insert(int i, T x);                 //插入x作為第i個結點，返回新插入結點指針
    bool remove(int i, T& old);                  //刪除第i個結點，被刪除元素存放在old變量中
    void clear();                                //清空單鏈表

    void insert(T x);                            //在單鏈表最后插入x元素
    void concat(SinglyLinkedList<T> &list);      //將list鏈接在當前單鏈表之后

    //第2章習題
    SinglyLinkedList(SinglyLinkedList<T> &list); //以單鏈表list構造新的單鏈表，復制單鏈表
    bool equals(SinglyLinkedList<T> &list);      //比較兩條單鏈表是否相等

    //第8章 8.2.1 順序查找
    Node<T>* search(T value, Node<T>* start);    //從單鏈表start結點開始順序查找指定元素
    Node<T>* search(T value);                    //順序查找指定元素
    bool contain(T value);                       //判斷單鏈表是否包含指定元素
    bool remove(T value);                        //移去指定元素首次出現結點

  private:
    int lengthFrom(Node<T>*p);                   //返回從p結點開始的單鏈表長度
    void printFrom(Node<T>*p);                   //輸出從p結點開始的單鏈表
    Node<T>* create(T value[], int n, int i);    //由指定數組構造單鏈表
    Node<T>* copy(Node<T> *p);                   //復制單鏈表
    bool equals(Node<T> *p, Node<T> *q);         //比較兩條單鏈表是否相等

};

template <class T>
SinglyLinkedList<T>::SinglyLinkedList()          //構造空單鏈表
{
    this->head = NULL;
}

template <class T>
SinglyLinkedList<T>::SinglyLinkedList(T value[], int n)    //構造由指定數組提供元素的單鏈表
{
    head = NULL;                                           //n=0時，構造空鏈表
    if (n>0)                                               //構造非空鏈表    
    {
        head = new Node<T>(value[0]);
        Node<T> *rear = head;                              //rear指向單鏈表最后一個結點
        int i=1;
        while (i<n)  
        {
            rear->next = new Node<T>(value[i++]);          //創建結點鏈入rear結點之后
            rear = rear->next;                             //rear指向新的鏈尾結點
        }
    }
}

template <class T>
SinglyLinkedList<T>::~SinglyLinkedList()         //析構函數
{
//    cout<<"析構~SinglyLinkedList\n";
    clear();                                     //清空單鏈表
}

template <class T>
bool SinglyLinkedList<T>::isEmpty()              //判斷單鏈表是否為空
{
    return head==NULL;
}

template <class T>
int SinglyLinkedList<T>::length()                //返回單鏈表長度
{                                                //單鏈表遍歷算法，O(n)
    int i=0;
    Node<T> *p=head;                             //p從head指向的結點開始
    while (p!=NULL)                              //若單鏈表未結束
    {
        i++;
        p = p->next;                             //p到達后繼結點
    }
    return i;
}

template <class T>
Node<T>* SinglyLinkedList<T>::getNode(int i)     //返回第i（i≥0）個結點指針
{                                                //若單鏈表空或序號錯誤返回NULL，O(n)
    if (i<0)
        return NULL;

    int j=0;
    Node<T> *p=head;
    while (p!=NULL && j<i)
    {
        j++;
        p = p->next;
    }
    return p;                                    //p指向第i個結點，若head==NULL，則p==NULL
}

template <class T>
T SinglyLinkedList<T>::get(int i)                //返回第i個元素
{                                                //若單鏈表空或i指定元素序號無效則拋出異常
    Node<T>* p = getNode(i);                     //p指向第i個結點
    if (p!=NULL)
        return p->data;
    throw "單鏈表空或參數i指定元素序號無效";
}

template <class T>
bool SinglyLinkedList<T>::set(int i, T x)        //設置第i個元素為x，O(n)
{
    Node<T>* p=getNode(i);                       //p指向第i個結點
    if (p!=NULL)
    {
        p->data = x;
        return true;
    }
    return false;
}

template <class T>
ostream& operator<<(ostream& out, SinglyLinkedList<T> &list)    //輸出單鏈表所有元素
{
    Node<T> *p = list.head;                      //p從head指向的結點開始
    out<<"(";
    while (p!=NULL)                              //若單鏈表未結束
    {
        out<<p->data;                            //訪問p結點
        p = p->next;                             //p到達后繼結點
        if (p!=NULL)
            out<<", ";
    }
    out<<")\n";
    return out;
}

template <class T>
Node<T>* SinglyLinkedList<T>::insert(int i, T x) //插入x作為第i個結點，返回新插入結點指針
{
    Node<T> *q=NULL;
    if (head==NULL || i<=0)                      //頭插入
    {
        q = new Node<T>(x, head);
        head = q;
    }
    else                                         //單鏈表不空且i>=1
    {
        int j=0; 
        Node<T> *p=head;
        while (p->next!=NULL && j<i-1)           //尋找插入位置
        {
            j++;
            p = p->next;
        }                                        //循環停止時，p指向第i-1個結點或鏈表最后一個結點
        q = new Node<T>(x, p->next);             //插入x作為p結點的后繼結點
        p->next = q;
    }
    return q;
}

template <class T>
bool SinglyLinkedList<T>::remove(int i, T& old)  //刪除第i個結點，被刪除元素存放在old變量中
{
    if (head!=NULL && i>=0)
        if (i==0)                                //頭刪除
        {
            Node<T> *q=head;
            old = q->data;
            head = head->next;
            delete q;                            //釋放結點占用的存儲單元
            return true;
        }
        else                                     //中間/尾刪除
        {
            Node<T>* p=getNode(i-1);             //p指向待刪除結點的前驅結點
            if (p!=NULL && p->next!=NULL)
            {
                Node<T> *q=p->next;              //q結點為p結點的后繼結點
                old = q->data;
                p->next = q->next;               //刪除p的后繼結點q
                delete q;
                return true;
            }
        }
    return false;
}

template <class T>
void SinglyLinkedList<T>::clear()                //清空單鏈表，O(n)
{
    Node<T> *p=head;
    while (p!=NULL)
    {
        Node<T> *q = p;
        p = p->next;                             //到達p的后繼結點
        delete q;                                //釋放q結點所占用的存儲單元
    }
    head = NULL;                                 //設置單鏈表為空，否則運行錯
}
//以上是第2章SinglyLinkedList類內容

//可行，效率較低，不必要
template <class T>
void SinglyLinkedList<T>::insert(T x)            //在單鏈表最后插入x元素
{
    insert(this->length(), x);                   //需兩次遍歷單鏈表，效率較低
}

//【例2.3】  將兩條單鏈表首尾相接合并成一條單鏈表。
template <class T>
void SinglyLinkedList<T>::concat(SinglyLinkedList<T> &list)   //將list鏈接在當前單鏈表之后
{
    if (this->head==NULL)
        this->head = list.head;
    else
    {
        Node<T> *p=head;
        while (p->next!=NULL)                    //找到最后一個結點
            p = p->next;
        p->next = list.head;                     //連接兩條單鏈表
    }
    list.head = NULL;                            //設置單鏈表為空，否則運行錯
}
/*
不能，相當于兩條鏈表合并，有問題
template <class T>
SinglyLinkedList<T>::SinglyLinkedList(Node<T> *head)       //構造指定頭指針的單鏈表
{
    this->head = head;
}
*/

//以下是第2章習題

template <class T>
SinglyLinkedList<T>::SinglyLinkedList(SinglyLinkedList<T> &list)   //以單鏈表list構造新的單鏈表，復制單鏈表
{
    this->head = NULL;
    if (list.head!=NULL)                         //構造非空鏈表    
    {
        this->head = new Node<T>(list.head->data);
        Node<T> *p=list.head->next;
        Node<T> *rear = this->head;              //rear指向單鏈表最后一個結點