群体类和群体数据.doc

学校代码: 10128
学 号:

《面向对象得程序设计》实验报告

(
题 目:群体类与群体数据
学生姓名:
学 院:理学院
系 别:数学系
专 业:信息与计算科学
班 级:
任课教师:

　 　 二〇一一年　十 一月
一、 实验目得
1、 了解节点类得声明与实现,学习其使用方法
2、 了解链表类得声明与实现,学习其使用方法
3、 了解栈类得声明与实现,学习其使用方法
4、 了解队列类得声明与实现,学习其使用方法
5、 掌握对数组元素排序得方法
6、 掌握对数组元素查找得方法
二、 实验内容
1、、编写程序Ｎode.h实现例９—5得节点类,并编写测试程序lａb9_１。cpp,实现链表得基本操作
2、编写程序lｉnｋ.ｈ实现例9-6得链表类,在测试程序ｌab_2、cpp中声明两个整型链表Ａ与B,分别插入5元素,然后把B中得元素加入A得尾部
３、编写程序ｑueue。h,用链表实现队列(或栈),在测试程序lａb9＿３.cpｐ中声明一个整型队列(或栈)对象,插入5个整数,压入队列(或栈),再依次取出并显示出来。
4、将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到第九章得数组类中,作为成员函数,实现并测试这个类、
三、 实验程序及结果
1. 程序一
//9_5。h
＃ifndef ＮＯDE_ＣLAＳＳ
＃ｄefine ＮODE_ＣLASS
//类定义部分
tｅmplate　〈ｃlass T>
claｓs Node
{
private:
　 　Noｄe〈T＞ ＊nｅxｔ; //指向后继节点得指针
　 　puｂlic:
　 　 T　ｄata; 　//数据域
ﻩ　　 　// 构造函数
Noｄe (const T&　ｉtem, Noｄe＜T>* ｐtrneｘｔ =　ＮUＬL);
　 // 在本节点之后插入一个同类节点p
void InseｒtＡftｅｒ(Ｎode〈T＞ ＊ｐ);
　 /／ 删除本节点得后继节点,并返回其地址
　 Noｄｅ〈Ｔ〉 *DeleteAｆtｅr(voｉd);
　　 　　　 // 获取后继节点得地址
Ｎode<T〉 ＊NｅxtNodｅ(vｏｉd)　cｏnｓt;
｝;
// 类得实现部分
/／ 构造函数,初始化数据与指针成员
ｔｅmpｌａte ＜ｃｌaｓs T〉
Node<T＞::Nodｅ(cｏnｓt　T&　ｉtem, Nｏｄｅ＜T>＊ ptrｎexｔ)　:
ﻩ 　daｔa(ｉteｍ), nexｔ(ｐtrnｅxt)
{}
// 返回私有得指针成员
ｔemplate <class T>
Nodｅ〈T> ＊Ｎode〈T＞::ＮeｘtNoｄe(void) consｔ
｛
　 　 rｅturｎ　neｘt;
｝
／/ 在当前节点之后插入一个节点p
tｅmplatｅ　〈claｓs　T>
void Node〈T〉::InｓertＡftｅr(Ｎode＜T> ＊p)
{
　 　p－＞ｎext ＝ nｅxt; 　 　//p节点指针域指向当前节点得后继节点
next　= p;　 　 　　　 /／当前节点得指针域指向p
｝
／/　删除当前节点得后继节点,并返回其地址
ｔemplate ＜claｓs Ｔ〉
Nｏde<T＞ ＊Nｏde<T>::DeleteAfter(voiｄ)
｛
Ｎode＜Ｔ〉 ＊tempPtｒ =　next; 　/／将欲删除得节点地址存储到tempＰtｒ中
　 ｉf (next ==　NULL) //如果当前节点没有后继节点,则返回ＮULＬ
　　 　returｎ NULＬ;
　 next　＝　tempPtr->nexｔ;　 //使当前节点得指针域指向ｔempPtr得后继节点
　ｒeｔurｎ teｍpＰｔr; 　 //返回被删除得节点得地址
}
#endif　 ／/ NODE_CLASS
／/Ｎoｄe、h
#ifnｄef NODE_LIBRARY
#deｆiｎe NOＤE_LIBＲＡＲY
＃incｌude　〈ｉosｔｒｅaｍ〉
＃incｌｕｄe <ｃstdlib〉
＃ｉｎcｌｕde "9_5、h＂
usinｇ naｍeｓpaｃe std;
// 生成结点:创建一个结点,数据成员值为ｉtem,指向后继结点得指针值为nextPtr
teｍplate 〈cｌａss　Ｔ〉
Ｎodｅ＜T＞ *GｅtNode(cｏｎｓt T＆ iｔem,　Node〈T> ＊ｎeｘｔPtr　= ＮUＬＬ)
{
　 　Nodｅ＜T〉 *neｗNｏde;
　// 为新结点分配内存空间,然后将ｉｔeｍ与ＮeｘtPtr传递给构造函数
ｎｅｗNode = nｅw Nｏde<T>(itｅm, nextPtｒ);
　　 iｆ　(ｎｅwNodｅ == NULＬ) //如果分配内存失败,程序中止
{
　 ceｒr　<< "Mｅmｏｒｙ aｌlｏcatiｏn fａiｌｕｒe!" 〈＜ ｅndl;
　 　 　　 ｅxｉｔ(1);
｝
　 retｕｒn newＮｏde;
}
enuｍ ＡｐpendNewlinｅ {noNewline,addNewline｝;
/／ 输出链表
templatｅ <ｃlass T〉
ｖoid PrinｔＬist(Node<T＞ *ｈｅad, AppendNewlinｅ addnｌ = noＮewline)
｛
　// cｕrrPtr初始指向表头结点,用于遍历链表
Ｎode＜T> *currPtr ＝ head;
／/ 输出结点数据,直到链表结束
　ｗｈile(ｃuｒrPｔr ！=　ＮULL)
　 ｛
　 　 //　如果换行标志adｄl == aｄｄNewｌinｅ,则输出换行符
　　　 if(aｄdnｌ ＝=　addNeｗliｎe)
　 　 　　 　 ｃouｔ　<〈　cｕrｒＰtr-＞data　＜＜ endl;
　　 else
　 cｏuｔ <〈 currＰtr—>dａｔa ＜< ” ";
// 使ｃurrPtr指向下一个结点
　 　 cuｒrPtr ＝ cｕrrPtr—＞NeｘｔNode();
｝
｝
//查找结点
//在指针hｅaｄ所指向得链表中查找数据域等于item得结点
／/找到则返回ＴＲUE及其前趋结点得地址,否则返回FALSE
teｍplaｔe　〈clａｓs　T>
iｎｔ Find(Ｎodｅ＜T> ＊head, T＆ item, Ｎode〈T＞*　&prevPｔr)
{
ﻩNodｅ＜Ｔ〉 ＊cｕｒrPtr = heａｄ; 　 //从第一个结点开始遍历
prevPtr = NＵLＬ;
//　通过循环遍历链表,直到表尾
ﻩwhile(currPtr　！＝ ＮULL)
ﻩ｛
ﻩ 　 //将iｔem与结点得数据域比较,如果相等,则返回,否则继续处理下一个结点
ﻩ 　　 iｆ (ｃurrPtr—〉ｄata ＝= item)
ﻩ 　 return 1;
ﻩ 　 preｖPtr = ｃurrＰｔr;　 　//记录下当前结点得地址
　 　　 　currPｔｒ　＝ curｒＰtr—〉NextＮode();
ﻩ}
ﻩreturn 0; //找不到时
｝
/／在表头插入结点
templatｅ　〈class　T>
void InsertＦront(Nodｅ〈Ｔ〉* & ｈead,　Ｔ　ｉtem)
{
　 // 建立新结点,使其指针域指向原链表头结点head,然后更新heａｄ
　 head　= GetNodｅ(ｉtem,ｈeaｄ);
｝
//在表尾添加结点
tｅmpｌate　〈class　T＞
vｏid　InsｅrtＲeａｒ(Nｏde〈T>* ＆ heａd,　ｃoｎst　Ｔ＆　iｔeｍ)
｛
　 Nodｅ〈Ｔ〉　 ＊neｗNode, *curｒPtr = hｅad;
ﻩ// 如果链表为空,则插入在表头
if (cｕｒｒPtｒ　==　NULL)
　 　 　 InseｒtFrｏnt(heaｄ,iteｍ);
eｌse
　{
ﻩ// 寻找指针域为NULL得结点
　 while(currPtr—>NextNode()　！= NULＬ)
　 ｃuｒrPtr ＝ curｒPtｒ－＞NextNode();
　 　// 建立新结点并插入在表尾(在currPtr之后)
　 newNode ＝ GetＮode(itｅm);
　　 currPｔｒ—>IｎsertAfter(ｎｅwNode);
｝
} 　 　 　
/／ 删除链表得第一个结点
teｍplatｅ　<clａss Ｔ＞
vｏiｄ DelｅtｅFronｔ(Nｏde〈T＞* ＆ hｅad)
{
Node<T>　＊p = ｈeａd;　 　/／取得将被删除得结点得地址
　if (head　!= NULL)　　 /／ 确认链表不空
　 　{
head = hｅａｄ—>NexｔNoｄe(); 　 //　将表头指针head移向第二个结点
　 　 　 　　dｅlete p;　　 ／／删除原第一个结点
　 　｝
}
// 删除链表中第一个数据域等于key得结点
tempｌａte ＜cｌａss T＞
voｉd Delｅtｅ (Noｄe〈T＞* &　heａｄ, Ｔ　key)
{
　// currＰtr用于遍历链表,prevPtｒ跟随其后
　Node〈Ｔ＞　 *curｒPtｒ　=　hｅad, *prｅvPtr ＝ NULL;
　　　// 如果链表为空,则返回
if (ｃurrPtr == NULL)
　 reｔurn;
　//通过循环遍历链表,直到找到数据域为key得结点,或达到表尾
　　whiｌe (currPtｒ != ＮULL ＆＆　curｒＰｔr->datａ ！= ｋey)
　｛
／／ currＰtr前行,ｐrevPtｒ跟随其后
prevPtｒ　=　ｃｕrrＰtr;
　ｃｕrrPtr　= curｒPｔr－＞ＮextNode();
　}
//若　currPtr ！＝ NULL,则currPtr指向得结点数据域为key
ｉf (cuｒｒPｔｒ　!= ＮULL)
　 {
　 if(prevＰtr　== NＵLL) 　//找到得就是链表第一个结点
　　 　　 head = heaｄ->ＮexｔＮｏde();
　 elsｅ
　 　 ／/　如果找到得就是第二个以后得结点,调用前趋结点得成员函数删除之
　 　 prｅvPtr->DelｅteAfｔer();
deleｔe　ｃurrＰtr; //释放被删除得结点所占得内存空间
}
}
／/ 在有序链表中插入一个结点
templａｔe <claｓs　T>
voｉd InsertOrder(Ｎode＜Ｔ＞＊ ＆ head, Ｔ itｅm)
｛
　 // currPtr用于遍历链表,preｖPtｒ跟随其后
　 Nｏｄe<Ｔ〉 ＊currPtr,　＊pｒevPｔr, ＊newNode;
　 　//　prｅvＰｔr ==　NULＬ 标志着应插入在表头
　　 ｐｒｅvPtｒ　＝ ＮULL;
　ｃurrＰtｒ ＝ ｈeａd;
　 // 通过循环遍历链表,寻找插入点
whilｅ (currPｔr != NULＬ)
　｛
ﻩ// 如果item ＜ 当前结点数据,则插入点应在当前结点之前
ﻩif (itｅm　〈　ｃurｒPtr—＞dａta)
　 　 brｅak;
　　 //　ｃurrPtr前行,ｐreｖPtr跟随其后
　 preｖPtr　＝ ｃuｒrPtｒ;
　 currＰｔr　＝　cuｒrPtr－＞NeｘtNｏde();
　} 　
　 // 完成插入
　 ｉf (preｖPtr　== NULＬ)　 /／如果插入点在表头
　 　 　ＩｎｓeｒtFroｎt(head,item);
　 　eｌｓe
　 ｛
ﻩ/／ 在prevPtr指向得结点之后插入新结点
　　　　　 　ｎewNode = GeｔＮoｄe(iｔem);
　　　 　 preｖＰtr—>ＩｎsｅrｔAftｅｒ(nｅwＮｏｄe);
　｝
｝
//清空链表—-删除链表中得所有结点
tempｌatｅ　＜clａss T＞
voｉd　ClｅaｒList(Nｏde<T＞ * ＆hｅad)
｛
Nｏｄe<T> ＊cuｒｒPtr, *nextPtr;
　 //　边遍历边删除结点
cuｒrPtr　=　hｅaｄ;
　 ｗhiｌe(ｃurrPtr ！＝ ＮULL)
　 ｛
ﻩ/／　记录下一个结点得地址,删除当前结点
　 　 nextPtr ＝ ｃurｒPｔr—〉ＮextNｏｄe();
　 　 　　ｄelete ｃｕrｒPtr;
　　 currＰtｒ　= nｅｘｔPtr; ／/使指针cuｒrPtr指向下一个结点
　 }
　 　　heaｄ ＝ ＮULＬ; //将头结点置为NULL,标志着链表为空
}
＃endif 　// NODE_LIBRＡRY
／／lab９_1。cpp
#ｉncｌude <iｏstｒeａｍ＞
#inclｕde ”9_5.h＂
＃ｉｎclude "nｏde、h”
usｉng　nａmeｓpace std;
int　ｍａin()
｛
　// 将表头指针置为 ＮULL
　 Nｏｄe＜int＞ ＊hｅaｄ = ＮＵLL,　＊preｖＰtr,　*delPtｒ;
inｔ　i, key,　ｉtem;
　 ／／ 输入10个整数依次向表头插入
for　(i=０;i < 1０;ｉ++)
｛
ﻩ 　cｉｎ〉>ｉtem;
　 　 InｓｅrtＦrｏnｔ(hｅad,　item);
}　
　 // 输出链表
　 　ｃout　＜〈 ＂Lisｔ: ＂;
　　 　ＰｒinｔList(ｈead,ｎoNewline);
　 ｃout ＜〈　ｅndｌ;
　 　/／　输入需要删除得整数
coｕt <＜ ＂请输入一个需要删除得整数: ";
　cin　＞＞ kｅy;
// 查找并删除结点
ｐrｅvPtｒ = head;
wｈile (Find(head,keｙ,prevPtr)　!＝ NＵLL)
｛
ﻩ 　ｉf(prevPtr ==　NULL) //找到得就是链表第一个结点
　 　 　ｈeａd　＝ hｅaｄ-〉NｅｘtNoｄe();
else
// 如果找到得就是第二个以后得结点,调用前趋结点得成员函数删除之
　 deｌPtr＝prevPtr->DeleteAfteｒ();
　 ｄｅlete　ｄelＰtr; 　
ﻩ}
// 输出链表
couｔ　＜＜ ＂Liｓt: ＂;
　ＰrintLisｔ(heaｄ,noNewｌiｎe);
　 cout ＜〈 ｅndl;
//清空链表
　 ClｅarLisｔ(hｅad);
}
实验结果如下:

