數據結構學習(C++)之雙向鏈表

2019-11-17 05:08:15

字體：大中小

來源：轉載

供稿：網友

　　原書這部分內容很多，至少相對于循環鏈表是很多。相信當你把單鏈表的指針域搞清楚后，這部分應該難不倒你。現在我的問題是，能不能從單鏈表派生出雙向鏈表？＜?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＞＞，注重連續的兩個"＞"之間要有空格?；蛘吒静欢x這樣的結構，直接拿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）中都可以直接拿來用，我們為什么還辛辛勞苦的寫，結果還不如人家原來的好。為了學習，這就是理由，這也是一切看起來很笨的事發生的理由。