//帶頭結(jié)點的循環(huán)雙鏈表類

#include <iostream.h>
#include "DLinkNode.h"                           //雙鏈表結(jié)點類

template <class T>
class CirHDoublyLinkedList                       //帶頭結(jié)點的循環(huán)雙鏈表類
{
  public:
    DLinkNode<T> *head;                          //雙鏈表的頭指針

    CirHDoublyLinkedList();                      //構(gòu)造空雙鏈表
    CirHDoublyLinkedList(T value[], int n);      //構(gòu)造由指定數(shù)組提供元素的雙鏈表
    ~CirHDoublyLinkedList();                     //析構(gòu)
 
    bool isEmpty();                              //判斷雙鏈表是否為空
    int length();                                //返回雙鏈表長度 
    DLinkNode<T>* getNode(int i);                //返回第i（i≥0）個結(jié)點指針
    T get(int i);                                //返回第i個元素
    bool set(int i, T x);                        //設(shè)置第i個元素為x
    friend ostream& operator<<(ostream& out, CirHDoublyLinkedList<T> &list);    //輸出雙鏈表
    DLinkNode<T>* insert(int i, T x);            //插入x作為第i個結(jié)點
    bool remove(int i, T& old);                  //刪除第i個結(jié)點
    void clear();                                //清空雙鏈表

    //循環(huán)雙鏈表增加的操作
    void printPrev();                            //輸出雙鏈表，從后向前，沿著前驅(qū)指針
    DLinkNode<T>* insert(T x);                   //在雙鏈表最后插入x元素結(jié)點
};

template <class T>
CirHDoublyLinkedList<T>::CirHDoublyLinkedList()  //構(gòu)造空雙鏈表
{
    this->head = new DLinkNode<T>();             //創(chuàng)建頭結(jié)點
    head->prev = head;
    head->next = head;
}

template <class T>
CirHDoublyLinkedList<T>::CirHDoublyLinkedList(T value[], int n)   //構(gòu)造由指定數(shù)組提供元素的雙鏈表
{
    head = new DLinkNode<T>();                   //創(chuàng)建頭結(jié)點
    head->prev = head;
    head->next = head;
    for (int i=0; i<n; i++) 
        insert(value[i]);                        //在雙鏈表最后插入結(jié)點
}

template <class T>
CirHDoublyLinkedList<T>::~CirHDoublyLinkedList() //析構(gòu)函數(shù)
{
    clear();                                     //清空雙鏈表
}

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

//以下函數(shù)算法同循環(huán)單鏈表
template <class T>
int CirHDoublyLinkedList<T>::length()            //返回雙鏈表長度
{
    int i=0;
    DLinkNode<T> *p=head->next;
    while (p!=head)
    {
        i++;
        p = p->next;
    }
    return i;
}

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

    int j=0;
    DLinkNode<T> *p=head->next;
    while (p!=head && j<i)
    {
        j++;
        p = p->next;
    }
    if (p!=head)
        return p;                                //p指向第i個結(jié)點
    return NULL;                                 //雙鏈表空或序號錯誤
}

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

template <class T>
bool CirHDoublyLinkedList<T>::set(int i, T x)    //設(shè)置第i個元素為x
{
    DLinkNode<T> *p = getNode(i);
    if (p!=NULL)
    {
        p->data = x;
        return true;
    }
    return false;
}

template <class T>
ostream& operator<<(ostream& out, CirHDoublyLinkedList<T> &list)    //輸出雙鏈表
{
    DLinkNode<T> *p = list.head->next;
    out<<"(";
    while (p!=list.head)
    {
        out<<p->data;
        p = p->next;
        if (p!=list.head)
            out<<", ";
    }
    out<<")\n";
    return out;
}

template <class T>
void CirHDoublyLinkedList<T>::printPrev()         //輸出雙鏈表，從后向前，沿著前驅(qū)域
{
    DLinkNode<T> *p = head->prev;
    cout<<"listPrev: (";
    while (p!=head)
    {
        cout<<p->data;
        p = p->prev;
        if (p!=head)
            cout<<", ";
    }
    cout<<")\n";
}

template <class T>
DLinkNode<T>* CirHDoublyLinkedList<T>::insert(int i, T x) //插入x作為第i個結(jié)點
{
    int j=0; 
    DLinkNode<T> *p=head;
    while (p->next!=head && j<i)                 //尋找插入位置
    {
        j++;
        p = p->next;
    }
    DLinkNode<T> *q = new DLinkNode<T>(x, p, p->next);  //插入在p結(jié)點之后
    p->next->prev = q;
    p->next = q;
    return q;
}

template <class T>
DLinkNode<T>* CirHDoublyLinkedList<T>::insert(T x)   //在雙鏈表最后插入結(jié)點
{
    DLinkNode<T> *q = new DLinkNode<T>(x, head->prev, head);  //插入在head頭結(jié)點之前，相當于尾插入
    head->prev->next = q;
    head->prev = q;
    return q;
}

template <class T>
bool CirHDoublyLinkedList<T>::remove(int i, T& old)   //刪除第i個結(jié)點，被刪除元素存放在old變量中
{
    DLinkNode<T>* p=getNode(i);                  //p指向待刪除結(jié)點
    if (p!=NULL)                                 //刪除p結(jié)點自己
    {
        old = p->data;
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        return true;
    }    
    return false;
}

template <class T>
void CirHDoublyLinkedList<T>::clear()            //清空雙鏈表
{
    DLinkNode<T> *p=head->next;
    while (p!=head)
    {
        DLinkNode<T> *q = p;
        p = p->next;
        delete q;
    }
    head->next = head;                           //設(shè)置循環(huán)雙鏈表為空
    head->prev = head;                           //比循環(huán)單鏈表多此一句
}

//以上是第2章內(nèi)容，實現(xiàn)線性表ADT