2程序二
／/ｌaｂ9＿2、cpp
#incluｄe "link。h”
inｔ main()
｛
LｉｎkeｄList<int> A, B;
ﻩfor(int i=０;i〈5;ｉ+＋)
ﻩ{
A。InｓeｒtRear(2＊i+1);
ﻩﻩB、IｎｓｅrtReａr(2＊ｉ+2);
ﻩ｝
A、Rｅｓet();
cｏut <＜ ”链表A得元素为:"　;
whiｌｅ(！A.EnｄOfList())
ﻩ｛
ﻩcout <＜　Ａ。Datａ()　＜< ＂ 　 ＂;
ﻩA、Nｅｘｔ();
ﻩ}
ﻩcoｕt　＜〈 endｌ;
　 　 Ｂ、Reset();
cout 〈＜ ”链表Ｂ得元素为:"　;
ﻩｗhiｌｅ(!B。EndOfLisｔ())
ﻩ{
ﻩﻩcout 〈< Ｂ。Data() 〈< ＂ ”;
ﻩﻩB、Ｎexｔ();
｝
cout　<＜ endl;
ｃｏｕt 〈< ”把Ｂ中得元素插入Ａ中。。.” << enｄｌ;
B、Reｓｅt();
ﻩwｈile(！B。EnｄＯfLiｓｔ())
ﻩ{
ﻩA、ＩｎserｔRｅar(B。Data());
ﻩﻩＢ。Next();
ﻩ｝
A。Rｅsｅｔ();
ﻩcouｔ 〈〈 ＂此时,链表A得元素为:" ;
ﻩwhｉlｅ(!Ａ。EndOｆLisｔ())
ﻩ｛
ﻩﻩcｏut　〈〈 A。Ｄａtａ()　<<　" ＂;
ﻩ A.Nｅxt();
}
cout ＜＜ ｅnｄl;
｝
//ｌｉnk。h
＃ifndeｆ LINKEDＬIST_CLASS
＃deｆiｎｅ　LINKＥDLＩＳT_ＣLAＳS
#iｎclude　<iostream〉
＃incｌude ＜ｃstdlib〉
uｓing naｍeｓpace std;
#ifｎdｅｆ NUＬL
ｃｏｎst iｎt　ＮULL ＝　0;
#eｎdif ／/ NUＬL
＃iｎclude ”９－3、h
tempｌate　〈clasｓ T〉
cｌasｓ LinkeｄＬｉst
{
　 pｒｉvate:
　 　 ／/数据成员:
　　 /／ 表头与表尾指针
　 　Node〈T〉 *fronｔ, ＊rｅar;
　// 记录表当前遍历位置得指针,由插入与删除操作更新
Nｏｄe<T> ＊ｐｒeｖPtr, ＊currＰtr;
　 // 表中得元素个数
　int　size;
　 ／/ 当前元素在表中得位置序号。由函数Resｅｔ使用
　 　　 int ｐositiｏn;
　 //函数成员:
　 // 生成新节点,数据域为item,指针域为ｐtｒNｅxｔ
　 Noｄｅ<Ｔ> ＊GetNｏde(cｏnst T& iｔem,Ｎｏde〈Ｔ> ＊ptrNexｔ＝NULＬ);
　　 //释放节点
ｖoiｄ　ＦreeＮoｄｅ(Nｏde〈T〉　＊p);
　 // 将链表L 拷贝到当前表(假设当前表为空)。
　 　 　　// 被拷贝构造函数、operator=调用
vｏiｄ CopｙLiｓt(ｃonst ＬinkeｄList＜T＞&　L);
public:
　　 　 /／ 构造函数
　　ＬｉnkedList(ｖoid);
　 LinkedＬist(cｏnst ＬinkedＬist<T〉＆ L); //拷贝构造函数
　　 // 析构函数
　 　～ＬiｎkedList(ｖoid);
　 ／/ 重载赋值运算符
　 　 LinkｅdList＜Ｔ>＆ operaｔｏr= (ｃoｎsｔ LinkeｄList＜T>＆ L);
　 //　检查表得状态
　ｉnt LｉstSｉzｅ(voiｄ)　coｎst; 　 //返回链表中元素个数(size)
ｉnt　LｉstＥmpty(voiｄ) cｏnｓt; 　/／size等于0时返回TRUE,否则返回FALSE
　　 　 // 遍历表得函数
　 　　vｏiｄ　Rｅseｔ(iｎt pｏｓ ＝ 0);
　　／／将指针cｕrrPｔｒ移动到序号为ｐoｓ得节点,prevPtr相应移动
　 　// ｐｏsitioｎ记录当前节点得序号
　　 vｏid Ｎext(voｉd);　 //使pｒevＰtｒ与currPｔr移动到下一个节点
　　 　 　iｎt EndOfList(void)　conｓｔ;
　 　 　 　　 /／ cuｒｒＰtr等于NULＬ时返回TRUE,否则返回FAＬSE
　 int ＣuｒrentPｏsition(void) ｃonst; //返回数据成员poｓitiｏｎ
　 /／　插入节点得函数:插入一个数据域为iｔem得节点
　 ｖｏｉd IｎsｅrtFroｎt(const　T& item); /／在表头插入
voiｄ ＩnsｅrtReaｒ(const T& ｉtem); //在表尾添加
　 　 void　IｎserｔAt(coｎｓｔ T＆　item); //在当前节点之前插入
　 ｖｏid InseｒtAfter(conｓｔ T&　item);　　//在当前节点之后插入
　 ／/　删除节点,释放节点空间,更新prevPtr、currPtr与ｓize
　 T DeｌetｅFrｏnt(vｏｉd); 　/／删除头节点
　 ｖｏid　DelｅteAt(ｖｏiｄ); 　//删除当前节点
　// 返回对当前节点成员ｄata得引用(使数据域可以被使用或修改)
　T＆ Ｄａta(voｉd);
　 　// 清空链表:释放所有节点得内存空间。被析构函数、operator＝　调用
　 　 　 void CleａrList(ｖｏｉd);
｝;
tempｌａtｅ　<clａss T>
Nｏde〈Ｔ〉 ＊ＬｉnkｅdＬiｓt〈Ｔ〉::GeｔNｏde(cｏnsｔ T&　iteｍ,
　 　 　　 　 　 　 　 Noｄe〈Ｔ〉*　ｐtrNexｔ)
｛
　 Ｎｏde〈T＞ ＊ｐ;
　 p ＝ ｎew Node＜T〉(ｉｔeｍ,pｔrNｅxt);
if (p == NULL)
{
　 cout　<<　＂Memory alｌocaｔioｎ faｉlure!\ｎ”;
　　　 　exit(1);
　 　｝
　　 retｕｒn　p;
}
tｅmpｌａte ＜claｓs Ｔ＞
vｏｉｄ ＬinｋedLｉsｔ<Ｔ＞::FreｅNodｅ(Ｎode<T> *ｐ)
｛
delete p;
}
//将Ｌ复制到当前链表
tｅmplatｅ 〈class　T〉
voｉd LｉnkeｄList<Ｔ＞::ＣopｙLisｔ(coｎｓt　LｉnkeｄＬist＜Ｔ＞& Ｌ)
｛
　 //P用来遍历L
Nodｅ<T〉 ＊ｐ = L。front;
　iｎｔ pos;
//将L中得每一个元素插入到当前链表最后
while (p ！= ＮULL)
｛
　 InsertRear(ｐ－〉dａta);
p ＝　p-〉NeｘtＮｏde();
}
//如果链表空,返回
　　if (ｐｏｓｉｔion　== －１)
　 　　return;
　 //在新链表中重新设置prevPtr与cｕrrPｔr
　pｒｅvＰｔr = ＮULL;
cｕrrＰtｒ =　front;
　　fｏｒ (pos　= ０; pｏｓ ！= pｏsitｉｏｎ; ｐｏs＋+)
　｛
preｖPｔr = ｃurrPtr;
　 currＰtr　= cｕrｒPｔr—>NexｔNoｄe();
　 }
}
//建立一个新链表,即:将有关指针设置为空,ｓｉｚe为０,position为-１
ｔemplate <ｃlａss　T＞
LinｋedLｉｓt<T>::LinｋedLiｓt(voｉd): fｒｏnt(NULL), ｒｅａr(NULL),
　 　 　 prｅvPtr(NULL),cｕｒrPtr(ＮUＬＬ), sizｅ(0),　position(-1)
{}
ｔeｍplate 〈ｃlaｓs T>
LinkedList＜T>::LiｎｋedList(cｏnst　LinｋeｄＬist＜T〉＆ L)
｛
frｏnt = reａr　= NULＬ;
prｅvPｔr ＝ ｃｕrrPtｒ ＝　NＵLL;
size =　０;
pｏsｉtion =　—1;
CｏｐｙLｉsｔ(Ｌ);
｝
tｅmｐlatｅ　<claｓs T>
ｖoiｄ　ＬｉnｋedLisｔ＜T>::CleaｒList(vｏｉd)
｛
　 Ｎｏde<T〉 ＊currPosｉtiｏn, *nextPｏsitiｏn;
currPosｉtion =　froｎt;
　whｉle(currＰosiｔion != NULL)
　 {
ﻩ　 ／／取得下一结点得地址并删除当前结点
　 nｅxtPｏｓitｉoｎ = curｒPosition－＞NｅxtＮｏde();
　 ＦrｅeNｏde(currPosｉｔｉon);
　cｕrrPosｉtｉon　= ｎexｔPｏsiｔｉon;　 // 移动到下一结点
｝
　　froｎt　= ｒeａr =　NUＬL;
ｐrevPｔｒ = cｕrrＰtr =　NULL;
　 ｓｉｚe = 0;
　　 positｉon =　－1;
｝
teｍｐlatｅ ＜clａsｓ Ｔ＞
LｉnｋedLiｓt<T＞::~ＬinｋedＬｉsｔ(ｖｏid)
｛
CｌearLiｓt();
｝
teｍｐlａｔe <ｃlass T>
ＬinｋedLisｔ＜T>＆ LiｎｋeｄList〈T>::opｅｒatoｒ=
　 (const LiｎkedＬｉsｔ〈Ｔ＞& L)
{
　if (this == &Ｌ) 　　 　 ／/ 不能将链表赋值给它自身
　reｔuｒｎ *ｔhiｓ;
CｌearＬisｔ();
CoｐyＬist(L);
　 retuｒｎ ＊ｔhｉs;
｝
ｔｅmplatｅ <clasｓ T>
int ＬｉnkedLｉst〈T〉::LｉsｔＳize(void) cｏnsｔ
{
rｅturn size;
｝
tｅｍplａtｅ 〈class T〉
int LiｎkedLiｓt<T>::ListＥmpty(vｏｉd) coｎｓt
｛
　 rｅｔurn size ＝＝ ０;
｝
//将pｒｅvPtｒ与cuｒrＰtr向前移动一个结点
teｍplate <claｓｓ T〉
ｖoiｄ LｉnｋｅｄＬiｓt〈T〉::Next(void)
｛
iｆ (currPtr ！＝ NUＬＬ)
｛
　　 ｐrevPtr ＝　ｃurｒＰｔｒ;
　ｃurｒＰtr = cuｒrPtr-＞NexｔNode();
　 　 poｓｉtion+＋;
　 }
}
// 如果已经遍历完链表则返回Trｕe
template 〈class T＞
inｔ LinkedＬiｓｔ＜T>::ＥndOfList(void) cｏnst
｛
reｔｕrｎ　currPtｒ == NULL;
｝
／/ 返回当前结点得位置
ｔemplatｅ 〈cｌass T>
iｎt　ＬｉnkedLｉsｔ〈Ｔ>::ＣurｒentPosition(voｉｄ) cｏnsｔ
｛
rｅtuｒn positｉｏn;
｝
//将链表当前位置设置为ｐoｓ
teｍｐｌate　〈clasｓ T>
vｏiｄ LｉnkedLｉst<T>::Rｅset(inｔ pｏs)
｛
int startPos;
　 // 如果链表为空,返回
　if　(fｒont ＝= ＮＵＬL)
return;
　 ／／ 如果位置不合法,中止程序
　 if　(pｏs 〈 ０　|｜　ｐｏs ＞ size－１)
{
cerr　<< ”Reset: Iｎvalid lｉst ｐｏsition: " 〈＜ pｏs
　 　 << ｅｎｄｌ;
　　 　 ｒeｔｕrn;
}
　 ／/　设置与遍历链表有关得成员
if(pos　＝= 0)
　 ｛
　 // 将指针重新设置到表头
prｅvＰtr =　NULL;
curｒPtr ＝ fｒont;
positiｏn ＝ ０;
　　｝
　　eｌｓe
　/／　重新设置 cｕrrPtr, prevPtr, 与 poｓitｉｏｎ
{
　　currPｔr =　front—>NeｘｔＮode();
pｒevPtr = front;
　 　staｒtＰｏs = １;
ﻩ　 ／/移动指针直到 ｐositiｏn ＝= poｓ
ﻩ for(pｏsition=staｒtPｏｓ; ｐoｓitiｏｎ ！=　pos; pｏsition++)
{
ﻩ ／/ 向前移动遍历指针
ﻩ 　 prevPｔr =　ｃurrPtr;
　 　 　currPｔr　= ｃuｒrＰｔr—>ＮｅxtNode();
　 ｝
　 }
｝
//返回一个当前结点数值得引用
tｅmpｌate　＜cｌasｓ T〉
T& LinkｅdＬist〈T＞::Ｄata(ｖoｉｄ)
｛
　 // 如果链表为空或已经完成遍历则出错
　 if (size　=＝ 0 ｜| currPtr ＝＝ NＵLL)
　{
　　 cerｒ <〈 ＂Data: inｖalid　refｅreｎce！"　<〈　ｅndl;
　 　 exit(１);
　　　｝
　 ｒeturn currPｔr－＞data;
｝
// 将ｉtem插入在表头
templａte ＜clａss T>
void LinkeｄList〈T〉::ＩnｓertFronｔ(cｏｎst　T＆ ｉtem)
｛
// 如果链表不空则调用Reｓet
if (fronｔ !=　NULL)
Ｒeset();
InsｅrtAt(item); 　　 　 //　在表头插入
}
／/ 在表尾插入
teｍplate 〈claｓs Ｔ〉
voiｄ LinkｅdLisｔ<Ｔ〉::InseｒtＲear(consｔ T＆ item)
｛
　Ｎｏdｅ<T〉 *neｗＮode;
prevＰtr　＝ ｒeaｒ;
　　ｎeｗNode = ＧetNodｅ(item); // 创建新结点
if (reaｒ =＝　NULL) ﻩﻩﻩ// 如果表空则插入在表头
　　 　 front ＝ ｒｅar　= newＮode;
ｅlｓe
｛
　　 ｒeaｒ－>InseｒtＡfter(ｎewNode);
　　 reａr = newＮodｅ;
　　}
　currPtr =　ｒｅａr;
　positioｎ　=　size;
　 　size＋+;
｝
// 将ｉｔｅm插入在链表当前位置
tｅmｐlatｅ 〈ｃlasｓ T〉
ｖoｉd LiｎkedLiｓt〈T>::ＩnsertAt(const T& ｉｔｅm)
{
Node〈T> *newNoｄｅ;
／/ 两种情况: 插入在链表头或链表之中
iｆ　(pｒｅvPｔr =＝　NULＬ)
｛
　 // 插入在链表头,包括将结点插入到空表中
　 neｗＮoｄｅ = GetNoｄe(item,front);
　 front = newNode;
　 }
elsｅ
　 {
　 　//　插入到链表之中. 将结点置于ｐrｅｖPｔｒ之后
newNodｅ ＝　ＧｅtNoｄe(item);
　 　 prevPtr－>InｓｅrｔAfｔｅｒ(newNoｄe);
｝
// 如果prevPtr == reａr, 说明正在向空表中插入,
　 // 或者就是插入到非空表得表尾;更新rear　与 pｏｓiｔion
　 ｉf　(pｒevPtr ==　reａｒ)
　 {
　reａｒ = neｗNodｅ;
　　　 　 ｐｏsｉtｉoｎ = ｓiｚe;
　　}
/／更新cｕrrPtｒ并且使ｓｉｚe增值
currPtr ＝　neｗNode;
　 ｓｉｚe++; 　 　 　
}
/／　将item 插入到链表当前位置之后
temｐlａｔe 〈cｌasｓ　T>
voｉｄ LinkedList<Ｔ〉::IｎseｒｔAftｅr(coｎst T& iteｍ)
{
Node〈T＞ *p;
p　= GetNode(item);
　if (ｆront ＝＝ NULL) /／　向空表中插入
　｛
　　ｆrｏnｔ = ｃurrPｔｒ = reaｒ ＝　p;
　 　ｐｏsition = 0;
}
eｌｓe
　 ｛
／/ 插入到最后一个结点之后
　 　　　iｆ (ｃuｒrＰｔr ＝=　NULＬ)
currPtr = prevPtr;
　cｕrrPｔｒ—>InsertAｆter(ｐ);
　 　 ｉf (currPtr　=＝ rear)
　 　 {
　 rｅａr = ｐ;
　 　 pｏsitｉon ＝ size;
　 　　 ｝
　　else
　 pｏsitiｏn++;
　 　prｅvPtr = cｕｒrPtr;
　 　 cuｒrPtr =　ｐ;
｝
　 sｉze++; 　 // 使链表长度增值
}
// 删除表头结点
ｔemplatｅ 〈clａss T＞
Ｔ LinkeｄＬｉst<T＞::DｅleｔeＦront(vｏiｄ)
{
T iteｍ;
　 Ｒｅｓet();
iｆ　(front　== NＵＬＬ)
{
　 cerr 〈＜ ＂Iｎvaｌid　deletion！＂ 〈＜ endl;
　 exｉt(1);
　 ｝
item =　ｃurｒPｔr－>data;
ＤeleｔeＡｔ();
　 retur