【正文】 數(shù)先建立一個(gè)頭結(jié)點(diǎn)，再以原鏈表的各結(jié)點(diǎn)的數(shù)據(jù)域來構(gòu)造新鏈表的各對應(yīng)結(jié)點(diǎn)。 cini。 n1=(m)。\t39。 int i。 if(i==0) return head。 NodeT*TempP=headlink,*TempR=NULL。}templatetypename TNodeT* ListT::DeleteNode(NodeT* p){ NodeT* tempP=head。}templatetypename Tvoid ListT::InsertOrder(NodeT *p){ NodeT *tempP=headlink,*tempQ=head。 tempP=tempPlink。 //搜索成功返回該結(jié)點(diǎn)地址，不成功返回NULL}templatetypename Tint ListT::Length(){ NodeT* tempP=headlink。 headlink=tempPlink。)。 //搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址 int Length()。 return tempP。}template typename T NodeT::Node(const T amp。 data)。二、編程與綜合練習(xí)題 給單鏈表類模板增加兩個(gè)成員函數(shù)：刪除鏈表中所有數(shù)據(jù)域?yàn)橹付ㄖ档慕Y(jié)點(diǎn)和取出鏈表中第K個(gè)元素（從1開始計(jì)數(shù)）。 對比順序棧與鏈棧各自的長處和短處。 要實(shí)現(xiàn)深拷貝，自定義的拷貝構(gòu)造函數(shù)應(yīng)該怎樣設(shè)計(jì)？答：如果類中有一個(gè)數(shù)據(jù)成員為指針，該類的一個(gè)對象中的這個(gè)指針p，指向了動(dòng)態(tài)分配的一個(gè)堆對象。后者多一個(gè)方括號，如果delete語句中少了方括號，因編譯器認(rèn)為該指針是指向數(shù)組第一個(gè)元素的指針，會(huì)產(chǎn)生回收不徹底的問題（只回收了第一個(gè)元素所占空間），加了方括號后就轉(zhuǎn)化為指向數(shù)組的指針，回收整個(gè)數(shù)組。答案：（1）循環(huán)隊(duì)列 二叉樹的特點(diǎn)是： （1） 和 （2） 。答案：（1）淺拷貝（2）同一個(gè)堆對象 單鏈表的結(jié)點(diǎn)包含兩個(gè)域： （1） 和 （2） 。答案：（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ū)。如果new返回的指針丟失，則所分配的自由存儲(chǔ)區(qū)空間無法收回，稱為 （2） 。答案：（1）向前（2）鏈表頭的位置（3）鏈表頭（4）向后（5）尾部（6）鏈表頭 在計(jì)算機(jī)中進(jìn)行表達(dá)式的計(jì)算，為解決優(yōu)先級和運(yùn)算的結(jié)合性，必須使用 （1） 和 （2） 。后者多一個(gè)[下標(biāo)表達(dá)式]，同時(shí)不能進(jìn)行初始化。 為什么動(dòng)態(tài)建立類對象數(shù)組時(shí)，類的定義一定要有缺省的構(gòu)造函數(shù)？答：new后面類（class）類型也可以有參數(shù)。 雙向鏈表與單向鏈表相比，操作上有什么優(yōu)點(diǎn)?答：雙向鏈表可以很方便地找到表結(jié)點(diǎn)的前驅(qū)和后繼。答：二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或?yàn)榭?，或是由一個(gè)根結(jié)點(diǎn)及兩棵分別稱為左子樹和右子樹的（注意有左右之分）互不相交的二叉樹組成，其中左右子樹分別可以為空子樹或均為空樹。 //數(shù)據(jù)域 NodeT *link。//增加取數(shù)據(jù)域函數(shù) friend class ListT。}templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。 //構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表) ~List()。 //按升序生成鏈表 NodeT*CreatNode(T data)。 delete head。amp。}templatetypename Tvoid ListT::PrintList(){ NodeT* tempP=headlink。}templatetypename Tvoid ListT::InsertRear(NodeT *p){ plink=taillink。 //插在tempP指向結(jié)點(diǎn)之前，tempQ之后 if(tail==tempQ) tail=tempQlink。 return tempPRemoveAfter()。 //僅返回最后一次找到的結(jié)點(diǎn)}templatetypename T NodeT* ListT::GetNode(int i){//取出鏈表中第K個(gè)元素(從1計(jì)數(shù)) NodeT*TempP=headlink。 } return TempP。 for(i=0。 (P1)。 cout輸出刪除所有指定結(jié)點(diǎn)后的鏈表：endl。} 為單鏈表類模板增加一個(gè)拷貝構(gòu)造函數(shù)和拷貝賦值運(yùn)算符（=）。 //數(shù)據(jù)域 NodeT *link。 //增加取數(shù)據(jù)域函數(shù) friend class ListT。}templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。 //構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表) List(ListT amp。 //搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址 int Length()。)。 P1link=taillink。 ls){ NodeT* TempP=link,*P1。}templatetypename Tvoid ListT::MakeEmpty(){ NodeT *tempP。tempPinfo!=data) tempP=tempPlink。 while(tempP!=NULL){ couttempPinfo39。 taillink=p。}templatetypename TNodeT* ListT::CreatNode(T data){//建立新節(jié)點(diǎn) NodeT*tempP=new NodeT(data)。} //本函數(shù)所用方法可省一個(gè)工作指針，與InsertOrder比較templatetypename T NodeT* ListT::RemoveAll(T amp。 int j=1。}//include int main(){ Nodeint * P1。i16。 //清空原鏈表，看是否深拷貝 cout如無輸出list1已清空：endl。要求不刪除原結(jié)點(diǎn)，也不另建一個(gè)鏈表來取代，而是通過改變指針域的鏈接方向來逆轉(zhuǎn)鏈表。//再定義鏈表類，~4中已給出的成員函數(shù)不再重復(fù) templatetypename Tclass List{ NodeT *head,*tail。//p1形成一個(gè)過渡帶頭結(jié)點(diǎn)的鏈表 tail=head。 //p1結(jié)點(diǎn)后的第一個(gè)節(jié)點(diǎn)從鏈中脫離 InsertRear(tempP)。 //隨機(jī)輸入16個(gè)整數(shù),有重復(fù)的 for(i=0。 ()。 while(p1!=NULL){ tempP=p1。 注意：當(dāng)采用友元函數(shù)重載+運(yùn)算符時(shí)，盡管重載函數(shù)是List的友元，而List是Node的友類，但因?yàn)橛言P(guān)系是不能傳遞的，還是不能訪問Node的私有成員，必須通過Node的接口函數(shù)去間接訪問。 operator=(ListT amp。 ls){//重載=運(yùn)算符 NodeT* TempP=link,*P1。}templatetypename TListT operator+(ListT amp。//刪去重復(fù)的結(jié)點(diǎn)。//為保證返回時(shí)用拷貝構(gòu)造函數(shù)復(fù)制一個(gè)鏈表返回，返回類型不能是引用，}//include int main(){ Nodeint * P1。 ()。 cout輸出合并成的list：endl。 includeiostreamusing namespace std。 friend class DblListT。 ~DblList()。 //清空鏈表 void Merge(DblListT amp。 //清空鏈表 delete head。 data){ //新節(jié)點(diǎn)在鏈尾 current=new DblNodeT。amp。 while(current!=headamp。 current=currentrlink。 dbl1,DblListT amp。 } if(tdp1!=) while(tdp1!=){ Insert(tdp1info)。 for(i=0。 cout雙向鏈表長度：()endl。 delete (tp)。*這是C++標(biāo)準(zhǔn)模板庫中的做法。data)。 //輸出棧內(nèi)所有數(shù)據(jù)}。\t39。 //返回棧頂元素，同時(shí)棧頂指針退1}templatetypename T T StackT::GetElem(int I){ assert(i=topamp。 //建立?？臻g assert(elements!=0)。i25。i25。 public: Stack(int maxs=20):stack(maxs){}。} //輸出棧內(nèi)所有數(shù)據(jù)}。 while(!()){ b[i]=()。 return 0。data)。 //輸出順序表內(nèi)所有數(shù)據(jù)}。\t39。 //返回順序表最后一個(gè)元素，同時(shí)last減1}templatetypename T T seqlistT::GetElem(int i){ assert(i=lastamp。 //建立順序表空間 assert(elements!=0)。templatetypename Tclass Queue。 link=l。 //進(jìn)隊(duì) T DeQue()。front=frontlink。 if(front==NULL) front=rear=p。 return data。i++) (str1[i])。}解2：在這里的第2種方法中采用類似STL中隊(duì)適配器的做法，鏈表作為隊(duì)的成員對象，采用聚合技術(shù)。} //進(jìn)隊(duì) T DeQue(){return ()。 char str1[]=abcdefghijklmnop。//先進(jìn)先出，串結(jié)束符成為空格放最前面 coutendl。} Node(T data,Node *l=NULL)。templatetypename T NodeT::Node(T data,Node *l){ info=data。)。 while(front!=NULL){ temp=front。 //出鏈 T GetFront()。}。}。 return 0。i17。} //查看隊(duì)頭數(shù)據(jù) void MakeEmpty(){()。采用適配器技術(shù)，可以通過模板類型參數(shù)選擇編程者認(rèn)可的任一種合適的線性表類對象作為放置數(shù)據(jù)的容器。i17。 return frontinfo。 front=p。 }}templatetypename TQueueT::~Queue(){MakeEmpty()。 //查看隊(duì)頭數(shù)據(jù) void MakeEmpty()。templatetypename Tclass Queue{ NodeT *front,*rear。 NodeT *link。ji。i=0)。}templatetypename T void seqlistT::Push_back(const T amp。 last=1。 //順序表彈出一個(gè)元素，top T GetElem(int i)。templatetypename Tclass seqlist{ int last。 } if(()) cout?？誩ndl。 Stackint istack(5)。data){(data)。\t39。 ()。ji。i=0)。}templatetypename T void StackT::Push(const T amp。 top=1。 //彈出，top T GetElem(int i)。templatetypename Tclass Stack{ int top。 ()。 (Dbl1,Dbl2)。i++) (a[i])。 } if(tdp2!=) while(tdp2!=){ Insert(tdp2info)。 while(t