1.专用链表和通用链表各自的特点与适用范围。
专用链表在这里是指它的实现和调用耦合在一起,只能被一个调用者使用,而不能单独在其它地方被重用。通用链表则相反,它具有通用性,可以在多处被重复使用。尽管通用链表相对专用链表来说有很多优越之处,不过简单的断定通用链表比专用链表好也是不公正的,因为它们都有自己的优点和适用范围:
专用链表的优点:
更高性能。专用链表的实现和调用在一起,可以直接访问数据成员,省去了包装函数带来的性能开销,可以提高时间性能。专用链表无需实现完整的接口,只要满足自己的需要就行了,生成的代码更小,因此可以提高空间性能。
更少依赖。自己实现不用依赖于别人。有时候你要写一个规模不大的跨平台程序,比如想在展讯手机平台和MTK手机平台上运行,虽然有现存的库可用,但你又不想把整个库移植过去,那么实现一个专用链表是不错的选择。
实现简单。实现专用链表时,不需要考虑在各种复杂应用情况下的特殊要求,也不需要提供完整的接口,所以实现起来比通用链表更为简单。
通用链表的优点(从全局来看):
可靠性更高。通用链表的实现要复杂得多,复杂的东西意味着不可靠。但它是可以重复使用的,其存在的问题会随每一次重用而被发现和改正,慢慢的就行成一个可靠的函数库。
开发效率更高。通用链表的实现要复杂得多,复杂的东西也意味着更高的开发成本。同样因为它是可以重复使用的,开发成本会随每一次重用而降低,从整个项目来看,会大大提高开发效率。
考虑到链表是最常用的数据结构之一,很多地方都会用到它,实现通用的链表会更有价值。接下来我们要实现一个通用的链表,不过请大家记住,实现通用的链表并不是我们的目标,而是我们学习软件设计方法的手段。前面我许诺过要以简单的数据结构讲述复杂的软件设计方法,链表就是其中的载体之一。
2.如何编写一个通用的链表?
编写通用链表是一项复杂的任务,不可能在这一节中把它阐述清楚,这里我们先考虑三个问题:
存值还是存指针
通用链表首先是要做能够存放任何数据类型的数据,新手常见的做法是定义一个抽象数据类型,需要什么存放什么就定义成什么。如:
typedef int Type;
typedef struct _DListNode
{
struct _DListNode* prev;
struct _DListNode* next;
Type data;
}DListNode;
这样的链表算不上是通用的,因为你存放整数时编译一次,存放字符串时,重义Type再编译一次,存放其它类型同样要重复这个过程。麻烦不说,关键是没有办法同时使用多个数据类型。我们要找到一种同时可以表示不同数据类型的类型才行,有人说可以用union,但是数据类型是无穷无尽的,不可能在union中表示它们的全部。
可行的办法有两种:
存值:
typedef struct _DListNode
{
struct _DListNode* prev;
struct _DListNode* next;
void* data;
size_t length;
}DListNode;
存入时拷贝一份数据,保存数据的指针和长度。考虑到拷贝数据会带来性能开销,不合符C语言的风格,而且C语言中没有构造函数,实现深拷贝比较麻烦,所以在C语言中以这种方式实现的链表很少见。
存指针:
typedef struct _DListNode
{
struct _DListNode* prev;
struct _DListNode* next;
void* data;
}DListNode;
只是保存指向对象的指针,存取效率高,是C语言中常见的做法。在存放整数时,可以把void*强制转换成整数使用,以避免内存分配(在现实中,90%以上的情况,链表都是存放结构的)。
让C++可以调用
这不是一个重要的话题,只是顺便提一下。C++中允许同名函数存在,所以编译器会对函数名重新编码。C++代码包含C语言的头文件时,重新编码名字与C语言库中的原函数名不一致,结果造成找不到函数的情况。为了让C语言实现的函数在C++中可以调用,需要在头文件中加点东西才行:
#ifdef __cplusplus
extern "C" {
#endif
…
#ifdef __cplusplus
}
#endif
它表示如果在C++中调用这里的函数,编译器不能对函数名进行重新编码。
完整的接口
作为一个通用的链表,接口要比较完整才行,否则无法满足各种情况的需要(提供完整的接口并不违背最小接口原则)。实现具有完整接口的链表不是件容易的事,读者先实现插入删除等基本操作就行了,后面我们会慢慢扩展它的功能。
(为了避免读起来拗口,本文把双向链表简写成链表了,希望读者不要介意)
分享到:
相关推荐
Java遵循WORA(Write Once, Run Anywhere。一次写入,到处运行)的原理,并且与平台无关。它也简单易学。 Java是世界上使用最广泛的编程语言之一。Java最初由Sun Microsystems在1990年代开发,用于开发从Web应用程序...
-跨平台兼容性:一次编写,到处运行(Write Once, Run Anywhere,WORA)。 -面向对象:基于类和对象,支持封装、继承和多态。 -健壮性:强类型检查和异常处理机制。 -安全性:提供了强大的安全管理器。 -多线程:...
Java遵循WORA(Write Once, Run Anywhere。一次写入,到处运行)的原理,并且与平台无关。它也简单易学。 Java是世界上使用最广泛的编程语言之一。Java最初由Sun Microsystems在1990年代开发,用于开发从Web应用程序...
Java 是由 Sun Microsystems(现在是 Oracle Corporation 的一部分)在 1995 年...Java 程序是在 Java 虚拟机(JVM)上运行的,这使得 Java 能够实现“一次编写,到处运行”(Write Once, Run Anywhere,WORA)的特性。
Java遵循WORA(Write Once, Run Anywhere。一次写入,到处运行)的原理,并且与平台无关。它也简单易学。 Java是世界上使用最广泛的编程语言之一。Java最初由Sun Microsystems在1990年代开发,用于开发从Web应用程序...
github页面包含与此monorepo分发的库相关的所有文档。 社区挑战 导致我创建此存储库的想法是,收集社区在github上所做的所有出色工作,以进行react和react-native,以便创建可在任何地方呈现的组件和实用程序。...
门户网站 2014年诺基亚基金会第三届AI学生开发的学校控制系统。WORA
(WORA)——编写一次运行——所有操作系统代码都支持任何地方,就像java独立一样。 2. 面向对象—— 现实生活 er sathe 对象 gulo mil reke amara 编程 korbo。 Java 支持的基于 Web 的应用程序。 健壮的语言: - ...
XPDA.net XPDA.net的网站(跨平台桌面应用程序)计划阶段1 充实内容。 将工具添加到列表中,填写其详细信息 语言,平台,弃用,利弊,框架,工具 添加实时过滤器(有关操作系统支持,语言等的过滤器)阶段2 改善页面...
角度继电器 贡献 给一星到存储库和共享,你会帮助项目和人民谁就会发现它有用 提出问题,您的问题是宝贵的帮助 欢迎PR ,但最好先打开此问题,以帮助我和其他人对此进行评估 请赞助我 安装 使用yarn或npm安装中继角...
本质上,所有Java程序本质上都是一次编写,可在任何地方运行(WORA),这意味着您可以在一个平台上编写代码,然后在多个受支持的平台上运行它。 这在Java中是可能的,因为用Java编写的代码被编译为中间结果,也称为...
它旨在让应用程序开发人员“编写一次,随处运行”(WORA),这意味着在一个平台上运行的代码无需重新编译即可在另一个平台上运行。 Java 应用程序通常被编译为可以在任何 Java 虚拟机 (JVM) 上运行的字节码,而不管...
当java1.0刚刚出现时还没有swing,当时的GUI基本编程库,sun取名叫AWT(Abstract Window Tookit),基本AWT库处理用户界面的方法是将这些元素的创建行为交给,底层操作系统的GUI工具箱进行处理,来实现WORA的目的。...
它是一种通用的编程语言,旨在让应用程序开发人员编写一次即可在任何地方运行(WORA),这意味着已编译的Java代码可以在支持Java的所有平台上运行而无需重新编译.Java应用程序通常被编译为可以可以在任何Java虚拟机...
)提供一致的api,从而使机器人开发可支持WORA(一次编写,可在任何地方运行)。 关于未来 Mirai是由独立开发人员开发的独立项目,为中国流行的IM软件(QQ)实现了该协议。 有关Mirai的更多详细信息,请。 关于...
它是一种通用编程语言,旨在让应用程序开发人员编写一次即可在任何地方运行(WORA),这意味着已编译的Java代码可以在支持Java的所有平台上运行,而无需重新编译。 Java应用程序通常被编译为可在任何Java虚拟机...