【正文】 R=NULL。 if(tempPlink==tail) tail=tempP。}templatetypename TNodeT* ListT::DeleteNode(NodeT* p){ NodeT* tempP=head。 } tempQInsertAfter(p)。}templatetypename Tvoid ListT::InsertOrder(NodeT *p){ NodeT *tempP=headlink,*tempQ=head。 if(tail==head) tail=p。 tempP=tempPlink。 } return count。 //搜索成功返回該結(jié)點(diǎn)地址，不成功返回NULL}templatetypename Tint ListT::Length(){ NodeT* tempP=headlink。 while(tempP!=NULLamp。 headlink=tempPlink。}templatetypename TListT::~List(){ MakeEmpty()。)。 //可用來向后生成鏈表，在表尾添加一個(gè)結(jié)點(diǎn) void InsertOrder(NodeT *p)。 //搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址 int Length()。//鏈表頭指針和尾指針public: List()。 return tempP。 link=p。}template typename T NodeT::Node(const T amp。 Getinfo()。 data)。templatetypename Tclass Node{ T info。二、編程與綜合練習(xí)題 給單鏈表類模板增加兩個(gè)成員函數(shù)：刪除鏈表中所有數(shù)據(jù)域?yàn)橹付ㄖ档慕Y(jié)點(diǎn)和取出鏈表中第K個(gè)元素（從1開始計(jì)數(shù)）。 寫出二叉樹的定義。 對(duì)比順序棧與鏈棧各自的長處和短處。 在單鏈表模板中為什么要把List類說明成Node的友元類？答：為了直接訪問結(jié)點(diǎn)的私有成員數(shù)據(jù)，以簡化程序。 要實(shí)現(xiàn)深拷貝，自定義的拷貝構(gòu)造函數(shù)應(yīng)該怎樣設(shè)計(jì)？答：如果類中有一個(gè)數(shù)據(jù)成員為指針，該類的一個(gè)對(duì)象中的這個(gè)指針p，指向了動(dòng)態(tài)分配的一個(gè)堆對(duì)象。注意這時(shí)釋放了p所指向的無名對(duì)象占用的內(nèi)存空間，也就是撤銷了該無名對(duì)象，稱動(dòng)態(tài)內(nèi)存釋放（dynamic memory deallocation），但指針p本身并沒有撤銷，它仍然存在，該指針?biāo)純?nèi)存空間并未釋放。后者多一個(gè)方括號(hào)，如果delete語句中少了方括號(hào)，因編譯器認(rèn)為該指針是指向數(shù)組第一個(gè)元素的指針，會(huì)產(chǎn)生回收不徹底的問題（只回收了第一個(gè)元素所占空間），加了方括號(hào)后就轉(zhuǎn)化為指向數(shù)組的指針，回收整個(gè)數(shù)組。答案：（1）二叉搜索樹（2）樹表（3）中序遍歷（4）升序序列 簡答題 new運(yùn)算符為一個(gè)變量或?qū)ο蠓峙浯鎯?chǔ)空間和為一個(gè)數(shù)組分配存儲(chǔ)空間，使用方法上有什么不同？對(duì)應(yīng)的delete運(yùn)算符使用有什么不同？答：為一個(gè)變量或?qū)ο蠓峙浯鎯?chǔ)空間其使用的格式如下：指針變量名=new 類型名(初始化式)；對(duì)于數(shù)組進(jìn)行動(dòng)態(tài)分配和撤銷的格式為：指針變量名=new 類型名[下標(biāo)表達(dá)式]。答案：（1）循環(huán)隊(duì)列 二叉樹的特點(diǎn)是： （1） 和 （2） 。對(duì)鏈隊(duì)，采用向 （4） 生成，新入隊(duì)的結(jié)點(diǎn)放在鏈的 （5） ，出隊(duì)操作在 （6） 位置。答案：（1）淺拷貝（2）同一個(gè)堆對(duì)象 單鏈表的結(jié)點(diǎn)包含兩個(gè)域： （1） 和 （2） 。答案：（1）3個(gè)（2）1個(gè)（3）30行10列的2位數(shù)組 當(dāng)動(dòng)態(tài)分配失敗，系統(tǒng)采用 （1） 來表示發(fā)生了異常。答案：（1）代碼區(qū)，存放程序代碼； （2）全局變量與靜態(tài)變量區(qū)，存放全局變量或?qū)ο螅òo態(tài)）；（3）局部變量區(qū)即棧（stack）區(qū)，存放局部變量；（4）自由存儲(chǔ)區(qū)（free store），即動(dòng)態(tài)存儲(chǔ)區(qū)或堆（heap）區(qū)。 靜態(tài)定義的變量和對(duì)象用標(biāo)識(shí)符命名，稱為 （1） ；而動(dòng)態(tài)建立的稱為 （2） ，動(dòng)態(tài)建立對(duì)象的初始化是通過 （3） 實(shí)現(xiàn) （4） 。如果new返回的指針丟失，則所分配的自由存儲(chǔ)區(qū)空間無法收回，稱為 （2） 。使用鏈表的最大的優(yōu)點(diǎn)是 （3） ，即使是動(dòng)態(tài)數(shù)組也做不到這一點(diǎn)。答案：（1）向前（2）鏈表頭的位置（3）鏈表頭（4）向后（5）尾部（6）鏈表頭 在計(jì)算機(jī)中進(jìn)行表達(dá)式的計(jì)算，為解決優(yōu)先級(jí)和運(yùn)算的結(jié)合性，必須使用 （1） 和 （2） 。答案：（1）每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子（2）子樹有左右之分 二叉樹的遍歷是按 （1） 分類，所謂中序遍歷是 （2） 。后者多一個(gè)[下標(biāo)表達(dá)式]，同時(shí)不能進(jìn)行初始化。delete [ ]的方括號(hào)中不需要填數(shù)組元素?cái)?shù)，系統(tǒng)自知。 為什么動(dòng)態(tài)建立類對(duì)象數(shù)組時(shí)，類的定義一定要有缺省的構(gòu)造函數(shù)？答：new后面類（class）類型也可以有參數(shù)。深拷貝時(shí)要給新建立的對(duì)象獨(dú)立分配一個(gè)堆對(duì)象。 雙向鏈表與單向鏈表相比，操作上有什么優(yōu)點(diǎn)?答：雙向鏈表可以很方便地找到表結(jié)點(diǎn)的前驅(qū)和后繼。答：順序?？梢噪S機(jī)訪問其中的元素，而鏈棧只能順序訪問。答：二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或?yàn)榭眨蚴怯梢粋€(gè)根結(jié)點(diǎn)及兩棵分別稱為左子樹和右子樹的（注意有左右之分）互不相交的二叉樹組成，其中左右子樹分別可以為空子樹或均為空樹。解：這兩個(gè)成員函數(shù)添在單鏈表類模板中（）本例數(shù)據(jù)域用了標(biāo)準(zhǔn)類string，也可以使用整數(shù)型。 //數(shù)據(jù)域 NodeT *link。//生成一般結(jié)點(diǎn)的構(gòu)造函數(shù) void InsertAfter(NodeT* P)。//增加取數(shù)據(jù)域函數(shù) friend class ListT。 data){ info=data。}templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。}templatetypename T T amp。 //構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表) ~List()。 //計(jì)算單鏈表長度 void PrintList()。 //按升序生成鏈表 NodeT*CreatNode(T data)。 //刪除鏈表中所有數(shù)據(jù)域?yàn)橹付ㄖ档慕Y(jié)點(diǎn) NodeT*GetNode(int)。 delete head。 //把頭結(jié)點(diǎn)后的第一個(gè)節(jié)點(diǎn)從鏈中脫離 delete tempP。amp。 int count=0。}templatetypename Tvoid ListT::PrintList(){ NodeT* tempP=headlink。 } coutendl。}templatetypename Tvoid ListT::InsertRear(NodeT *p){ plink=taillink。 //tempQ指向tempP前面的一個(gè)節(jié)點(diǎn) while(tempP!=NULL){ if(pinfotempPinfo)break。 //插在tempP指向結(jié)點(diǎn)之前，tempQ之后 if(tail==tempQ) tail=tempQlink。 while(tempPlink!=NULLamp。 return tempPRemoveAfter()。 while(TempP!=NULL){ //也可以利用尾指針 if(TempPinfo==p){ delete TempR。 //僅返回最后一次找到的結(jié)點(diǎn)}templatetypename T NodeT* ListT::GetNode(int i){//取出鏈表中第K個(gè)元素(從1計(jì)數(shù)) NodeT*TempP=headlink。 while(TempP!=NULLamp。 } return TempP。 Liststring list1。 for(i=0。 coutendl。 (P1)。 if(n1){ cout刪除所有含“n1Getinfo()”的結(jié)點(diǎn)。 cout輸出刪除所有指定結(jié)點(diǎn)后的鏈表：endl。 n1=(i)。} 為單鏈表類模板增加一個(gè)拷貝構(gòu)造函數(shù)和拷貝賦值運(yùn)算符（=）。如果看不懂拷貝構(gòu)造函數(shù)請(qǐng)畫一個(gè)空鏈表，逐步跟蹤拷貝過程，只要跟蹤幾個(gè)結(jié)點(diǎn)就可以理解。 //數(shù)據(jù)域 NodeT *link。 //生成一般結(jié)點(diǎn)的構(gòu)造函數(shù) void InsertAfter(NodeT* P)。 //增加取數(shù)據(jù)域函數(shù) friend class ListT。 data){ info=data。}templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。}templatetypename T T amp。 //構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表) List(ListT amp。 operator=(ListTamp。 //搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址 int Length()。 //可用來向后生成鏈表，在表尾添加一個(gè)結(jié)點(diǎn) void InsertOrder(NodeT *p)。)。}templatetypename TListT::List(ListT amp。 P1link=taillink。 }}templatetypename TListT::~List(){ MakeEmpty()。 ls){ NodeT* TempP=link,*P1。//向后生成list1 taillink=P1。}templatetypename Tvoid ListT::MakeEmpty(){ NodeT *tempP。 //刪除(釋放)脫離下來的結(jié)點(diǎn) } tail=head。tempPinfo!=data) tempP=tempPlink。 while(tempP!=NULL){ tempP=tempPlink。 while(tempP!=NULL){ couttempPinfo39。}templatetypename Tvoid ListT::InsertFront(NodeT *p){ plink=headlink。 taillink=p。 //找第一個(gè)比插入結(jié)點(diǎn)大的結(jié)點(diǎn)，由tempP指向 tempQ=tempP。}templatetypename TNodeT* ListT::CreatNode(T data){//建立新節(jié)點(diǎn) NodeT*tempP=new NodeT(data)。amp。} //本函數(shù)所用方法可省一個(gè)工作指針，與InsertOrder比較templatetypename T NodeT* ListT::RemoveAll(T amp。 TempR=DeleteNode(TempP)。 int j=1。amp。}//include int main(){ Nodeint * P1。 for(i=0。i16。 ()。 //清空原鏈表，看是否深拷貝 cout如無輸出list1已清空：endl。 cout輸出list3：endl。要求不刪除原結(jié)點(diǎn)，也不另建一個(gè)鏈表來取代，而是通過改變指針域的鏈接方向來逆轉(zhuǎn)鏈表。也可以用尾鏈表第一個(gè)結(jié)點(diǎn)重新鏈到原頭結(jié)點(diǎn)后面，并如此向前生成鏈表，同樣可以逆轉(zhuǎn)鏈表。//再定義鏈表類，~4中已給出的成員函數(shù)不再重復(fù) templatetypename Tclass List{ NodeT *head,*tail。templatetypename T void ListT::Reverse(){//鏈表翻轉(zhuǎn)函數(shù) NodeT*p1,*tempP,*tempQ。//p1形成一個(gè)過渡帶頭結(jié)點(diǎn)的鏈表 tail=head。 tempP=tempPlink。 //p1結(jié)點(diǎn)后的第一個(gè)節(jié)點(diǎn)從鏈中脫離 InsertRear(tempP)。 cout請(qǐng)輸入16個(gè)整數(shù)endl。 //隨機(jī)輸入16個(gè)整數(shù),有重復(fù)的 for(i=0。 //向前生成list1 } cout輸出list1：endl。 ()。 if(head==tail||headlink==tail) return。 while(p1!=NULL){ tempP=p1?？捎糜言瘮?shù)。 注意：當(dāng)采用友元函數(shù)重載+運(yùn)算符時(shí)，盡管重載函數(shù)是List的友元，而List是Node的友類，但因?yàn)橛言P(guān)系是不能傳遞的，還是不能訪問Node的