面向?qū)ο蟪绦蛟O(shè)計

第六章模板

C++Templates楊衛(wèi)東左崢嶸華中科技大學(xué)自動化學(xué)院2017秋參考資料C++primer第四版

EffectiveC++3rdC++Templates(簡體中文版).pdf內(nèi)容

模板的定義函數(shù)模板類模板標(biāo)準(zhǔn)模板庫STL問題提出實現(xiàn)一個函數(shù)，輸入2個變量，輸出這兩個變量中值比較大的元素。要求:此函數(shù)可以接受int,char以及double類型的參數(shù)。C語言實現(xiàn)://函數(shù)1charMaxOfChar(charcNum1,charcNum2){return(cNum1>cNum2)?cNum1:cNum2;}//函數(shù)2intMaxOfInt(intiNum1,intiNum2){return(iNum1>iNum2)?iNum1:iNum2;}//函數(shù)3doubleMaxOfDouble(doubledNum1,doubledNum2){return(dNum1>dNum2)?dNum1:dNum2;}C語言函數(shù)重載c++時代，由于存在重載的概念，所以實現(xiàn)起來應(yīng)該是這個樣子://函數(shù)1charMax(charcNum1,charcNum2){return(cNum1>cNum2)?cNum1:cNum2;}//函數(shù)2intMax(intiNum1,intiNum2){return(iNum1>iNum2)?iNum1:iNum2;}//函數(shù)3doubleMax(doubledNum1,doubledNum2){return(dNum1>dNum2)?dNum1:dNum2;}#defineMAX(x,y)((x>y)?x:y)函數(shù)名字統(tǒng)一但代碼量沒有什么變化能否進一步？C++宏定義宏定義#defineMax(Inputl,Input2)((Inputl>Input2)?Inputl:Input2)宏無類型檢查，不建議模板(函數(shù)模板)template<classT>TMax(constT&Inputl,constT&Input2){return(Inputl>Input2)?Inputl:Input2;}可以接受任何類型的參數(shù)，包括上邊提到的int,char,double，甚至任何自定義類型(只要你實現(xiàn)了它的比較運算符operator>)具體選用什么樣的實際函數(shù)是在編譯時刻就決定好的，絲毫不會影響運行時的效率Input參數(shù)中用的是const&的，好處是減少函數(shù)調(diào)用時候的開銷，因為我們不知道T類型到底有多大模板定義代碼重用是程序設(shè)計的重要特性，為實現(xiàn)代碼重用，使得代碼具有更好的通用性，需要代碼不受數(shù)據(jù)類型的限制，自動適應(yīng)不同的數(shù)據(jù)類型，實現(xiàn)參數(shù)化程序設(shè)計。模板是C++中進行通用程序設(shè)計的工具之一模板是C++支持參數(shù)化多態(tài)的工具，使用模板可以使用戶為類或者函數(shù)聲明一種一般模式，使得類中的某些數(shù)據(jù)成員或者成員函數(shù)的參數(shù)、返回值取得任意類型如希望函數(shù)或類能夠處理多種不同類型數(shù)據(jù)，可以通過模板為函數(shù)或類設(shè)計一個通用樣板(通用數(shù)據(jù)類型)，當(dāng)處理實際數(shù)據(jù)時，根據(jù)給定數(shù)據(jù)的實際類型來確定模板是c++語言最強大卻最少被使用的特征之一，便于重復(fù)利用已經(jīng)開發(fā)好的數(shù)據(jù)結(jié)構(gòu)和算法，可以提高代碼的復(fù)用性和開發(fā)效率，是通用編程實現(xiàn)方法之一。在c++中，模板讓程序員能夠定義一種使用不同類型對象的行為。比方用模板類定義一種鏈表，那么通過不同的模板參數(shù)〔在調(diào)用時提供〕，可以生成不同類型的鏈表有點像宏，但是宏不是類型平安的，而模板是類型平安的分函數(shù)模板和類模板兩種模板的特點6.1

函數(shù)模板

