数据结构学习(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）中都可以直接拿来用，我们为什么还辛辛劳苦的写，结果还不如人家原来的好。为了学习，这就是理由，这也是一切看起来很笨的事发生的理由。 更多内容请看数据结构  数据结构教程  数据结构相关文章专题，或