科技行者

行者学院 转型私董会 科技行者专题报道 网红大战科技行者

知识库

知识库 安全导航

至顶网软件频道基础软件数据结构学习(C++)之双向链表

数据结构学习(C++)之双向链表

  • 扫一扫
    分享文章到微信

  • 扫一扫
    关注官方公众号
    至顶头条

介绍如何从单链表中派生出双链表

作者:happycock 来源:论坛 2007年10月28日

关键字: 数据结构 C++ 双向链表 Linux

  • 评论
  • 分享微博
  • 分享邮件
原书这部分内容很多,至少相对于循环链表是很多。相信当你把单链表的指针域搞清楚后,这部分应该难不倒你。现在我的问题是,能不能从单链表派生出双向链表?<?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)中都可以直接拿来用,我们为什么还辛辛苦苦的写,结果还不如人家原来的好。为了学习,这就是理由,这也是一切看起来很笨的事发生的理由。

查看本文来源

    • 评论
    • 分享微博
    • 分享邮件
    邮件订阅

    如果您非常迫切的想了解IT领域最新产品与技术信息,那么订阅至顶网技术邮件将是您的最佳途径之一。

    重磅专题
    往期文章
    最新文章