else
cout<data<<"";
//使currPtr指向下一个结点
currPtr=currPtr->NextNode（）;
}
}
//查找结点
//在指针head所指向的链表中查找数据域等于item的结点
//找到则返回TRUE及其前趋结点的地址，否则返回FALSE
template
intFind（Node*head,T&item,Node*&prevPtr）
{
Node*currPtr=head;//从第一个结点开始遍历
prevPtr=NULL;
//通过循环遍历链表，直到表尾
while（currPtr!
=NULL）
{
//将item与结点的数据域比较，如果相等，则返回，否则继续处理下一个结点
if（currPtr->data==item）
return1;
prevPtr=currPtr;//记录下当前结点的地址
currPtr=currPtr->NextNode（）;
}
return0;//找不到时
}
//在表头插入结点
template
voidInsertFront（Node*&head,Titem）
{
//建立新结点，使其指针域指向原链表头结点head，然后更新head
head=GetNode（item,head）;
}
//在表尾添加结点
template
voidInsertRear（Node*&head,constT&item）
{
Node*newNode,*currPtr=head;
//如果链表为空，则插入在表头
if（currPtr==NULL）
InsertFront（head,item）;
else
{
//寻找指针域为NULL的结点
while（currPtr->NextNode（）!
=NULL）
currPtr=currPtr->NextNode（）;
//建立新结点并插入在表尾（在currPtr之后）
newNode=GetNode（item）;
currPtr->InsertAfter（newNode）;
}
}
//删除链表的第一个结点
template
voidDeleteFront（Node*&head）
{
Node*p=head;//取得将被删除的结点的地址
if（head!
=NULL）//确认链表不空
{
head=head->NextNode（）;//将表头指针head移向第二个结点
deletep;//删除原第一个结点
}
}
//删除链表中第一个数据域等于key的结点
template
voidDelete（Node*&head,Tkey）
{
//currPtr用于遍历链表，prevPtr跟随其后
Node*currPtr=head,*prevPtr=NULL;
//如果链表为空，则返回
if（currPtr==NULL）
return;
//通过循环遍历链表，直到找到数据域为key的结点，或达到表尾
while（currPtr!
=NULL&&currPtr->data!
=key）
{
//currPtr前行，prevPtr跟随其后
prevPtr=currPtr;
currPtr=currPtr->NextNode（）;
}
//若currPtr!
=NULL，则currPtr指向的结点数据域为key
if（currPtr!
=NULL）
{
if（prevPtr==NULL）//找到的是链表第一个结点
head=head->NextNode（）;
else
//如果找到的是第二个以后的结点，调用前趋结点的成员函数删除之
prevPtr->DeleteAfter（）;
deletecurrPtr;//释放被删除的结点所占的内存空间
}
}
//在有序链表中插入一个结点
template
voidInsertOrder（Node*&head,Titem）
{
//currPtr用于遍历链表，prevPtr跟随其后
Node*currPtr,*prevPtr,*newNode;
//prevPtr==NULL标志着应插入在表头
prevPtr=NULL;
currPtr=head;
//通过循环遍历链表，寻找插入点
while（currPtr!
=NULL）
{
//如果item<当前结点数据，则插入点应在当前结点之前
if（itemdata）
break;
//currPtr前行，prevPtr跟随其后
prevPtr=currPtr;
currPtr=currPtr->NextNode（）;
}
//完成插入
if（prevPtr==NULL）//如果插入点在表头
InsertFront（head,item）;
else
{
//在prevPtr指向的结点之后插入新结点
newNode=GetNode（item）;
prevPtr->InsertAfter（newNode）;
}
}
//清空链表--删除链表中的所有结点
template
voidClearList（Node*&head）
{
Node*currPtr,*nextPtr;
//边遍历边删除结点
currPtr=head;
while（currPtr!
=NULL）
{
//记录下一个结点的地址，删除当前结点
nextPtr=currPtr->NextNode（）;
deletecurrPtr;
currPtr=nextPtr;//使指针currPtr指向下一个结点
}
head=NULL;//将头结点置为NULL，标志着链表为空
}
#endif//NODE_LIBRARY
//lab9_1.cpp
#include
#include"9_5.h"
#include"node.h"
usingnamespacestd;
intmain（）
{
//将表头指针置为NULL
Node*head=NULL,*prevPtr,*delPtr;
inti,key,item;
//输入10个整数依次向表头插入
for（i=0;i<10;i++）
{
cin>>item;
InsertFront（head,item）;
}
//输出链表
cout<<"List:
";
PrintList（head,noNewline）;
cout<//输入需要删除的整数
cout<<"请输入一个需要删除的整数:
";
cin>>key;
//查找并删除结点
prevPtr=head;
while（Find（head,key,prevPtr）!
=NULL）
{
if（prevPtr==NULL）//找到的是链表第一个结点
head=head->NextNode（）;
else
//如果找到的是第二个以后的结点，调用前趋结点的成员函数删除之
delPtr=prevPtr->DeleteAfter（）;
deletedelPtr;
}
//输出链表
cout<<"List:
";
PrintList（head,noNewline）;
cout<//清空链表
ClearList（head）;
}
实验结果如下：
2程序二
//lab9_2.cpp
#include"link.h"
intmain（）
{
LinkedListA,B;
for（inti=0;i<5;i++）
{
A.InsertRear（2*i+1）;
B.InsertRear（2*i+2）;
}
A.Reset（）;
cout<<"链表A的元素为：
";
while（!
A.EndOfList（））
{
cout<A.Next（）;
}
cout<B.Reset（）;
cout<<"链表B的元素为：
";
while（!
B.EndOfList（））
{
cout<B.Next（）;
}
cout<cout<<"把B中的元素插入A中..."<B.Reset（）;
while（!
B.EndOfList（））
{
A.InsertRear（B.Data（））;
B.Next（）;
}
A.Reset（）;
cout<<"此时，链表A的元素为：
";
while（!
A.EndOfList（））
{
cout<A.Next（）;
}
cout<}
//link.h
#ifndefLINKEDLIST_CLASS
#defineLINKEDLIST_CLASS
#include
#include
usingnamespacestd;
#ifndefNULL
constintNULL=0;
#endif//NULL
#include"9-3.h
template
classLinkedList
{
private:
//数据成员：
//表头和表尾指针
Node*front,*rear;
//记录表当前遍历位置的指针，由插入和删除操作更新
Node*prevPtr,*currPtr;
//表中的元素个数
intsize;
//当前元素在表中的位置序号。
由函数Reset使用
intposition;
//函数成员：
//生成新节点，数据域为item，指针域为ptrNext
Node*GetNode（constT&item,Node*ptrNext=NULL）;
//释放节点
voidFreeNode（Node*p）;
//将链表L拷贝到当前表（假设当前表为空）。
//被拷贝构造函数、operator=调用
voidCopyList（constLinkedList&L）;
public:
//构造函数
LinkedList（void）;
LinkedList（constLinkedList&L）;//拷贝构造函数
//析构函数
~LinkedList（void）;
//重载赋值运算符
LinkedList&operator=（constLinkedList&L）;
//检查表的状态
intListSize（void）const;//返回链表中元素个数（size）
intListEmpty（void）const;//size等于0时返回TRUE,否则返回FALSE
//遍历表的函数
voidReset（intpos=0）;
//将指针currPtr移动到序号为pos的节点，prevPtr相应移动
//position记录当前节点的序号
voidNext（void）;//使prevPtr和currPtr移动到下一个节点
intEndOfList（void）const;
//currPtr等于NULL时返回TRUE,否则返回FALSE
intCurrentPosition（void）const;//返回数据成员position
//插入节点的函数：
插入一个数据域为item的节点
voidInsertFront（constT&item）;//在表头插入
voidInsertRear（constT&item）;//在表尾添加
voidInsertAt（constT&item）;//在当前节点之前插入
voidInsertAfter（constT&item）;//在当前节点之后插入
//删除节点，释放节点空间，更新prevPtr、currPtr和size
TDeleteFront（void）;//删除头节点
voidDeleteAt（void）;//删除当前节点
//返回对当前节点成员data的引用（使数据域可以被使用或修改）
T&Data（void）;
//清空链表：
释放所有节点的内存空间。
被析构函数、operator=调用
voidClearList（void）;
};
template
Node*LinkedList:
:
GetNode（constT&item,
Node*ptrNext）
{
Node*p;
p=newNode（item,ptrNext）;
if（p==NULL）
{
cout<<"Memoryallocationfailure!
\n";
exit
（1）;
}
returnp;
}
template
voidLinkedList:
:
FreeNode（Node*p）
{
deletep;
}
//将L复制到当前链表
template
voidLinkedList:
:
CopyList（constLinkedList&L）
{
//P用来遍历L
Node*p=L.front;
intpos;
//将L中的每一个元素插入到当前链表最后
while（p!
=NULL）
{
InsertRear（p->data）;
p=p->NextNode（）;
}
//如果链表空,返回
if（position==-1）
return;
//在新链表中重新设置prevPtr和currPtr
prevPtr=NULL;
currPtr=front;
for（pos=0;pos!
=position;pos++）
{
prevPtr=currPtr;
currPtr=currPtr->NextNode（）;
}
}
//建立一个新链表,即:
将有关指针设置为空,size为0,position为-1
template
LinkedList:
:
LinkedList（void）:
front（NULL）,rear（NULL）,
prevPtr（NULL）,currPtr（NULL）,size（0）,position（-1）
{}
template
LinkedList:
:
LinkedList（constLinkedList&L）
{
front=rear=NULL;
prevPtr=currPtr=NULL;
size=0;
position=-1;
CopyList（L）;
}
template
voidLinkedList:
:
ClearList（void）
{
Node*currPosition,*nextPosition;
currPosition=front;
while（currPosition!
=NULL）
{
//取得下一结点的地址并删除当前结点
nextPosition=currPosition->NextNode（）;
FreeNode（currPosition）;
currPosition=nextPosition;//移动到下一结点
}
front=rear=NULL;
prevPtr=currPtr=NULL;
size=0;
position=-1;
}
template
LinkedList:
:
~LinkedList（void）
{
ClearList（）;
}
template
LinkedList&LinkedLi
升级会员 