【文章內(nèi)容簡介】 //tempQ指向tempP前面的一個節(jié)點 while(tempP!=NULL){ if(pinfotempPinfo)break。 //找第一個比插入結(jié)點大的結(jié)點，由tempP指向 tempQ=tempP。 tempP=tempPlink。 } tempQInsertAfter(p)。 //插在tempP指向結(jié)點之前，tempQ之后 if(tail==tempQ) tail=tempQlink。}templatetypename TNodeT* ListT::CreatNode(T data){//建立新節(jié)點 NodeT*tempP=new NodeT(data)。 return tempP。}templatetypename TNodeT* ListT::DeleteNode(NodeT* p){ NodeT* tempP=head。 while(tempPlink!=NULLamp。amp。tempPlink!=p) tempP=tempPlink。 if(tempPlink==tail) tail=tempP。 return tempPRemoveAfter()。} //本函數(shù)所用方法可省一個工作指針，與InsertOrder比較templatetypename T NodeT* ListT::RemoveAll(T amp。p){/*利用已有的DeleteNode()*/ bool b=false。 NodeT*TempP=headlink,*TempR=NULL。 while(TempP!=NULL){ //也可以利用尾指針 if(TempPinfo==p){ delete TempR。 TempR=DeleteNode(TempP)。 } TempP=TempPlink。 } return TempR。}templatetypename T NodeT* ListT::GetNode(int i){//取出鏈表中第K個元素(從1開始) NodeT*TempP=headlink。 int j=1。 if(i0) return NULL。 if(i==0) return head。 while(TempP!=NULLamp。amp。ji){ TempP=TempPlink。 j++。 } return TempP。}//include int main(){ Nodeint * P1。 Listint list1。 int a[16],i。 cout請輸入16個整數(shù)endl。 for(i=0。i16。i++)cina[i]。 //隨機輸入16個整數(shù) for(i=0。i16。i++){ P1=(a[i])。 (P1)。 //向前生成list1 } cout輸出list1：endl。 ()。 Listint list2(list1),list3。 list3=list1。 ()。 //清空原鏈表，看是否深拷貝 cout如無輸出list1已清空：endl。 ()。 cout輸出list2：endl。 ()。 cout輸出list3：endl。 ()。 return 0。} 試為單鏈表類模板設(shè)計一個將鏈表逆轉(zhuǎn)的成員函數(shù)。要求不刪除原結(jié)點，也不另建一個鏈表來取代，而是通過改變指針域的鏈接方向來逆轉(zhuǎn)鏈表。解：。逆轉(zhuǎn)鏈表的成員函數(shù)對空鏈表和單結(jié)點鏈表不處理。對多結(jié)點鏈表，用尾指針指向第一個結(jié)點，找到該尾鏈表最后一個結(jié)點重新鏈到原頭結(jié)點后面；再找到該尾鏈表最后一個結(jié)點，并如此向后生成鏈表，就可以逆轉(zhuǎn)鏈表。也可以用尾鏈表第一個結(jié)點重新鏈到原頭結(jié)點后面，并如此向前生成鏈表，同樣可以逆轉(zhuǎn)鏈表。解1：//includeiostreamusing namespace std。 //首先看結(jié)點組織，采用結(jié)點類，templatetypename Tclass List。templatetypename Tclass Node{ ……}。//再定義鏈表類，~4中已給出的成員函數(shù)不再重復(fù) templatetypename Tclass List{ NodeT *head,*tail。//鏈表頭指針和尾指針public: List()。 //構(gòu)造函數(shù)，生成頭結(jié)點(空鏈表) …… void Reverse()。//翻轉(zhuǎn)鏈表}。templatetypename T void ListT::Reverse(){//鏈表翻轉(zhuǎn)函數(shù) NodeT*p1,*tempP,*tempQ。 if(head==tail||headlink==tail) return。//空鏈表和單結(jié)點鏈表不必處理 p1=new NodeT()。 p1link=headlink。//p1形成一個過渡帶頭結(jié)點的鏈表 tail=head。 headlink=NULL。 while(p1link!=NULL){//鏈表有頭結(jié)點可以保證算法無特殊結(jié)點 tempP=p1。 while(tempPlink!=NULL){ tempQ=tempP。 tempP=tempPlink。 }。//找到p1鏈的鏈尾tempP。 tempQlink=NULL。 //p1結(jié)點后的第一個節(jié)點從鏈中脫離 InsertRear(tempP)。 //脫離下來的結(jié)點重新向前生成翻轉(zhuǎn)后的新鏈表 }}//include int main(){ Nodeint * P1。 Listint list1。 int a[16],i。 cout請輸入16個整數(shù)endl。 for(i=0。i16。i++) cina[i]。 //隨機輸入16個整數(shù),有重復(fù)的 for(i=0。i16。i++){ P1=(a[i])。 (P1)。 //向前生成list1 } cout輸出list1：endl。 ()。 ()。 cout輸出逆轉(zhuǎn)后的list1：endl。 ()。 return 0。}解2：采用向前生成鏈表，此程序更簡單。templatetypename T void ListT::Reverse(){//鏈表翻轉(zhuǎn)函數(shù) NodeT*p1,*tempP。 if(head==tail||headlink==tail) return。//空鏈表和單結(jié)點鏈表不必處理 p1=headlink。//p1指針指向第一個元素,形成一個無頭結(jié)點的過渡鏈表 tail=head。 headlink=NULL。 while(p1!=NULL){ tempP=p1。 p1=tempPlink。 //p1結(jié)點后的第一個節(jié)點從鏈中脫離 InsertFront(tempP)。 //脫離下來的結(jié)點重新向前生成翻轉(zhuǎn)后的新鏈表 }} 為單鏈表重載“+”運算符，實現(xiàn)兩個單鏈表對象的連接，但要去除數(shù)據(jù)域相同的結(jié)點。可用友元函數(shù)。解：為了實現(xiàn)ls3=ls1+ls2,需重載=和+兩個運算符。=運算符先清空左邊的鏈表，再模仿拷貝構(gòu)造函數(shù)的編法編程。+運算符先建立一個局部鏈表，拷入被加鏈表，再以加鏈表的數(shù)據(jù)域生成局部鏈表后面的結(jié)點，最后去除數(shù)據(jù)域相同的結(jié)點。 注意：當(dāng)采用友元函數(shù)重載+運算符時，盡管重載函數(shù)是List的友元，而List是Node的友類，但因為友元關(guān)系是不能傳遞的，還是不能訪問Node的私有成員，必須通過Node的接口函數(shù)去間接訪問。//includeiostreamusing namespace std。 templatetypename Tclass List。templatetypename Tclass Node{ ……public: ……NodeT*Getlink(){return link。}//取指針域}。templatetypename Tclass List{ NodeT *head,*tail。//鏈表頭指針和尾指針public: List()。 //構(gòu)造函數(shù)，生成頭結(jié)點(空鏈表) …… ListT amp。 operator=(ListT amp。)。 //重載=運算符 friend ListT operator+(ListT amp。 ,ListT amp。 )。 //重載+運算符}。templatetypename TListT amp。 ListT::operator=(ListT amp。 ls){//重載=運算符 NodeT* TempP=link,*P1。 MakeEmpty()。 //清空后tail= head while(TempP!=NULL){ P1=new NodeT(TempPinfo)。 P1link=taillink。 //向后生成list1 taillink=P1。 tail=P1。 TempP=TempPlink。 } return *this。}templatetypename TListT operator+(ListT amp。 ls1,ListT amp。 ls2){//重載+運算符 ListT ls(ls1)。 //新鏈表，生命期僅在本函數(shù)域中 NodeT* P1=Getlink(),*P2,*P3。 //雖然本函數(shù)是List的友元，而List是Node的友類，但還是不能訪問Node的私有成員 while(P1!=NULL){ P2=(P1Getinfo())。 (P2)。 //向后生成list1 P1=P1Getlink()。 } P1=Getlink()。//刪去重復(fù)的結(jié)點。 while(P1!=NULL){ P2=P1Getlink()。 while(P2!=NULL){//與后面結(jié)點逐個比較 if(P1Getinfo()==P2Getinfo()){//有重復(fù)的就刪去； P3=P2Getlink()。//刪去后P2空懸 (P2)。 P2=P3。 } P2=P2Getlink()。//到后面一個結(jié)點 } P1=P1Getlink()。//再用第二個....}//先用第一個結(jié)點，與后面結(jié)點逐個比較，有重復(fù)的就刪去；再用第二個.... return ls。//為保證返回時用拷貝構(gòu)造函數(shù)復(fù)制一個鏈表返回，返回類型不能是引用，}//include int main(){ Nodeint * P1。 Listint list1,list2,list。 int a[16]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16},i。 for(i=0。i16。i++){ P1=(a[i])。 (P1)。//向后生成list1 } cout輸出list1：endl。 ()。 for(i=0。i16。i++){ P1=(a[i]+10)。 (P1)。//向后生成list1 } cout輸出list2：endl。 ()。 list=list1+list2。 cout輸出合并成的list：endl。 ()。 return 0。} 將兩個有序的雙向鏈表合并為一個有序的雙向鏈表，刪去相同結(jié)點。解：。函數(shù)為：void Merge(DblListT amp。 ,DblListT amp。)。 includeiostreamusing namespace std。templatetypename T class DblList。templatetypename T class DblNode{ //結(jié)點類 T info。 //數(shù)據(jù)域 DblNodeT *llink,*rlink。 //前驅(qū)（左鏈）、后繼（右鏈）指針public: DblNode(T data)。 DblNode()。 T Getinfo(){return info。}。 friend class DblListT。}。templatetypename T DblNodeT::DblNode(){ llink=rlink=NULL。}templatetypename T DblNodeT::DblNode(T data){ info=data。 llink=NULL。 rlink=NULL。}templatetypename Tclass DblList{ //雙鏈表類 DblNodeT *hea