您所在位置：主题：链表的类实现 ,请大家帮我改错...谢谢!!1
yeliyun
[专家分：0] 发布于 2006-10-20 13:09:00
#include <iostream.h>
template <class Type>class List;
template <class Type>
class ListNode {//链表结点类的定义
friend class List<Type>; //List类作为友元类定义
public:
ListNode ( ){}; //不给数据的构造函数
ListNode ( const Type& item ) ; //给数据的构造函数
ListNode ( const Type& item, ListNode<Type>* next );
ListNode<Type> *NextNode ( ) { return next; } //给出当前结点的下一个结点地址
void InsertAfter ( ListNode<Type> *p ); //当前结点插入
ListNode<Type> *GetNode ( const Type& item, ListNode<Type> *next ); //建立一个新结点
ListNode<Type> *RemoveAfter ( ); //删除当前结点的下一结点
private:
Type data; //数据域
ListNode<Type> *link; //链指针域
};
template <class Type>
class List { //单链表类定义
public:
List ( ) { last =first = new ListNode<Type> ( ); } //构造函数, 建立一个空链表
~List ( ); //析构函数
void MakeEmpty ( ); //将链表置为空表
int Length ( ) ; //计算链表的长度
void InsertLast( ListNode<Type> *&first,const Type&item ); //寻找表尾，在其后加值
void Insertfront( ListNode<Type> *&first,const Type&item ); //往表头加结点
ListNode<Type> *FindValue ( Type value ); //在链表中搜索含数据value的结点
ListNode<Type> *FindPosition ( int i ); //搜索链表中第i个元素的地址
int Insert ( Type value, int i ); //将新元素value插入在链表中第i个位置
Type *Remove ( int i ); //将链表中的第i个元素删去
Type *Get ( int i ); //取出链表中第i个元素
void Print(ListNode<Type> first);
private:
ListNode<Type> *first, *last; //链表的表头指针, 表尾指针
};
//以下为类模板的实现
template<class Type >//给数据的构造函数
ListNode <Type>::ListNode ( const Type& item )
{ item=data;}
template<class Type >//给数据的构造函数
ListNode <Type>::ListNode ( const Type& item, ListNode<Type>* next )
{
item=data;
next=link;
}
template<class Type >
void ListNode <Type>:: InsertAfter ( ListNode<Type> *p ) //当前结点插入
{ //p指向当前结点的后继结点，然后将当前结点指向p;
p->next=next;
next=p;
}
template<class Type >
ListNode<Type> ListNode <Type>::*GetNode ( const Type& item, ListNode<Type> *next )
//建立一个新结点成员函数
{
ListNode<Type> *next=NULL;
ListNode *temp=new ListNode ;
//向堆内存申请一个结点的内存空间
temp=new ListNode <Type> (item,next);
if(temp==Null)
{cout<<"Memory allocation failure!"<<endl;
exit(1);}
return temp;
}
template<class Type >
ListNode<Type> ListNode<Type> ::*RemoveAfter ( ) //删除当前结点的下一结点
{
//保存指向被删除结点的指针
ListNode <Type> *p=next;
//若没有后继结点，返回NULL
if(next==NULL)
ruturn NULL;
//使当前结点指向p的后继结点
next=p->next;
//返回被删除结点的指针
return p;
}
template<class Type >
int List <Type>::Insert ( Type value, int i )
//将新元素value插入在链表中第i个位置
{ int newLength=Length();
if((i<)||(i>newLength))
cout<<"out of range"<<endl;
else
{
ListNode *newPtr=new ListNode ;
//向堆内存申请一个结点的内存空间
if(newPtr==NULL)
cout<<"insert cannot allocate memory"<<endl;
else
{
newPtr=ListNode<Type>*GetNode ( const Type& item, ListNode<Type> *next );
newPtr->data=value;
int sum=0;
for(ListNode * s=first;s->next;s=s->next)
{ sum++;
if(sum==(i-1))
{
newPtr->next= s->next;
s->next=newPtr;
}
break;
}
}
}
}
template<class Type>
List<Type>::~List()
//定义链表类的析构函数
{
while(first!=NULL)
//删除链表中所有结点，释放结点数据所空间
{ListNode<Type> * p;
p=first;
//first=first->next;
delete p;
}
}
template<class Type >
void List <Type>:: MakeEmpty ( )
{
//将链表置为空表
for(ListNode * s=first;s->next;s=s->next)
s->data=NULL;
}
template<class Type >
Type List <Type>::*Get ( int i )
//取出链表中第i个元素
{
Type m;
int sum=0;
for(ListNode * s=first;s->next;s=s->next)
{ sum++;
if (sum==i)
{
m=s->item;
cout<<"链表中第"<<i<<"个元素"<<"是"<<endl;
cout<<m<<endl;
break;
}
}
}
template<class Type >
ListNode<Type> List <Type>:: *FindPosition ( int i )
//搜索链表中第i个元素的地址
{
int sum=0;
for(ListNode * s=first;s->next;s=s->next)
{ sum++;
if (sum==(i-1))
{
cout<<"第"<<i<<"个元素的地址是"<<s->next<<endl;
}
break;
}
}
template<class Type >
int List <Type>:: Length ( )
//计算链表的长度
{
int sum=0;
for(ListNode * s=first;s->next;s=s->next)
sum++;
cout<<"该链表的长度是："<<sum<<endl;
}
template <class Type >
Type List<Type>::*Remove ( int i )
//定义删除节点的成员函数
{
ListNode *q=0;
if (*(first->next)==i)
//判断要删除的节点是否是头节点，如是，链首指针指向下一个节点，把第一个节点脱链
{
q=first;
first=first->next;
}
else
//顺链查找
{
for(ListNode * p=first;p->next;p=p->next)
if (*(p->next->next)==i)
//链中待删结点前后的两个结点链接起来，以使待删结点脱链
{
q=p->next;
p->next=q->next;
break;
}
}
if(q){
delete q->next;
//删除待删结点上的Type类的对象
delete q;
//删除待删结点
}
}
template <class Type >
ListNode<Type> List<Type>:: *FindValue ( Type value )
//在链表中搜索含数据value的结点
{
Type da;
int position=0;
for(ListNode * s=first;s->next;s=s->next)
{
if (s->data==value)
//链中待删结点前后的两个结点链接起来，以使待删结点脱链
{
da=value;
cout<<value<<"是"<<"第"<<position<<"个结点"<<endl;
break;
}
position++;
}}
template <class Type >
void List<Type>::Insertfront( ListNode<Type> *&first,const Type&item ) //往表头加结点
{//申请新结点，并使其指向原表头，再修改原表头
first=GetNode(item,first);}
template <class Type >
void List<Type>::InsertLast( ListNode<Type> * & first,const Type &item ) //寻找表尾，在其后加值
{
ListNode<Type> *currPtr=first, *newNode;
if(currPtr==NULL)//若表为空，则在表头插入item
Insertfront(first,item);
else
{
while (currPtr->NextNode()!=NULL) //找到指针指向NULL的结点
currPtr=currPtr->NextNode(); //创建新结点并插入到表尾
// newNode=GetNode(item);
// currPtr->InserAfter(newNode);
}
}
template <class Type >
void List<Type>::Print(ListNode<Type> first)
{
ListNode<Type> *currPtr=first;
//用指针currPtr从表头开始遍历
while(currPtr!=NULL)
{
cout<<currPtr->data<<" ";
currPtr= currPtr->NextNode();
}
}
void main()
{
//List <float> floatList;
//将List实例化，并创建对象floatList
List <int> intList;
//将List实例化，并创建对象intList
ListNode<int> *head=NULL, *currPtr=NULL;
int i ,count=0;
for(i=0;i<10;i++)
{ intList.InsertLast(head,i);}//初始化
intList.InsertLast(head,i);
intList.Print(intList.*FindValue ( Type value )); //在链表中搜索含数据3的结点
// intList.Insert( 5, 1 );
// float *i=floatList.Get (0);
// cout<<i<<endl;
// ListNode<float> *p=floatList.FindPosition (0);
/*
for(int i=1;i<7;i++)
{
floatList.InsertAfter (* new float(i+0.6));
// 调用成员函数InsertAfter
intList.InsertAfter (* new int(i));
// 调用成员函数InsertAfter
}
*/
//floatList.Print ();
/*
float b=3.6;
float * pf=floatList.FindPosition(b);
// 调用成员函数FindPosition()
if(pf)
floatList.Remove(* pf);
// 调用成员函数Remove()
int c=3;
int * pi=intList.FindPosition (c);
// 调用成员函数FindPosition ()
if(pi)
intList.Remove(*pi);
// 调用成员函数Remove()
*/
}
template <class Type>class List;
template <class Type>
class ListNode {//链表结点类的定义
friend class List<Type>; //List类作为友元类定义
public:
ListNode ( ){}; //不给数据的构造函数
ListNode ( const Type& item ) ; //给数据的构造函数
ListNode ( const Type& item, ListNode<Type>* next );
ListNode<Type> *NextNode ( ) { return next; } //给出当前结点的下一个结点地址
void InsertAfter ( ListNode<Type> *p ); //当前结点插入
ListNode<Type> *GetNode ( const Type& item, ListNode<Type> *next ); //建立一个新结点
ListNode<Type> *RemoveAfter ( ); //删除当前结点的下一结点
private:
Type data; //数据域
ListNode<Type> *link; //链指针域
};
template <class Type>
class List { //单链表类定义
public:
List ( ) { last =first = new ListNode<Type> ( ); } //构造函数, 建立一个空链表
~List ( ); //析构函数
void MakeEmpty ( ); //将链表置为空表
int Length ( ) ; //计算链表的长度
void InsertLast( ListNode<Type> *&first,const Type&item ); //寻找表尾，在其后加值
void Insertfront( ListNode<Type> *&first,const Type&item ); //往表头加结点
ListNode<Type> *FindValue ( Type value ); //在链表中搜索含数据value的结点
ListNode<Type> *FindPosition ( int i ); //搜索链表中第i个元素的地址
int Insert ( Type value, int i ); //将新元素value插入在链表中第i个位置
Type *Remove ( int i ); //将链表中的第i个元素删去
Type *Get ( int i ); //取出链表中第i个元素
void Print(ListNode<Type> first);
private:
ListNode<Type> *first, *last; //链表的表头指针, 表尾指针
};
//以下为类模板的实现
template<class Type >//给数据的构造函数
ListNode <Type>::ListNode ( const Type& item )
{ item=data;}
template<class Type >//给数据的构造函数
ListNode <Type>::ListNode ( const Type& item, ListNode<Type>* next )
{
item=data;
next=link;
}
template<class Type >
void ListNode <Type>:: InsertAfter ( ListNode<Type> *p ) //当前结点插入
{ //p指向当前结点的后继结点，然后将当前结点指向p;
p->next=next;
next=p;
}
template<class Type >
ListNode<Type> ListNode <Type>::*GetNode ( const Type& item, ListNode<Type> *next )
//建立一个新结点成员函数
{
ListNode<Type> *next=NULL;
ListNode *temp=new ListNode ;
//向堆内存申请一个结点的内存空间
temp=new ListNode <Type> (item,next);
if(temp==Null)
{cout<<"Memory allocation failure!"<<endl;
exit(1);}
return temp;
}
template<class Type >
ListNode<Type> ListNode<Type> ::*RemoveAfter ( ) //删除当前结点的下一结点
{
//保存指向被删除结点的指针
ListNode <Type> *p=next;
//若没有后继结点，返回NULL
if(next==NULL)
ruturn NULL;
//使当前结点指向p的后继结点
next=p->next;
//返回被删除结点的指针
return p;
}
template<class Type >
int List <Type>::Insert ( Type value, int i )
//将新元素value插入在链表中第i个位置
{ int newLength=Length();
if((i<)||(i>newLength))
cout<<"out of range"<<endl;
else
{
ListNode *newPtr=new ListNode ;
//向堆内存申请一个结点的内存空间
if(newPtr==NULL)
cout<<"insert cannot allocate memory"<<endl;
else
{
newPtr=ListNode<Type>*GetNode ( const Type& item, ListNode<Type> *next );
newPtr->data=value;
int sum=0;
for(ListNode * s=first;s->next;s=s->next)
{ sum++;
if(sum==(i-1))
{
newPtr->next= s->next;
s->next=newPtr;
}
break;
}
}
}
}
template<class Type>
List<Type>::~List()
//定义链表类的析构函数
{
while(first!=NULL)
//删除链表中所有结点，释放结点数据所空间
{ListNode<Type> * p;
p=first;
//first=first->next;
delete p;
}
}
template<class Type >
void List <Type>:: MakeEmpty ( )
{
//将链表置为空表
for(ListNode * s=first;s->next;s=s->next)
s->data=NULL;
}
template<class Type >
Type List <Type>::*Get ( int i )
//取出链表中第i个元素
{
Type m;
int sum=0;
for(ListNode * s=first;s->next;s=s->next)
{ sum++;
if (sum==i)
{
m=s->item;
cout<<"链表中第"<<i<<"个元素"<<"是"<<endl;
cout<<m<<endl;
break;
}
}
}
template<class Type >
ListNode<Type> List <Type>:: *FindPosition ( int i )
//搜索链表中第i个元素的地址
{
int sum=0;
for(ListNode * s=first;s->next;s=s->next)
{ sum++;
if (sum==(i-1))
{
cout<<"第"<<i<<"个元素的地址是"<<s->next<<endl;
}
break;
}
}
template<class Type >
int List <Type>:: Length ( )
//计算链表的长度
{
int sum=0;
for(ListNode * s=first;s->next;s=s->next)
sum++;
cout<<"该链表的长度是："<<sum<<endl;
}
template <class Type >
Type List<Type>::*Remove ( int i )
//定义删除节点的成员函数
{
ListNode *q=0;
if (*(first->next)==i)
//判断要删除的节点是否是头节点，如是，链首指针指向下一个节点，把第一个节点脱链
{
q=first;
first=first->next;
}
else
//顺链查找
{
for(ListNode * p=first;p->next;p=p->next)
if (*(p->next->next)==i)
//链中待删结点前后的两个结点链接起来，以使待删结点脱链
{
q=p->next;
p->next=q->next;
break;
}
}
if(q){
delete q->next;
//删除待删结点上的Type类的对象
delete q;
//删除待删结点
}
}
template <class Type >
ListNode<Type> List<Type>:: *FindValue ( Type value )
//在链表中搜索含数据value的结点
{
Type da;
int position=0;
for(ListNode * s=first;s->next;s=s->next)
{
if (s->data==value)
//链中待删结点前后的两个结点链接起来，以使待删结点脱链
{
da=value;
cout<<value<<"是"<<"第"<<position<<"个结点"<<endl;
break;
}
position++;
}}
template <class Type >
void List<Type>::Insertfront( ListNode<Type> *&first,const Type&item ) //往表头加结点
{//申请新结点，并使其指向原表头，再修改原表头
first=GetNode(item,first);}
template <class Type >
void List<Type>::InsertLast( ListNode<Type> * & first,const Type &item ) //寻找表尾，在其后加值
{
ListNode<Type> *currPtr=first, *newNode;
if(currPtr==NULL)//若表为空，则在表头插入item
Insertfront(first,item);
else
{
while (currPtr->NextNode()!=NULL) //找到指针指向NULL的结点
currPtr=currPtr->NextNode(); //创建新结点并插入到表尾
// newNode=GetNode(item);
// currPtr->InserAfter(newNode);
}
}
template <class Type >
void List<Type>::Print(ListNode<Type> first)
{
ListNode<Type> *currPtr=first;
//用指针currPtr从表头开始遍历
while(currPtr!=NULL)
{
cout<<currPtr->data<<" ";
currPtr= currPtr->NextNode();
}
}
void main()
{
//List <float> floatList;
//将List实例化，并创建对象floatList
List <int> intList;
//将List实例化，并创建对象intList
ListNode<int> *head=NULL, *currPtr=NULL;
int i ,count=0;
for(i=0;i<10;i++)
{ intList.InsertLast(head,i);}//初始化
intList.InsertLast(head,i);
intList.Print(intList.*FindValue ( Type value )); //在链表中搜索含数据3的结点
// intList.Insert( 5, 1 );
// float *i=floatList.Get (0);
// cout<<i<<endl;
// ListNode<float> *p=floatList.FindPosition (0);
/*
for(int i=1;i<7;i++)
{
floatList.InsertAfter (* new float(i+0.6));
// 调用成员函数InsertAfter
intList.InsertAfter (* new int(i));
// 调用成员函数InsertAfter
}
*/
//floatList.Print ();
/*
float b=3.6;
float * pf=floatList.FindPosition(b);
// 调用成员函数FindPosition()
if(pf)
floatList.Remove(* pf);
// 调用成员函数Remove()
int c=3;
int * pi=intList.FindPosition (c);
// 调用成员函数FindPosition ()
if(pi)
intList.Remove(*pi);
// 调用成员函数Remove()
*/
}