1、數(shù)據(jù)類型作為參數(shù)的背景例：求絕對值的函數(shù)intabs(intx){ returnx<0?-x:x;}doubleabs(doublex){ returnx<0?-x:x;}特點：算法完全相同，僅僅只是數(shù)據(jù)類型不同。(函數(shù)重載)問題：能否以數(shù)據(jù)類型作為參數(shù)，實現(xiàn)通用代碼設(shè)計。

2、模板模板是由可以使用任何數(shù)據(jù)類型的通用代碼構(gòu)成。模板以數(shù)據(jù)類型作為參數(shù)。模板的定義形式是：template<typename標(biāo)識符>函數(shù)定義說明：template是關(guān)鍵字，表示定義的是模板。<>括起來的是模板的參數(shù)，可以有一個或多個。如：template<classT>或者：template<classT1,classT2>

3、例子定義一個求絕對值函數(shù)的模板。#include<iostream.h>template<typenameT>Tabs(Tx){ returnx<0?-x:x;}voidmain(){ intn=-5; doubled=-5.5; cout<<abs(n)<<endl;//由n的類型為int推導(dǎo)出T為int cout<<abs(d)<<endl;//由d的類型為double推導(dǎo)出T為double}分析：編譯器調(diào)用abs()時，用其實參的類型推導(dǎo)出函數(shù)模板的類型參數(shù)。當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個函數(shù)。以abs(n)調(diào)用為例，編譯器將生成一個函數(shù)：intabs(intx){ returnx<0?-x:x;}編譯過程舉例——函數(shù)模板支持所有數(shù)據(jù)類型的函數(shù)模板template<classT>inlineTsquare(Tx){ Tresult; result=x*x; returnresult;};Test62_pow2.cppTMatrix.dsw舉例1——數(shù)組//模板，動態(tài)數(shù)組，類型T1D，2D，高維？template<typenameT,int_m,int_n>classDynamic2Dim{public:Dynamic2Dim();~Dynamic2Dim(); Dynamic1Dim<T,_n>&operator[](intindex);protected:public: Dynamic1Dim<T,_n>*m_pBuf;};template<typenameT,int_size>classDynamic1Dim{public:Dynamic1Dim();~Dynamic1Dim();T&operator[](intindex);protected:public:T*m_pBuf;};Test61_ArrType.cpp Dynamic1Dim<Dynamic1Dim<Dynamic1Dim<TYPE1,5>,5>,2>_TD31;舉例2——矩陣template<classType>classMatrix{public://constructorsanddestructorMatrix();Matrix(constMatrix<Type>&A);Matrix(introws,intcolumns,constType&x=Type(0));Matrix(introws,intcolumns,constType*v);~Matrix();//assignmentsMatrix<Type>&operator=(constMatrix<Type>&A);Matrix<Type>&operator=(constType&x);Test62_TmatrixsDemo.dsw模板是C++支持參數(shù)化的工具使用類模板使用戶可以為類聲明一種模式，使類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值能夠取任意類型。類模板的聲明形式如下：template<模板參數(shù)表>類聲明模板參數(shù)表為：class標(biāo)識符；如：template<classT>模板參數(shù)表包含上面多項內(nèi)容時，各項內(nèi)容以逗號分隔。模板類的成員函數(shù)必須是函數(shù)模板

6.2類模板在類模板首部以外的成員函數(shù)定義都要以下面的形式開頭。template<classT>與函數(shù)模板相同，類模板只有使用的時候才被具體化為某一種類型用模板類創(chuàng)立對象的一般形式：模板<模板參數(shù)表>對象名1，對象名2，…，對象名n;模板參數(shù)表為用逗號分隔的假設(shè)干類型標(biāo)識符或常量表達式構(gòu)成。6.2類模板#include<iostream.h>#include<stdlib.h>//結(jié)構(gòu)體StudentstructStudent{intid;//學(xué)號floatgpa;//平均分};template<classT>//類模板：實現(xiàn)對任意類型數(shù)據(jù)進行存取classStore{private:Titem;//item用于存放任意類型的數(shù)據(jù)inthaveValue;//haveValue標(biāo)記item是否已被存入內(nèi)容

public:Store(void);//缺省形式〔無形參〕的構(gòu)造函數(shù)

