循环单链表（带有附加头结点）C++实现

╰半夏微凉° 2022-05-22 11:17 145阅读 0赞

\#include<iostream>  
using namespace std;  
template<class T> //采用模板类型  
struct CircLinkNode\{ //单链表节点类的定义  
T data; //节点的数据域  
CircLinkNode<T> \*next; //节点的指针域  
CircLinkNode(CircLinkNode<T> \*link=NULL):next(link)\{\} //节点的构造函数  
CircLinkNode(T d,CircLinkNode<T> \*link=NULL):next(link),data(d)\{\}  
\};

template<class T> //循环单链表的类定义，含有附加头节点  
class CircLink\{  
public:  
CircLink(const T& x); //默认构造函数  
CircLink(const CircLink<T>& L); //复制构造函数  
~CircLink(); //析构函数  
  
int Length() const; //计算循环链表的长度  
bool IsEmpty(); //判断表是否为空  
CircLinkNode<T> \*getHead() const; //返回附加头结点的地址  
CircLinkNode<T> \*Search(T x); //搜索含有数据x的元素  
CircLinkNode<T> \*Locate(int i); //定位第i个元素  
  
T getData(int i); //取出第i个元素的值  
void setData(int i,T &x); //用x修改第i个元素的值  
bool Insert(int i,T& x); //在第i个元素的位置插入含有x的节点  
bool Remove(int i,T& x); //删除第i个元素，x返回该元素的值  
  
private:  
CircLinkNode<T> \*first; //定义first指针，指向链表的附加头节点  
  
\};

template<class T>  
CircLink<T>::CircLink(const T& x)\{  
first=CircLinkNode<T>(x);  
if(first==NULL)\{  
cerr<<"存储分配错误"<<endl; exit(1);  
\}  
first->next=first; //带有附加头结点，对附加头节点进行操作，使其next指针指向自己，从而构成循环  
\}

template<class T>  
CircLink<T>::CircLink(const CircLink<T>& L)\{  
CircLinkNode<T> \*srcptr=L.getHead(); //被复制表的附加头结点的地址  
CircLinkNode<T> \*desptr=first=new CircLinkNode<T>(); //建立附加头结点，并用first 指向附加头结点  
T value;  
while(srcptr->next!=first)\{  
value=srcptr->next->data; //取得第一个节点（注意不是附加头结点,一般附加头结点中是不存放数据的）中的数值  
desptr->next=new CircLinkNode<T>(value); //建立第一个节点,附加头结点指向该节点  
desptr=desptr->next; //desptr现在代表整个节点，包括数据和指针  
srcptr=srcptr->next; //指向下一个节点  
\}  
srcptr->next=first; //最后一个节点指向附加头结点  
\}

template<class T>  
CircLink<T>::~CircLink()\{  
CircLinkNode<T> \*p;  
while(first->next!=first)\{  
p=first->next;  
first->next=p->next;  
delete p;  
p=NULL;  
\}  
\}

template<class T>  
int CircLink<T>::Length() const\{  
CircLinkNode<T> \*p=first->next;int count=0;  
while(p!=first)\{  
p=p->next;  
count++;  
\}  
return count;  
\}

template<class T>  
bool CircLink<T>::IsEmpty()\{  
return first->next==first?true:false;  
\}

template<class T>  
CircLinkNode<T>\* CircLink<T>::getHead() const\{  
return first;  
\}

template<class T>  
CircLinkNode<T>\* CircLink<T>::Search(T x)\{  
CircLinkNode<T> \*current=first->next;  
while(current->next!=first)\{  
if(current->data==x) break;  
else current=current->next;  
\}  
return current;  
\}

template<class T>  
CircLinkNode<T>\* CircLink<T>::Locate(int i)\{  
if(i<0)return NULL;  
CircLinkNode<T> \*current=first->next;int k=0;  
while(current!=first&&k<i)\{  
current=current->next;  
k++;  
\}  
return current;//返回第i个节点的地址 ,第0个节点为附加头结点  
\}

template<class T>  
T CircLink<T>::getData(int i)\{  
CircLinkNode<T> \*p=Locate(i);  
return p->data;  
\}

template<class T>  
void CircLink<T>::setData(int i,T& x)\{  
CircLinkNode<T> \*p=Locate(i);  
p->data=x;  
\}

template<class T>  
bool CircLink<T>::Insert(int i,T& x)\{  
CircLinkNode<T> \*p=Locate(i-1); //为了在第i个位置插入节点，需要在先找到第i-1个节点  
CircLinkNode<T> \*newNode=new CircLinkNode<T>(x);  
if(newNode==NULL)\{  
cerr<<"存储分配失败"<<endl;exit(1);\}  
newNode->next=p->next;  
p->next=newNode;  
return true;  
\}

template<class T>  
bool CircLink<T>::Remove(int i,T& x)\{  
CircLinkNode<T> \*current=Locate(i-1); //获得第i-1个节点的地址  
if(current==NULL||current->next==first) return false; //先进行判断，如果节点是最后一个节点则报错  
CircLinkNode<T> \*del=current->link; //应该被删除的节点  
current->link=del->link; //第i-1个节点指向第i+1个节点  
x=del->data;  
delete del;  
return true;  
\}