C++单链表类型模板
<上一节
下一节>
单链表的概念和基本算法请点击这里:C++单链表的基本算法
分析:考虑单链表的特点及其基本操作,可以将每个节点归属成一个节点类,该类的一个对象就是一个节点,凡与节点数据(或指向节点的指针)操作有关函数作为节点类成员函数,包括生成新节点、在当前节点后插入节点、在当前节点后删除一个节点、……;
在节点类的基础上,再定义链表类,该类的一个对象就是一个单链表,操作包括生成(建立)有序链表、搜索遍历、插入、删除、取数据等;
template<typename T>class Node;//节点类声明
template<typename T>class List; //链表类声明
template<typename T>class Node
{
T info; //数据域
Node<T> *link; //指针域
public:
Node(); //生成头节点的构造函数
Node(const T & data); //生成一般节点
void InsertAfter(Node<T>* p); //在当前节点后插入一个节点
Node<T>* RemoveAfter(); //删除当前节点的后继节点
friend class List<T>; //以List为友元类,List可直接访问Node的私有成员
};//节点类模板声明结束
以下是节点类的成员函数的定义
template <typename T> Node<T>::Node()
{
link=NULL;
} //此节点的数据域不用,仅作头节点
template <typename T> Node<T>::Node(const T & data)
{
info=data; link=NULL;
} //设置当前节点
template<typename T> void Node<T>::InsertAfter(Node<T>* p)
{
p->link=link; link=p;
} //在当前节点后插入p
template<typename T> Node<T>* Node<T>::RemoveAfter()
{
Node<T>* tempP=link;
if(link==NULL)
tempP=NULL; //已在链尾,后面无节点
else
link=tempP->link;
return tempP; //从链中取出该节点并返回(可以作其他用)
}
//链表类声明,操作包括建立有序链表、搜索遍历、插入、删除、取数据等:
template<typename T>class List
{
Node<T> *head,*tail; //链表头、尾指针
public:
List(); //构造函数,生成头节点(空链表)
~List(); //析构函数
void MakeEmpty(); //清空一个链表,只余表头节点
Node<T>* Find(T data); //搜索数据域与data相同的节点,返回该节点的地址
int Length(); //计算单链表长度
void PrintList(); //打印链表的数据域
void InsertFront(Node<T>* p); //在当前链表前插入新节点(向前生成链表)
void InsertRear(Node<T>* p); //在当前链表后插入新节点(向后生成链表)
void InsertOrder(Node<T> *p); //按升序要求在当前链表中插入新节点
Node<T>*CreatNode(T data); //创建一个节点(孤立节点)
Node<T>*DeleteNode(Node<T>* p); //从当前链表中删除指定节点p并返回
};//链表类声明结束
以下是链表类成员函数的定义
template<typename T>List<T>::List()
{
head=tail=new Node<T>();
}//将调用Node类构造
template<typename T>List<T>::~List()
{
MakeEmpty();
delete head;
}
template<typename T>int List<T>::Length()
{
Node<T>* tempP=head->link;
int count=0;
while(tempP!=NULL)
{
tempP=tempP->link;
count++;
}
return count;
}//算不算head节点?
……
其他成员函数代码略,请参见【例7.5_h】和【例7.5】。
分析:考虑单链表的特点及其基本操作,可以将每个节点归属成一个节点类,该类的一个对象就是一个节点,凡与节点数据(或指向节点的指针)操作有关函数作为节点类成员函数,包括生成新节点、在当前节点后插入节点、在当前节点后删除一个节点、……;
在节点类的基础上,再定义链表类,该类的一个对象就是一个单链表,操作包括生成(建立)有序链表、搜索遍历、插入、删除、取数据等;
template<typename T>class Node;//节点类声明
template<typename T>class List; //链表类声明
template<typename T>class Node
{
T info; //数据域
Node<T> *link; //指针域
public:
Node(); //生成头节点的构造函数
Node(const T & data); //生成一般节点
void InsertAfter(Node<T>* p); //在当前节点后插入一个节点
Node<T>* RemoveAfter(); //删除当前节点的后继节点
friend class List<T>; //以List为友元类,List可直接访问Node的私有成员
};//节点类模板声明结束
以下是节点类的成员函数的定义
template <typename T> Node<T>::Node()
{
link=NULL;
} //此节点的数据域不用,仅作头节点
template <typename T> Node<T>::Node(const T & data)
{
info=data; link=NULL;
} //设置当前节点
template<typename T> void Node<T>::InsertAfter(Node<T>* p)
{
p->link=link; link=p;
} //在当前节点后插入p
template<typename T> Node<T>* Node<T>::RemoveAfter()
{
Node<T>* tempP=link;
if(link==NULL)
tempP=NULL; //已在链尾,后面无节点
else
link=tempP->link;
return tempP; //从链中取出该节点并返回(可以作其他用)
}
//链表类声明,操作包括建立有序链表、搜索遍历、插入、删除、取数据等:
template<typename T>class List
{
Node<T> *head,*tail; //链表头、尾指针
public:
List(); //构造函数,生成头节点(空链表)
~List(); //析构函数
void MakeEmpty(); //清空一个链表,只余表头节点
Node<T>* Find(T data); //搜索数据域与data相同的节点,返回该节点的地址
int Length(); //计算单链表长度
void PrintList(); //打印链表的数据域
void InsertFront(Node<T>* p); //在当前链表前插入新节点(向前生成链表)
void InsertRear(Node<T>* p); //在当前链表后插入新节点(向后生成链表)
void InsertOrder(Node<T> *p); //按升序要求在当前链表中插入新节点
Node<T>*CreatNode(T data); //创建一个节点(孤立节点)
Node<T>*DeleteNode(Node<T>* p); //从当前链表中删除指定节点p并返回
};//链表类声明结束
以下是链表类成员函数的定义
template<typename T>List<T>::List()
{
head=tail=new Node<T>();
}//将调用Node类构造
template<typename T>List<T>::~List()
{
MakeEmpty();
delete head;
}
template<typename T>int List<T>::Length()
{
Node<T>* tempP=head->link;
int count=0;
while(tempP!=NULL)
{
tempP=tempP->link;
count++;
}
return count;
}//算不算head节点?
……
其他成员函数代码略,请参见【例7.5_h】和【例7.5】。
<上一节
下一节>