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

循环链表和单链表很多操作是一样的，只是细小的区别。下面在单链表代码的基础上，定义一个循环单链表的类。并使用尾指针。

?1.声明结点类型

???? 结点类型和单链表一样。

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

2.声明循环链表类

?? 也基本和单链表一样，只是使用的是尾指针。

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

3.类的构造函数定义代码

  
/********************************/  
/***** 定义模板类操作函数   *****/  
/********************************/  
  
template <class DataType>  
Circular_LinkList<DataType> ::Circular_ LinkList( )  
{  
    rear = new Node<DataType>;                        //生成头结点，头结点也是尾结点  
    rear->next =rear;                                //尾结点的指针域指向自己  
}  
  
template <class DataType>    
Circular_LinkList<DataType> :: Circular_LinkList(DataType a[ ],int n)  
{  
    Node<DataType> *f,*s;  
    rear = new Node<DataType>;                    //生成头结点  
    f = rear;                                    //头结点指针初始化  
    for (int i = 0; i < n; i++)  
    {   
        s = new Node<DataType>; s->data = a[i];        //为每个数组元素建立一个结点  
        rear->next = s; rear = s;                 //将结点s插入到终端结点之后  
    }  
    r->next = f;       //单链表建立完毕，将终端结点的指针指向头结点 
} 

其它函数代码大家自己可以写。