TGetElem(void);//提取數(shù)據(jù)函數(shù)voidPutElem(Tx);//存入數(shù)據(jù)函數(shù)};舉例//以下實現(xiàn)各成員函數(shù)。//注意：模板類的成員函數(shù)，假設(shè)在類外實現(xiàn)，那么必須是模板函數(shù)//缺省形式構(gòu)造函數(shù)的實現(xiàn)template<classT>Store<T>::Store(void):haveValue(0){}//提取數(shù)據(jù)函數(shù)的實現(xiàn)template<classT>TStore<T>::GetElem(void){//如果試圖提取未初始化的數(shù)據(jù)，那么終止程序if(haveValue==0){cout<<"Noitempresent!"<<endl;exit(1);}returnitem;//返回item中存放的數(shù)據(jù)}//存入數(shù)據(jù)函數(shù)的實現(xiàn)template<classT>voidStore<T>::PutElem(Tx){haveValue++;//將haveValue置為TRUE，表示item中已存入數(shù)值

item=x;//將x值存入item}voidmain(void){Studentg={1000,23}; //定義Student類型結(jié)構(gòu)體變量的同時賦以初值

Store<int>S1,S2; //定義兩個Store類對象，其中數(shù)據(jù)成員item為int類型

Store<Student>S3; //定義Store類對象S3，其中數(shù)據(jù)成員item為Student類型

Store<double>D; //定義Store類對象D，其中數(shù)據(jù)成員item為double類型

S1.PutElem(3);//向?qū)ο骃1中存入數(shù)據(jù)〔初始化對象S1〕S2.PutElem(-7);//向?qū)ο骃2中存入數(shù)據(jù)〔初始化對象S2〕cout<<S1.GetElem()<<""<<S2.GetElem()<<endl; //輸出對象S1和S2的數(shù)據(jù)成員

S3.PutElem(g);//向?qū)ο驞中存入數(shù)據(jù)〔初始化對象D〕cout<<"Thestudentidis"<<S3.GetElem().id<<endl; //輸出對象S3的數(shù)據(jù)成員//D.PutElem(6.5);cout<<"RetrievingobjectD"; cout<<D.GetElem()<<endl;//輸出對象D的數(shù)據(jù)成員 //由于D未經(jīng)初始化,在執(zhí)行函數(shù)D.GetElement()過程中導(dǎo)致程序終止}運行結(jié)果：類模板舉例//EXAMPLE9_01.H#ifndefEXAMPLE9_01_H#defineEXAMPLE9_01_Htemplate<classT>classMax//聲明類模板Max{private:Titem1,//類型為T,T在該類的對象生成時具體化

item2,item3;public:Max(){}Max(Tthefirst,Tthesecond,Tthethird);TGetMaxItem();//求得3個元素中的最大值并按類型T返回

voidSetItem(Tthefirst,Tthesecond,Tthethird);//設(shè)置類中的3個元素的值}#endif//EXAMPLE9_01B.H

//類模板的實現(xiàn)#ifndefEXAMPLE9_01B_H#defineEXAMPLE9_01B_Htemplate<classT>TMax<T>::Max(Tthefirst,Tthesecond,Tthethird): item1(thefirst),item2(thesecond),item3(thethird){return;}template<classT>voidMax<T>::SetItem(Tthefirst,Tthesecond,Tthethird){item1=thefirst;item2=thesecond;item3=thethird;}template<classT>TMax<T>::GetMaxItem()

