-- template 的用法
在程序設(shè)計(jì)當(dāng)中經(jīng)常會(huì)出現(xiàn)使用同種數(shù)據(jù)結(jié)構(gòu)的不同實(shí)例的情況。例如:在一個(gè)程序中
可以使用多個(gè)隊(duì)列、樹(shù)、圖等結(jié)構(gòu)來(lái)組織數(shù)據(jù)。同種結(jié)構(gòu)的不同實(shí)例,也許只在數(shù)據(jù)元素
的類(lèi)型或數(shù)量上略有差異,如果對(duì)每個(gè)實(shí)例都重新定義,則非常麻煩且容易出錯(cuò)。那么能
否對(duì)同種類(lèi)型數(shù)據(jù)結(jié)構(gòu)僅定義一次呢?答案是肯定的,C++提供的類(lèi)模板(Class Template
)就可以實(shí)現(xiàn)該功能。

一、類(lèi)模板
類(lèi)模板是C++提供的一種特殊機(jī)制,通過(guò)它我們可以定義一種特殊的類(lèi)(稱(chēng)為模板類(lèi)),在類(lèi)
的定義中可以包含待定的類(lèi)型參數(shù),在聲明類(lèi)的實(shí)例時(shí),系統(tǒng)會(huì)自動(dòng)根據(jù)傳遞的類(lèi)型生成
用戶想要生成的類(lèi)實(shí)例。下面是用C++實(shí)現(xiàn)的一個(gè)簡(jiǎn)單的模板類(lèi)Clist的定義。
Template <class T, int I> class CList
{
public:
int SetItem(int Index, const T &Item);
int GetItem(int Index, T &Item);
private:
T Buffer;
}
在這里,T是類(lèi)型參數(shù),I是整型常量參數(shù)。T和I的實(shí)際值是在聲明具體類(lèi)實(shí)例時(shí)指定的。
模板類(lèi)的<>號(hào)內(nèi)可以包括任意個(gè)類(lèi)型參數(shù)和常量參數(shù)(至少要有一個(gè)參數(shù))。類(lèi)型參數(shù)和
常量參數(shù)可以是任何合法的標(biāo)準(zhǔn)類(lèi)型和用戶自定義類(lèi)型,包括簡(jiǎn)單類(lèi)型及各種結(jié)構(gòu)體。同
其他類(lèi)一樣,類(lèi)成員函數(shù)SetItem的實(shí)現(xiàn)可以在類(lèi)定義內(nèi)完成,也可以在類(lèi)CList定義處實(shí)
現(xiàn):
template<class T, int I> int CList<T, I>::SetItem(int Index, const T &Item)
{
if ( (Index<0)||(Index>I-1) )
　return 0; // 出錯(cuò)
Buffer[Index]= Item ;
　return 1; // 成功
}
值得注意的是,在類(lèi)定義外完成函數(shù)實(shí)現(xiàn)時(shí),必須以關(guān)鍵字template和類(lèi)模板定義中相同
的參數(shù)表(<>號(hào)內(nèi)的)開(kāi)頭(上例為template<class T, int I>),并且范圍分解操作符前的
類(lèi)名后應(yīng)跟上模板參數(shù)名清單(上例為CList<T, I>)。另外,與非模板類(lèi)不同的是,必須將
函數(shù)實(shí)現(xiàn)包括在調(diào)用它的每個(gè)源文件中,使編譯器能從函數(shù)實(shí)現(xiàn)產(chǎn)生代碼。通常的做法是
將模板類(lèi)的函數(shù)實(shí)現(xiàn)也放在定義該類(lèi)的頭文件中,這樣只需在調(diào)用的源文件中包含該頭文
件即可。
那么,如何使用生成特定的類(lèi)實(shí)例呢?我們可以像使用其他類(lèi)一樣來(lái)使用模板類(lèi),不過(guò)必須
指定模板參數(shù)的值。例如采用如下聲明:
CList <int, 100> IntList;
則使IntList成為CList類(lèi)的實(shí)例,每次出現(xiàn)的T參數(shù)都換成int, 每次出現(xiàn)的I參數(shù)都換成
100。這樣,IntList類(lèi)中的Buffer就是一個(gè)長(zhǎng)度為100的整型數(shù)組,SetItem和GetItem函數(shù)
參數(shù)是int值的引用。例:
IntList.SetItem(0, 5); //給數(shù)組第一個(gè)元素賦為整數(shù)5
模板類(lèi)還可以像其他類(lèi)一樣可以定義構(gòu)造函數(shù)和析構(gòu)函數(shù)。下面我們以一種簡(jiǎn)單的數(shù)據(jù)
結(jié)構(gòu)——堆棧為例,來(lái)說(shuō)明如何用類(lèi)模板來(lái)構(gòu)造通用數(shù)據(jù)結(jié)構(gòu)。

