程序员为什么要学数据结构？

作者: b241fd26e57f | 来源:发表于2018-06-29 15:45 被阅读707次

参与文末话题讨论，每日赠送异步图书

——异步小编

作为软件开发人员，在面对全新的任务和挑战时，我们常常会将这些问题分解为自己所熟知的各类解决方案和代码片段，并根据客户需求和任务截止日期，制定最快的方案进行开发。但是，这样做只是单纯地完成了工作要求，有时对于学到更多的开发技巧和理念从而成为一名更优秀、更高效的开发者的帮助并没有想象中的那么大。

为什么要学习数据结构？在计算机发展的初期，人们使用计算机的主要目的是处理数值计算问题。使用计算机解决具体问题一般需要经过以下几个步骤：首先从具体问题抽象出适当的数学模型，然后设计或选择解此数学模型的算法，接着编写程序并进行调试、测试，直至得到最终的解答。

由于最初涉及的运算对象是简单的整型、实型或布尔型数据，所以程序设计者的主要精力集中于程序设计的技巧上，而无需重视数据结构。随着计算机应用领域的扩大和软硬件的发展，非数值计算问题显得越来越重要。据统计，当今处理非数值计算问题占用了90%以上的机器时间。这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构。

著名的瑞士计算机科学家沃思（N.Wirth）教授曾提出：

算法 + 数据结构＝程序

程序设计的实质是对实际问题设计/选择好的数据结构和好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。

数据类型：基本的数据结构

将数据类型称作基本的数据结构可能有些用词不当，但开发人员往往使用这些数据类型来构建他们自己的类和数据集，因此从他们的角度思考的话，这样的称呼也未尝不可。所以，在我们进一步学习数据结构之前，最好先快速地回顾一下数据类型。

1.1　数值数据类型

C#、Java、Objective-C和Swift这4种语言中全部数值数据类型的详细说明都可以再写一本书了。这里，我们只回顾每种语言中最常用的数值数据类型标识符。评价这些数据类型最简单的方法是基于其实际数据大小用每个语言分别举例，并在同一个框架内来分析讨论。

看起来一样，实际却不一样！

当在多个移动平台上开发应用时，应当注意到不同的语言可能会共用同一个/套数据类型标识符或关键字，但从底层来看，这些标识符并不一定等价。同样地，同一种数据类型在不同的语言中也可能会有不同的标识符。以16位无符号整型（16-bit unsigned integer）为例，在Objective-C中它被称作unsigned short类型。但在C#或Swift里，却分别用ushort类型和UInt16类型来表示。Java规定16位无符号整型只能用作char类型，尽管这个类型通常不用于数值型数据。以上每一种数据类型都表示一个16位无符号整型，只是名称有所不同。这貌似问题不大，但当你分别使用每个平台的原生语言为多个设备进行应用开发时，为保证一致性，需注意到这种差别。否则，将会带来不同平台上出现特定错误/漏洞的风险，这将是非常难以检测和判断的。

1.1.1　整型

整型数据类型的定义为表示有符号（负值、零或正值）或无符号（零或正值）的整数。对于整型，每种语言都有其特定的标识符和关键字，因此按照存储长度来思考最为简便。为达到我们的目的，我们只讨论表示8、16、32和64位存储对象的整型。

8位数据类型，或统称为字节（byte），是我们探讨的最小的数据类型。如果你复习过二进制数学，你会知道1个8位的内存块可表示28或256个值。有符号字节的可取值范围为−128～127或−27～27−1。无符号字节的可取值范围为0～255或0～28−1。

除了一些特殊情况，16位数据类型通常称为短整型（short）。这种数据类型可表示216个值。有符号短整型的可取值范围为−215～215−1。无符号短整型的可取值范围为0～216−1。

32位数据类型一般被认为是整型，有些时候也会被认为是长整型（long）。整型可表示232个值。有符号整型的可取值范围为−231～231−1。无符号整型的可取值范围为0～232−1。

最后，64位数据类型一般被认为是长整型，而Objective-C中规定其为双长整型（long long）。长整型可以表示264个值。有符号长整型的可取值范围为−263～263−1。无符号长整型的可取值范围为0～264−1。

需注意的是，以上所提到的取值在我们所使用的4种语言中是一致的，但在其他的语言中可能会有细微的变化。熟悉所用语言数值标识符的详细细节总是一个好主意，尤其是当你需要用到标识符规定极值的情况下。

C#用整型来表示整数类型。它提供byte和sbyte两种机制来生成8位整型。这两种整型都能表示256个值，无符号的字节可取值范围为0～255。有符号的字节对负值提供支持，因此取值范围为−128～127，具体代码如下。

有趣的是，对于更长位的标识符C#改变了其命名模式。它用u作无符号（unsigned）的前缀，而不是使用sbyte中s作为有符号（signed）的前缀。因此C#分别使用short，ushort；int，uint；long，ulong作为16位、32位以及64位的整型标识符，其代码实现如下。

Java

Java将整型作为其原始数据类型的一部分。Java只提供一种建立8位类型的方式，即byte。这是一个有符号的数据类型，因此可表示−127～128的取值。Java还提供了名为Byte的包装类，其不仅包装了原始值，并对像“42”这些能够转换为数值的可解析字符串或文本提供了额外的构造函数支持。这种模式重复体现在16位、32位和64位类型中。

Java和C#共用了所有整型的标识符，这意味着Java对8位、16位、32位和64位类型也提供了byte、short、int及long标识符。Java中只有一个例外，即提供了16位无符号数据类型的标识符char。值得注意的是，char类型通常只用作分配ASCII字符，而不是实际的整数数值。

在以上的代码中，须注意int类型和Integer类。不同于其他原始包装类，Integer并不和其支持的标识符共用名称。

此外，注意long类型和其分配的数值。在每个例子中，这些值都有后缀L。这是Java对long类型的要求，因为编译器将所有的数值文字默认翻译为32位整数。当需要明确说明字面数值是长于32位时，必须为其加上后缀L。不然的话，编译器可能会报错。然而，当给Long类型构造函数传递字符串值时，则不受这种限制：

Objective-C

对于8位数据，Objective-C提供了有符号和无符号两种格式的char类型。与其他语言相同，有符号的数据类型取值为−127～128，而无符号的类型取值为0～255。开发人员还可以选择使用Objective-C的定宽整型int8_t和uint8_t。这种模式重复体现在16位、32位和64位类型中。最后，Objective-C还以NSNumber类的形式对每种整型提供了面向对象的包装类。

char或其他整型和其定宽整型有非常显著的区别。除了char类型总是为1字节长度以外，其他Objective-C中的整型长度会根据实现方式和底层架构的不同而改变。这是因为Objective-C是基于C语言的，而C语言被设计成能够在不同种类的底层架构上高效工作。尽管可以在运行和编译时就确定整型数据结构的确切长度，但在一般情况下，你只能确定的是short <= int <= long <= long long。

这时定宽整型就派上用场了。在需要严格控制字节长度的情况下，(u)int_t整型可以让你精确定义出8位、16位、32位或64位长度的整数。

从上面的例子可以看出，当在代码中使用char类型时，必须指定标识符unsigned，例如unsigned char。signed是char类型的默认标识符，可以省略，这也意味着char类型与signed char等价。Objective-C中的其他整型也遵循这种模式。

Objective-C中更大的整型包括用于16位的short类型，用于32位的int类型以及用于64位的long long类型。以上每种整型都依照(u)int_t的模式有其定宽整型。NSNumber对每种整型都提供了支持方法。

Swift

Swift语言和其他语言类似，对于有符号和无符号的整数提供了各自的标识符，如Int8和UInt8。依据标识符名称来确定可应用的数据类型，这样的方式适用于Swift的每种整型，也使得Swift也许会成为最简单的语言。

为清晰地展示声明过程，上面的例子使用:Int8和:UInt8标识符明确地声明了数据类型。在Swift里，还可以不加这些标识符，让Swift在运行时动态地推断出数据类型。

我为什么需要知道这些？你可能会问，我为什么需要知道数据类型的这些复杂细节？我难道不能只声明一个int对象或其他类似的东西后去写一些有趣的代码？现代计算机甚至是移动设备都能够提供近乎无穷的资源，所以这没什么大不了的，对吧？

事实并非如此。在你日常编程的经历中，大多数情况下随便使用哪一个数据类型可能都行。比如，遍历出任意一天西佛吉尼亚州全州车管部门签发的牌照列表，结果可能从几十个到上百个。你可以使用一个短整型变量或一个双长整型变量来控制for循环迭代。无论选用何种方式，这个循环为你的系统性能所带来的影响几乎可以忽略。

