双向链表的应用

《双向链表的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、双向链表从单链表派生出双向链表可以有以下做法：一种就是先定义一个双链节点■•但是，它的名字必须叫Node,这是没办法的事；不然你就只好拷贝一份单链表的实现文件，把其中的Node全都替换成你的双链节点名字，但是这就不叫继承了。另一-种做法就是先定义一种结构例如这样的：templateclassnewtype{public:Typedata;Node*link;}当你派生双向链表时，这样写templateclassDbIList:publicList

2、type>,注意连续的两个">”之间要有空格。或者根本不定义这样的结构，直接拿Node类型來做，例如我下浙给出的。但是，请注意要完成-==n的重载，否则，你又要重写Find惭数，并且其他的某些操作也不方便。在开始完成你的从单链表派生出來的双向链表Z前，要在单链表这个棊类中添加修改当前指针和当前前驱指针的接口，如下所示：protected:voidPut(Node*p)〃尽量不用，双向链表将使用这个完成向前移动{current=p;voidPutPrior(Node*p)〃尽量不用

3、，原因同上prior=p;因为这个接口很危险，而且几乎用不到，所以我在前面并没有给出，但要完成双向链表最••杰出••的优点-向前移动当前指针，必须要使用。另外说的是，我从前也从來没计划从单链表派生双链表，下面你将看到，这个过程很让人烦人，甚至不如重写一个来的省事，执行效率也不是很好，这种费力不讨好的事做它有什么意思呢？的确，我也觉得我在钻牛角尖。定义和实现#ifndefDblList_H#defineDblList_Hinclude”List.h”templateclassDblList:pu

4、blicList>{public:Type*Get(){讦(pGel()!=NULL)return&pGet()->data.data;elsereturnNULL;}Type*Next(){pNext();returnGet();}Type*Prior(){if(pGetPrior!=NULL){Put(pGetPrior());PutPrior((Node>*)pGet()->data.link);returnGet();}returnNULL;}voidInsert

5、(constType&value)Nodenewdata(value,(Node*)pGet());List>::Insert(newdata);if(pGetNext()->link!=NULL)pGetNext()->link->data.link=(Node*)pGetNext();}BOOLRemove(){if(List>::Remove()){pGet()->data.link=(Node*)pGetPrior(

6、);returnTURE;}returnFALSE;}}；#endif【说明】只完成了最重要的Insert和Remove函数和最具特点的Prior()函数，英他的没有重新实现。所以，你在这里使用单链表的其他方法，我不保证一定正确。并且，这里的指针类型转换依赖于编译器实现，我也不能肯定其他的编译器编译出来也能止确。对于让不让Prior返回头节点的data,我考虑再三，反正用First();Get();这样的组合也能返回，所以就不在乎他了，所以耍是用Prior遍历直到返回NULL,就会将头节点的data输出来了。【补充

7、】至于双向循环链表，也可以从这个双向链表派牛(仿照派牛循环链表的方法)；或者从循环链表派牛(仿照派牛双向链表的方法)，就不一一举例了(再这样下去，我就真闹心的要吐血了)。至此，可以得出一个结论，链表的各种结构都是能从单-链表派生出来的。换句话说，单链表是根木所在，如果研究透了单链表，各种链式结构都不难。一小段测试程序voidDblListTest_int()DblLista;for(inti=10;i>1;i—)a.Insert(i);for(i=10;i>1;i-)cout<<*a.Next()<<""

8、a.First();cout<