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