双向链表的应用

双向链表的应用

ID:43331150

大小:49.00 KB

页数:4页

时间:2019-09-28

双向链表的应用_第1页
双向链表的应用_第2页
双向链表的应用_第3页
双向链表的应用_第4页
资源描述:

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

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<

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。