假设你在处理一组数据，这组数据中的每个离散结果都与16位类型匹配，而你习惯性地使用32位类型来处理，这会导致什么结果呢？这样做的结果会使处理这个数据集所需的内存空间翻倍。当离散结果只有100个或100 000个的时候，这样做可能并没什么不妥。但如果要处理的数据集很大，有百万个以及更多的离散结果的时候，这么做肯定会给系统性能带来非常大的影响。

1.1.2　单精度浮点类型

单精度浮点（single precision floating point）类型通常称为单精度类型（float），用32位浮点容器能够存储比整型更高精度的数值，通常有6～7位有效数字。多种语言使用float关键字/标识符来标记单精度浮点数值，本书所讨论的4种语言也是如此。

需要注意的是，由于浮点数值不能精确地表示以10为基的数字，因此其精度受限于归零误差。浮点类型的数值算法非常复杂，无论何时其中的细节都与大部分开发人员不太相关。然而，学习浮点类型可以加深对底层技术及每种语言实现细节的了解。

..\技巧.tif{8%}

由于我并不是这方面的专家，因此只简单了解一下这些类型背后的科学原理，并不涉及具体的数学算法。我在本章末尾的附加资料中列出了这个领域专家们的一些研究成果，强烈建议你们学习。

C#使用float关键字标识32位浮点值。C#中float类型精度为6位有效数字，近似取值范围从−3.4×1038～+3.4×1038：

从上面的代码可以看出，使用float在赋值时有f作为后缀。这是因为C#和其他基于C的语言一样，在处理赋值语句右边的小数数字时，默认其为双精度型（double，稍后讨论）。如果在赋值时不用f或F后缀，而直接将一个双精度浮点的数值赋给单精度浮点类型，则会产生编译错误。

此外，注意到最后一位的归零误差。我们将30位有效数字的圆周率赋值给piFloat。但由于float只能保留6位有效数字，其后数字都会被约去。若直接对圆周率值保留6位有效数字，我们得到3.141592，但由于归零误差，浮点数的实际值为3.141593。

Java

与C#相同，Java使用float标识符确定浮点值。Java中float类型精度为6或7位有效数字，近似取值范围为−3.4×1038～+3.4×1038：

从上面的代码可以看出，浮点赋值操作有f后缀。这是因为Java和其他基于C的语言一样，在处理赋值语句右边的小数数字时，默认其为双精度型。如果在赋值时不加入f或F后缀，而直接将一个双精度浮点的数值赋给单精度浮点类型，则会产生编译错误。

Objective-C

Objective-C使用float标识符确定浮点值。在Objective-C中，float类型精度为6位有效数字，近似取值范围从−3.4×1038～+3.4×1038：

从上面的代码可以看出，浮点赋值操作有f后缀。这是因为Objective-C和其他基于C的语言一样，在处理赋值语句右边的小数数字时，默认其为双精度型。如果在赋值时不加入f或F后缀，而直接将一个双精度浮点的数值赋给单精度浮点类型，则会产生编译错误。

Swift

Swift使用float标识符确定浮点值。在Swift中，float类型精度为6位有效数字，近似取值范围从−3.4×1038～+3.4×1038：

从上面的代码可以看出，浮点赋值操作有f后缀。这是因为Swift和其他基于C的语言一样，在处理赋值语句右边的实数数字时，默认其为双精度型。如果在赋值时不加入f或F后缀，而直接将一个双精度浮点的数值赋给单精度浮点类型，则会产生编译错误。

此外，注意到最后一位的归零误差。我们将30位有效数字的圆周率赋值给floatValue。但由于float只能保留6位有效数字，其后数字都会被约去。若直接对圆周率值保留6位有效数字，我们得到3.141 592，但由于归零误差，浮点数的实际值为3.141 593。

1.1.3　双精度浮点类型

双精度浮点（double precision floating point）类型通常称为双精度型（double）。用64位浮点容器能够存储比整型更高精度的数值，该类型通常有15位有效数字。多种语言使用double关键字/标识符来标记双精度浮点数值，我们所讨论的4种语言也是如此。

在大多数情况下，无论选用float还是double都无关紧要，除非内存空间较为紧张，这时应该尽可能选择float。很多人认为在多数情况下float比double更高效，一般来说，也确实是这样。但在一些情况下，double会比float更高效。事实上，由于存在太多无法在这里详述的标准，每种类型的效率会因情况而异。因此，如果需要在特定应用中达到最高的效率，你需要仔细研究各种影响因素来选用最合适的类型。如果对效率并不是那么在意，那就任选一个合适的类型，接着干活。