〔續(xù)〕{Tmaxitem;maxitem=item1>item2?item1:item2;maxitem=maxitem>item3?maxitem:item3;returnmaxitem;}#endif//EXAMPLE9_1.CPP//主程序#include<iostream.h>#include″EXAMPLE901.H″#include″EXAMPLE901B.H″voidmain(){Max<int>nmyMax(1,2,3);Max<double>dblmyMax(1.2,1.3,-1.4);cout<<nmyMax.GetMaxItem()<<endl;cout<<dblmyMax.GetMaxItem()<<endl;}〔續(xù)〕C++標(biāo)準(zhǔn)模板庫STLSTL(StandardTemplateLibrary)C++STLTraining.pdfC++標(biāo)準(zhǔn)模板庫STL介紹.pdf標(biāo)準(zhǔn)模板庫STL〔StandardTemplateLibrary〕，即標(biāo)準(zhǔn)模板庫，是一個具有工業(yè)強度的、高效的C++程序庫。它被容納于C++標(biāo)準(zhǔn)程序庫〔C++StandardLibrary〕中，是ANSI/ISOC++標(biāo)準(zhǔn)中最新的也是極具革命性的一局部。該庫包含了諸多在計算機科學(xué)領(lǐng)域里所常用的根本數(shù)據(jù)結(jié)構(gòu)和根本算法，為廣闊C++程序員們提供了一個可擴展的應(yīng)用框架，高度表達了軟件的可復(fù)用性。這種現(xiàn)象有些類似于MicrosoftVisualC++中的MFC〔MicrosoftFoundationClassLibrary〕，或者是BorlandC++Builder中的VCL(VisualComponentLibrary)。STL是最新的C++標(biāo)準(zhǔn)函數(shù)庫中的一個子集，這個龐大的子集占據(jù)了整個庫大約80%的分量。STL的引入STL〔StandardTemplateLibrary，標(biāo)準(zhǔn)模板庫〕是惠普實驗室開發(fā)的一系列軟件的統(tǒng)稱。STL提供了一系列具有良好結(jié)構(gòu)的通用C++組件，這些組件提供強大的功能。標(biāo)準(zhǔn)庫的設(shè)計必須確保所有的模板算法既能操作庫中的數(shù)據(jù)類型，也能操作C++固有的數(shù)據(jù)類型。例如，所有的算法都適用于普通指針類型。庫中各組件功能是獨立的，或者說，用戶可以自己設(shè)計算法操作庫提供的數(shù)據(jù)結(jié)構(gòu)，也可以使用標(biāo)準(zhǔn)庫的算法操作自定義的數(shù)據(jù)類型。STL概貌把軟件部件想象成一個三位空問。第i維表示數(shù)據(jù)類型(int,double,char,...),第j維表示容器(array,linked-list,…)，第k維表示算法(sort,merge,search,…)數(shù)據(jù)

算法容器STL優(yōu)勢需要設(shè)計i*j*k個不同的代碼版本，比方整數(shù)數(shù)組的排序算法、double數(shù)組的排序算法，doublelinked-list的搜索算法…通過使用數(shù)據(jù)類型作為參數(shù)的模板函數(shù)，i軸可取消，僅需要設(shè)計j*k個不同的代碼下一步是讓算法可以工作在不同的容器上，這就意味著排序算法既可以用在array上，也可用在linked-list上。只需設(shè)計j+k個不同的代碼版本了STL具體化了上述思想，期望通過減少開發(fā)時問以簡化軟件開發(fā)，簡化調(diào)試、維護并增加代碼的可移植性，其使用的算法非?？煽壳倚矢逽TL組成STL包含5個主要的局部:算法(Algorithm):能運行在不同容器(container)上的計算過程容器((Container):能夠保存并管理對象的對象迭代器(Iterator):算法存取容器(algorithm-accesstocontainers)的抽象，以便算法可以應(yīng)用在不同的容器上函數(shù)對象(FunctionObject):定義了函數(shù)調(diào)用操作符(operatorU)的類適應(yīng)器(Adaptor):封裝一個部件以提供另外的接口(例如用list實現(xiàn)stack)容器(Container)容器類型標(biāo)準(zhǔn)STL序列容器：vector、string、deque和list標(biāo)準(zhǔn)STL關(guān)聯(lián)容器：set、multiset、map和multimap非標(biāo)準(zhǔn)序列容器slist和rope非標(biāo)準(zhǔn)的關(guān)聯(lián)容器hash_set、hase_multiset、hash_map和hash_multimap容器容器局部主要由頭文件<vector>、<list>、<deque>、<set>、<map>、<stack>和<queue>組成。對于常用的一些容器和容器適配器〔可以看作由其他容器實現(xiàn)的容器〕。數(shù)據(jù)結(jié)構(gòu)描述實現(xiàn)頭文件向量（vector）連續(xù)存儲的元素<vector>列表（list）由節(jié)點組成的雙向鏈表，每個節(jié)點包含著一個元素<list>雙隊列（deque）連續(xù)存儲的指向不同元素的指針?biāo)M成的數(shù)組<deque>集合（set）由節(jié)點組成的紅黑樹，每個節(jié)點都包含著一個元素，節(jié)點之間以某種作用于元素對的謂詞排列，沒有兩個不同的元素能夠擁有相同的次序<set>多重集合（multiset）允許存在兩個次序相等的元素的集合<set>容器數(shù)據(jù)結(jié)構(gòu)描述實現(xiàn)頭文件棧（stack）后進先出的值的排列<stack>隊列（queue）先進先出的執(zhí)的排列<queue>優(yōu)先隊列（priority_queue）元素的次序是由作用于所存儲的值對上的某種謂詞決定的的一種隊列<queue>映射（map）由{鍵,值}對組成的集合，以某種作用于鍵對上的謂詞排列<map>多重映射（multimap）允許鍵對有相等的次序的映射<map>迭代器(Iterator)算法和函數(shù)對象二分搜索的根本算法(genericbianrysearchalgorithm)，給定一個排好序的整數(shù)數(shù)組，要求二分搜索某個值的位置適應(yīng)器(Adaptor)，是提供接口映射的模板類。適應(yīng)器基于其他類來實現(xiàn)新的功能，合并以得到新的功能。成員函數(shù)可以被添加、隱藏，也可合并舉例——容器#include＜set＞#include＜iostream＞usingnamespacestd;intmain(intargc,char*argv[]){set＜string＞strset;set＜string＞::iteratorsi;strset.insert("cantaloupes");strset.insert("apple");strset.insert("orange");strset.insert("banana");strset.insert("grapes");strset.insert("grapes");for(si=strset.begin();si!=strset.end();si++){cout＜＜*si＜＜"";}return0;}1．包含10個元素的序列逐個插入vector容器中，插入完成后將vector容器中的所有元素輸出?！窘獯稹吭撛囶}主要考查vector容器的使用。根據(jù)前面的學(xué)習(xí)，讀者知道vector容器利用索引直接存取任何一個元素，在尾部插入元素或移除元素均非?？焖?。2．編寫一個C++程序，創(chuàng)立了一個矢量容器〔STL的和數(shù)組等價的對象〕，并使用迭代器在其中搜索，找到值為100的元素?！窘獯稹吭撛囶}主要考查迭代器在容器中的使用。該試題可以使用vector容器來實現(xiàn)存儲數(shù)據(jù)，其相當(dāng)于數(shù)組，通過迭代器的begin()和end()方法表示容器的首尾，通過循環(huán)語句依次對容器中的所有元素進行比較，直到找到指定元素為止STL小結(jié)掌握STL可以使你的程序結(jié)構(gòu)更合理，數(shù)據(jù)存儲和管理更科學(xué)，掌握STL的精華本質(zhì)所在，真正理解泛型編程的意義。模板使得數(shù)據(jù)結(jié)構(gòu)和類型別離，而STL算法只通過某個數(shù)據(jù)結(jié)構(gòu)的幾個根本的語義屬性，屏蔽了數(shù)據(jù)結(jié)構(gòu)的特定實現(xiàn)，成功的將算法與數(shù)據(jù)結(jié)構(gòu)別離，在沒有效率損失的前提下，得到了及大的彈性。STL可以看作是由不同的逐漸組成的系統(tǒng)，理解容器、迭代器、適配器的概念十分重要，在此根底上，真正理解STL算法的本質(zhì)。有些算法被表示為容器類方法，但大量STL算法都是通用的、非成員函數(shù)的，這時將迭代器作為容器和算法間的接口來實現(xiàn)的，另外，STL算法通過迭代器和指針的概念融合，可用于非STL容器，如常規(guī)數(shù)組、以及后面要介紹的string對象等。從零開始學(xué)C++之STL〔二〕：實現(xiàn)簡單容器模板類Vec〔vectorcapacity增長問題、allocator內(nèi)存分配器〕舉例——通用鏈表類用類模板實現(xiàn)通用鏈表類。將鏈表類結(jié)點的數(shù)據(jù)類型參數(shù)化，構(gòu)成了一個通用模板，可以用來生成結(jié)點數(shù)據(jù)為任意類型的鏈表。//EXAMPLE9_02.H#ifndefEXAMPLE9_02_H#defineEXAMPLE9_02_H#include<iostream.h>#include<stdlib.h>template<classT>classListNode//結(jié)點類{public:ListNode(){}//結(jié)點類構(gòu)造函數(shù)

