【正文】 T info。 includeiostreamusing namespace std。 ,DblListT amp。解：。 return 0。 cout輸出合并成的list：endl。 ()。 (P1)。i16。 ()。 (P1)。i16。 int a[16]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16},i。//為保證返回時(shí)用拷貝構(gòu)造函數(shù)復(fù)制一個(gè)鏈表返回，返回類型不能是引用，}//include int main(){ Nodeint * P1。//到后面一個(gè)結(jié)點(diǎn) } P1=P1Getlink()。 P2=P3。 while(P2!=NULL){//與后面結(jié)點(diǎn)逐個(gè)比較 if(P1Getinfo()==P2Getinfo()){//有重復(fù)的就刪去； P3=P2Getlink()。//刪去重復(fù)的結(jié)點(diǎn)。 //向后生成list1 P1=P1Getlink()。 //雖然本函數(shù)是List的友元，而List是Node的友類，但還是不能訪問Node的私有成員 while(P1!=NULL){ P2=(P1Getinfo())。 ls2){//重載+運(yùn)算符 ListT ls(ls1)。}templatetypename TListT operator+(ListT amp。 TempP=TempPlink。 //向后生成list1 taillink=P1。 //清空后tail= head while(TempP!=NULL){ P1=new NodeT(TempPinfo)。 ls){//重載=運(yùn)算符 NodeT* TempP=link,*P1。templatetypename TListT amp。 )。 //重載=運(yùn)算符 friend ListT operator+(ListT amp。 operator=(ListT amp。//鏈表頭指針和尾指針public: List()。}//取指針域}。 templatetypename Tclass List。 注意：當(dāng)采用友元函數(shù)重載+運(yùn)算符時(shí)，盡管重載函數(shù)是List的友元，而List是Node的友類，但因?yàn)橛言P(guān)系是不能傳遞的，還是不能訪問Node的私有成員，必須通過Node的接口函數(shù)去間接訪問。=運(yùn)算符先清空左邊的鏈表，再模仿拷貝構(gòu)造函數(shù)的編法編程?？捎糜言瘮?shù)。 //p1結(jié)點(diǎn)后的第一個(gè)節(jié)點(diǎn)從鏈中脫離 InsertFront(tempP)。 while(p1!=NULL){ tempP=p1。//p1指針指向第一個(gè)元素,形成一個(gè)無頭結(jié)點(diǎn)的過渡鏈表 tail=head。 if(head==tail||headlink==tail) return。}解2：采用向前生成鏈表，此程序更簡單。 ()。 ()。 //向前生成list1 } cout輸出list1：endl。i++){ P1=(a[i])。 //隨機(jī)輸入16個(gè)整數(shù),有重復(fù)的 for(i=0。i16。 cout請輸入16個(gè)整數(shù)endl。 Listint list1。 //p1結(jié)點(diǎn)后的第一個(gè)節(jié)點(diǎn)從鏈中脫離 InsertRear(tempP)。//找到p1鏈的鏈尾tempP。 tempP=tempPlink。 while(p1link!=NULL){//鏈表有頭結(jié)點(diǎn)可以保證算法無特殊結(jié)點(diǎn) tempP=p1。//p1形成一個(gè)過渡帶頭結(jié)點(diǎn)的鏈表 tail=head。//空鏈表和單結(jié)點(diǎn)鏈表不必處理 p1=new NodeT()。templatetypename T void ListT::Reverse(){//鏈表翻轉(zhuǎn)函數(shù) NodeT*p1,*tempP,*tempQ。 //構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表) …… void Reverse()。//再定義鏈表類，~4中已給出的成員函數(shù)不再重復(fù) templatetypename Tclass List{ NodeT *head,*tail。 //首先看結(jié)點(diǎn)組織，采用結(jié)點(diǎn)類，templatetypename Tclass List。也可以用尾鏈表第一個(gè)結(jié)點(diǎn)重新鏈到原頭結(jié)點(diǎn)后面，并如此向前生成鏈表，同樣可以逆轉(zhuǎn)鏈表。逆轉(zhuǎn)鏈表的成員函數(shù)對空鏈表和單結(jié)點(diǎn)鏈表不處理。要求不刪除原結(jié)點(diǎn)，也不另建一個(gè)鏈表來取代，而是通過改變指針域的鏈接方向來逆轉(zhuǎn)鏈表。 return 0。 cout輸出list3：endl。 cout輸出list2：endl。 //清空原鏈表，看是否深拷貝 cout如無輸出list1已清空：endl。 list3=list1。 ()。 (P1)。i16。i++)cina[i]。 for(i=0。 int a[16],i。}//include int main(){ Nodeint * P1。 j++。amp。 if(i==0) return head。 int j=1。 } return TempR。 TempR=DeleteNode(TempP)。 NodeT*TempP=headlink,*TempR=NULL。} //本函數(shù)所用方法可省一個(gè)工作指針，與InsertOrder比較templatetypename T NodeT* ListT::RemoveAll(T amp。 if(tempPlink==tail) tail=tempP。amp。}templatetypename TNodeT* ListT::DeleteNode(NodeT* p){ NodeT* tempP=head。}templatetypename TNodeT* ListT::CreatNode(T data){//建立新節(jié)點(diǎn) NodeT*tempP=new NodeT(data)。 } tempQInsertAfter(p)。 //找第一個(gè)比插入結(jié)點(diǎn)大的結(jié)點(diǎn)，由tempP指向 tempQ=tempP。}templatetypename Tvoid ListT::InsertOrder(NodeT *p){ NodeT *tempP=headlink,*tempQ=head。 taillink=p。 if(tail==head) tail=p。}templatetypename Tvoid ListT::InsertFront(NodeT *p){ plink=headlink。 tempP=tempPlink。 while(tempP!=NULL){ couttempPinfo39。 } return count。 while(tempP!=NULL){ tempP=tempPlink。 //搜索成功返回該結(jié)點(diǎn)地址，不成功返回NULL}templatetypename Tint ListT::Length(){ NodeT* tempP=headlink。tempPinfo!=data) tempP=tempPlink。 while(tempP!=NULLamp。 //刪除(釋放)脫離下來的結(jié)點(diǎn) } tail=head。 headlink=tempPlink。}templatetypename Tvoid ListT::MakeEmpty(){ NodeT *tempP。 TempP=TempPlink。//向后生成list1 taillink=P1。 while(TempP!=NULL){ P1=new NodeT(TempPinfo)。 ls){ NodeT* TempP=link,*P1。}templatetypename TListTamp。 }}templatetypename TListT::~List(){ MakeEmpty()。 tail=P1。 P1link=taillink。 head=tail=new NodeT()。}templatetypename TListT::List(ListT amp。/*取出鏈表中第K個(gè)元素（從1開始計(jì)數(shù)）*/}。)。 //創(chuàng)建一個(gè)結(jié)點(diǎn)(孤立結(jié)點(diǎn)) NodeT*DeleteNode(NodeT* p)。 //可用來向后生成鏈表，在表尾添加一個(gè)結(jié)點(diǎn) void InsertOrder(NodeT *p)。 //打印鏈表的數(shù)據(jù)域 void InsertFront(NodeT* p)。 //搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址 int Length()。 void MakeEmpty()。 operator=(ListTamp。 //拷貝構(gòu)造函數(shù) ~List()。 //構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表) List(ListT amp。}//增加取數(shù)據(jù)域函數(shù)//再定義鏈表類，選擇常用操作：包括建立有序鏈表、搜索遍歷、插入、刪除、取數(shù)據(jù)等templatetypename Tclass List{ NodeT *head,*tail。}templatetypename T T amp。 //已在鏈尾,后面無結(jié)點(diǎn) else link=tempPlink。}templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。}templatetypename Tvoid NodeT::InsertAfter(NodeT* p){ plink=link。 data){ info=data。template typename T NodeT::Node(){link=NULL。 //增加取數(shù)據(jù)域函數(shù) friend class ListT。 //刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)，返回該結(jié)點(diǎn)備用 T amp。 //生成一般結(jié)點(diǎn)的構(gòu)造函數(shù) void InsertAfter(NodeT* P)。 //生成頭結(jié)點(diǎn)的構(gòu)造函數(shù) Node(const T amp。 //數(shù)據(jù)域 NodeT *link。//首先看結(jié)點(diǎn)組織，采用結(jié)點(diǎn)類，凡與結(jié)點(diǎn)數(shù)據(jù)和指針操作有關(guān)函數(shù)作為成員函數(shù)templatetypename Tclass List。如果看不懂拷貝構(gòu)造函數(shù)請畫一個(gè)空鏈表，逐步跟蹤拷貝過程，只要跟蹤幾個(gè)結(jié)點(diǎn)就可以理解。注意：，即前一題增加的成員函數(shù)在本題中全部保留。} 為單鏈表類模板增加一個(gè)拷貝構(gòu)造函數(shù)和拷貝賦值運(yùn)算符（=）。 else cout鏈表出界！endl。 n1=(i)。 cout要求尋找第幾個(gè)節(jié)點(diǎn)？endl。 cout輸出刪除所有指定結(jié)點(diǎn)后的鏈表：endl。 delete n1。 if(n1){ cout刪除所有含“n1Getinfo()”的結(jié)點(diǎn)。 ()。 (P1)。ih。 coutendl。i++) coutsp[i]39。 for(i=0。 string m(東南大學(xué)),sp[h]={南京大學(xué),東南大學(xué),交通大學(xué),清華大學(xué),天津大學(xué),東南大學(xué),復(fù)旦大學(xué),浙江大學(xué),同濟(jì)大學(xué)}。 Liststring list1。int main(){ const int h=9。 } return TempP。ji){ TempP=TempPlink。 while(TempP!=NULLamp。 if(i0) return NULL。 //僅返回最后一次找到的結(jié)點(diǎn)}templatetypename T NodeT* ListT::GetNode(int i){//取出鏈表中第K個(gè)元素(從1計(jì)數(shù)) NodeT*TempP=headlink。 } TempP=TempPlink。 while(TempP!=NULL){ //也可以利用尾指針 if(TempPinfo==p){ delete TempR。p){//利用已有的DeleteNode() bool b=false。 return tempPRemoveAfter()。tempPlink!=p) tempP=tempPlink。 while(tempPlink!=NULLamp。 return tempP。 //插在tempP指向結(jié)點(diǎn)之前