原書這部分內容很多，至少相對於循環鏈表是很多。相信當你把單鏈表的指針域搞清楚後，這部分應該難不倒你。現在我的問題是，能不能從單鏈表派生出雙向鏈表？＜?xml:namespace prefix = o ns = "urn:schemas-microsoft-com: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 "List.h"
template ＜class Type＞ class DblList : public List＜ Node＜Type＞ ＞
{
public:
Type *Get()
{
if (pGet() != NULL) return &pGet()-＞data.data;
else return NULL;
}
Type *Next()
{
pNext();
return Get();
}
Type *Prior()
{
if (pGetPrior != NULL)
{
Put(pGetPrior());
PutPrior( (Node＜ Node＜Type＞ ＞*)pGet()-＞data.link);
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-＞data.link = (Node＜Type＞*)pGetNext();
}
BOOL Remove()
{
if (List＜ Node＜Type＞ ＞::Remove())
{
pGet()-＞data.link = (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 = 10; i ＞ 1; i--) a.Insert(i);
for (i = 10; i ＞ 1; i--) cout ＜＜ *a.Next() ＜＜ " ";
a.First();
cout ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
a.Remove();
cout ＜＜ *a.Get() ＜＜ endl;
cout ＜＜ *a.Prior() ＜＜ endl;
cout ＜＜ *a.Prior() ＜＜ endl;
cout ＜＜ *a.Prior() ＜＜ endl;
}
【後記】從我對雙向鏈表不負責任的實現來看，我並不想這麼來實現雙向鏈表，我只是嘗試怎樣最大限度的利用已有的類來實現這種類型。實踐證明，不如重寫一個。別人看起來也好看一些，自己寫起來也不用這樣鬧心。不過，這個過程讓我對函數的調用和返回的理解又更深了一步。如果你能第一次就寫對這裡的Insert函數，相信你一定對C++有一定的感觸了。我也覺得，只有做一些創新，才能最已經很成熟的東西更深入的了解。比如，這些數據結構，在C++的標准庫（STL）中都可以直接拿來用，我們為什麼還辛辛苦苦的寫，結果還不如人家原來的好。為了學習，這就是理由，這也是一切看起來很笨的事發生的理由。