ListNode(constT&nItem,ListNode<T>*ptrNext=NULL);//結(jié)點類帶參數(shù)構(gòu)

//造函數(shù)

T&ShowDate(){returnDate;}//返回本結(jié)點數(shù)據(jù)的引用

voidInsertAfter(ListNode<T>*ptr);//插入新結(jié)點作為本結(jié)點的后續(xù)結(jié)點

ListNode<T>*DeleteAfter(void);//刪除本結(jié)點的后續(xù)結(jié)點

ListNode<T>*NextListNode()const;//獲得本結(jié)點的后續(xù)結(jié)點的指針

voidSetNext(ListNode<T>*ptr){ptrNext=ptr;}//設(shè)置本結(jié)點的后續(xù)結(jié)點指針private:TDate;//本結(jié)點的數(shù)據(jù)

ListNode<T>*ptrNext;//指向本結(jié)點的后續(xù)結(jié)點的指針};template<classT>classLinkedList//鏈表類的聲明及其實現(xiàn){public:LinkedList(void);LinkedList(constLinkedList<T>&list);//拷貝構(gòu)造函數(shù)～LinkedList(void){DeleteAll();}//析構(gòu)函數(shù),釋放鏈表占用的資源

LinkedList<T>&operator=(constLinkedList<T>&list);//″=″號運算符

//的重載

voidNext();//指向鏈表的下一個結(jié)點

intEndOfList()const{return(!ptrCurr);}//判斷鏈表當(dāng)前位置是否是表尾

intCurrPosition()const{returnnPosition;}//獲得當(dāng)前位置指針在鏈表中的位置〔續(xù)〕voidInsertFront(constT&nItem);//將數(shù)據(jù)為nItem的結(jié)點插入到鏈表頭

voidInsertTail(constT&nItem);//將數(shù)據(jù)為nItem的結(jié)點插入到鏈表尾

voidInsertAt(constT&nItem);//將數(shù)據(jù)為nItem的結(jié)點插入到鏈表的當(dāng)前位置

voidInsertAfter(constT&nItem);//將數(shù)據(jù)為nItem的結(jié)點插入到鏈表的當(dāng)前

//位置之后

voidInsertOrder(TnItem);

//將數(shù)據(jù)為nItem的結(jié)點插入到排序鏈表中,并構(gòu)成新的排序鏈表

intDeleteHead();//刪除鏈表頭結(jié)點

voidDeleteCurr();//刪除鏈表當(dāng)前結(jié)點

voidDelete(Tkey);//刪除鏈表中數(shù)據(jù)為key的結(jié)點

voidDeleteAll();//刪除鏈表中的所有結(jié)點

T&GetDate();//得到鏈表中的當(dāng)前結(jié)點數(shù)據(jù)

voidDisplayList();//顯示鏈表中所有結(jié)點的數(shù)據(jù)

intFind(T&nItem);//在鏈表中找到數(shù)據(jù)為nItem的結(jié)點

intListLength()const{returnnListLength;};//求鏈表的長度

intListEmpty()const{returnnListLength;}//判斷鏈表是否為空

voidReset(intnPos=0);//重新設(shè)置鏈表的當(dāng)前指針的位置

〔續(xù)〕private:ListNode<T>*ptrFront,//鏈表的頭結(jié)點指針*ptrTail,//鏈表的尾結(jié)點指針*ptrPrev,//鏈表的當(dāng)前結(jié)點的前一個結(jié)點的指針*ptrCurr;//鏈表的當(dāng)前結(jié)點指針

intnListLength;//鏈表的長度

intnPosition;//鏈表的當(dāng)前結(jié)點指針的位置

ListNode<T>*GetListNode(constT&nItem,ListNode<T>*ptrNext=NULL);

//獲得鏈表的下一個結(jié)點指針

