/****************************/ /*********声明模板类*********/ /****************************/ template<class DateTpe> struct Node { DateType data; Node<DataType> *next; }; template<class DataType> class Circular_LinkList { public: Circular_LinkList(); //无参构造函数，建立只有头结点的空链表 Circular_LinkList(DataType a[],int n); //有参构造函数，建立有n个元素的单链表 ~Circular_LinkList(); //析构函数 int Length(); //求单链表的长度 DataType Get(int i); //按位查找。在单链表中查找第i个结点的元素值 int Locate(DataType x); //按值查找。在单链表中查找值为x的元素序号 void Insert(int i,DataType x); //插入操作，在第i个位置插入元素值为x的结点 DataType Delete(int i); //删除操作，在单链表中删除第i个结点 void PrintLink(); //遍历操作，按序号依次输出各元素 private: Node<DataType> *rear; //单链表的尾指针 }; /******************************/ /******定义模板类操作函数******/ /******************************/ 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插入到终端结点之后 } rear->next=f; //单链表建立完毕，将终端结点的指针指向头结点 } template<class DataType> Circular_LinkList<DataType>::~Circular_LinkLise() //析构函数，将整个链表删除，这里采用的是正序撤销 { Node<DataType> *p=rear->next; while(p!=rear) //释放单链表的每一个结点的存储空间 { Node<DataType> *q=p; //暂存被释放结点 p=p->next; //p指向被释放结点的下一个结点 delete q; } delete rear; } template<class DataType> int Circular_LinkList<DataType>::Length() //求循环链表长度算法 { p=(rear->next)->next;count=0; //工作指针p和累加器count初始化 while(p!=rear) { p=p->next; count++; } return count; } template<class DataType> DataType LinkList<DataType>::Get(int i) { p=(rear->next;count=1; while(p!=NULL && count<i) { p=p->next; //工作指针p后移 count++; } if(p==NULL) throw"位置"; else return p->data; } template<class DataType> int LinkList<DataType>::Locate(DatType x) { p=(rear->next)->next;count=1; while(p!=NULL) { if(p->data==x) return count; //查找成功，结束函数并返回序号 p=p->next; count++; } return 0; } template<class DataType> void LinkList<DataType>::Insert(int i,DataType x) { p=rear->next;count=0; //工作指针p指向头结点 while(p!=NULL && count<i-1) //查找第i-1个结点 { p=p->next; //工作指针p后移 count++; } if(p==NULL) throw"位置"; //没有找到第i-1个结点 else{ s=new Node;s->data=x; //申请一个结点s，其数据域为x s->next=p->next;p->next=s; //将结点s插入到结点p之后 } } template<class DataType> DataType LinkList<DataType>::Delete(int i) { p=rear->next;count=0; //工作指针p指向头结点 while(p!=NULL && count<i-1) //查找第i-1个结点 { p=p->next; count++; } if(p==NULL||p->next==NULL) //结点p不存在或p的后继结点不存在 throw"位置"; else{ q=p->next;x=q->data; //暂存被删结点 p->next=q->next; //摘链 delete q; return x; } } template<class DataType> void Circular_LinkList<DataType>::PrintList() { p=(rear->next)->next; //工作指针初始化 while(p!=rear) { cout<<p->date; p=p->next; //工作指针p后移 } }