STL版本的循环链表

[cpp] view plaincopy

/*
  循环链表
  实现功能，创建循环链表，插入指定数据
  到指定位置，删除，查找数据位置，插入
  到指定位置
*/
#include
using namespace std;

template<class T>
struct Node
{
   T data;
   struct Node *next;/*指针域，在这里可省略*/
};

template <class T>
class ClinkList
{
 public:
  ClinkList()
  {
   head=new Node ;
   head->next=head;
  }        /*无参构造函数*/
  ClinkList(T a[], int n);  /*有参构造函数，使用含有n个元素的数组a初始化单链表(头插法和尾插法）*/
  ~ClinkList();      /*析构函数*/
  int GetLength();    /*获取线性表的长度*/
  Node * Get(int i);   /*获取线性表第i个位置上的元素*/
  int Locate(T x);    /*查找线性表中值为x的元素，找到后返回其位置*/
  void Insert(int i, T x);        /*在线性表的第i个位置上插入值为x的新元素*/
  int Delete(int i);    /*删除线性表第i个元素，并将该元素返回*/
  void PrintList();    /*按次序遍历线性表中的各个数据元素*/
 private:
  Node  *head;     /*尾指针*/
};


template<class T>
ClinkList::ClinkList(T a[],int n)     //头插法建立循环列表
{
 head = new Node;
    head->next = head;
 head->data = n;
 for(int i=0;i<=n-1;i++)
 {
  Node *s=new Node;   //修改新节点的指针域
  s->data=a[i];     //修改头结点的指针域，将新节点加入到链表中
  s->next=head->next;
  head->next=s;
 }
}



template <class T>
int ClinkList::GetLength()
{
 int i=0;
 Node*p=head;
 while(p->next!=head)
 {
  i++;
  p=p->next;
 }
 return i;
}

template <class T>
Node* ClinkList::Get(int i)
{
 if(i>head->data) cout<<"超出范围";
 Node *p= head;
 int k = 0;
 while(k!=i)
 {
  k++;
  p=p->next;
 }
 return p;
}
/*查找x这个数据在循环链表中的位置*/
template <class T>
int ClinkList:: Locate(T x)
{   int i = 0;
 Node *p = head;
 while(p->data!=x)
 {
        p=p->next;
        i++;
    }
 if(i>head->data)
  throw"该链表中无此数";
 else
        return i;
}

/*插入到第i个数据后面*/
template<class T>
void ClinkList:: Insert(int i, T x)
{
 if(i>head->data) throw"插入位置错误";
 Node *p = head;
 int k = 0;
 while(k!=i)
 {
  k++;
  p=p->next;
 }
    Node *s=new Node;
    s->data=x;
    s->next=p->next;
    p->next=s;
    head->data++;
}

template<class T>
int ClinkList:: Delete(int i)
{
 if(i>head->data) throw"删除位置错误";
 Node *p=head->next;
 Node *q=head;
 int k = 1;
 while(k!=i)
 {   k++;
        q = p;
  p = p->next;
 }
 int x = p->data;
 q->next = p->next;
 delete p;
 p = NULL;
 head->data--;
 return x;
}

template <class T>
void ClinkList:: PrintList()
{
 Node *p=head->next;
 //int i=GetLength();
 int i = head->data;
 cout<<"length = "<
 while(p!=head)
 {
  cout<data<<"   ";
  p = p->next;
    }
    cout<
}

template <class T>
ClinkList::~ClinkList()
{
    while(head->next!=head)
    {
       Node *p = head->next;
       head->next = p->next;
       delete p;
       p = NULL;
    }
    delete head;
    head = NULL;
}

int main()
{
 int b[]={0,1,2,3,4,5,6,7,8,9};
 ClinkList<int>  circleLinkList(b,10);
 circleLinkList.PrintList();

    circleLinkList.Delete(5);
    cout<"after circleLinkList.Delete(5)"<
 circleLinkList.PrintList();

 Node<int> *result = circleLinkList.Get(5);
 cout<"circleLinkList.Get(5) is "<data<

 circleLinkList.Insert(4,5);
 circleLinkList.PrintList();

 cout<"circleLinkList.Locate(7) is at  "<

 return 0;
}