雙向鏈表
原書這部分內容很多至少相對於循環鏈表是很多相信當你把單鏈表的指針域搞清楚後這部分應該難不倒你現在我的問題是能不能從單鏈表派生出雙向鏈表？＜?xml:namespace prefix = o ns = urn:schemasmicrosoftcom:office:office /＞
你可以有幾種做法
一種就是先定義一個雙鏈節點但是它的名字必須叫Node這是沒辦法的事不然你就只好拷貝一份單鏈表的實現文件把其中的Node全都替換成你的雙鏈節點名字但是這就不叫繼承了
另一種做法就是先定義一種結構例如這樣的
template ＜class Type＞ class newtype
{
public:
Type data;
Node＜newtype＞ *link;
}
當你派生雙向鏈表時這樣寫template ＜calss Type＞ class DblList : public List＜newtype＜Type＞ ＞注意連續的兩個＞之間要有空格或者根本不定義這樣的結構直接拿Node類型來做例如我下面給出的但是請注意要完成==的重載否則你又要重寫Find函數並且其他的某些操作也不方便
在開始完成你的從單鏈表派生出來的雙向鏈表之前要在單鏈表這個基類中添加修改當前指針和當前前驅指針的接口如下所示
protected:
void Put(Node＜Type＞ *p)//盡量不用雙向鏈表將使用這個完成向前移動
{
current = p;
}
void PutPrior(Node＜Type＞ *p)//盡量不用原因同上
{
prior = p;
}
因為這個接口很危險而且幾乎用不到所以我在前面並沒有給出但要完成雙向鏈表最傑出的優點向前移動當前指針必須要使用另外說的是我從前也從來沒計劃從單鏈表派生雙鏈表下面你將看到這個過程很讓人煩人甚至不如重寫一個來的省事執行效率也不是很好這種費力不討好的事做它有什麼意思呢？的確我也覺得我在鑽牛角尖
定義和實現
#ifndef DblList_H
#define DblList_H
#include Listh
template ＜class Type＞ class DblList : public List＜ Node＜Type＞ ＞
{
public:
Type *Get()
{
if (pGet() != NULL) return &pGet()＞datadata;
else return NULL;
}
Type *Next()
{
pNext();
return Get();
}
Type *Prior()
{
if (pGetPrior != NULL)
{
Put(pGetPrior());
PutPrior( (Node＜ Node＜Type＞ ＞*)pGet()＞datalink);
return Get();
}
return NULL;
}
void Insert(const Type &value)
{
Node＜Type＞ newdata(value (Node＜Type＞*)pGet());
List＜ Node＜Type＞ ＞::Insert(newdata);
if (pGetNext()＞link != NULL)
pGetNext()＞link＞datalink = (Node＜Type＞*)pGetNext();
}
BOOL Remove()
{
if (List＜ Node＜Type＞ ＞::Remove())
{
pGet()＞datalink = (Node＜Type＞*)pGetPrior();
return TURE;
}
return FALSE;
}
};
#endif
【說明】只完成了最重要的Insert和Remove函數和最具特點的Prior()函數其他的沒有重新實現所以你在這裡使用單鏈表的其他方法我不保證一定正確並且這裡的指針類型轉換依賴於編譯器實現我也不能肯定其他的編譯器編譯出來也能正確對於讓不讓Prior返回頭節點的data我考慮再三反正用First();Get();這樣的組合也能返回所以就不在乎他了所以要是用Prior遍歷直到返回NULL就會將頭節點的data輸出來了
【補充】至於雙向循環鏈表也可以從這個雙向鏈表派生（仿照派生循環鏈表的方法）或者從循環鏈表派生（仿照派生雙向鏈表的方法）就不一一舉例了（再這樣下去我就真鬧心的要吐血了）至此可以得出一個結論鏈表的各種結構都是能從單鏈表派生出來的換句話說單鏈表是根本所在如果研究透了單鏈表各種鏈式結構都不難
一小段測試程序
void DblListTest_int()
{
DblList＜int＞ a;
for (int i = ; i ＞ ; i) aInsert(i);
for (i = ; i ＞ ; i) cout ＜＜ *aNext() ＜＜ ;
aFirst();
cout ＜＜ endl;
cout ＜＜ *aNext() ＜＜ endl;
cout ＜＜ *aNext() ＜＜ endl;
cout ＜＜ *aNext() ＜＜ endl;
cout ＜＜ *aNext() ＜＜ endl;
aRemove();
cout ＜＜ *aGet() ＜＜ endl;
cout ＜＜ *aPrior() ＜＜ endl;
cout ＜＜ *aPrior() ＜＜ endl;
cout ＜＜ *aPrior() ＜＜ endl;
}
【後記】從我對雙向鏈表不負責任的實現來看我並不想這麼來實現雙向鏈表我只是嘗試怎樣最大限度的利用已有的類來實現這種類型實踐證明不如重寫一個別人看起來也好看一些自己寫起來也不用這樣鬧心不過這個過程讓我對函數的調用和返回的理解又更深了一步如果你能第一次就寫對這裡的Insert函數相信你一定對C++有一定的感觸了我也覺得只有做一些創新才能最已經很成熟的東西更深入的了解比如這些數據結構在C++的標准庫（STL）中都可以直接拿來用我們為什麼還辛辛苦苦的寫結果還不如人家原來的好為了學習這就是理由這也是一切看起來很笨的事發生的理由
From:http://tw.wingwit.com/Article/program/sjjg/201311/22872.html
