如何实现带头节点的单向循环链表 C++类实现

//这个好像和你的差不多。
//head 是头节点,本身的link指向自己,first指向第一个真实的存储数据的节点
//头节点的初始化在构造函数中已经实现,但插入第一个节点是不知如何插入,还是头节点那样初始化根本就不对? head->link指向新结点，新节点link指向表头(为便于操作，可设置尾指针指向表头)
//在Chain类中只有first和head两个指针的情况下能否实现单向循环链表? 该实例能。

你问题补充的回答：是你弄反了。头节点（有尾结点的链表尾结点也不存储数据。）是不存储实际数据元素的（数据域可自己定义使用，该实例中用于存储实际结点的数目）。因为一个空表头结点也是存在的。first的存在只是为了便于修改原来的程序，实际上是不必要的。

#include "stdio.h"
#include
//#include
using namespace std;

template
class Chain;
template
class ChainNode
{
friend Chain;
private:
T data;
ChainNode *link;
};
template
class Chain
{
public:
Chain()
{
head=new ChainNode;//头节点
tail=head;
head->link=tail;
tail->link=head;
first=head->link;
}
~Chain();
bool IsEmpty() const {return first==0;}
int Length() const;
bool Find(int k,T&x) const;
int Search(const T&x) const;
Chain& Delete(int k,T&x);
Chain& Insert(int k,const T&x);
void Output(ostream& out) const;
private:
ChainNode *first;//指向第一个真实节点的指针
ChainNode *head;//表头指针
ChainNode *tail;//表尾指针
};

