循环链表

循环链表的定义

template<typename T>
struct Node
{
    T data;
  Node<T> *next;
};
template<typename T>
class CycleLinkList{
public:
  CycleLinkList();
  CycleLinkList(T a[],int n);
  CycleLinkList(T a[],int n,int i);
  ~CycleLinkList();
  int Length();
  T Get(int i);
  void Insert(int i,T x);
  T Delete(int i);
  void PrintList();
private:
  Node<T> *first;
};

空表的构造

template<typename T>
CycleLinkList<T>::CycleLinkList()
{
   first=new Node<T>;
   first->next=first;
}

尾插法构造循环链表

template<typename T>
CycleLinkList<T>::CycleLinkList(T a[],int n)
{
   first=new Node<T>;//生成头结点
   Node<T> *r,*s;
   r=first;//尾指针初始化
   for(int i=0;i<n;i++)
   {
     s=new Node<T>;
   s->data=a[i];
   r->next=s;
   r=s;
   }
   r->next=first;//单链表建立完毕,将终端结点的指针域指向头结点
}

头插法构造循环链表

template<typename T>
CycleLinkList<T>::CycleLinkList(T a[],int n,int i)
{
  first=new Node<T>;//生成头结点
  first->next=first;
  Node<T> *s;
  for(int i=1;i<n;i++)
  {
    s=new Node<T>;
  s->data=a[i];//为每个数组元素建立一个结点
  s->next=first->next;
  first->next=s;
  }
}

将非循环的单链表改造成循环的单链表

p=first;
while(p->next)
{ 
       p=p->next;  
 }
p->next=first

 

发布者

deng

听闻余生久不遇,相逢别错过。

发表评论

电子邮件地址不会被公开。 必填项已用*标注