C#使用double关键字标识64位浮点数值。在C#中，double类型的精度为14或15位有效数字，近似取值范围从±5.0×10−324～±1.7×10308：

从上面的代码可以看出，wholeDouble变量的赋值操作加了d后缀。这是因为C#和其他基于C的语言一样，在处理赋值语句右边的整数数字时，默认其为整型。如果在赋值时不加入d或D后缀，而试图直接将一个整型数值赋给双精度型，则会收到编译错误。

此外，注意到最后一位的归零误差。我们将30位有效数字的圆周率赋值给piDouble。但double只能保留14位有效数字，其后数字都会被约去。若直接对圆周率值保留15位有效数字，我们得到3.141 592 653 589 793，但由于归零误差，浮点数的实际值为3.141 592 653 589 79。

Java

Java使用double关键字标识64位浮点数值。在Java中，double类型的精度为15或16位有效数字，近似取值范围为±4.9×10−324～±1.8×10308：

查看上面的代码，注意到最后一位的归零误差。我们将30位有效数字的圆周率赋值给piDouble。但double只能保留15位有效数字，其后数字都会被约去。若直接对圆周率值保留15位有效数字，我们得到3.141 592 653 589 793 2，但由于归零误差，浮点数的实际值为3.141 592 653 589 793。

Objective-C

Objective-C也使用double标识符来确定64位浮点数值。在Objective-C中，double类型的精度为15位有效数字，近似取值范围从2.3×10−308到1.7×10308。为进一步提高精确性，Objective-C还提供了一个更高精度版本的double类型，即长双精度型（long double）。long double类型能够存储80位浮点数值，精度为19位有效数字，近似取值范围从3.4×10−4932～1.1×104932：

Swift

Swift使用double标识符来确定64位浮点数值。在Swift中，double类型的精度为15位有效数字，近似取值范围从2.3×10−308～1.7×10308。需注意的是，根据Apple公司的Swift文档，当float和double类型均能满足需求时，推荐使用double类型：

查看上面的代码，注意最后一位的归零误差。我们将30位有效数字的圆周率赋值给doubleValue。但由于double只能保留15位有效数字，其后数字都会被约去。若直接对圆周率值保留15位有效数字，我们得到3.141 592 653 589 793，但由于归零误差，浮点数的实际值为3.141 592 653 589 79。

1.1.4　货币类型

由于浮点运算事实上是基于二进制数学的，有着固有的不准确性，因此单精度和双精度浮点类型无法精确地表示我们使用的十进制货币。乍一看，将货币用单精度或双精度浮点类型表示或许是个好主意，因为它能够约去运算过程带来的细微误差。但是，当把这些本来就不怎么精确的结果再进行大量、复杂的运算后，误差会不断累积，造成严重的偏差和难以跟踪的错误。这使得单精度和双精度浮点类型无法用于对精确度要求近乎完美的十进制货币。幸运的是，对于货币和其他需要进行高精度十进制运算的数学问题，我们所讨论的这4种语言都提供了相应机制。

C#使用decimal关键字来标识精确浮点值。在C#中，decimal的精度为28或29位有效数字，取值范围为±1.0×10−28～±7.9×1028：

上述代码中，我们将30位有效数字的圆周率赋值给decimal Value，但它只保留了28位有效数字。

Java

Java以BigDecimal类的形式对货币类问题提供了一种面向对象的方案：

在上述代码中，我们把十进制值以文本形式作为构造函数的参数来初始化BigDecimal类。程序运行结果表明BigDecimal类返回了30位有效数字，没有精度损失。

Objective-C

Objective-C以NSDecimalNumber类的形式对货币类问题提供了一种面向对象的方案：

Swift

Swift用与Objective-C中同名的类NSDecimalNumber对货币类问题提供了一种面向对象的方案。这个类在Swift和Objective-C中的初始化操作有些区别，但功能并无二致。

注意，Objective-C和Swift两例的输出结果都有30位有效数字，这说明NSDecimal Number类适用于处理货币及其他十进制数值。

透露一下，对于这些定制类型，还有一种简单的、可以说是更为优雅的替代方法。可使用int或long类型来进行货币计算，用分代替元来计数：

1.1.5　类型转换

