//帶頭結點的單鏈表類

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

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

    HSLinkedList();                              //構造空單鏈表
    HSLinkedList(T value[], int n);              //構造由指定數組提供元素的單鏈表
    ~HSLinkedList();                             //析構
 
    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, HSLinkedList<T> &list);    //輸出單鏈表所有元素

    friend ostream& operator<<(ostream& out, HSLinkedList<T> &list);    //輸出單鏈表所有元素
    Node<T>* insert(int i, T x);                 //插入x作為第i個結點，返回新插入結點指針
    bool remove(int i, T& old);                  //刪除第i個結點，被刪除元素存放在old變量中
    void clear();                                //清空單鏈表

    //第9章 排序
    void selectSort();                           //單鏈表的直接選擇排序

};

template <class T>
HSLinkedList<T>::HSLinkedList()                  //構造空單鏈表
{
    this->head = new Node<T>();                  //創建頭結點，數據域未初始化
}

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

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

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

template <class T>
int HSLinkedList<T>::length()                    //返回單鏈表長度
{                                                //單鏈表遍歷算法，O(n)
    int i=0;
    Node<T> *p=head->next;                       //p指向第一個結點
    while (p!=NULL)
    {
        i++;
        p = p->next;
    }
    return i;
}

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

    int j=0;
    Node<T> *p=head->next;
    while (p!=NULL && j<i)
    {
        j++;
        p = p->next;
    }
    return p;                                    //p指向第i個結點，若單鏈表空或序號錯誤，則p==NULL
}

template <class T>
T HSLinkedList<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 HSLinkedList<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, HSLinkedList<T> &list)    //輸出單鏈表所有元素
{
    Node<T> *p = list.head->next;
    out<<"(";
    while (p!=NULL)
    {
        out<<p->data;
        p = p->next;
        if (p!=NULL)
            out<<", ";
    }
    out<<")\n";
    return out;
}

template <class T>
Node<T>* HSLinkedList<T>::insert(int i, T x)     //插入x作為第i個結點，返回新插入結點指針
{
    int j=0; 
    Node<T> *p=head;
    while (p->next!=NULL && j<i)                 //尋找插入位置
    {
        j++;
        p = p->next;
    }
    Node<T> *q = new Node<T>(x, p->next);        //插入x作為p結點的后繼結點
    p->next = q;
    return q;
}

template <class T>
bool HSLinkedList<T>::remove(int i, T& old)      //刪除第i個結點，被刪除元素存放在old變量中
{
    int j=0;
    Node<T> *front=head;
    while (front->next!=NULL && j<i)             //定位到待刪除結點的前驅結點
    {
        j++;
        front = front->next;
    }
    if (front->next!=NULL)
    {
        Node<T> *q=front->next;                  //q結點為front結點的后繼結點
        old = q->data;
        front->next = q->next;                   //刪除front的后繼結點q
        delete q;
        return true;
    }
    return false;
}

template <class T>
void HSLinkedList<T>::clear()                    //清空單鏈表，O(n)
{
    Node<T> *p=head->next;                       //p指向第一個結點
    while (p!=NULL)
    {
        Node<T> *q = p;
        p = p->next;                             //到達p的后繼結點
        delete q;                                //釋放q結點所占用的存儲單元
    }
    head->next = NULL;                           //設置單鏈表為空
}

//以上是第2章內容，實現線性表ADT

//【例9.2】  單鏈表的直接選擇排序。

template <class T>
void HSLinkedList<T>::selectSort()               //單鏈表的直接選擇排序
{
    Node<T> *shead=NULL, *srear=NULL;            //已排序單鏈表的頭指針、尾指針
    while (head->next!=NULL)                     //非空單鏈表
    {
        Node<T> *min=head->next;                 //min指向最小值結點
        Node<T> *mfront=head;                    //mfront是min的前驅結點
        if (min->next!=NULL)
        {
            Node<T> *pfront=min, *p=min->next;   //pfront是p的前驅結點
            while (p!=NULL)
            {   
                if (p->data < min->data)
                {
                    mfront = pfront;
                    min = p;
                }
                pfront = p;
                p = p->next;
            }  
        }
        mfront->next = min->next;                //從head鏈表中刪除min結點
        min->next=NULL;
        if (shead==NULL)                         //在已排序單鏈表中插入min結點
            shead = min;                         //頭插入
        else
            srear->next = min;                   //尾插入
        srear = min;
    }
    head->next = shead;                          //頭結點指向已排序單鏈表
}


/*
下列算法不完善。

template <class T>
void HSLinkedList<T>::insert(int i, T x)         //插入x作為第i個結點
{
    Node<T>* p=getNode(i-1);                     //p指向待刪除結點的前驅結點
    if (p!=NULL)
        p->next = new Node<T>(x, p->next);       //插入x作為p結點的后繼結點
}
    錯誤：不能插入為第一個結點。當i=0時，getNode(i-1)返回NULL，則無法插入。
    該算法沒有序號容錯功能，當i<0或i>length()+1時，getNode(i-1)返回NULL，則無法插入。


template <class T>
bool HSLinkedList<T>::remove(int i, T& old)      //刪除第i個結點，被刪除元素存放在old變量中
{
    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;
}
*/