循环链表

╰+哭是因爲堅強的太久メ 2022-08-13 13:52 237阅读 0赞

循环链表和单链表没有本质上的差别。唯一不同的链表的最后不再是空的了，而是指向了first头指针。只有这样我们才会实现链表的循环功能，那么问题来了，我们在下面的函数功能中我们只是需要把里面用的头指针的重用名换到first->next中，而且其中的计数器count也从1开始计数，这样就避免了在while的循环中第一步实行不下去。废话不多说。详细看wo的代码吧。

\#ifndef CirLinkList\_H  
\#define CirLinkList\_H  
\#include<iostream>  
using namespace std;  
template<typename T>  
struct Node\{//结点  
 T data;  
 Node<T> \* next;  
\};  
template<typename T>  
class CirLinkList \{//无头结点的循环单链表  
 template<typename T>  
 friend ostream & operator<<(ostream &,CirLinkList<T> &);  
public:  
 CirLinkList();    //创建空循环单链表（即：first指向空指针）。  
 CirLinkList(T a\[\],int n); //建立含n个元素的循环单链表。  
 ~CirLinkList();   //析构函数，清除所有结点。  
 int Length();   //求表长度。  
 T Get(int i);   //取表中第i个元素。10分  
 void Insert(int i,T & x);//在第i个结点之后，插入新元素。  
 T Delete(int i);  //删除第ｉ个元素。  
 bool isEmpty();   //判断表是否为空。  
 void DelTheSame();  //删除表中相同元素，仅保留一个。  
private:  
 Node<T> \* first;  
\};  
template<typename T>  
ostream & operator<<(ostream & os,CirLinkList<T> & l)\{  
 Node<T> \* p=l.first->next;  
 if(p!=l.first)\{  
  do\{  
   os<<p->data<<",";  
   p=p->next;  
  \}while(p!=l.first);  
 \}  
 else  
  os<<endl;  
 return os;  
\}  
template<typename T>  
CirLinkList<T>::CirLinkList()  
\{  
   Node<T> \*first;  
   first=new Node<T>;  
   first->next=first;//初始化循环单链表  
\}  
template<typename T>  
CirLinkList<T>::CirLinkList(T a\[\],int n)  
\{  
  Node<T> \*r,\*s;  
  first=new Node<T>;  
  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;//这里的first一直没变  
\}  
template<typename T>  
CirLinkList<T>::~CirLinkList()  
\{  
  Node<T> \*q=NULL;  
  while(first!=NULL)  
  \{  
   q=first;  
   first=first->next;  
   delete q;      //可能有问题？  
  \}  
\}  
template<typename T>  
int CirLinkList<T>::Length()  
\{  
 Node<T> \*p=first->next;  
 int count=0;  
 while(p!=first)  
 \{  
  p=p->next;  
  count++;  
 \}  
 return count;  
\}  
template<typename T>  
T CirLinkList<T>::Get(int i)  
\{  
 Node<T> \*p=first->next;  
 int count=1;  
 while(p!=first&&count<i)  
 \{  
  p=p->next;  
  count++;  
 \}  
 if(p==first)throw"位置";  
 else return p->data;  
\}  
template<typename T>  
void CirLinkList<T>::Insert(int i,T & x)  
\{  
 Node<T> \*p=first->next;  
  int count=1;  
  while(p!=first&&count<i)  
  \{  
   p=p->next;  
   count++;  
  \}  
  if(p==first)throw"位置";  
  else  
  \{  
    Node<T> \*s;  
 s=new Node<T>;  
 s->data=x;  
 s->next=p->next;  
 p->next=s;  
  \}  
\}  
template<typename T>  
T CirLinkList<T>::Delete(int i)  
\{  
 Node<T> \*p=first->next;  
  T x;int count=1;  
  while(p!=first&&count<i-1)  
  \{  
    p=p->next;  
 count++;  
  \}  
  if(p==first||p->next==first)throw"位置";  
  else  
  \{  
    Node<T> \*q;  
 q=p->next;  
 x=q->data;  
 p->next=q->next;  
 delete q;  
 return x;  
  \}  
\}  
template<typename T>  
bool CirLinkList<T>::isEmpty()  
\{  
  Node<T> \*q;  
  if(first=first->next)  
   return 0;  
\}  
template<typename T>  
void CirLinkList<T>::DelTheSame()  
\{  
 Node<T> \*q=first->next;  
 while(q!=first)  
 \{  
  Node<T> \*s=q->next;  
  Node<T> \*r;  
  r=s;  
  if(q==r)  
  \{  
    delete s;  
    r=r->next;  
  \}  
 \}  
\}  
\#endif  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
\#include<iostream>  
\#include"CirLinkList.h"  
using namespace std;  
int main()\{  
 int ary\[\]=\{2,4,6,8,12,32,43,6,9,2,7\},x=11;  
 CirLinkList<int> myLink(ary,11);  
 cout<<"链表内容："<<myLink<<endl;  
 cout<<"链表长度："<<myLink.Length()<<endl;  
 cout<<"第11号元素："<<myLink.Get(11)<<endl;  
 myLink.Insert(3,x);  
 cout<<"在3号元素后插入11后，链表内容："<<myLink<<endl;  
 cout<<"被删除的5号元素内容："<<myLink.Delete(5)<<endl;  
 cout<<"链表当前内容："<<myLink<<endl;  
 myLink.DelTheSame();  
 cout<<"删除相同元素后，链表内容："<<myLink<<endl;  
 if(myLink.isEmpty())  
  cout<<"空:";  
 return 0;  
\}