循環(huán)鏈表

循環(huán)鏈表和單鏈表沒有本質(zhì)上的差別。唯1不同的鏈表的最后不再是空的了，而是指向了first頭指針。只有這樣我們才會(huì)實(shí)現(xiàn)鏈表的循環(huán)功能，那末問題來了，我們在下面的函數(shù)功能中我們只是需要把里面用的頭指針的重用名換到first->next中，而且其中的計(jì)數(shù)器count也從1開始計(jì)數(shù)，這樣就避免了在while的循環(huán)中第1步實(shí)行不下去。空話不多說。詳細(xì)看wo的代碼吧。

#ifndef CirLinkList_H
#define CirLinkList_H
#include<iostream>
using namespace std;
template<typename T>
struct Node{//結(jié)點(diǎn)
 T data;
 Node<T> * next;
};
template<typename T>
class CirLinkList {//無頭結(jié)點(diǎn)的循環(huán)單鏈表
 template<typename T>
 friend ostream & operator<<(ostream &,CirLinkList<T> &);
public:
 CirLinkList();    //創(chuàng)建空循環(huán)單鏈表（即：first指向空指針）。
 CirLinkList(T a[],int n); //建立含n個(gè)元素的循環(huán)單鏈表。
 ~CirLinkList();   //析構(gòu)函數(shù)，清除所有結(jié)點(diǎn)。
 int Length();   //求表長度。
 T Get(int i);   //取表中第i個(gè)元素。10分
 void Insert(int i,T & x);//在第i個(gè)結(jié)點(diǎn)以后，插入新元素。
 T Delete(int i);  //刪除第ｉ個(gè)元素。
 bool isEmpty();   //判斷表是不是為空。
 void DelTheSame();  //刪除表中相同元素，僅保存1個(gè)。
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;//初始化循環(huán)單鏈表
}
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;//這里的first1直沒變
}
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⑴)
  {
    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<<"鏈表內(nèi)容："<<myLink<<endl;
 cout<<"鏈表長度："<<myLink.Length()<<endl;
 cout<<"第11號(hào)元素："<<myLink.Get(11)<<endl;
 myLink.Insert(3,x);
 cout<<"在3號(hào)元素后插入11后，鏈表內(nèi)容："<<myLink<<endl;
 cout<<"被刪除的5號(hào)元素內(nèi)容："<<myLink.Delete(5)<<endl;
 cout<<"鏈表當(dāng)前內(nèi)容："<<myLink<<endl;
 myLink.DelTheSame();
 cout<<"刪除相同元素后，鏈表內(nèi)容："<<myLink<<endl;
 if(myLink.isEmpty())
  cout<<"空:";
 return 0;
}

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)