第 21 讲 模板应用举例
教学目的与要求：
了解各类模板的特征 。
掌握栈,队列,链表的应用 。
教学内容提要：
1,栈类模板；
2,队列类模板；
2,链表类模板；
教学重点,链表类的声明和使用 。
教学难点：链表类的声明和使用 。
教学进度,P228～ P238
教学过程：
栈顶
┆
an
┆
a1
a0
入栈 出栈数组下标
max
n
1
0
一般状态栈顶入栈 出栈数组下标初始状态（栈空）
max
n
1
0
栈顶amax┆
an
┆
a1
a0
入栈 出栈数组下标 max
n
1
0
栈满状态
21.1 栈类模板例 21.1 使用栈类模板的使用 。
#include<iostream.h>
const int size=10;
template<class Type> //声明一个类模板
class stack{
public:
void init(){ tos=0; }
void push(Type ch); //参数取 Type类型
Type pop(); //返回类型取 Type类型
private:
Type stck[size]; //数组的类型为类型参数 Type，
即可取任意类型
int tos; };
template <class Type>
void stack<Type>::push(Type ob)
{ if (tos==size){ cout<<"stack is full"; return ; }
stck[tos]=ob; tos++; }
template <class Type>
Type stack <Type>::pop()
{
if (tos==0)
{
cout<<"stack is empty";
return 0;
}
tos--;
return stck[tos];
}
main()
{
//定义字符堆栈
stack <char> s1,s2; //创建两个模板参数为 char型的对象
int i;
s1.init(); s2.init();
s1.push('a'); s2.push('x');
s1.push('b'); s2.push('y');
s1.push('c'); s2.push('z');
for(i=0;i<3;i++) cout<<"pop s1,"<<s1.pop()<<endl;
for(i=0;i<3;i++) cout<<"pop s2,"<<s2.pop()<<endl;
//定义整型堆栈
stack <int> is1,is2; //创建两个模板参数为 int型的对象
is1.init(); is2.init();
is1.push(1); is2.push(2);
is1.push(3); is2.push(4);
is1.push(5); is2.push(6);
for (i=0;i<3;i++)
cout<<"pop is1,"<<is1.pop()<<endl;
for (i=0;i<3;i++)
cout<<"pop is2,"<<is2.pop()<<endl;
return 0;
}
21.2队列类模板队列与栈不同，对数据采用,先进先出,--FIFO的管理方式（而栈则使用,先进后出,--FILO方式）。
队列数据放于作为类成员的动态数组 queue之中，在构造函数中，将通过 new来生成该动态数组，动态数组 queue的大小由类的私有数据成员 Maxsize之值来确定。但注意，此示例并没有循环使用上述的动态数组 queue空间。即是说，
队列中至多可以存放 Maxsize个数据项，即使取走若干项后有了空闲空间后也不可重新进行使用。若稍加改造，使存取数据时首先通过对下标进行模 Maxsize的运算，则可实现循环使用动态数组 queue空间的功能。
a1 a2 an-1 an……
队头 队尾入队出队 a0
#include <iostream.h>
#include <process.h>
template <class keytype>
class Queue {
int Maxsize; //队列的大小
int front,rear; //元素放在 queue[front+1]到 queue[rear]之中
keytype *queue; //动态数组 queue，用来存放队列数据
public:
Queue (int size) { //构造函数，生成动态数组来存放队列数据
Maxsize=size;
queue=new keytype[Maxsize];
front=rear=-1; //意味着队列为空
};
int IsFull () {
if (rear==Maxsize-1)
return 1;
else
return 0;
};
int IsEmpty () {
if (front==rear)
return 1;
else
return 0;
};
void Add(const keytype &);
keytype Delete(void);
};
//Delete在类体外定义，函数名前要加类限定符,Queue<keytype>::”
template <class keytype> keytype Queue<keytype>::Delete(void){
if (IsEmpty()){
cout << "the queue is empty"<<endl;
exit (0);
}
return queue [++front];
}
//Add在类体外定义
template <class keytype> void Queue<keytype>::Add(const keytype & item){
if (IsFull())
cout << "the queue is full"<<endl;
else
queue[++rear]=item;
};
void main() {
int i=0; Queue<int> Qi(10);
Queue<double> Qf1(10),Qf2(10);
while (!Qi.IsFull()) { //Qi中只能盛 10个数
Qi.Add(2*i++); //Qi中,0,2,4,6,8,10,12,14,16,18
Qf1.Add(3.0*i); //Qf1中,3,6,9,12,15,18,21,24,27,30
}
for (i=0; i<4; i++){ //四次循环，每次总
//先往 Qf2的队列尾部加入两个数，而后又从首部删取一个数并输出
Qf2.Add(4.5*Qi.Delete());
//从 Qi首删取一元素，乘以 4.5，而后将其加入到 Qf2尾部
//四次循环往 Qf2队列尾加入,0*4.5,2*4.5,4*4.5,6*4.5
...
}
}
程序执行后的显示结果如下：
0
1.5
9
3
通过模板类定义，可以解决代码冗繁问题：
template<class T>
class Node{
public:
Node(const T& d):c(d),
next(0),pref(0){}
T c;
Node *next,*pref;
};
又例如下面的模板类定义，含有模板类的成 员：
template<class T>
class List{
Node<T> *first,*last;
public:
List();
void add(const T& c);
void remove(const T& c);
Node<T>* find(const T& c)const;
void print()const;
~List();
};
用类模板实现通用链表类。将链表类结点的数据类型参数化，构成了一个通用模板，可以用来生成结点数据为任意类型的链表。
【 21.3 链表类 】
通用链表类
#include <iostream.h>
#include <stdlib.h>
template<class T>
class ListNode //结点类
{
public:
ListNode(){} //结点类构造函数
ListNode(const T& nItem,ListNode<T> *ptrNext=NULL); //结点类带参数构
//造函数
T& ShowDate(){return Date;} //返回本结点数据的引用
void InsertAfter(ListNode<T> *ptr); //插入新结点作为本结点的后续结点
ListNode<T> *DeleteAfter(void); //删除本结点的后续结点例 21.3
ListNode<T> *NextListNode() const; //获得本结点的后续结点的指针
void SetNext(ListNode<T> *ptr){ptrNext=ptr;} //设置本结点的后续结点指针
private:
T Date; //本结点的数据
ListNode<T> *ptrNext; //指向本结点的后续结点的指针
};
template <class T>
class LinkedList //链表类的声明及其实现
{
public:
LinkedList(void);
LinkedList(const LinkedList<T> &list); //拷贝构造函数
～ LinkedList(void){DeleteAll();} //析构函数,释放链表占用的资源
LinkedList<T> &operator=(const LinkedList<T> &list); // ″=″号运算符
//的重载
void Next();//指向链表的下一个结点
int EndOfList() const {return (!ptrCurr);} //判断链表当前位置是否是表尾
int CurrPosition() const {return nPosition;}//获得当前位置指针在链表中的位置
（续）
void InsertFront(const T& nItem); //将数据为 nItem的结点插入到链表头
void InsertTail(const T& nItem); //将数据为 nItem的结点插入到链表尾
void InsertAt(const T& nItem); //将数据为 nItem的结点插入到链表的当前位置
void InsertAfter(const T& nItem); //将数据为 nItem的结点插入到链表的当前
//位置之后
void InsertOrder(T nItem);
//将数据为 nItem的结点插入到排序链表中,并构成新的排序链表
int DeleteHead(); //删除链表头结点
void DeleteCurr(); //删除链表当前结点
void Delete(T key); //删除链表中数据为 key的结点
void DeleteAll(); //删除链表中的所有结点
T& GetDate(); //得到链表中的当前结点数据
void DisplayList(); //显示链表中所有结点的数据
int Find(T& nItem); //在链表中找到数据为 nItem的结点
int ListLength() const{return nListLength;}; //求链表的长度
int ListEmpty() const{return nListLength;} //判断链表是否为空
void Reset(int nPos=0); //重新设置链表的当前指针的位置 （续）
private:
ListNode<T> *ptrFront,//链表的头结点指针
*ptrTail,//链表的尾结点指针
*ptrPrev,//链表的当前结点的前一个结点的指针
*ptrCurr; //链表的当前结点指针
int nListLength; //链表的长度
int nPosition; //链表的当前结点指针的位置
ListNode<T> *GetListNode(const T &nItem,ListNode<T> *ptrNext=NULL);
//获得链表的下一个结点指针
void FreeListNode(ListNode<T> *ptr){delete ptr;} //释放结点资源
void CopyList(const LinkedList<T>& list); //逐项拷贝链表
};
#include <iostream.h>
（续）
//结点类带参数构造函数的实现
template<class T>
ListNode<T>::ListNode(const T& nItem,ListNode<T> *ptrNext):
Date(nItem),ptrNext(ptrNext)
{}
//返回指向后续结点的指针
template<class T>
ListNode<T> *ListNode<T>::NextListNode() const
{
return ptrNext;
}
template<class T>
void ListNode<T>::InsertAfter(ListNode<T> *ptr)
{
ptr->ptrNext=ptrNext; //将 ptr的 ptrNext指针指向本结点的后续结点
ptrNext=ptr;//本结点的 ptrNext指针指向 ptr
}
（续）
template<class T>
ListNode<T> *ListNode<T>::DeleteAfter()
{
ListNode<T> *ptrTemp=ptrNext;
if(ptrNext==NULL) //处理本结点为尾结点时的情况
return NULL;
ptrNext=ptrTemp->ptrNext; //一般情况
return ptrTemp;
}
//链表类构造函数,4个私有指针成员设置为空,链表初始长度设置为 0,初始当前结点
//初始位置为 -1
template<class T>
LinkedList<T>::LinkedList(void):ptrFront(NULL),ptrTail(NULL),
ptrPrev(NULL),ptrCurr(NULL),nListLength(0),nPosition(-1)
{ }
//重载 ″=″号运算符
template<class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& list)
{ （续）
if(this!=&list)
{
DeleteAll();
CopyList(list);
}
return *this;
}
//拷贝构造函数
template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& list)
{
CopyList(list);
}
//重新设置当前指针的位置
template<class T>
void LinkedList<T>::Reset(int nPos)
{
int nStartPos; （续）
if(!ptrFront) //如果当前指针为空,链表为空直接返回
{
return;
}
if(nPos>=nListLength||nPos<0) //位置越界检查
{
cerr<<″Invalid Position!″<<endl;
return;
}
if(nPos==0) //置当前指针为头结点
{
ptrPrev=NULL;
ptrCurr=ptrFront;
nPosition=0;
}
else //一般情况
{
ptrCurr=ptrFront->NextListNode();
ptrPrev=ptrFront;
nStartPos=1;
for(nPosition=nStartPos;nPosition!=nPos;nPosition++)
//寻找该位置并使当前指针指向该位置
（续）
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
}
}
//当前指针指向当前结点的后续结点
template<class T>
void LinkedList<T>::Next()
{
if(ptrCurr)
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
nPosition++;
}
}
//将数据为 nItem的结点插入到链表头
template<class T> （续）
void LinkedList<T>::InsertFront(const T& nItem)
{
ListNode<T> *newListNode=GetListNode(nItem); //获得一个封装有该数据
//的结点
newListNode->SetNext(ptrFront);
ptrFront=newListNode;
nListLength++;
}
//将数据为 nItem的结点插入到链表尾
template<class T>
void LinkedList<T>::InsertTail(const T& nItem)
{
ListNode<T> *newListNode;
if(ptrCurr==NULL) InsertFront(nItem); //若链表为空,使之成为头结点
//(也是尾结点 )
else //一般情况
{
while(ptrCurr->NextListNode()) //寻找尾结点
ptrCurr=ptrCurr->NextListNode(); （续）
newListNode=GetListNode(nItem);
ptrCurr->InsertAfter(newListNode);
}
}
//将数据为 nItem的结点插入到链表的当前位置之前
template<class T>
void LinkedList<T>::InsertAt(const T& nItem)
{
ListNode<T> *newListNode;
if(!ptrPrev) //插入到头结点
{
newListNode=GetListNode(nItem,ptrFront);
newListNode->SetNext(ptrFront);
ptrFront=newListNode;
nListLength++;
}
else //一般情况
{ （续）
newListNode=GetListNode(nItem);
ptrPrev->InsertAfter(newListNode);
}
if(ptrPrev==ptrTail)
{
ptrTail=newListNode;
nPosition=nListLength;
}
ptrCurr=newListNode;
}
//将数据为 nItem的结点插入到链表当前结点之后
template<class T>
void LinkedList<T>::InsertAfter(const T& nItem)
{
ListNode<T> *newListNode;
if(!ptrCurr) //处理空链表的情况
{ （续）
newListNode=GetListNode(nItem);
ptrCurr=newListNode;
ptrFront=ptrCurr;
}
else //一般情况
{
newListNode=GetListNode(nItem);
ptrCurr->InsertAfter(newListNode);
}
if(ptrPrev==ptrTail)
{
ptrTail=newListNode;
nPosition=nListLength;
}
ptrCurr=newListNode;
nListLength++;
}
//删除链表中的当前结点
template<class T>
void LinkedList<T>::DeleteCurr() （续）
{
ListNode<T> *ptr;
if(!ptrCurr) //处理空链表的情况
{
cerr<<″The List is empty!″<<endl;
exit(1);
}
if(!ptrPrev) //删除头结点的情况
{
ptr=ptrFront;
ptrFront=ptrFront->NextListNode();
}
else //一般情况
ptr=ptrPrev->DeleteAfter();
if(ptr==ptrTail)
{
ptrTail=ptrPrev;
nPosition--;
}
ptrCurr=ptr->NextListNode();
FreeListNode(ptr); （续）
nListLength--;
}
//删除链表中所有结点并释放资源
template<class T>
void LinkedList<T>::DeleteAll()
{
ListNode<T> *ptrCurrPos,
*ptrNextPos;
ptrCurrPos=ptrFront;
while(ptrCurrPos) //循环处理删除链表中的各个结点
{
ptrNextPos=ptrCurrPos->NextListNode();
FreeListNode(ptrCurrPos);
ptrCurrPos=ptrNextPos;
}
ptrFront=NULL;
ptrTail=NULL;
ptrPrev=NULL;
ptrCurr=NULL; （续）
nListLength=0;
nPosition=-1;
}
//删除链表的头结点
template<class T>
int LinkedList<T>::DeleteHead()
{
ListNode<T> *ptr=ptrFront;
if(ptrFront)
{
ptrFront=ptrFront->NextListNode();
delete ptr;
nListLength--;
return 1;
}
else //处理链表为空的情况
{
cout<<″The List is empty!″<<endl;
return 0;
}
}
（续）
//获得链表中当前结点的数据
template<class T>
T& LinkedList<T>::GetDate()
{
if(nListLength==0||!ptrCurr) //空链表的处理
{
cerr<<″Invalid!″<<endl;
exit(1);
}
return ptrCurr->ShowDate();
}
//逐项拷贝链表中的各个结点
template<class T>
void LinkedList<T>::CopyList(const LinkedList<T> &list)
{
ListNode<T> *ptr=list.ptrFront;
ptrCurr=NULL;
while(ptr) //遍历 list并创建新链表 （续）
{
InsertAfter(ptr->ShowDate());
ptr=ptr->NextListNode();
}
if(nPosition==-1) //list为空
return;
ptrPrev=NULL;
ptrCurr=ptrFront;
for(int nPos=0;nPos!=list.CurrPosition();nPos++)
//将新链表的各个数据成员设置与原链表相同
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
nPosition=nPos;
nListLength=list.ListLength();
}
（续）
//获得下一个新结点,返回新结点地址
template<class T>
ListNode<T> *LinkedList<T>::GetListNode(const T& nItem,ListNode<T> *preNext)
{
ListNode<T> *newListNode;
newListNode=new ListNode<T>(nItem,preNext);
if(!newListNode)
{
cerr<<″Memory allocation failure!″<<endl;
exit(1);
}
return newListNode;
}
//输出链表中的各个结点数据
template<class T>
void LinkedList<T>::DisplayList()
{
ptrCurr=ptrFront;
while(ptrCurr) //遍历链表
{
cout<<ptrCurr->ShowDate()<<endl; （续）
ptrCurr=ptrCurr->NextListNode();
}
}
//在链表中查找数据
template<class T>
int LinkedList<T>::Find(T& nItem)
{
ptrCurr=ptrFront;
ptrPrev=NULL;
while(ptrCurr)
{
if(ptrCurr->ShowDate()==nItem)
return 1;
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
return 0;
}
//删除链表中满足条件的结点
template<class T> （续）
void LinkedList<T>::Delete(T key)
{
ptrCurr=ptrFront;
ptrPrev=NULL;
if(!ptrCurr)
return;
while(ptrCurr&[KG-*4]&ptrCurr->ShowDate()!=key) //查找相应的结点
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
nPosition++;
}
if(ptrCurr) //如果找到该结点,删除它
{
if(!ptrPrev) ptrFront=ptrFront->NextListNode();
else ptrPrev->DeleteAfter();
delete ptrCurr;
}
}
//在排序链表中插入新结点构成新的排序链表 （续）
template<class T>
void LinkedList<T>::InsertOrder(T nItem)
{
ListNode<T> *newListNode,
*next,//用于遍历链表
*prev; //next指向结点的前一个结点的指针
ptrPrev=NULL;
ptrCurr=ptrFront;
prev=ptrCurr;
next=ptrCurr->NextListNode();
while((prev->ShowDate()==next->ShowDate())&[KG-*4]&(next))
//判断原链表的排序方式,升序或者降序
{
prev=next;
next=next->NextListNode();
}
if(!next) InsertFront(nItem); //如果原链表中所有结点均相等,则将结点
//作为原链表的首结点
else if(prev->ShowDate()>next->ShowDate()) //降序排列时
{ （续）
while(ptrCurr) //寻找插入位置
{
if(nItem>=ptrCurr->ShowDate()) break;
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
if(!ptrPrev) InsertFront(nItem);
else
{
newListNode=GetListNode(nItem);
ptrPrev->InsertAfter(newListNode);
}
}
else //升序排列时
{
while(ptrCurr) //寻找插入位置
{
if(nItem<=ptrCurr->ShowDate()) break;
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
} （续）
if(!ptrPrev) InsertFront(nItem);
else
{
newListNode=GetListNode(nItem);
ptrPrev->InsertAfter(newListNode);
}
}
}
在应用类模板过程中，在类外实现成员函数时要注意不要漏写
template <class T>。同时，所有涉及类模板的地方都要用 <T>。
注
（续）
小结：
1、栈类模板声明和使用；
2、队列类模板声明和使用；
2、链表类的声明和使用；
作业：
教学目的与要求：
了解各类模板的特征 。
掌握栈,队列,链表的应用 。
教学内容提要：
1,栈类模板；
2,队列类模板；
2,链表类模板；
教学重点,链表类的声明和使用 。
教学难点：链表类的声明和使用 。
教学进度,P228～ P238
教学过程：
栈顶
┆
an
┆
a1
a0
入栈 出栈数组下标
max
n
1
0
一般状态栈顶入栈 出栈数组下标初始状态（栈空）
max
n
1
0
栈顶amax┆
an
┆
a1
a0
入栈 出栈数组下标 max
n
1
0
栈满状态
21.1 栈类模板例 21.1 使用栈类模板的使用 。
#include<iostream.h>
const int size=10;
template<class Type> //声明一个类模板
class stack{
public:
void init(){ tos=0; }
void push(Type ch); //参数取 Type类型
Type pop(); //返回类型取 Type类型
private:
Type stck[size]; //数组的类型为类型参数 Type，
即可取任意类型
int tos; };
template <class Type>
void stack<Type>::push(Type ob)
{ if (tos==size){ cout<<"stack is full"; return ; }
stck[tos]=ob; tos++; }
template <class Type>
Type stack <Type>::pop()
{
if (tos==0)
{
cout<<"stack is empty";
return 0;
}
tos--;
return stck[tos];
}
main()
{
//定义字符堆栈
stack <char> s1,s2; //创建两个模板参数为 char型的对象
int i;
s1.init(); s2.init();
s1.push('a'); s2.push('x');
s1.push('b'); s2.push('y');
s1.push('c'); s2.push('z');
for(i=0;i<3;i++) cout<<"pop s1,"<<s1.pop()<<endl;
for(i=0;i<3;i++) cout<<"pop s2,"<<s2.pop()<<endl;
//定义整型堆栈
stack <int> is1,is2; //创建两个模板参数为 int型的对象
is1.init(); is2.init();
is1.push(1); is2.push(2);
is1.push(3); is2.push(4);
is1.push(5); is2.push(6);
for (i=0;i<3;i++)
cout<<"pop is1,"<<is1.pop()<<endl;
for (i=0;i<3;i++)
cout<<"pop is2,"<<is2.pop()<<endl;
return 0;
}
21.2队列类模板队列与栈不同，对数据采用,先进先出,--FIFO的管理方式（而栈则使用,先进后出,--FILO方式）。
队列数据放于作为类成员的动态数组 queue之中，在构造函数中，将通过 new来生成该动态数组，动态数组 queue的大小由类的私有数据成员 Maxsize之值来确定。但注意，此示例并没有循环使用上述的动态数组 queue空间。即是说，
队列中至多可以存放 Maxsize个数据项，即使取走若干项后有了空闲空间后也不可重新进行使用。若稍加改造，使存取数据时首先通过对下标进行模 Maxsize的运算，则可实现循环使用动态数组 queue空间的功能。
a1 a2 an-1 an……
队头 队尾入队出队 a0
#include <iostream.h>
#include <process.h>
template <class keytype>
class Queue {
int Maxsize; //队列的大小
int front,rear; //元素放在 queue[front+1]到 queue[rear]之中
keytype *queue; //动态数组 queue，用来存放队列数据
public:
Queue (int size) { //构造函数，生成动态数组来存放队列数据
Maxsize=size;
queue=new keytype[Maxsize];
front=rear=-1; //意味着队列为空
};
int IsFull () {
if (rear==Maxsize-1)
return 1;
else
return 0;
};
int IsEmpty () {
if (front==rear)
return 1;
else
return 0;
};
void Add(const keytype &);
keytype Delete(void);
};
//Delete在类体外定义，函数名前要加类限定符,Queue<keytype>::”
template <class keytype> keytype Queue<keytype>::Delete(void){
if (IsEmpty()){
cout << "the queue is empty"<<endl;
exit (0);
}
return queue [++front];
}
//Add在类体外定义
template <class keytype> void Queue<keytype>::Add(const keytype & item){
if (IsFull())
cout << "the queue is full"<<endl;
else
queue[++rear]=item;
};
void main() {
int i=0; Queue<int> Qi(10);
Queue<double> Qf1(10),Qf2(10);
while (!Qi.IsFull()) { //Qi中只能盛 10个数
Qi.Add(2*i++); //Qi中,0,2,4,6,8,10,12,14,16,18
Qf1.Add(3.0*i); //Qf1中,3,6,9,12,15,18,21,24,27,30
}
for (i=0; i<4; i++){ //四次循环，每次总
//先往 Qf2的队列尾部加入两个数，而后又从首部删取一个数并输出
Qf2.Add(4.5*Qi.Delete());
//从 Qi首删取一元素，乘以 4.5，而后将其加入到 Qf2尾部
//四次循环往 Qf2队列尾加入,0*4.5,2*4.5,4*4.5,6*4.5
...
}
}
程序执行后的显示结果如下：
0
1.5
9
3
通过模板类定义，可以解决代码冗繁问题：
template<class T>
class Node{
public:
Node(const T& d):c(d),
next(0),pref(0){}
T c;
Node *next,*pref;
};
又例如下面的模板类定义，含有模板类的成 员：
template<class T>
class List{
Node<T> *first,*last;
public:
List();
void add(const T& c);
void remove(const T& c);
Node<T>* find(const T& c)const;
void print()const;
~List();
};
用类模板实现通用链表类。将链表类结点的数据类型参数化，构成了一个通用模板，可以用来生成结点数据为任意类型的链表。
【 21.3 链表类 】
通用链表类
#include <iostream.h>
#include <stdlib.h>
template<class T>
class ListNode //结点类
{
public:
ListNode(){} //结点类构造函数
ListNode(const T& nItem,ListNode<T> *ptrNext=NULL); //结点类带参数构
//造函数
T& ShowDate(){return Date;} //返回本结点数据的引用
void InsertAfter(ListNode<T> *ptr); //插入新结点作为本结点的后续结点
ListNode<T> *DeleteAfter(void); //删除本结点的后续结点例 21.3
ListNode<T> *NextListNode() const; //获得本结点的后续结点的指针
void SetNext(ListNode<T> *ptr){ptrNext=ptr;} //设置本结点的后续结点指针
private:
T Date; //本结点的数据
ListNode<T> *ptrNext; //指向本结点的后续结点的指针
};
template <class T>
class LinkedList //链表类的声明及其实现
{
public:
LinkedList(void);
LinkedList(const LinkedList<T> &list); //拷贝构造函数
～ LinkedList(void){DeleteAll();} //析构函数,释放链表占用的资源
LinkedList<T> &operator=(const LinkedList<T> &list); // ″=″号运算符
//的重载
void Next();//指向链表的下一个结点
int EndOfList() const {return (!ptrCurr);} //判断链表当前位置是否是表尾
int CurrPosition() const {return nPosition;}//获得当前位置指针在链表中的位置
（续）
void InsertFront(const T& nItem); //将数据为 nItem的结点插入到链表头
void InsertTail(const T& nItem); //将数据为 nItem的结点插入到链表尾
void InsertAt(const T& nItem); //将数据为 nItem的结点插入到链表的当前位置
void InsertAfter(const T& nItem); //将数据为 nItem的结点插入到链表的当前
//位置之后
void InsertOrder(T nItem);
//将数据为 nItem的结点插入到排序链表中,并构成新的排序链表
int DeleteHead(); //删除链表头结点
void DeleteCurr(); //删除链表当前结点
void Delete(T key); //删除链表中数据为 key的结点
void DeleteAll(); //删除链表中的所有结点
T& GetDate(); //得到链表中的当前结点数据
void DisplayList(); //显示链表中所有结点的数据
int Find(T& nItem); //在链表中找到数据为 nItem的结点
int ListLength() const{return nListLength;}; //求链表的长度
int ListEmpty() const{return nListLength;} //判断链表是否为空
void Reset(int nPos=0); //重新设置链表的当前指针的位置 （续）
private:
ListNode<T> *ptrFront,//链表的头结点指针
*ptrTail,//链表的尾结点指针
*ptrPrev,//链表的当前结点的前一个结点的指针
*ptrCurr; //链表的当前结点指针
int nListLength; //链表的长度
int nPosition; //链表的当前结点指针的位置
ListNode<T> *GetListNode(const T &nItem,ListNode<T> *ptrNext=NULL);
//获得链表的下一个结点指针
void FreeListNode(ListNode<T> *ptr){delete ptr;} //释放结点资源
void CopyList(const LinkedList<T>& list); //逐项拷贝链表
};
#include <iostream.h>
（续）
//结点类带参数构造函数的实现
template<class T>
ListNode<T>::ListNode(const T& nItem,ListNode<T> *ptrNext):
Date(nItem),ptrNext(ptrNext)
{}
//返回指向后续结点的指针
template<class T>
ListNode<T> *ListNode<T>::NextListNode() const
{
return ptrNext;
}
template<class T>
void ListNode<T>::InsertAfter(ListNode<T> *ptr)
{
ptr->ptrNext=ptrNext; //将 ptr的 ptrNext指针指向本结点的后续结点
ptrNext=ptr;//本结点的 ptrNext指针指向 ptr
}
（续）
template<class T>
ListNode<T> *ListNode<T>::DeleteAfter()
{
ListNode<T> *ptrTemp=ptrNext;
if(ptrNext==NULL) //处理本结点为尾结点时的情况
return NULL;
ptrNext=ptrTemp->ptrNext; //一般情况
return ptrTemp;
}
//链表类构造函数,4个私有指针成员设置为空,链表初始长度设置为 0,初始当前结点
//初始位置为 -1
template<class T>
LinkedList<T>::LinkedList(void):ptrFront(NULL),ptrTail(NULL),
ptrPrev(NULL),ptrCurr(NULL),nListLength(0),nPosition(-1)
{ }
//重载 ″=″号运算符
template<class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& list)
{ （续）
if(this!=&list)
{
DeleteAll();
CopyList(list);
}
return *this;
}
//拷贝构造函数
template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& list)
{
CopyList(list);
}
//重新设置当前指针的位置
template<class T>
void LinkedList<T>::Reset(int nPos)
{
int nStartPos; （续）
if(!ptrFront) //如果当前指针为空,链表为空直接返回
{
return;
}
if(nPos>=nListLength||nPos<0) //位置越界检查
{
cerr<<″Invalid Position!″<<endl;
return;
}
if(nPos==0) //置当前指针为头结点
{
ptrPrev=NULL;
ptrCurr=ptrFront;
nPosition=0;
}
else //一般情况
{
ptrCurr=ptrFront->NextListNode();
ptrPrev=ptrFront;
nStartPos=1;
for(nPosition=nStartPos;nPosition!=nPos;nPosition++)
//寻找该位置并使当前指针指向该位置
（续）
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
}
}
//当前指针指向当前结点的后续结点
template<class T>
void LinkedList<T>::Next()
{
if(ptrCurr)
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
nPosition++;
}
}
//将数据为 nItem的结点插入到链表头
template<class T> （续）
void LinkedList<T>::InsertFront(const T& nItem)
{
ListNode<T> *newListNode=GetListNode(nItem); //获得一个封装有该数据
//的结点
newListNode->SetNext(ptrFront);
ptrFront=newListNode;
nListLength++;
}
//将数据为 nItem的结点插入到链表尾
template<class T>
void LinkedList<T>::InsertTail(const T& nItem)
{
ListNode<T> *newListNode;
if(ptrCurr==NULL) InsertFront(nItem); //若链表为空,使之成为头结点
//(也是尾结点 )
else //一般情况
{
while(ptrCurr->NextListNode()) //寻找尾结点
ptrCurr=ptrCurr->NextListNode(); （续）
newListNode=GetListNode(nItem);
ptrCurr->InsertAfter(newListNode);
}
}
//将数据为 nItem的结点插入到链表的当前位置之前
template<class T>
void LinkedList<T>::InsertAt(const T& nItem)
{
ListNode<T> *newListNode;
if(!ptrPrev) //插入到头结点
{
newListNode=GetListNode(nItem,ptrFront);
newListNode->SetNext(ptrFront);
ptrFront=newListNode;
nListLength++;
}
else //一般情况
{ （续）
newListNode=GetListNode(nItem);
ptrPrev->InsertAfter(newListNode);
}
if(ptrPrev==ptrTail)
{
ptrTail=newListNode;
nPosition=nListLength;
}
ptrCurr=newListNode;
}
//将数据为 nItem的结点插入到链表当前结点之后
template<class T>
void LinkedList<T>::InsertAfter(const T& nItem)
{
ListNode<T> *newListNode;
if(!ptrCurr) //处理空链表的情况
{ （续）
newListNode=GetListNode(nItem);
ptrCurr=newListNode;
ptrFront=ptrCurr;
}
else //一般情况
{
newListNode=GetListNode(nItem);
ptrCurr->InsertAfter(newListNode);
}
if(ptrPrev==ptrTail)
{
ptrTail=newListNode;
nPosition=nListLength;
}
ptrCurr=newListNode;
nListLength++;
}
//删除链表中的当前结点
template<class T>
void LinkedList<T>::DeleteCurr() （续）
{
ListNode<T> *ptr;
if(!ptrCurr) //处理空链表的情况
{
cerr<<″The List is empty!″<<endl;
exit(1);
}
if(!ptrPrev) //删除头结点的情况
{
ptr=ptrFront;
ptrFront=ptrFront->NextListNode();
}
else //一般情况
ptr=ptrPrev->DeleteAfter();
if(ptr==ptrTail)
{
ptrTail=ptrPrev;
nPosition--;
}
ptrCurr=ptr->NextListNode();
FreeListNode(ptr); （续）
nListLength--;
}
//删除链表中所有结点并释放资源
template<class T>
void LinkedList<T>::DeleteAll()
{
ListNode<T> *ptrCurrPos,
*ptrNextPos;
ptrCurrPos=ptrFront;
while(ptrCurrPos) //循环处理删除链表中的各个结点
{
ptrNextPos=ptrCurrPos->NextListNode();
FreeListNode(ptrCurrPos);
ptrCurrPos=ptrNextPos;
}
ptrFront=NULL;
ptrTail=NULL;
ptrPrev=NULL;
ptrCurr=NULL; （续）
nListLength=0;
nPosition=-1;
}
//删除链表的头结点
template<class T>
int LinkedList<T>::DeleteHead()
{
ListNode<T> *ptr=ptrFront;
if(ptrFront)
{
ptrFront=ptrFront->NextListNode();
delete ptr;
nListLength--;
return 1;
}
else //处理链表为空的情况
{
cout<<″The List is empty!″<<endl;
return 0;
}
}
（续）
//获得链表中当前结点的数据
template<class T>
T& LinkedList<T>::GetDate()
{
if(nListLength==0||!ptrCurr) //空链表的处理
{
cerr<<″Invalid!″<<endl;
exit(1);
}
return ptrCurr->ShowDate();
}
//逐项拷贝链表中的各个结点
template<class T>
void LinkedList<T>::CopyList(const LinkedList<T> &list)
{
ListNode<T> *ptr=list.ptrFront;
ptrCurr=NULL;
while(ptr) //遍历 list并创建新链表 （续）
{
InsertAfter(ptr->ShowDate());
ptr=ptr->NextListNode();
}
if(nPosition==-1) //list为空
return;
ptrPrev=NULL;
ptrCurr=ptrFront;
for(int nPos=0;nPos!=list.CurrPosition();nPos++)
//将新链表的各个数据成员设置与原链表相同
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
nPosition=nPos;
nListLength=list.ListLength();
}
（续）
//获得下一个新结点,返回新结点地址
template<class T>
ListNode<T> *LinkedList<T>::GetListNode(const T& nItem,ListNode<T> *preNext)
{
ListNode<T> *newListNode;
newListNode=new ListNode<T>(nItem,preNext);
if(!newListNode)
{
cerr<<″Memory allocation failure!″<<endl;
exit(1);
}
return newListNode;
}
//输出链表中的各个结点数据
template<class T>
void LinkedList<T>::DisplayList()
{
ptrCurr=ptrFront;
while(ptrCurr) //遍历链表
{
cout<<ptrCurr->ShowDate()<<endl; （续）
ptrCurr=ptrCurr->NextListNode();
}
}
//在链表中查找数据
template<class T>
int LinkedList<T>::Find(T& nItem)
{
ptrCurr=ptrFront;
ptrPrev=NULL;
while(ptrCurr)
{
if(ptrCurr->ShowDate()==nItem)
return 1;
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
return 0;
}
//删除链表中满足条件的结点
template<class T> （续）
void LinkedList<T>::Delete(T key)
{
ptrCurr=ptrFront;
ptrPrev=NULL;
if(!ptrCurr)
return;
while(ptrCurr&[KG-*4]&ptrCurr->ShowDate()!=key) //查找相应的结点
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
nPosition++;
}
if(ptrCurr) //如果找到该结点,删除它
{
if(!ptrPrev) ptrFront=ptrFront->NextListNode();
else ptrPrev->DeleteAfter();
delete ptrCurr;
}
}
//在排序链表中插入新结点构成新的排序链表 （续）
template<class T>
void LinkedList<T>::InsertOrder(T nItem)
{
ListNode<T> *newListNode,
*next,//用于遍历链表
*prev; //next指向结点的前一个结点的指针
ptrPrev=NULL;
ptrCurr=ptrFront;
prev=ptrCurr;
next=ptrCurr->NextListNode();
while((prev->ShowDate()==next->ShowDate())&[KG-*4]&(next))
//判断原链表的排序方式,升序或者降序
{
prev=next;
next=next->NextListNode();
}
if(!next) InsertFront(nItem); //如果原链表中所有结点均相等,则将结点
//作为原链表的首结点
else if(prev->ShowDate()>next->ShowDate()) //降序排列时
{ （续）
while(ptrCurr) //寻找插入位置
{
if(nItem>=ptrCurr->ShowDate()) break;
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
if(!ptrPrev) InsertFront(nItem);
else
{
newListNode=GetListNode(nItem);
ptrPrev->InsertAfter(newListNode);
}
}
else //升序排列时
{
while(ptrCurr) //寻找插入位置
{
if(nItem<=ptrCurr->ShowDate()) break;
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
} （续）
if(!ptrPrev) InsertFront(nItem);
else
{
newListNode=GetListNode(nItem);
ptrPrev->InsertAfter(newListNode);
}
}
}
在应用类模板过程中，在类外实现成员函数时要注意不要漏写
template <class T>。同时，所有涉及类模板的地方都要用 <T>。
注
（续）
小结：
1、栈类模板声明和使用；
2、队列类模板声明和使用；
2、链表类的声明和使用；
作业：
