数据布局进修(C++)之双向链表

　　原书这部门内容许多，至少相对付轮回链表是许多。相信当你把单链表的指针域搞清楚后，这部门应该难不倒你。此刻我的问题是，能不能从单链表派生出双向链表？＜?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）中都可以直接拿来用，我们为什么还辛辛苦苦的写，功效还不如人家本来的好。为了进修，这就是来由，这也是一切看起来很笨的事产生的来由。

当前位置：以往代写 > C/C++ 教程 >数据布局进修(C++)之双向链表