《2022年数据结构学习双向链表 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构学习双向链表 .pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构学习（ C+ ）双向链表happycock（原作）转自 CSDN原书这部分内容很多，至少相对于循环链表是很多。相信当你把单链表的指针域搞清楚后 ， 这 部 分 应 该 难 不 倒 你 。 现 在 我 的 问 题 是 ，能 不 能 从 单 链表 派 生 出 双 向链 表 ？你可以有几种做法：一种就是先定义一个双链节点但是，它的名字必须叫Node ，这是没办法的事；不然你就只好拷贝一份单链表的实现文件，把其中的Node 全都替换成你的双链节点名字，但是这就不叫继承了。另一种做法就是先定义一种结构例如这样的：template class newtypepublic:Type data;Nod
2、e *link;当 你 派 生 双 向 链 表 时 ， 这 样 写template class DblList : public Listnewtype ，注意连续的两个 “”之间要有空格。 或者根本不定义这样的结构，直接拿Node类型来做，例如我下面给出的。但是，请注意要完成“= ”的重载，否则，你又要重写Find 函数，并且其他的某些操作也不方便。在开始完成你的从单链表派生出来的双向链表之前，要在单链表这个基类中添加修改当前指针和当前前驱指针的接口，如下所示：protected:void Put(Node *p)/尽量不用，双向链表将使用这个完成向前移动current = p;void P
3、utPrior(Node *p)/尽量不用，原因同上prior = p;因为这个接口很危险， 而且几乎用不到， 所以我在前面并没有给出， 但要完成双向链表最“杰出”的优点向前移动当前指针，必须要使用。另外说的是，我从前也从来没计划从单链表派生双链表，下面你将看到，这个过程很让人烦人，甚至不如重写一个来的省事， 执行效率也不是很好， 这种费力不讨好的事做它有什么意思呢？的确，我也觉得我在钻牛角尖。（别拿鸡蛋丢我）定义和实现#ifndef DblList_H#define DblList_H名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -
4、 - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - #include List.htemplate class DblList : public List Node 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 *)pG
5、et()-data.link);return Get();return NULL;void Insert(const Type &value)Node newdata(value, (Node*)pGet();List Node :Insert(newdata);if (pGetNext()-link != NULL) pGetNext()-link-data.link = (Node*)pGetNext();BOOL Remove()if (List Node :Remove()pGet()-data.link = (Node*)pGetPrior();return TURE;return
6、FALSE;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - ;#endif【说明】只完成了最重要的Insert 和 Remove函数和最具特点的Prior() 函数，其他的没有重新实现。所以，你在这里使用单链表的其他方法，我不保证一定正确。并且，这里的指针类型转换依赖于编译器实现，我也不能肯定其他的编译器编译出来也能正确。对于让不让Prior 返回头节点的data ，我考虑再三，反正用First();Get(); 这样的组合也能
7、返回，所以就不在乎他了，所以要是用Prior 遍历直到返回NULL ，就会将头节点的data 输出来了。【补充】至于双向循环链表，也可以从这个双向链表派生（仿照派生循环链表的方法）；或者从循环链表派生（仿照派生双向链表的方法），就不一一举例了（再这样下去，我就真闹心的要吐血了） 。至此，可以得出一个结论，链表的各种结构都是能从单链表派生出来的。换句话说，单链表是根本所在，如果研究透了单链表，各种链式结构都不难。一小段测试程序void DblListTest_int()DblList a;for (int i = 10; i 1; i-) a.Insert(i);for (i = 10; i 1
8、; 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;【后记】 从我对双向链表不负责任的实现来看，我并不想这么来实现双向链表，我只是尝试怎样最大限度的利用已有的类来实现这种类型。实践证明， 不如重写一个。 别人看起来也好看一
9、些， 自己写起来也不用这样闹心。不过， 这个过程让我对函数的调用和返回的理解又更深了一步。如果你能第一次就写对这里的Insert 函数，相信你一定对C+ 有一定的感触了。我也觉得， 只有做一些创新， 才能最已经很成熟的东西更深入的了解。比如，这些数据结构，在 C+ 的标准库（ STL ）中都可以直接拿来用，我们为什么还辛辛苦苦的写，结果还不如人家原来的好。为了学习，这就是理由，这也是一切看起来很笨的事发生的理由。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -