《数据与数据结构》（基于新课标的高中信息科技教材之一）（1）

第1章 引言

章首语：

程序 = 数据结构 + 算法。

本章从计算机科学的视角，开启关于数据类型和数据结构的讨论。数据类型是程序设计语言中的概念，让我们能够方便地表达丰富多样的事物。数据结构是与算法紧密关联的概念，让各种算法能够有效地通过程序实现。数据结构中的“数据”，在计算机内最底层的逻辑表示都是0、1串，其含义的解释在于数据类型。数据结构中的“结构”，是本课程学习的主要内容，在程序中既服务于算法，也是算法的结果。数据结构并不神秘，从同学们开始学习程序设计的那一刻起，它就已经悄无声息地存在于代码的字里行间啦。

本章学习目标：

l  进一步理解数据的概念，尤其是从计算机程序的角度看数据的含义

l  理解数据类型的意义，了解有哪些不同的数据类型，理解不同数据类型的适用性和针对性

l  初步理解数据结构的概念和意义

l  了解数据类型与数据结构的关系

-----------------------------------------------------  

1.1  数据

数据是信息技术/计算机学科中一个最常用的术语，其内涵和外延都十分丰富。作为对本课程后面学习内容的一个引导，本小节首先描述对数据概念的一个多视角认识，同时指出在本课程中数据概念的主要定位，并通过几个例子讨论了数据类型的基本意义。

1.1.1 数据的含义

从本课程的先导模块《数据与计算》的学习中我们已经了解，数据（Data）是一个含义十分宽泛的概念。人们需要对数据话题的语境有一定的共识，才能够有效地讨论与数据相关的问题。本模块《数据与数据结构》中的“数据”，主要指计算机程序直接处理的数据，而不是人们日常提到的诸如“我想了解上海学生的健康数据”，“今年国民经济运行的主要数据”之中的“数据”。

对于一般电脑用户而言，能看到电脑桌面上和文件夹中有各种数据文件，例如一个电子表格，一个MP4视频文件，等等。它们通常是由某些特定的应用程序生成，也需要特定的应用程序才能打开。因此，我们可以说它们是应用程序的输入或输出数据。

对于计算机编程人员，或者说计算机应用开发人员，他们除了要理解上述输入数据外，还要理解程序内部的数据，具体就是每一个常量，每一个变量，它们代表什么，能对它们做些什么（施行什么操作）。

如果说人们日常提到的数据的含义是综合应用层面的，加上前面两种含义的数据，从信息技术的角度看，它们由表及里，表达了数据作为一个概念的三种实用性解释。为指代方便起见，不妨称为三个层次。这样一种概念上的区分有利于我们讨论问题，看到不同含义下作为一个术语的数据，服务于不同的目的。例如，当我们谈论数据的价值，所指的数据，主要是第一层面的。在前面两个必修模块中已有充分讨论。当我们谈论两个功能相似但品牌不同的应用程序的兼容性，则可能会涉及第二层面数据的问题 [1] 。而本课程中讨论的数据，从第2章开始，主要关心第三层含义的数据，即计算机程序具体操作的数据。

关于数据概念的这样一种划分虽然不是完备的（即不一定每一个现实情境下的数据都能恰好归到其中某一种），但它有益于我们在讨论数据问题的时候保持适当的针对性和相关性。

最后，在一些场合可能与数据互换使用的术语还有数据集、数据元素、数据项，等等。它们的区别是第2章学习的内容，在这里只需理解后者是相对具象的表达就可以了。在从第3章开始的数据结构学习中，有时也用“数据单元”来表示能够容纳一个数据元素的存储空间。

1.1.2数据的类型

当下常见的计算机又称通用计算机，即同一套硬件设施，能运行各种各样的应用程序，让我们感到它“什么都能干”。为什么能做到呢？在理论层面，计算机科学家（图灵）证明了，类似于乘法操作可以通过若干次加法完成，任何复杂的指令都可以由几条简单的指令实现；在实践层面，数据分类是一个重要基础，它让我们能够比较方便高效地表达各种事物。

下面是一个可以通过实际操作，体会数据分类的含义及其意义的例子。打开电脑中的某一个目录，你很可能一个看到类似于图1.1所示的情形。

图 1.1 不同类型的文件

里面有9个文件，由不同的图标代表。用鼠标双击某一个图标，就会启动某一个应用程序，然后你可以做有关的事情，编辑文档、看视频，等等。作为一个电脑用户，这似乎已经成为了自然，不会想为什么这种过程能够发生。但你现在可以尝试回答三个问题，（1）为什么点击左上角的那个文件（A.docx），文本编辑软件Word就会启动，点击第二排第一个文件（D.mp4），视频播放器就会启动呢？（2）如果修改文件名，将A.docx改成X.docx，情况会改变吗？如果将A.docx改成A.mp4呢？（3）C.png和G.jpg的文件名和扩展名都不相同，分别点击它们，会成功启动同一个应用程序吗？为什么呢？

这就属于从计算机应用的角度看数据类型的问题，计算机需要用户（以文件扩展名的形式）显示地告诉它数据文件的类型，方能正常有效地工作。同时，也是本课程的重点，在计算机应用开发人员的视野下，数据类型也是一个重要的概念，几乎无处不在。

在先导模块《数据与计算》中我们已经知道，计算机硬件最核心的抽象是“CPU+存储器”。存储器由若干能够存放固定字长（即基本存取单元中0或1的个数，称为“位数”是统一的，例如8位或一个字节）的数据单元构成，CPU按照程序指令安排的次序将其中的数据取出，做某种简单操作，然后再放回去。这意味着任何二进制码对计算机（硬件）而言没有特定的含义。例如，我们知道在ASCII编码中，00100011表示“#”，00111111表示“?”，如果让计算机做00100011+00111111，它会做，并正确地给出01100010，即ASCII编码的“b”。但一般看来这没有任何意义。这里只是说计算机做了没有意义的操作，在其他情况下则有可能由于程序员的疏忽，让计算机做了明显不该做的操作而导致错误，造成损失。

在计算机发展的早期，程序员只能用机器语言，情况就是这样的。他们必须带着对各个二进制串的理解，小心翼翼地编程序，避免让计算机做不该做的操作。这样，软件生产率很低，也难以编出大规模复杂的程序，呈现出一个明显的瓶颈，阻碍着计算机在人们经济社会生活中的普及应用。

高级程序设计语言（例如Fortran, C, Java, Python，等等）及其编译（解释）技术的发展，是解决这个瓶颈问题的基本途径。程序语言中让程序员指出数据的类型（数值型、逻辑型、字符型、指针型，等等），编译器根据不同数据类型的语义，检查是否有“不合法”的操作，若发现，则在程序调试阶段就报告给程序员，从而避免在生产运行时出错，造成损失。例如在Python中，如果你试图运行如下程序：

a = ‘1’

b = ‘2’

c = a*b

就会被告知一个类型错误（TypeError），说a和b是两个字符串，不能相乘。这个例子看起来简单，但要做好各种类型错误的检查是很不容易的，是现代编译器的一个重要功能。

    数据类型，作为程序设计语言中的一个重要概念，也是不断发展的，其不懈的追求是希望给程序员提供更有效地向计算机表达问题求解算法的能力，提高程序开发的效率。所谓“更有效地”含义之一就是表达层次更高。例如要写一个将100个数求和的程序，原则上可以用100个标量来表示那些数，然后在程序中显式写出99次加法，但那真的很麻烦。而有了数组类型后，就是一个变量名，用下标来指示不同的数，99次加法蕴含在循环语句的1次加法中，大大方便。

程序设计语言中各种数据类型的有效运用，离不开编译（解释）技术的配合。我们有时侯可能听人说，程序语言中规定了某种功能，但某一版本的编译器“不支持”，过了一段时间后，又听说出新版编译器了，支持那种功能，就是这个道理。例如，当赋值语句两边类型不相同时，Python2会做一些缺省的处理（看起来省事，但容易隐含错误），而Python3则要求程序员在程序中显式表达类型转换，以避免疏忽造成的错误。举个例子，下面这段程序，在Python2和Python3中的执行结果是不同的：