二、 利用類(lèi)模板實(shí)現(xiàn)通用堆棧結(jié)構(gòu)
任何抽象數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn),歸根結(jié)底都只有兩種方式:順序存儲(chǔ)(用數(shù)組實(shí)現(xiàn))
,鏈?zhǔn)酱鎯?chǔ)(用指針實(shí)現(xiàn))。堆棧也不例外,按其實(shí)現(xiàn)方式可分為順序棧(用數(shù)組實(shí)現(xiàn))和鏈
棧(用指針實(shí)現(xiàn))。

1. 通用順序棧的實(shí)現(xiàn)
因?yàn)轫樞驐Ｖ械脑卦诳臻g上連續(xù)存儲(chǔ),棧頂?shù)脑匚恢眯枰⒚?所以構(gòu)造順序棧的模
板類(lèi)應(yīng)該有這樣的一些成員變量:一個(gè)待定類(lèi)型和長(zhǎng)度的數(shù)組Buffer,一個(gè)記錄棧頂元素
的數(shù)組下標(biāo)的整型變量top。堆棧的基本操作主要有:入棧(Push)、出棧(Pop)、置空(Se
tEmpty)、判斷當(dāng)前狀態(tài)(IsEmpty)等,它們應(yīng)用模板類(lèi)的成員函數(shù)來(lái)實(shí)現(xiàn)。作為一個(gè)標(biāo)準(zhǔn)
的類(lèi),它還應(yīng)該有自己的構(gòu)造函數(shù)和析構(gòu)函數(shù)。具有這些功能的模板類(lèi),就可以作為一個(gè)
通用的順序棧來(lái)使用了。該類(lèi)的定義如下:
template <class T,int SIZE> class CArrayStackTemp
{
public:
CArrayStackTemp () //缺省構(gòu)造函數(shù),構(gòu)造一個(gè)空堆棧
{
top= -1;
};
～ CArrayStackTemp (){};//析構(gòu)函數(shù)
　void SetEmpty (); //置空堆棧
　bool IsEmpty(); //判斷堆棧是否為空
　bool Push(T element); //入棧
　bool Pop(T& element);//出棧
private:
T Buffer[SIZE];
　int top;
};
與堆棧的基本操作相對(duì)應(yīng)的成員函數(shù)的實(shí)現(xiàn)如下:
template <class T, int SIZE> void CArrayStackTemp<T, SIZE>:: SetEmpty ()
{
top= -1; //將棧頂指針賦 -1,并不實(shí)際清除數(shù)組元素
}
template <class T, int SIZE> bool CArrayStackTemp<T, SIZE>:: IsEmpty ()
{
return(top == -1);
}
template <class T, int SIZE> bool CArrayStackTemp<T, SIZE>:: Push (T element
)
{
top++;
if (top>SIZE-1)
{
top--;
return false; //堆棧已滿,不能執(zhí)行入棧操作
}
Buffer[top]=element;
return true;
}
template <class T, int SIZE> void CArrayStackTemp<T, SIZE>:: Pop (T& element
)
{
if (IsEmpty())
　return false;
element =Buffer[top];
top--;
return true;
}
根據(jù)實(shí)際需要,還可以擴(kuò)充堆棧功能。例如:加入取棧頂元素、求堆棧長(zhǎng)度等操作,其方法
如上。

