数据结构学习(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

[1]  

【责编:huangchunmei】

--------------------next---------------------