a1 = 3; a2=3.0

b = 2

print (a1/b,a2/b)

Python2给出(1, 1.5)，Python3给出(1.5, 1.5)。也就是说，Python2如果看到两个操作数都是整数，算的结果就自动取整（称为“缺省”操作）。这有时候似乎很方便，但更多的是带来潜在的错误。在Python3中，如果就是想“取整”，则需要做print(int(a1/b))或者print(a1//b)，把意图显式地表达出来。

在计算机领域，与数据类型相关的，还有一个概念是“数据格式”，它们与采用数据的应用程序相关，通常用文件扩展名标识，例如我们可以说图1.1中有9个文件，代表8种数据格式。就程序开发而言，针对程序的输入和输出，我们常听见纯文本文件和二进制文件两种说法。前者是指文件内容都是ASCII编码（在中文情形就是国标汉字编码）的字符，可以用任何常用的文本编辑软件打开，因而具有人工可读性。二进制文件则常常是特定应用生成的，包含一些（或者全部）非ASCII编码的内容，只有知道其生成规则（格式）的程序才能正常打开。常常，我们会听到说“这文件是乱码”。有时候不一定真是乱码，而是试图打开它的程序不对。从1.1.2节的例子及其练习中我们可以得到切身体会。初学程序设计，通常喜欢用纯文本文件，而成熟的商业应用程序，绝大多数都采用二进制文件。

进而，数据类型还是其他一些学科领域的基础概念。最明显的，当属统计学科。在那里，有类别数据和数值数据之分，例如性别就是一种类别数据，它可以取值“男”或“女”。当用计算机做统计数据处理的时候（这是当下大数据时代经常出现的需求），例如本书第2章的项目活动，我们需要在两个学科不同数据类型体系之间建立某种方便的对应，如用计算机中的数值0和1分别表示统计类别数据值“男”和“女”。

1.2  数据结构

如果说数据类型是多个学科都可能有的概念（含义有别），数据结构则是计算机学科的特有概念。关于数据结构的知识是计算机学科的专业基础知识，运用数据结构的能力是开发高水平程序必需的能力，理解了数据结构及其运用中蕴含的逻辑常常令人欣喜。本节从总体上讨论数据结构的意义及其与数据类型的关系，各种典型的数据结构与应用是本书的主体，将在第3、4、5章详细介绍。

1.2.1数据结构的意义

数据结构这个概念，并不是在计算机诞生之初就有的，它是伴随着程序设计技术的发展，旨在弥合计算机硬件的简单性和程序应用的复杂性之间的鸿沟，逐步形成和发展起来的。我们通过一个应用例子，来初步体会上面的陈述。

假设要有一个程序，不断接收输入数据（即它面对的是一个“数据流”），对每一个新到的数据（严格讲，数据元素），它要判断是否曾经收到过。如果是，则抛弃；如果否，则保留。我们关心如何让这个判断过程的效率比较高 [2] 。作为一个例子，设输入数据流中来了8个数：4，3，5，1，4，2，3，1。

一种方法是采用简单的线性存储结构 [3] ，即存储空间中的存储单元是顺序编号的 0，1，2，3，…，n-1，处理过程可如下描述：

每收到一个数，就依次和空间中已有的数比较，发现有相等的，就停止；若一直到最后还没有相等的，就把这个新数放在后面。

如果用比较次数作为效率衡量的指标，对上面给出的8个数，在存储空间中留下的结果是4，3，5，1，2，在每一个输入数据上用的比较次数见表1.1，总的比较次数为17。

表1.1 简单线性结构下的比较次数

另一种方法是，想象有一种非线性的存储结构，每当收到一个新的数，就在该结构的引导下进行判断过程，必要的话，也对该结构进行动态更新，以支持对后续数据的判断。图1.2展示在这个例子数据上该结构的变化过程，其中有8个框，分别对应8个数据依次到来判断处理后的结果，虚线框表示收到的是已有的数据，也是要做判断的，但对整个留存的结果没影响。

图1.2 在输入序列4, 3, 4, 1, 4, 2, 3, 1下的二叉查找树变化过程

    这样的结构称为“二叉树”（是后面要学习的重点内容之一，这里只需要体会大致含义就够了），它由一些“节点”和“边”构成。最顶上的节点称为根节点，根节点左下方整个称为“左子树”，右下方的是“右子树” [4] 。基于这样的结构，具体操作是这样的：

当收到一个新的数（x），首先和树根相比，如果相等，就停止；如果较小，就试图和左子树比，若左边没有可比的，就把x放到左下，让它成为左子树的根；如果较大，就试图和右子树比，若右边没有可比的，就把x放到右下，让它成为右子树的根。其中“试图和左子树比”和“试图和右子树比”，是一个递归的过程 [5] ，即把它们也看成是二叉树（但要小一些），照样进行。

对我们的例子数据跟踪这个过程，可以看到在每一个输入数据上用的比较次数 [6] 见表1.2，总的比较次数为13。

表1.2 二叉树结构下的比较次数

这里的重点不是要讨论13和17相比到底有多好，而是要意识到，有可能通过采用不同的数据组织方式来提高计算的效率。类似于二叉树这样的（逻辑）结构，计算机硬件是不懂的，需要计算机科学家发明出来，并通过软件的方式体现在硬件的线性存储空间上。几十年来，人们根据不同的计算需求发明了多种数据组织的形态，以支持高效软件的开发，统称为数据结构，是本课程学习的重点。其中，二叉树是颇具代表性的，在本书多处都会涉及到。

上述例子让我们得到了数据结构的一种直观印象，即它表达了程序数据之间的某种关系。这里特别值得认识到的是，此例图1.2中数据之间的那种关系，是由算法逻辑派生出来的，反过来又支持算法逻辑的贯彻执行。一般而言，数据结构上的数据，可能是程序的输入数据，也可能不是，常常也包括程序运行过程中产生的中间结果数据或控制数据。即便数据结构上的数据就是程序输入数据，由数据结构表达出来的关系，可能是那些数据之间的一种天然关系，也可能不是。一般而言，数据结构中数据的关系是根据算法逻辑的需要形成的关系。

1.2.2 数据结构与算法

计算（过程）是操作（或指令执行）的序列；算法（程序）是操作序列的描述：先做什么、后做什么、当某个条件出现时该做什么，等等；操作是作用在数据（或数据项）上的，数据结构是数据的组织形态，体现数据元素之间的某种关系，以支持算法的高效执行。

有时候，数据之间有一种天然的结构 [7] ，算法设计者依据该结构来编排操作序列，按照计算任务的需要，对该结构上的数据进行比较、交换、更新等操作。在整个过程中，数据结构不发生变化。

还有些时候，数据之间的结构关系是在算法过程中形成的。上一节图1.2就是一个示例。在这种情况下，算法设计者在脑子里有某种抽象的结构，所设计的操作序列一边在数据基础上构建具体的数据结构，一边依托已构成的部分结构完成计算任务所要求的数据操作。我们体会一下，按照这样的算法编写的程序，是不是有“边执行边给自己创造条件”的意味？

上述两种情形（不妨顾名思义，称前者为静态，后者为动态），都是在计算机应用中常见的，但后者更体现数据结构应用的精髓，体现了算法与数据结构的精巧互动。当然，也有许多场合，在同一个算法中既用到静态数据结构，也用到动态数据结构。

瑞士计算机科学家，Pascal等编程语言发明人，1984年图灵奖得主，尼古拉斯·沃斯（Niklaus Wirth）教授在1975年曾给出“算法+数据结构=程序”的著名等式，是对数据结构与算法关系的一个精辟诠释。这样一种见解，在动态数据结构的运用中显得格外精彩。

1.2.3 数据结构与数据类型

    在1.1节，我们聚焦的是数据类型的含义和意义。数据类型是程序语言中的概念，帮助提高程序开发的效率。1.2节讨论的数据结构是程序设计中的概念，与算法一起，旨在开发运行效率高的程序 [8] 。尽管有如此区别，在计算机科学的实践中它们也有密切的联系。

    首先，虽然各种数据结构的概念本身是抽象的（或者说是逻辑的），但在程序中的实现总是具体的，由若干数据元素及其关系构成。而数据元素（或其中的数据项）总会有一定的数据类型，同一种数据结构在不同的应用中其数据元素完全可能是不同的数据类型，例如1.2.1中的那个例子，数据可能是整数，也可能是实数，但数据结构不变。这是一种简单的“你中有我”。

    如我们要在第2章重点学习的，现代高级程序设计语言，除了提供我们在《数据与计算》模块中已经熟悉的数值型、字符型等基本数据类型外，还支持程序员定义比较复杂的数据类型。例如一个表达个人信息的数据元素，可以定义为由一个字符串（姓名），一个数字（年龄）和一个字符（性别）构成的数据类型（例如命名为“Person”）。这样的数据元素也可以看成是一个数据结构。于是我们可以说基于数据结构定义了一个数据类型。这是简单的“我中有你”。

    更复杂一些的，还可以基于诸如线性表、二叉树等数据结构定义数据类型。而在那样的数据类型上的操作，就对应在相应数据结构上支持的操作。以线性表为例，就可以做插入、删除、读取第i个元素等操作。

    鉴于上述数据类型和数据结构概念在程序设计应用中相互交织的情形，对一个具体的变量来说，取决于提及的场合，就可能有两种身份，例如既可以说它是具有线性表（列表）类型的数据，也可以说它是一个线性表（数据结构）。有些概念，在运用上也具有两重性，例如字符串和数组，在编程中主要看做是数据类型，但因为它们也体现了其中数据元素之间的关系，有时人们也称它们为数据结构。这样的现象对初学者可能造成困扰，但他们一旦习惯，就能感受到那正是计算机科学的魅力之一。

最后，在讨论数据结构相关问题时，常常会涉及“逻辑结构”与“物理实现”之类的说法。理解后者中的“物理”不是物理学科中的物理的含义，本质上是另一个层次的“逻辑”（甚至只是另一种逻辑），是有意义的。这样我们就能意识到，当我们在程序中实现某种数据结构，一切都只是发生在相应程序设计语言管理的程序数据空间中，与计算机硬件的存储器（物理）其实没有直接的映射关系。这样，当我们在一些数据结构教材中看到“计算机存储器”和“内存”等术语，一种合适的理解是它们不过是“线性地址空间”的一种方便的讲法，包括但不一定就是计算机硬件存储器。

学生活动1：

1.  课堂上（也可以课后），实际动手体验1.1.2节中的例子，回答所提出的问题，包括讨论为什么修改文件名很顺利，而修改文件扩展名可能会得到警告。

2.  在Python中编一个会产生“TypeError”的小程序。

3.  参照1.2.1节中的例子，对16个数的序列：5，3，5，4，2，1，6，8，3，3，4，1，7，8，4，2，给出类似于表1.1和表1.2那样的结果。

[1] 例如有的视频播放器能读入多种格式的视频文件并正常播放，有的则只能播放单一格式的。前者被认为是兼容性强。还例如我们经常会碰到某些网站只能通过特定品牌（或版本）的浏览器访问，也属于这类问题。因为网页就可以看成是浏览器程序的输入数据。

[2] 这个例子听起来简单，但它是许多实际应用的抽象，例如互联网路由器就需要有类似的功能。

[3] 计算机硬件的存储器就是一个例子，在程序中用的一维数组也是一个例子。

[4] 每个节点可能左右两个子树都有，也可能只有一个，或者没有。没有子树的节点称为叶节点。

[5] 后面要学习的一个概念，此处可以比拟俄罗斯套娃的情景，在形态上都是一样的，一个套一个，一个比一个小。

[6] 鉴于此处例子不可能用太多数据，这里假设了用1次比较就能给出<, =, >的判断。在本书的5.2节将会看到，这个假设不影响二叉树优于线性查找的基本结论。

[7] 例如每小时测一次气温，一天得到24个数字，依时间顺序成一列。这里的“一列”就可以看成是一种数据结构。

[8] 严格讲，合适数据类型的采用也可能提高程序运行效率，良好数据结构的采用也可能提高程序开发的效率，但它们的作用重点有区别。