//////////////析构函数///////////////////
template
Chain::~Chain()
{
ChainNode *next;
while(first!=tail)
{
next=first->link;
delete first;
first=next;
}
delete head;
}
//////////////输出//////////////
template
void Chain::Output(ostream& out)const
{
ChainNode *current;
int num=0;
for(current=first;current!=tail;current=current->link)
{
out<data<<" ";
num++;
if(num%10==0)
cout<}
}
template
ostream& operator<<(ostream& out,const Chain& x)
{
x.Output(out);return out;
}
///////////删除/////////////////
template
Chain& Chain::Delete(int k,T& x) //这个x何用？
{
if(k<1||first==tail) {cout<<"Error!";exit(1);}
ChainNode *p=first;
if(k==1)
{
first=first->link;
head->link=first->link;
}
else
{
ChainNode *q=first;
for(int index=1;indexq=q->link;
if((q==tail)||(q->link==tail)) {cout<<"Error!";exit(1);}
p=q->link;
q->link=p->link;
}
x=p->data;
delete p;
return *this;
}
//////////////插入//////
template
Chain& Chain::Insert(int k,const T& x)
{
if(k<0) {cout<<"Error!";exit(1);}
ChainNode *p=first;
for(int index=1;indexp=p->link;
if(k>0&&(p==tail)) {cout<<"Error!";exit(1);}
ChainNode *y=new ChainNode;
y->data=x;
if(k) //插入k位置
{
y->link=p->link;
p->link=y;
}
else
{
y->link=tail; //插入表头
first=y;
head->link=first;//这条语句丢掉了
}
return *this;
}

void main()
{
Chain cn;
for(int i=0;i<100;i++)
{
cn.Insert(i,i);

}
int x;
cn.Delete(10,x);
cout<system("pause");

}

风格有点不一样
class point
{
public:
int data;
point* next;
};

class link
{
public:
point* head;
point* tail;
void add(int dat);
link();
};

link::link()
{
head=NULL;
tail=NULL;
}

void link::add(int dat)
{
if(head)
{
point* p=new point;
p->data=dat;
p->next=head;
tail->next=p;
}
else
{
head=new point;
head->data=dat;
head->next=head;
tail=head;
}
}

跟这个问题一样，我回答的是没有头节点的。但这个兄弟给了头节点的，并且调通了。
http://zhidao.baidu.com/question/72616983.html

#include
#include
using namespace std;

template
class Chain;
template
class ChainNode
{
friend Chain;
private:
T data;
ChainNode *link;
};
template
class Chain
{
public:
Chain()
{
head=new ChainNode;//头节点
tail=head;
head->link=tail;
tail->link=head;
first=head->link;
}
~Chain();
bool IsEmpty() const {return first==0;}
int Length() const;
bool Find(int k,T&x) const;
int Search(const T&x) const;
Chain& Delete(int k,T&x);
Chain& Insert(int k,const T&x);
void Output(ostream& out) const;
private:
ChainNode *first;//指向第一个真实节点的指针
ChainNode *head;//表头指针
ChainNode *tail;//表尾指针
};

//////////////析构函数///////////////////
template
Chain::~Chain()
{
ChainNode *next;
while(first!=tail)
{
next=first->link;
delete first;
first=next;
}
delete head;
}
//////////////输出//////////////
template
void Chain::Output(ostream& out)const
{
ChainNode *current;
int num=0;
for(current=first;current!=tail;current=current->link)
{
out<data<<" ";
num++;
if(num%10==0)
cout<}
}
template
ostream& operator<<(ostream& out,const Chain& x)
{
x.Output(out);return out;
}
///////////删除/////////////////
template
Chain& Chain::Delete(int k,T& x) //这个x何用？
{
if(k<1||first==tail) {cout<<"Error!";exit(1);}
ChainNode *p=first;
if(k==1)
{
first=first->link;
head->link=first->link;
}
else
{
ChainNode *q=first;
for(int index=1;indexq=q->link;
if((q==tail)||(q->link==tail)) {cout<<"Error!";exit(1);}
p=q->link;
q->link=p->link;
}
x=p->data;
delete p;
return *this;
}
//////////////插入//////
template
Chain& Chain::Insert(int k,const T& x)
{
if(k<0) {cout<<"Error!";exit(1);}
ChainNode *p=first;
for(int index=1;indexp=p->link;
if(k>0&&(p==tail)) {cout<<"Error!";exit(1);}
ChainNode *y=new ChainNode;
y->data=x;
if(k) //插入k位置
{
y->link=p->link;
p->link=y;
}
else
{
y->link=tail; //插入表头
first=y;
head->link=first;//这条语句丢掉了
}
return *this;
}

void main()
{
Chain cn;
for(int i=0;i<100;i++)
{
cn.Insert(i,i);

}
int x;
cn.Delete(10,x);
cout<system("pause");
}

感觉是不行,,具体怎么改 要想想

#ifndef LISTNODE_H
#define LISTNODE_H
templateclass LIST;
template
class LISTNODE
{
friend class LIST;
public:
LISTNODE();
LISTNODE(const T &x);
T GetData()const {return data;}
private:
T data;
LISTNODE *next;
};
template
LISTNODE::LISTNODE():next(0){}
template
LISTNODE::LISTNODE(const T&x):data(x),next(0){}
#endif

#ifndef LIST_H
#define LIST_H
#include
#include "LISTNODE.H"

template
class LIST
{
public:
LIST();
LIST(const T&x);
~LIST();
bool Insert(const T &x,const int i);
bool Remove(const int i);
int Length()const;
bool IsEmpty()const {return first->next==0;}
void MakeEmpty();
T GetPrivor(const T&)const;
T GetNext(const T&)const;
void Print()const;
T GetData(const int i)const;
LISTNODE*Find(const T&x);
void SetData(const T&x){first->data=x;}
void CreateList();
private:
LISTNODE*first,*last;

};
template
LIST::LIST()
{
last=first=new LISTNODE(0);
}
template
LIST::LIST(const T&x)
{
last=first=new LISTNODE(x);
}
template
LIST::~LIST()
{
MakeEmpty();
delete first;
last=first=0;
}
template
void LIST::MakeEmpty()
{
LISTNODE *q;
while(first->next!=0)
{
q=first->next;
first->next=q->next;
delete q;
}
last=first;
}
template
bool LIST::Insert(const T& x,const int i)
{
LISTNODE*p=first;
int k=0;
while(p!=0&&k {
k++;
p=p->next;
}
if(p==0||i<0)
{
cerr<<"no this position"< return false;
}
else
{
LISTNODE*newnode=new LISTNODE(x);
newnode->next=p->next;
if(p->next==0)
last=newnode;
p->next=newnode;
}
return true;
}
template
int LIST::Length()const
{
LISTNODE*p=first->next;
int i=0;
while(p!=0)
{
p=p->next;
i++;
}
return i;
}
template
void LIST::Print()const
{
LISTNODE *p=first;
while(p!=0)
{
cout<data<<" ";
p=p->next;
}
cout<}
template
bool LIST::Remove(const int i)
{
LISTNODE*p=first,*q;
int j=0;
while(p->next!=0&&j {
j++;
p=p->next;
}
if(p->next==0||i<1)
{
cerr<<"no this position!"< return false;
}
else
{
q=p->next;
p->next=q->next;
if(p->next==0)
last=p;
delete q;
}
return true;
}
template
T LIST::GetPrivor(const T&x)const
{
LISTNODE*p=first;
while(p->next!=0&&p->next->data!=x)
p=p->next;
if(p->next==0||p==first)
return 0;
else return p->data;
}
template
T LIST::GetNext(const T&x)const
{
LISTNODE*p=first->next;
while(p!=0&&p->data!=x)
p=p->next;
if(p==0||p->next==0)
return 0;
else return p->next->data;
}
template
LISTNODE*LIST::Find(const T&x)
{
LISTNODE*p=first->next;
while(p!=0&&p->data!=x)
p=p->next;
return p;
}
template
T LIST::GetData(const int i)const
{
LISTNODE*p=first->next;
int j=0;
while(p!=0&&j {
j++;
p=p->next;
}
if(p!=0&&j==i)
return p->data;
else return 0;
}
template
void LIST::CreateList()
{
T data;
cout<<"Please input the data:";
cin>>data;
LISTNODE *p=new LISTNODE(data);
p->next=first->next;
first->next=p;
last=p;
cout<<"please input the data:";
while(cin>>data)
{
LISTNODE *q=new LISTNODE(data);
q->next=first->next;
first->next=q;
cout<<"Please input the data:";
}
}
#endif

#include
#include "LIST.H"

template
LIST::LIST()
{
last=first=new LISTNODE(0);
}
template
LIST::LIST(const T&x)
{
last=first=new LISTNODE(x);
}
template
LIST::~LIST()
{
MakeEmpty();
delete first;
last=first=0;
}
template
void LIST::MakeEmpty()
{
LISTNODE *q;
while(first->next!=0)
{
q=first->next;
first->next=q->next;
delete q;
}
last=first;
}
template
bool LIST::Insert(const T& x,const int i)
{
LISTNODE*p=first;
int k=0;
int j=0;
while(p!=0&&k {
k++;
p=p->next;
}
if(p==0||i<1)
{
cerr<<"no this position"< return false;
}
else
{
LISTNODE*newnode=new LISTNODE(x);
newnode->next=p->next;
if(p->next==0)
last=newnode;
p->next=newnode;
}
return true;
}
template
int LIST::Length()const
{
LISTNODE*p=first->next;
int i=0;
while(p!=0)
{
p=p->next;
i++;
}
return i;
}
template
void LIST::Print()const
{
LISTNODE *p=first;
while(p!=0)
{
cout<data<<" ";
p=p->next;
}
cout<}
template
bool LIST::Remove(const int i)
{
LISTNODE*p=first,*q;
int j=0;
while(p->next!=0&&j {
j++;
p=p->next;
}
if(p->next==0||i<1)
{
cerr<<"no this position!"< return false;
}
else
{
q=p->next;
p->next=q->next;
if(p->next==0)
last=p;
delete q;
}
return true;
}
template
T LIST::GetPrivor(const T&x)const
{
LISTNODE*p=first;
while(p->next!=0&&p->next->data!=x)
p=p->next;
if(p->next==0||p==first)
return 0;
else return p->data;
}
template
T LIST::GetNext(const T&x)const
{
LISTNODE*p=first->next;
while(p!=0&&p->data!=x)
p=p->next;
if(p==0||p->next==0)
return 0;
else return p->next->data;
}
template
LISTNODE*LIST::Find(const T&x)
{
LISTNODE*p=first->next;
while(p!=0&&p->data!=x)
p=p->next;
return p;
}
template
T LIST::GetData(const int i)const
{
LISTNODE*p=first->next;
int j=0;
while(p!=0&&j {
j++;
p=p->next;
}
if(p!=0&&j=i)
return p->data;
else return 0;
}