2. 通用鏈棧的實(shí)現(xiàn)
模板類(lèi)中允許使用指針和定義自己的結(jié)構(gòu),這就為實(shí)現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)提供了保證。這里采用一
個(gè)單鏈表來(lái)實(shí)現(xiàn)堆棧,棧頂指針指向鏈表的第一個(gè)結(jié)點(diǎn),入棧和出棧均在鏈表的頭進(jìn)行。
該模板類(lèi)的定義如下:
template <class T> class CLinkStackTemp
{
public:
　//類(lèi)的缺省構(gòu)造函數(shù),生成一個(gè)空堆棧
CLinkStackTemp ()
{
top=NULL;
};
～ClinkStackTemp(){}; //析構(gòu)函數(shù)
　//定義結(jié)點(diǎn)結(jié)構(gòu)
　struct node
{
T
　 data; //入棧元素
　node* next; //指向下一結(jié)點(diǎn)的指針
};
　void SetEmpty(); //置空堆棧
　bool IsEmpty(); //判斷堆棧是否為空
　bool Push(T element); //壓入堆棧
　bool Pop(T& element);//彈出堆棧
private:
　node* top;
};
該類(lèi)的成員函數(shù)實(shí)現(xiàn)如下:
template <class T> void CLinkStackTemp <T>::SetEmpty()
{
//釋放堆棧占用的內(nèi)存
node* temp;
while (top!=NULL)
{
　temp=top;
　top=top->next;
　delete temp;
}
}
template <class T> bool CLinkStackTemp <T>::IsEmpty()
{
return (top==NULL);
}
template <class T> bool CLinkStackTemp <T>::Push(T element)
{
node* temp=new node();
if (temp ==NULL)
　return false ;
temp->data=element;
temp->next=top;
top=temp;
return true;
}
template <class T> bool CLinkStackTemp <T>::Pop(T& element)
{
if ( IsEmpty())
　return false;
node* q = top;
element = top->data;
top=top->next;
delete q;
return true;
}
與順序棧的實(shí)現(xiàn)略有不同,鏈棧不必指定棧的容量,其大小可以是近似"無(wú)限"的。為了程
序的使用方便,我們同樣可以加入一些增強(qiáng)的功能。

三、 通用堆棧類(lèi)的使用
通用堆棧類(lèi)的使用較為簡(jiǎn)單,堆棧類(lèi)的實(shí)例就是一個(gè)可以方便使用的堆棧。對(duì)堆棧的操作
都是通過(guò)類(lèi)的成員函數(shù)來(lái)實(shí)現(xiàn)的。使用的具體步驟如下:

1. 在要使用堆棧類(lèi)的程序代碼的文件開(kāi)頭包括模板類(lèi)及其成員函數(shù)的定義。

2. 類(lèi)的實(shí)例化,可聲明成變量,也可以聲明它的指針,如:
CArrayStackTemp <int, 100> intStack; //生成一個(gè)長(zhǎng)度為100的int型堆棧
//生成一個(gè)元素為Record型的堆棧,Record為自定義結(jié)構(gòu)
CLinkStackTemp <Record>* RecordStack;
RecordStack=new CLinkStackTemp<Record>;
應(yīng)注意在定義順序棧時(shí),必須指定棧的大小,而鏈棧則不必。另外在指定指針類(lèi)型和執(zhí)行
new操作時(shí),必須對(duì)模板參數(shù)賦值,并且前后要一致。

3. 對(duì)堆棧進(jìn)行操作,如:
intStack.Push(3); //將整數(shù)3入棧
RecordStack.SetEmpty(); //將堆棧置空
無(wú)論我們使用哪種堆棧類(lèi),對(duì)用戶來(lái)講都是透明的,操作起來(lái)并無(wú)差別。