日期：2011-03-22 13:55:00 来源：本站整理

数据构造学习(C++)之双向链表[VC/C++编程]

赞助商链接

分享到： QQ空间新浪微博腾讯微博人人网

本文“数据构造学习(C++)之双向链表[VC/C++编程]”是由七道奇为您精心收集，来源于网络转载，文章版权归文章作者所有，本站不对其观点以及内容做任何评价，请读者自行判断，以下是其具体内容：
　　原书这部份内允很多,至少相关于循环链表是很多.相信当你把单链表的指针域搞清楚后,这部份应当难不倒你.目前我的问题是,能不能从单链表派生出双向链表?＜?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）中都可以直接拿来用,我们为什么还辛辛劳苦的写,后果还不如人家本来的好.为了学习,这就是来由,这也是一切看起来很笨的事发生的来由.
　　以上是“数据构造学习(C++)之双向链表[VC/C++编程]”的内容，如果你对以上该文章内容感兴趣，你可以看看七道奇为您推荐以下文章：

hosts是什么 hosts文件在什么位置若何改正hosts

在 Windows 8 中手动安装语言包

五个常见 PHP数据库问题

Windows中Alt键的12个高效快速的利用本领介绍

MySQL ORDER BY 的实现解析

详解MySQL存储历程参数有三种范例(in、out、inout)

Win8系统恢复出来经典的开始菜单的办法

Win8系统花屏怎么办 Win8系统花屏的办理办法

Windows 7系统下无线网卡安装

为什么 Linux不需求碎片整理

Windows 8中删除账户的几种办法(图)

教你如安在win7下配置路由器