數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)(C++)之雙向鏈表

2019-11-17 05:08:15

字體：大中小

供稿：網(wǎng)友

　　原書這部分內(nèi)容很多，至少相對(duì)于循環(huán)鏈表是很多。相信當(dāng)你把單鏈表的指針域搞清楚后，這部分應(yīng)該難不倒你。現(xiàn)在我的問(wèn)題是，能不能從單鏈表派生出雙向鏈表？＜?xml:namespace PRefix = o ns = "urn:schemas-microsoft-com:Office:office" /＞
你可以有幾種做法：

　　一種就是先定義一個(gè)雙鏈節(jié)點(diǎn)--但是，它的名字必須叫Node，這是沒(méi)辦法的事；不然你就只好拷貝一份單鏈表的實(shí)現(xiàn)文件，把其中的Node全都替換成你的雙鏈節(jié)點(diǎn)名字，但是這就不叫繼續(xù)了。
另一種做法就是先定義一種結(jié)構(gòu)例如這樣的：

template ＜class Type＞ class newtype
{
public:
Type data;
Node＜newtype＞ *link;
}
　　當(dāng)你派生雙向鏈表時(shí)，這樣寫template ＜calss Type＞ class DblList : public List＜newtype＜Type＞＞，注重連續(xù)的兩個(gè)"＞"之間要有空格。或者根本不定義這樣的結(jié)構(gòu)，直接拿Node類型來(lái)做，例如我下面給出的。但是，請(qǐng)注重要完成"=="的重載，否則，你又要重寫Find函數(shù)，并且其他的某些操作也不方便。

　　在開始完成你的從單鏈表派生出來(lái)的雙向鏈表之前，要在單鏈表這個(gè)基類中添加修改當(dāng)前指針和當(dāng)前前驅(qū)指針的接口，如下所示：

protected:
void Put(Node＜Type＞ *p)//盡量不用，雙向鏈表將使用這個(gè)完成向前移動(dòng)
{
current = p;
}

void PutPrior(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)

#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
　　【說(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)了。

　　【補(bǔ)充】至于雙向循環(huán)鏈表，也可以從這個(gè)雙向鏈表派生（仿照派生循環(huán)鏈表的方法）；或者從循環(huán)鏈表派生（仿照派生雙向鏈表的方法），就不一一舉例了（再這樣下去，我就真鬧心的要吐血了）。至此，可以得出一個(gè)結(jié)論，鏈表的各種結(jié)構(gòu)都是能從單鏈表派生出來(lái)的。換句話說(shuō)，單鏈表是根本所在，假如研究透了單鏈表，各種鏈?zhǔn)浇Y(jié)構(gòu)都不難。

　　一小段測(cè)試程序

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;

}
　　【后記】從我對(duì)雙向鏈表不負(fù)責(zé)任的實(shí)現(xiàn)來(lái)看，我并不想這么來(lái)實(shí)現(xiàn)雙向鏈表，我只是嘗試怎樣最大限度的利用已有的類來(lái)實(shí)現(xiàn)這種類型。實(shí)踐證實(shí)，不如重寫一個(gè)。別人看起來(lái)也好看一些，自己寫起來(lái)也不用這樣鬧心。不過(guò)，這個(gè)過(guò)程讓我對(duì)函數(shù)的調(diào)用和返回的理解又更深了一步。假如你能第一次就寫對(duì)這里的Insert函數(shù)，相信你一定對(duì)C++有一定的感慨了。我也覺(jué)得，只有做一些創(chuàng)新，才能最已經(jīng)很成熟的東西更深入的了解。比如，這些數(shù)據(jù)結(jié)構(gòu)，在C++的標(biāo)準(zhǔn)庫(kù)（STL）中都可以直接拿來(lái)用，我們?yōu)槭裁催€辛辛勞苦的寫，結(jié)果還不如人家原來(lái)的好。為了學(xué)習(xí)，這就是理由，這也是一切看起來(lái)很笨的事發(fā)生的理由。