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

//head 是头节点,本身的link指向自己,first指向第一个真实的存储数据的节点
//头节点的初始化在构造函数中已经实现,但插入第一个节点是不知如何插入,还是头节点那样初始化根本就不对?
//在Chain类中只有first和head两个指针的情况下能否实现单向循环链表?
//请高手帮忙修改Insert(),其他的函数也帮忙改改,不胜感激
#include<iostream.h>
#include<stdlib.h>
/////////////////类定义//////////////////
template <class T>
class Chain;
template <class T>
class ChainNode
{
friend Chain<T>;
private:
T data;
ChainNode<T> *link;
};
template<class T>
class Chain
{
public:
Chain()
{
head=new ChainNode<T>;
head->link=first;
head->data=0;//head是不存储数据的头节点，头节点的LINK指向自己
}
~Chain();
Chain<T>& Insert(int k,const T&x);
void Output(ostream& out) const;
private:
ChainNode<T> *first,*head;//first是指向第一个真实数据的节点
};

//////////////析构函数///////////////////
template<class T>
Chain<T>::~Chain()
{
ChainNode<T> *next;
while(first)
{
next=first->link;
delete first;
first=next;
}
}
//////////////输出//////////////
template<class T>
void Chain<T>::Output(ostream& out) const
{
ChainNode<T> *current;
int index=0;
for(current=first;index<10;current=current->link)//输入3个数据，循环输出10个
{
out<<current->data<<" ";
index++;
}
}
template<class T>
ostream& operator<<(ostream& out,const Chain<T>& x)
{
x.Output(out);return out;
}
//////////////插入//////
template<class T>
Chain<T>& Chain<T>::Insert(int k,const T& x)
{
if(k<0) {cout<<"Error!";exit(1);}
ChainNode<T> *p=first;
for(int index=1;index<k&&p;index++)
p=p->link;
if(k>0&&!p) {cout<<"Error!";exit(1);}
ChainNode<T> *y=new ChainNode<T>;
y->data=x;
if(k)
{
y->link=p->link;
p->link=y;
}
else
{
//头节点如何插入
}
return *this;
}

////////////////主函数、测试/////////////////
void main()
{
Chain<int> L;
int ll;
cout<<L<<endl;
for(int i=0;i<3;i++)
{
cin>>ll;
L.Insert(i,ll);
}
cout<<"List is"<<L<<endl;
}
head 和first好像弄反了，head 是第一个存储真实数据的节点，first是不存储数据的头节点。
构造函数改为
Chain()
{
first=new ChainNode<T>;
first->link=first;
first->data=0;//first是不存储数据的头节点，头节点的LINK指向自己
}

举报该问题

推荐答案推荐于2016-09-28

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

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

#include "stdio.h"
#include<iostream>
//#include<stdlib>
using namespace std;

template <class T>
class Chain;
template <class T>
class ChainNode
{
friend Chain<T>;
private:
T data;
ChainNode<T> *link;
};
template<class T>
class Chain
{
public:
Chain()
{
head=new ChainNode<T>;//头节点
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<T>& Delete(int k,T&x);
Chain<T>& Insert(int k,const T&x);
void Output(ostream& out) const;
private:
ChainNode<T> *first;//指向第一个真实节点的指针
ChainNode<T> *head;//表头指针
ChainNode<T> *tail;//表尾指针
};

//////////////析构函数///////////////////
template<class T>
Chain<T>::~Chain()
{
ChainNode<T> *next;
while(first!=tail)
{
next=first->link;
delete first;
first=next;
}
delete head;
}
//////////////输出//////////////
template<class T>
void Chain<T>::Output(ostream& out)const
{
ChainNode<T> *current;
int num=0;
for(current=first;current!=tail;current=current->link)
{
out<<current->data<<" ";
num++;
if(num%10==0)
cout<<endl;
}
}
template<class T>
ostream& operator<<(ostream& out,const Chain<T>& x)
{
x.Output(out);return out;
}
///////////删除/////////////////
template<class T>
Chain<T>& Chain<T>::Delete(int k,T& x) //这个x何用？
{
if(k<1||first==tail) {cout<<"Error!";exit(1);}
ChainNode<T> *p=first;
if(k==1)
{
first=first->link;
head->link=first->link;
}
else
{
ChainNode<T> *q=first;
for(int index=1;index<k-1&&(q!=tail);index++)
q=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<class T>
Chain<T>& Chain<T>::Insert(int k,const T& x)
{
if(k<0) {cout<<"Error!";exit(1);}
ChainNode<T> *p=first;
for(int index=1;index<k&&(p!=tail);index++) //p不会为NULL
p=p->link;
if(k>0&&(p==tail)) {cout<<"Error!";exit(1);}
ChainNode<T> *y=new ChainNode<T>;
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<int> cn;
for(int i=0;i<100;i++)
{
cn.Insert(i,i);

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

}

参考资料：http://zhidao.baidu.com/question/72616983.html

温馨提示：答案为网友推荐，仅供参考

当前网址：http://88.wendadaohang.com/zd/cg1B1MVM.html

其他回答

第1个回答 2008-10-22

风格有点不一样
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;
}
}

第2个回答 2008-10-22

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

#include <stdio.h>
#include <iostream>
using namespace std;

template <class T>
class Chain;
template <class T>
class ChainNode
{
friend Chain<T>;
private:
T data;
ChainNode<T> *link;
};
template<class T>
class Chain
{
public:
Chain()
{
head=new ChainNode<T>;//头节点
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<T>& Delete(int k,T&x);
Chain<T>& Insert(int k,const T&x);
void Output(ostream& out) const;
private:
ChainNode<T> *first;//指向第一个真实节点的指针
ChainNode<T> *head;//表头指针
ChainNode<T> *tail;//表尾指针
};

//////////////析构函数///////////////////
template<class T>
Chain<T>::~Chain()
{
ChainNode<T> *next;
while(first!=tail)
{
next=first->link;
delete first;
first=next;
}
delete head;
}
//////////////输出//////////////
template<class T>
void Chain<T>::Output(ostream& out)const
{
ChainNode<T> *current;
int num=0;
for(current=first;current!=tail;current=current->link)
{
out<<current->data<<" ";
num++;
if(num%10==0)
cout<<endl;
}
}
template<class T>
ostream& operator<<(ostream& out,const Chain<T>& x)
{
x.Output(out);return out;
}
///////////删除/////////////////
template<class T>
Chain<T>& Chain<T>::Delete(int k,T& x) //这个x何用？
{
if(k<1||first==tail) {cout<<"Error!";exit(1);}
ChainNode<T> *p=first;
if(k==1)
{
first=first->link;
head->link=first->link;
}
else
{
ChainNode<T> *q=first;
for(int index=1;index<k-1&&(q!=tail);index++)
q=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<class T>
Chain<T>& Chain<T>::Insert(int k,const T& x)
{
if(k<0) {cout<<"Error!";exit(1);}
ChainNode<T> *p=first;
for(int index=1;index<k&&(p!=tail);index++) //p不会为NULL
p=p->link;
if(k>0&&(p==tail)) {cout<<"Error!";exit(1);}
ChainNode<T> *y=new ChainNode<T>;
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<int> cn;
for(int i=0;i<100;i++)
{
cn.Insert(i,i);

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

参考资料：http://zhidao.baidu.com/question/72616983.html

第3个回答 2008-10-22

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

第4个回答 2008-10-22

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

#ifndef LIST_H
#define LIST_H
#include <iostream.h>
#include "LISTNODE.H"

template<class T>
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<T>*Find(const T&x);
void SetData(const T&x){first->data=x;}
void CreateList();
private:
LISTNODE<T>*first,*last;

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

#include<iostream.h>
#include "LIST.H"

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

1 2 下一页

相似回答

用C++实现含头结点的单链表,然后实现单链表的两个结点交换位置答：p->nextnode=q->nextnode;q->sno=tnode->sno; //把保存的临时节点重新存入目标节点实现交换 q->data=tnode->data;q->nextnode=tnode->nextnode;} 注:由于是单向链表,所以交换前必须从表头查起,查到源节点和目标节点两者各自的前一个节点,并修改这两个节点的指针批向新的位置,以上只是一...

将若干城市的信息,存入一个带头结点的单链表。结点中的城市信息包括:城 ...答：include <math.h> include<conio.h> include<string> using namespace std;struct Node { char Name[20];double x,y;Node *next;};class List { private:Node *head,*f;int size;public:List();void Insert();void Delete();void Search();void update();void init();void cha();void ...

输入一组整数,建立带头结点的单链表,并实现线性表的求长度、插入和删除...答：cout<<"请输入需要插入的数:";cin>>newValue;p=new Node; //创建需要插入的结点 p->Value = newValue;p->next = NULL;if(d == NULL) //如果链表为空，直接插在头结点后面 s->next = p;else { //不为空链表则循环 while(1){ ...

求1个C++链式链表的程序答：List是一个比较简单的单向链表类，拥有插入删除等基本功能。Node是结点类，只在List中用到。我加了比较详细的注释，相信你能看的懂：）include <iostream> //结点类 class Node { //申明List为友元 friend class List;private://构造函数设为私有，只有友元可以调用 Node(int data = 0, Node* p...

用C++语言的类的单链表如何实现答：1、数据域：用来存储本身数据 2、链域或称为指针域：用来存储下一个结点地址或者说指向其直接后继的指针。例：typedef struct node { char name[20];struct node *link;}stud;这样就定义了一个单链表的结构，其中char name[20]是一个用来存储姓名的字符型数组，指针*link是一个用来存储其直接后继...

c++使用单向循环链表结构实现循环队列。答：using namespace std;struct Node { int data;Node *next;};class List { public:List();~List();List(List&rhs);List &operator=(List&);int operator >>(int x);//让>>从尾部输入x int operator <<(int x);//让<<删除x virtual void push(int x);void push(int x,int idx);v...

试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。下面各...答：p指向带数据的第一个结点while(p){//如果p非空，i长度加1，且指向下一个结点p=p->next;i++;} return i;//返回i，即链表的长度}。从键盘直接读入字符而不用等RETURN键的方法在某个级别, 与键盘的交互输入一般上都是由系统取得一行的输入才提供给需要的程序。这给操作系统提供了一个加入行...

在以L为头结点的单链表的第i个位置插入值为e的结点。用c++实现,求源...答：include<iostream>using namespace std;struct node { int a; node * next; };int n; //链表节点数node * creat() { struct node * L; struct node * p1; n=0; L= new node; p1= new node;cout<<"请输入整数并回车，输入0，并回车结束输入！"<<endl;cin>>p1->a; L-...

大家正在搜

不带头节点的循环单向链表假设带头节点的单向循环链表带头节点的双向循环链表在带头节点的循环链表l中不带头节点的循环链表假设以带头节点的循环链表不带头节点的单链表带头节点双循环链表带头指针的单循环链表