《数据结构》循环双链表类的定义参考代码

循双环链表结点类型不同，下面定义一个循环双链表的类。并使用头指针。

?1.声明结点类型

    /*************************/    
    /***** 声明模板类    *****/    
    /*************************/    
        
    template <class DataType>    
    struct Node    
    {    
          DataType data;    
          Node<DataType> *prior,*next;      
    };     

2.声明循环双链表类

?? 因为双链表访问结点是双向的，在此使用的是头指针。

template <class DataType>    
class Dou_Circular_LinkList    
{    
public:    
    Dou_Circular_LinkList( );                         //构造函数，含头结点的空链表    
    Dou_Circular_LinkList(DataType a[ ],int n);      //构造函数，建立有n个元素的单链表    
    ~Dou_Circular_LinkList( );                        //析构函数    
    void PrintList( );                   //遍历操作，按序号依次输出各元素    
private:    
    Node<DataType> *first;                //双链表的尾指针    
};    

    
template <class DataType>    
Dou_Circular_LinkList<DataType> ::Dou_Circular_ LinkList( )    
{    
    first = new Node<DataType>;                        //生成头结点，头结点也是尾结点    
    first->next =first; 
    first->prior=first;                             //尾结点的指针域指向自己    
}    
    
template <class DataType>      
Dou_Circular_LinkList<DataType> ::Dou_Circular_LinkList(DataType a[ ],int n)    
{    
    Node<DataType> *f,*s;    
    first = new Node<DataType>;                    //生成头结点    
    f = first;                                    //头结点指针初始化    
    for (int i = 0; i < n; i++)    
    {     
        s = new Node<DataType>; s->data = a[i];        //为每个数组元素建立一个结点    
        s->prior=f;
        f->next=s;
        f=f->next;                            
    }    
    f->next = first;    //双链表建立完毕，将终端结点的指针指向头结点，头结点指向终端结点  
    first->prior=f;
}