双向链表
原书这部分内容很多至少相对于循环链表是很多相信当你把单链表的指针域搞清楚后这部分应该难不倒你现在我的问题是能不能从单链表派生出双向链表？＜?xml:namespace prefix = o ns = urn:schemasmicrosoftcom: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 Listh
template ＜class Type＞ class DblList : public List＜ Node＜Type＞ ＞
{
public:
Type *Get()
{
if (pGet() != NULL) return &pGet()＞datadata;
else return NULL;
}
Type *Next()
{
pNext();
return Get();
}
Type *Prior()
{
if (pGetPrior != NULL)
{
Put(pGetPrior());
PutPrior( (Node＜ Node＜Type＞ ＞*)pGet()＞datalink);
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＞datalink = (Node＜Type＞*)pGetNext();
}
BOOL Remove()
{
if (List＜ Node＜Type＞ ＞::Remove())
{
pGet()＞datalink = (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 = ; i ＞ ; i) aInsert(i);
for (i = ; i ＞ ; i) cout ＜＜ *aNext() ＜＜ ;
aFirst();
cout ＜＜ endl;
cout ＜＜ *aNext() ＜＜ endl;
cout ＜＜ *aNext() ＜＜ endl;
cout ＜＜ *aNext() ＜＜ endl;
cout ＜＜ *aNext() ＜＜ endl;
aRemove();
cout ＜＜ *aGet() ＜＜ endl;
cout ＜＜ *aPrior() ＜＜ endl;
cout ＜＜ *aPrior() ＜＜ endl;
cout ＜＜ *aPrior() ＜＜ endl;
}
【后记】从我对双向链表不负责任的实现来看我并不想这么来实现双向链表我只是尝试怎样最大限度的利用已有的类来实现这种类型实践证明不如重写一个别人看起来也好看一些自己写起来也不用这样闹心不过这个过程让我对函数的调用和返回的理解又更深了一步如果你能第一次就写对这里的Insert函数相信你一定对C++有一定的感触了我也觉得只有做一些创新才能最已经很成熟的东西更深入的了解比如这些数据结构在C++的标准库（STL）中都可以直接拿来用我们为什么还辛辛苦苦的写结果还不如人家原来的好为了学习这就是理由这也是一切看起来很笨的事发生的理由