voidFreeListNode(ListNode<T>*ptr){deleteptr;}//釋放結(jié)點資源

voidCopyList(constLinkedList<T>&list);//逐項拷貝鏈表};#endif//EXAMPLE9_02B.H#ifndefEXAMPLE9_02B_H#defineEXAMPLE9_02B_H#include<iostream.h> 〔續(xù)〕#include″EXAMPLE9_02.H″//結(jié)點類帶參數(shù)構(gòu)造函數(shù)的實現(xiàn)template<classT>ListNode<T>::ListNode(constT&nItem,ListNode<T>*ptrNext):Date(nItem),ptrNext(ptrNext){}//返回指向后續(xù)結(jié)點的指針template<classT>ListNode<T>*ListNode<T>::NextListNode()const{returnptrNext;}template<classT>voidListNode<T>::InsertAfter(ListNode<T>*ptr){ptr->ptrNext=ptrNext;//將ptr的ptrNext指針指向本結(jié)點的后續(xù)結(jié)點

ptrNext=ptr;//本結(jié)點的ptrNext指針指向ptr}

template<classT>ListNode<T>*ListNode<T>::DeleteAfter(){ListNode<T>*ptrTemp=ptrNext;if(ptrNext==NULL)//處理本結(jié)點為尾結(jié)點時的情況

returnNULL;ptrNext=ptrTemp->ptrNext;//一般情況

returnptrTemp;}//鏈表類構(gòu)造函數(shù),4個私有指針成員設(shè)置為空,鏈表初始長度設(shè)置為0,初始當(dāng)前結(jié)點//初始位置為-1template<classT>LinkedList<T>::LinkedList(void):ptrFront(NULL),ptrTail(NULL),ptrPrev(NULL),ptrCurr(NULL),nListLength(0),nPosition(-1){}//重載″=″號運算符template<classT>LinkedList<T>&LinkedList<T>::operator=(constLinkedList<T>&list){

if(this!=&list){DeleteAll();CopyList(list);}return*this;}//拷貝構(gòu)造函數(shù)template<classT>LinkedList<T>::LinkedList(constLinkedList<T>&list){CopyList(list);}//重新設(shè)置當(dāng)前指針的位置template<classT>voidLinkedList<T>::Reset(intnPos){intnStartPos;

if(!ptrFront)//如果當(dāng)前指針為空,鏈表為空直接返回

{return;}if(nPos>=nListLength||nPos<0)//位置越界檢查

{cerr<<″InvalidPosition!″<<endl;return;}if(nPos==0)//置當(dāng)前指針為頭結(jié)點

{ptrPrev=NULL;ptrCurr=ptrFront;nPosition=0;}else//一般情況

{ptrCurr=ptrFront->NextListNode();ptrPrev=ptrFront;nStartPos=1;for(nPosition=nStartPos;nPosition!=nPos;nPosition++)

//尋找該位置并使當(dāng)前指針指向該位置{ptrPrev=ptrCurr;ptrCurr=ptrCurr->NextListNode();}}}//當(dāng)前指針指向當(dāng)前結(jié)點的后續(xù)結(jié)點template<classT>voidLinkedList<T>::Next(){if(ptrCurr){ptrPrev=ptrCurr;ptrCurr=ptrCurr->NextListNode();nPosition++;}}//將數(shù)據(jù)為nItem的結(jié)點插入到鏈表頭template<classT>

voidLinkedList<T>::InsertFront(constT&nItem){ListNode<T>*newListNode=GetListNode(nItem);//獲得一個封裝有該數(shù)據(jù) //的結(jié)點newListNode->SetNext(ptrFront);ptrFront=newListNode;nListLength++;}//將數(shù)據(jù)為nItem的結(jié)點插入到鏈表尾template<classT>voidLinkedList<T>::InsertTail(constT&nItem){ListNode<T>*newListNode;if(ptrCurr==NULL)InsertFront(nItem);//假設(shè)鏈表為空,使之成為頭結(jié)點 //(也是尾結(jié)點)else//一般情況{while(ptrCurr->NextListNode())//尋找尾結(jié)點ptrCurr=ptrCurr->NextListNode(); newListNode=GetListNode(nItem);ptrCurr->InsertAfter(newListNode);}}//將數(shù)據(jù)為nItem的結(jié)點插入到鏈表的當(dāng)前位置之前template<classT>voidLinkedList<T>::InsertAt(constT&nItem){ListNode<T>*newListNode;if(!ptrPrev)//插入到頭結(jié)點

{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;

}//將數(shù)據(jù)為nItem的結(jié)點插入到鏈表當(dāng)前結(jié)點之后template<classT>voidLinkedList<T>::InsertAfter(constT&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++;}//刪除鏈表中的當(dāng)前結(jié)點template<classT>voidLinkedList<T>::DeleteCurr()

{ListNode<T>*ptr;if(!ptrCurr)//處理空鏈表的情況

{cerr<<″TheListisempty!″<<endl;exit(1);}if(!ptrPrev)//刪除頭結(jié)點的情況

{ptr=ptrFront;ptrFront=ptrFront->NextListNode();}else//一般情況

ptr=ptrPrev->DeleteAfter();if(ptr==ptrTail){ptrTail=ptrPrev;nPosition--;}ptrCurr=ptr->NextListNode();FreeListNode(ptr);

nListLength--;}//刪除鏈表中所有結(jié)點并釋放資源template<classT>voidLinkedList<T>::DeleteAll(){ListNode<T>*ptrCurrPos,*ptrNextPos;ptrCurrPos=ptrFront;while(ptrCurrPos)//循環(huán)處理刪除鏈表中的各個結(jié)點

{ptrNextPos=ptrCurrPos->NextListNode();FreeListNode(ptrCurrPos);ptrCurrPos=ptrNextPos;}ptrFront=NULL;ptrTail=NULL;ptrPrev=NULL;ptrCurr=NULL;

nListLength=0;nPosition=-1;}//刪除鏈表的頭結(jié)點template<classT>intLinkedList<T>::DeleteHead(){ListNode<T>*ptr=ptrFront;if(ptrFront){ptrFront=ptrFront->NextListNode();deleteptr;nListLength--;return1;}else//處理鏈表為空的情況

{cout<<″TheListisempty!″<<endl;return0;}}

//獲得鏈表中當(dāng)前結(jié)點的數(shù)據(jù)template<classT>T&LinkedList<T>::GetDate(){if(nListLength==0||!ptrCurr)//空鏈表的處理{cerr<<″Invalid!″<<endl;exit(1);}returnptrCurr->ShowDate();}//逐項拷貝鏈表中的各個結(jié)點template<classT>voidLinkedList<T>::CopyList(constLinkedList<T>&list){ListNode<T>*ptr=list.ptrFront;ptrCurr=NULL;while(ptr)//遍歷list并創(chuàng)立新鏈表 {InsertAfter(ptr->ShowDate());ptr=ptr->NextListNode();}if(nPosition==-1)//list為空

return;ptrPrev=NULL;ptrCurr=ptrFront;for(intnPos=0;nPos!=list.CurrPosition();nPos++)

//將新鏈表的各個數(shù)據(jù)成員設(shè)置與原鏈表相同

{ptrPrev=ptrCurr;ptrCurr=ptrCurr->NextListNode();}nPosition=nPos;nListLength=list.ListLength();}

//獲得下一個新結(jié)點,返回新結(jié)點地址template<classT>ListNode<T>*LinkedList<T>::GetListNode(constT&nItem,ListNode<T>*preNext){ListNode<T>*newListNode;newListNode=newListNode<T>(nItem,preNext);if(!newListNode){cerr<<″Memoryallocationfailure!″<<endl;exit(1);}returnnewListNode;}//輸出鏈表中的各個結(jié)點數(shù)據(jù)template<classT>voidLinkedList<T>::DisplayList(){ptrCurr=ptrFront;while(ptrCurr)//遍歷鏈表

{cout<<ptrCurr->ShowDate()<<endl;

ptrCurr=ptrCurr->NextListNode();}}//在鏈表中查找數(shù)據(jù)template<classT>intLinkedList<T>::Find(T&nItem){ptrCurr=ptrFront;ptrPrev=NULL;while(ptrCurr){if(ptrCurr->ShowDate()==nItem)