雙向鏈表的應(yīng)用

雙向鏈表從單鏈表派生出雙向鏈表可以有以下做法：一種就是先定義一個(gè)雙鏈節(jié)點(diǎn)--但是，它的名字必須叫Node，這是沒(méi)辦法的事；不然你就只好拷貝一份單鏈表的實(shí)現(xiàn)文件，把其中的Node全都替換成你的雙鏈節(jié)點(diǎn)名字，但是這就不叫繼承了。另一種做法就是先定義一種結(jié)構(gòu)例如這樣的：template<classType>classnewtype{public:Typedata;Node<newtype>*link;}當(dāng)你派生雙向鏈表時(shí)，這樣寫template<calssType>classDblList:publicList<newtype<Type>>，注意連續(xù)的兩個(gè)">"之間要有空格?；蛘吒静欢x這樣的結(jié)構(gòu)，直接拿Node類型來(lái)做，例如我下面給出的。但是，請(qǐng)注意要完成"=="的重載，否則，你又要重寫Find函數(shù)，并且其他的某些操作也不方便。在開(kāi)始完成你的從單鏈表派生出來(lái)的雙向鏈表之前，要在單鏈表這個(gè)基類中添加修改當(dāng)前指針和當(dāng)前前驅(qū)指針的接口，如下所示：protected:voidPut(Node<Type>*p)//盡量不用，雙向鏈表將使用這個(gè)完成向前移動(dòng){current=p;}voidPutPrior(Node<Type>*p)//盡量不用，原因同上{prior=p;}因?yàn)檫@個(gè)接口很危險(xiǎn)，而且?guī)缀跤貌坏?，所以我在前面并沒(méi)有給出，但要完成雙向鏈表最"杰出"的優(yōu)點(diǎn)--向前移動(dòng)當(dāng)前指針，必須要使用。另外說(shuō)的是，我從前也從來(lái)沒(méi)計(jì)劃從單鏈表派生雙鏈表，下面你將看到，這個(gè)過(guò)程很讓人煩人，甚至不如重寫一個(gè)來(lái)的省事，執(zhí)行效率也不是很好，這種費(fèi)力不討好的事做它有什么意思呢？的確，我也覺(jué)得我在鉆牛角尖。定義和實(shí)現(xiàn)#ifndefDblList_H#defineDblList_H#include"List.h”template<classType>classDblList:publicListVNodeVType>>{public:Type*Get(){if(pGet()!=NULL)return&pGet()->data.data;elsereturnNULL;}Type*Next(){pNext();returnGet();}Type*Prior(){if(pGetPrior!=NULL){Put(pGetPrior());PutPrior((NodeVNode<Type>>*)pGet()->data.link);returnGet();}returnNULL;}voidInsert(constType&value){NodeVType>newdata(value,(NodeVType>*)pGet());ListVNodeVType>>::Insert(newdata);if(pGetNext()->link!=NULL)pGetNext()->link->data.link=(NodeVType>*)pGetNext();}BOOLRemove(){if(ListVNodeVType>>::Remove()){pGet()->data.link=(NodeVType>*)pGetPrior();returnTURE;}returnFALSE;}};#endif【說(shuō)明】只完成了最重要的Insert和Remove函數(shù)和最具特點(diǎn)的Prior()函數(shù)，其他的沒(méi)有重新實(shí)現(xiàn)。所以，你在這里使用單鏈表的其他方法，我不保證一定正確。并且，這里的指針類型轉(zhuǎn)換依賴于編譯器實(shí)現(xiàn)，我也不能肯定其他的編譯器編譯出來(lái)也能正確。對(duì)于讓不讓Prior返回頭節(jié)點(diǎn)的data，我考慮再三，反正用First();Get();這樣的組合也能返回，所以就不在乎他了，所以要是用Prior遍歷直到返回NULL，就會(huì)將頭節(jié)點(diǎn)的data輸出來(lái)了?！狙a(bǔ)充】至于雙向循環(huán)鏈表，也可以從這個(gè)雙向鏈表派生(仿照派生循環(huán)鏈表的方法)或者從循環(huán)鏈表派生(仿照派生雙向鏈表的方法)，就不一一舉例了(再這樣下去，我就真鬧心的要吐血了)。至此，可以得出一個(gè)結(jié)論，鏈表的各種結(jié)構(gòu)都是能從單鏈表派生出來(lái)的。換句話說(shuō)，單鏈表是根本所在，如果研究透了單鏈表，各種鏈?zhǔn)浇Y(jié)構(gòu)都不難。一小段測(cè)試程序voidDblListTest_int(){DblListVint>a;for(inti=10;i>1;i--)a.Insert(i);for(i=10;i>1;i--)coutVV*a.Next()VV"";a.First();cout VV endl;cout VV *a.Next() VV endl;cout VV *a.Next() VV endl;cout VV *a.Next() VV endl;cout VV *a.Next() VV endl;a.Remove();cout VV *a.Get()VVendl;cout VV *a.Prior() VV endl;cout VV *a.Prior() VV endl;cout VV *a.Prior() VV endl;}【后記】從我對(duì)雙向鏈表不負(fù)責(zé)任的實(shí)現(xiàn)來(lái)看，我并不想這么來(lái)實(shí)現(xiàn)雙向鏈表，我只是嘗試怎樣最大限度的利用已有的類來(lái)實(shí)現(xiàn)這種類型。實(shí)踐證明，不如重寫一個(gè)。別人看起來(lái)也好看一些，自己寫起來(lái)也不用這樣鬧心。不過(guò)，這個(gè)過(guò)程讓我對(duì)函數(shù)的調(diào)用和返回的理解又更深了一步。如果你能第一次就寫對(duì)這里的Insert函數(shù)，相信你一定對(duì)C++有一定的感