数据结构学习(C )之双向链表
2008-02-23 05:24:43来源:互联网 阅读 ()
您能够有几种做法:
一种就是先定义一个双链节点--但是,他的名字必须叫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)中都能够直接拿来用,我们为什么还辛辛苦苦的写,结果还不如人家原来的好。为了学习,这就是理由,这也是一切看起来很笨的事发生的理由。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇: C 中数组和指针类型的关系浅议
下一篇: 关于C 异常处理的心得体会
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash