原书这部分内容很多,至少相对于循环链表是很多。相信当你把单链表的指针域搞清楚后,这部分应该难不倒你。现在我的问题是,能不能从单链表派生出双向链表?
你可以有几种做法:
一种就是先定义一个双链节点——但是,它的名字必须叫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: