学步园

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

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

template <class T>
class ClinkList
{
 public:
  ClinkList()
  {
   head=new Node <T>;
   head->next=head;
  }        /*无参构造函数*/
  ClinkList(T a[], int n);  /*有参构造函数，使用含有n个元素的数组a初始化单链表(头插法和尾插法）*/
  ~ClinkList();      /*析构函数*/
  int GetLength();    /*获取线性表的长度*/
  Node<T> * 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 <T> *head;     /*尾指针*/
};


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

 

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

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

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

template<class T>
int ClinkList<T>:: Delete(int i)
{
 if(i>head->data) throw"删除位置错误";
 Node<T> *p=head->next;
 Node<T> *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<T>:: PrintList()
{
 Node<T> *p=head->next;
 //int i=GetLength();
 int i = head->data;
 cout<<"length = "<<i<<endl;
 while(p!=head)
 {
  cout<<p->data<<"   ";
  p = p->next;
    }
    cout<<endl;
}

template <class T>
ClinkList<T>::~ClinkList()
{
    while(head->next!=head)
    {
       Node<T> *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<<endl<<"after circleLinkList.Delete(5)"<<endl;
 circleLinkList.PrintList();

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

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

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

 return 0;
}