cirhdoublylinkedlist.h

回顾基础

//带头结点的循环双链表类

#include <iostream.h>
#include "DLinkNode.h"                           //双链表结点类

template <class T>
class CirHDoublyLinkedList                       //带头结点的循环双链表类
{
  public:
    DLinkNode<T> *head;                          //双链表的头指针

    CirHDoublyLinkedList();                      //构造空双链表
    CirHDoublyLinkedList(T value[], int n);      //构造由指定数组提供元素的双链表
    ~CirHDoublyLinkedList();                     //析构
 
    bool isEmpty();                              //判断双链表是否为空
    int length();                                //返回双链表长度 
    DLinkNode<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, CirHDoublyLinkedList<T> &list);    //输出双链表
    DLinkNode<T>* insert(int i, T x);            //插入x作为第i个结点
    bool remove(int i, T& old);                  //删除第i个结点
    void clear();                                //清空双链表

    //循环双链表增加的操作
    void printPrev();                            //输出双链表，从后向前，沿着前驱指针
    DLinkNode<T>* insert(T x);                   //在双链表最后插入x元素结点
};

template <class T>
CirHDoublyLinkedList<T>::CirHDoublyLinkedList()  //构造空双链表
{
    this->head = new DLinkNode<T>();             //创建头结点
    head->prev = head;
    head->next = head;
}

template <class T>
CirHDoublyLinkedList<T>::CirHDoublyLinkedList(T value[], int n)   //构造由指定数组提供元素的双链表
{
    head = new DLinkNode<T>();                   //创建头结点
    head->prev = head;
    head->next = head;
    for (int i=0; i<n; i++) 
        insert(value[i]);                        //在双链表最后插入结点
}

template <class T>
CirHDoublyLinkedList<T>::~CirHDoublyLinkedList() //析构函数
{
    clear();                                     //清空双链表
}

template <class T>
bool CirHDoublyLinkedList<T>::isEmpty()          //判断双链表是否为空
{
    return head->next==head;
}

//以下函数算法同循环单链表
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）个结点指针，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个结点
    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 "双链表空或参数i指定元素序号无效";
}

template <class T>
bool CirHDoublyLinkedList<T>::set(int i, T x)    //设置第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()         //输出双链表，从后向前，沿着前驱域
{
    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个结点
{
    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结点之后
    p->next->prev = q;
    p->next = q;
    return q;
}

template <class T>
DLinkNode<T>* CirHDoublyLinkedList<T>::insert(T x)   //在双链表最后插入结点
{
    DLinkNode<T> *q = new DLinkNode<T>(x, head->prev, head);  //插入在head头结点之前，相当于尾插入
    head->prev->next = q;
    head->prev = q;
    return q;
}

template <class T>
bool CirHDoublyLinkedList<T>::remove(int i, T& old)   //删除第i个结点，被删除元素存放在old变量中
{
    DLinkNode<T>* p=getNode(i);                  //p指向待删除结点
    if (p!=NULL)                                 //删除p结点自己
    {
        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;                           //设置循环双链表为空
    head->prev = head;                           //比循环单链表多此一句
}

//以上是第2章内容，实现线性表ADT