在计算机科学领域中，类型转换（type conversion或typecasting）是指将对象或数据从一种类型转换到另一种类型。例如，你调用了一个返回类型为整型的方法，并需要将这个返回值作为另一个方法的传入参数，但第二个方法要求传入参数必须是长整型。由于整型数值在定义上存在于长整型所允许的数值范围之内，因此int值可以重定义为long类型。

通常，可通过隐式转换（implicit conversion）或显式转换（也叫强制类型转换, explicit conversion）进行类型转换。此外，我们还需要了解静态类型语言（static languages）和动态类型语言（dynamic languages）的区别，才能完全领会类型转换的意义。

1．静态类型语言和动态类型语言

静态类型语言会在编译时进行类型检查（type checking）。这意味着当你试图生成解决方案时，编译器会检查和实施程序中所有数据类型的约束条件。如果检查失败，会停止生成并报错。C#、Java以及Swift均是静态类型语言。

另一方面，动态类型语言会在执行时进行大多数甚至所有的类型检查。这意味着如果开发人员在编程时有所疏忽，程序或许在生成阶段一切正常，但在执行时可能会出错。Objective-C混用了静态和动态类型对象，它是一种动态类型语言。本章之前所讨论的用于存储数值型数据的纯C对象均为静态类型，而Objective-C中的NSNumber和NSDecimalNumber类均为动态类型。思考下面的Objective-C代码示例：

编译器会对第一行代码报错，内容为“Initializing 'double' with an expression of incompatible type 'NSString *'”。这是因为double是一个纯C的静态类型。编译器甚至在生成之前就知道应该怎样处理这个静态类型，因此这段代码通不过检查。

然而，对于第二行代码，编译器只会发出内容为“Incompatible pointer types initializing 'NSNumber *' with an expression of type 'NSString *'”的警告。这是因为Objective-C的NSNumber类是一个动态类型。编译器很智能，能够发现错误，但仍然会允许进行生成（除非你在生成设置里指示过编译器将警告视为错误）。

显然，前面的例子在运行时会出现错误，但在有些情况下，即使存在警告，你的应用依然会正常运行。然而，无论你使用的是哪种语言，最好不断地清除掉已有的警告，再继续编程。这样有助于保持代码的整洁，并避免出现一些难以诊断的运行错误。

有时也许并不能及时地处理警告，这时应当清楚地记录下代码并说明警告源，以便其他开发人员了解来龙去脉。在万不得已的时候，可以利用宏和预处理器（预编译器）命令来一条条地忽略警告。

2．隐式转换和显式转换

不需要在源代码中使用任何特殊语法的类型转换为隐式转换（implicit casting）。隐式转换较为方便。思考下面的C#代码示例：

在上面的例子中，由于a既可以定义为int类型，也可以定义为double类型，且这两种类型都经过了人为定义，因此可以将a转换为double类型。然而，由于隐式转换并不一定要进行人为的类型定义，因此编译器不一定能完全判断类型转换所适用的约束条件，所以，直到程序运行前，编译器都无法进行类型转换检查。这样会使隐式转换存在一定的风险。思考下面的C#代码示例：

上面的例子并没有告诉编译器该如何处理字符串值，因此这是一个隐式转换。在这种情况下进行应用生成，编译器会针对这行代码报错，内容为“Cannot implicitly convert type 'string' to 'double'”。现在，思考同样例子的显式转换：

假设字符串是可解析的，上述类型转换即显式转换，因此是类型安全的。

3．缩限转换和扩展转换

两种数据类型在进行类型转换时，转换结果是否在目标数据结构所允许的范围之内非常关键。如果源数据类型比目标数据类型所支持的字节数多，则这种类型转换为缩限转换（narrowing conversion）。

缩限转换不是什么情况下都能够进行，并且在转换过程中很可能会丢失信息。举例来说，将浮点类型转换为整型会丢失数据（损失精度），转换结果会被近似为与原始值最接近的整数。在绝大多数静态类型语言中，缩限转换是不能被隐式执行的。以本章之前出现过的单精度和双精度类型的C#代码为例，将双精度缩限转换为单精度：

在这个例子中，编译器会报错，内容为“Cannot implicitly convert type 'double' to 'float'. And explicit conversion exists (Are you missing a cast?)”。编译器发现了这个缩限转换，并将精度损失视作错误。错误信息建议我们使用显式转换来解决问题。