【IT168技术文档】

  原书这部分内容很多，至少相对于循环链表是很多。相信当你把单链表的指针域搞清楚后，这部分应该难不倒你。现在我的问题是，能不能从单链表派生出双向链表？＜?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