第 1 章　计算机科学：将抽象机械化

优质

小牛编辑

156浏览

2023-12-01

计算机科学是个新领域，不过它几乎已经触及人类工作的每个方面。计算机、信息系统、文本编辑器、电子表格的普及，以及使得计算机更便于使用、人们生产效率的精彩应用程序的激增，都显示出计算机科学对社会的影响。该领域有个重要的部分，涉及如何让程序设计更容易以及让软件更可靠。不过从根本上讲，计算机科学是一门抽象的科学，它为人们思考问题以及找到适当的机械化技术解决问题而建立模型。

其他科学是顺其自然地研究宇宙。例如，物理学家的工作就是理解世界是如何运转的，而不是去创造一个用物理定律能更好地理解的世界。而计算机科学家则必须抽象现实世界中的问题，使其既可以为计算机用户所理解，又可以在计算机内加以表示和操作。

进行抽象的过程有时很简单。例如，我们能熟练地用“命题逻辑”这种抽象方式，为制造计算机所使用的电子电路的行为建模。通过逻辑表达式进行的电路建模是不准确的，它简化了或者说是抽象掉了很多细节，比如电子流经电路和门所花的时间。然而，命题逻辑模型已经足够帮助我们顺利设计计算机电路了。我们将在第12章中更多地探讨命题逻辑。

再举个例子，假设我们要为各种课程的期末考试排定时间。也就是说，我们必须为各门课程的考试指定时段，只有在没有学生同时选择某两门课程的前提下，才将这两门课程的考试安排在同一时段。如何为这一问题建模，起初可能不太好确定。一种方式是为每门课程画一个称为节点（node）的圆，如果有学生同时选择了两门课程，就画一条线来连接相应的两个节点，这条线称为边（edge）。图1-1表示了5门课程可能的关系图，这幅图就是课程冲突图。

图 1-1　5门课程的课程冲突图，两门课程之间的边表示至少有一个学生同时选择了这两门课程

有了课程冲突图，我们就可以通过在图中反复找出并删除“最大独立集”来解决考试安排问题。独立集是没有边相连接的节点的集合。如果不能再向某独立集添加图中的其他节点了，那么就说这个独立集是最大独立集。即，一个图中包含节点数目最多的独立集称为最大独立集。在说课程时，最大独立集就是指没有共同学生的课程的最大集合。在图1-1中，｛经济学，英语，物理｝就是一个最大独立集。最大独立集中的这些课程被指定到第一个时段。

我们从图中删除第一个最大独立集中的节点以及这些节点附带的边，接着在剩下的课程中找出最大独立集。下一个可选的最大独立集是单元素集｛计算机科学｝。这个最大独立集中的课程便被分配到第二个时段。

如此重复找出并删除最大独立集，直到课程冲突图中不再有任何节点。至此，所有课程都已经被分配到各时段中。本例中，在两次迭代之后，课程冲突图中就只剩下数学节点了，而它就组成了最后一个最大独立集，将被指定到第三个时段中。形成的考试排期如下：

时段	课程考试
1	经济学，英语，物理
2	计算机科学
3	数学

这一算法不见得会将各门需要考试的课程分布在数目尽可能少的时段中，不过它很简单，而且生成的时间安排中所含的时段数目往往接近最小值。利用第9章介绍的技术，它也很容易被设计成计算机程序。

请注意，这种方式会将一些可能很重要的问题细节抽象掉。例如，它可能会让某个学生在5个连续的时段内参加5科考试。也许我们可以建立这样一个模型，对某个学生一次可能连续参加考试的科目数加以限制，不过这样一来，建立的模型和考试安排问题的解决方案都可能变得更加复杂。

抽象：不用担心
读者可能会对“抽象”这个词有所忌惮，因为我们都有这样一种直觉：抽象的东西都是难以理解的。例如，人们一般会认为抽象代数（研究群、环，诸如此类）要比高中时学的代数难。然而，我们所使用的抽象意味着简化，是将现实中复杂而详细的情景替换为解决问题所使用的可理解模型。也就是说，我们将那些对解决问题而言影响甚微或根本没有影响的细节“抽象掉”了，从而建立一个让我们能处理问题实质的模型。

通常情况下，找到好的抽象方式是相当困难的，因为计算机能执行的任务有限，执行速度也有限。在计算机科学的初期阶段，一些乐观主义者认为机器人很快就能像《星球大战》中的C3PO机器人那样神通广大。自那时起，我们已经了解到，要让计算机（或机器人）具有“智能”行为，就需要为计算机提供一个本质上跟人类所支配的世界一样详细的模型，不仅要包括事实（“萨莉的电话号码是555-1234”），还要包括原则和关系（“如果抛出某物体，它通常会向下坠落”）。

我们在“知识的表示”这一问题上已经取得了很大的进步，设计出了一些抽象方式，可用来构建进行某类推理的程序。有向图便是这种抽象的一个例子，它用节点表示实体（“猫”或“松毛”），用从一个节点指向另一个节点的箭头（称为弧）代表关系（“松毛是只猫”，“猫是动物”，“松毛的牛奶碟子归松毛所有”），图1-2就展示了这样一幅图。

图 1-2　这幅图用于表示与“松毛”相关的知识

另一种实用的抽象是形式逻辑，它让我们可以运用推理规则推导事实，比如“如果X 是只猫，Y 是X 的母亲，那么Y 是只猫”。不过，为现实世界或其关键部分建模（或者说是对其进行抽象）的过程，却仍是计算机科学所面临的一大挑战，是近期没法彻底解决的。

1.1　本书主要内容

本书目标读者应当具有一定的ANSI C语言程序设计实践经验，本书旨在为这些读者介绍计算机科学的基本概念和重点内容。书中强调了如下三种重要的问题解决工具。

1. 数据模型。数据特征的抽象，用来描述问题。我们已经提到了两种模型：逻辑和图，而在本书中还会看到很多其他的模型。

2. 数据结构。用来表示数据模型的编程语言结构。例如，C语言提供了内置的抽象，比如结构和指针，使我们能够构建数据结构，表示像图这类的复杂抽象。

3. 算法。操作用数据模型抽象、数据结构等形式表示的数据，从而获取解决方案的技术。

1.1.1　数据模型

我们在两种情况下会提到数据模型。像本章开头讨论的图这样的数据模型，是常用于协助形成问题解决方案的抽象。我们还会在本书中了解多种这样的数据模型，比如第5章介绍的树、第6章介绍的表、第7章介绍的集、第8章介绍的关系、第9章介绍的图、第10章介绍的有限自动机、第11章介绍的语法，以及第12章和第14章介绍的逻辑。

数据模型还与编程语言及计算机相关。比如，C语言的数据模型就包含诸如字符、多种长度的整数以及浮点数这类的抽象。C语言中的整数和浮点数只是数学意义上整数和实数的近似值，因为计算机所能提供的算术精度是有限的。C语言数据模型还包括结构、指针和函数这样的类型，我们将在1.4节中详细介绍。

1.1.2　数据结构

当手头问题的数据模型不能直接用编程语言内置的数据模型表示时，我们就必须使用该语言所支持的抽象来表示所需的数据模型。为此，我们研究了数据结构，将编程语言中没有显式包含的抽象，以该语言的数据模型表示出来。不同的编程语言可能有着大不相同的数据模型。例如，与C语言不同，Lisp语言直接支持树，而Prolog语言则内置了逻辑数据模型。

1.1.3　算法

算法是对可机械执行的一系列步骤精准而明确的规范。用来表示算法的可以是任何一种可被常人理解的语言，不过在计算机科学领域，算法多用编程语言正式地表现为计算机程序，或用编程语言混合英语语句的非正式风格来表示。大家在学习编程时很可能已经遇到过一些重要算法。例如，有不少为数组元素排序的算法，就是按照从小到大的顺序排列数组元素。有一些诸如二叉查找（binary searching）之类的查找算法很巧妙，可以通过反复将某给定元素在数组中可能出现的部分对半划分，迅速地找到这个元素。

这些算法以及其他一些解决常规问题的“招数”，是计算机科学家们在设计程序时会用到的工具。我们将在本书中学习诸多此类技巧，包括重要的排序和查找方法。此外，我们还要了解使一种算法优于其他算法的因素。很多时候，运行时间（running time），或者说算法处理输入所花的时间，是算法“质量”的重要一环，我们会在第3章中讨论。

算法的其他方面也很重要，特别是简易性。理想情况下，算法应该易于理解，并易于转变成可运转的程序。而且，懂得相应知识的人在阅读了实现该算法的代码后，应该能理解由该算法转变而来的程序。不过快速和简易往往是不能两全的，所以我们必须要明智地选择算法。

1.1.4　基本思路

在进一步阅读本书的过程中，我们将遇到一些重要的统一原则。在这里要提以下两点。

1. 设计代数。在底层模型得到充分了解的某些领域，我们可以提出一些表示法，以便表示和评价某些折衷的设计方案。通过这样的认识，我们可以提出一些设计理论以构建出设计良好的系统。命题逻辑，加上第12章中的布尔代数这种相关的表示法，就是设计代数的一个好例子。有了它，我们可以为数字计算机中的子系统设计高效的电路。其他设计代数的例子还包括第7章中的集代数、第8章中的关系代数，以及第10章中的正则表达式代数。

2. 递归。作为一种可用来定义概念和解决问题的实用技术，递归特别值得一提。我们会在第2章中详细讨论递归，本书后续内容中也会反复用到它。每当我们需要精确地定义对象，或需要解决问题时，都应该问一问：“递归解决方案应当是什么样子呢？”递归方案的简易和效率常使其成为最优方法。

1.2　本章主要内容

本章接下来的部分将为计算机科学的学习做好铺垫，要介绍以下主要概念。

数据模型（1.3节）。
C语言的数据模型（1.4节）。
软件开发流程的主要步骤（1.5节）。

我们会介绍一些例子，讲讲抽象和模型出现在计算机系统的几种方式。其中特别提到了编程语言中的模型、特定系统程序（比如操作系统）中的模型，以及计算机所使用电路中的模型。由于软件是当今计算机系统的重要组成部分，因此我们需要理解软件开发流程、模型和算法扮演的角色，以及软件开发中计算机科学只能以有限方式解决的那些方面。

在1.6节中会介绍一些常规定义，它们在全书的C语言程序中都将用到。

1.3　数据模型

任何数学概念都可称为数据模型。而在计算机科学领域，数据模型通常包含以下两个方面。

1. 对象可以采用的值。例如，很多数据模型包含具有整数值的对象。数据模型的这个方面是静态的，它告诉我们对象能接受哪些值。编程语言数据模型的这一静态部分通常被称为类型系统。

2. 数据的运算。例如，我们常常会对整数执行加法这样的运算。模型的这一方面是动态的，它告诉我们改变值和创建新值的方式。

1.3.1　编程语言数据模型

每种编程语言都有自己的数据模型，这些数据模型互不相同，而且通常有相当大的差异。多数编程语言处理数据所遵循的基本原则是，每个程序都可以访问我们用于表示存储区域的“框”。每个框都具有一个类型，比如int或char。框中可以存储类型对应的值，通常将可以存储到这些框中的值称为数据对象。

我们还要为这些框命名。一般来说，框的名称可以是任何指示该框的表述性词语。我们通常会将框的名称视作该程序的变量，不过情况并非完全如此。例如，如果x 是递归函数F 的局部变量，那么就可能会有很多名为x 的框，每个x 都与对F 的不同调用相关联。这样的话，这种框的真实名称就是x 与对F 的某次调用的组合。

C语言中的多数数据类型都是我们熟悉的：整数、浮点数、字符、数组、结构和指针。这些都是静态的概念。

可以对数据进行的操作包括整数和浮点数的常规算术运算、数组或结构元素的存取操作，以及指针的解引用（也就是找到指针所指向的元素）。这些运算都只是C语言数据模型动态部分的一部分。

在程序设计课程中，我们可能会看到C语言中不包括的重要数据模型，比如表、树和图。用数学语言来讲，表就是可以写成(a₁, a₂ , … , a_n)这种形式的n 个元素组成的序列，其中a₁是第一个元素，a₂是第二个，以此类推。表的运算包含插入新元素、删除元素，以及拼接表（也就是将一个表追加到另一表的末端）。

示例1.1

在C语言中，整数表可以用链表这种数据结构表示，表的元素被存储在链表的节点中。链表及其节点可用如下类型声明定义。

typedef struct CELL *LIST;
struct CELL {
    int element;
    struct LIST next;
};

该声明定义了有着两个字段的自引用结构CELL。第一个字段是element，存放着表中元素的值，而且其类型为int。

每个CELL的第二个字段是next，存放着指向节点的指针。请注意，LIST类型其实是指向CELL的指针。因此，CELL类型的结构可以通过它们的next字段链接起来，构成我们通常所说的链表，如图1-3所示。next字段既可以被视为指向下一个节点的指针，也可以代表从某节点起的整段链表。同理，整个链表也可以用指向链表第一个单元的LIST类型的指针表示。

{%}

图 1-3　表示表(a₁, a₂, … , a_n)的链表

单元是用长方形表示的，其左边部分表示元素，右边部分存放指针（表示为指向下一个单元的箭头）。存放指针的方框中的点表示该指针为NULL1。第6章将更详细地介绍表。

1NULL是标准头文件stdio.h中定义的符号常量，用来表示未指向任何内容的指针的值。本书中的NULL指针都作此义解释。

数据模型与数据结构
尽管名称类似，但“表”和“链表”却是非常不同的概念。表是种数学抽象，或者说是数据模型。而链表则是种数据结构，是通常用于C语言及相似语言中的数据结构，用来表示程序中的抽象表。而有些编程语言则不需要用数据结构来表示抽象表。例如，表(a₁, a₂, … , a_n)在Lisp语言中可以直接表示为[a₁, a₂,… , a_n]，而在Prolog语言中也可以表示为类似形式。

1.3.2　系统软件的数据模型

数据模型不仅存在于编程语言中，而且存在于操作系统和应用程序中。大家可能熟悉UNIX或MS-DOS这样的操作系统，也可能熟悉Microsoft Windows。2操作系统的功能是管理和调度计算机的资源。像UNIX这样的操作系统，其数据模型具有文件、目录和进程这样的概念。

2如果对操作系统不熟悉，那么可以跳过下面几个段落。不过大多数读者都应该接触过操作系统，可能只是称呼不同。例如，Macintosh“系统”就是一种操作系统，只是使用了不同的术语。例如，在苹果用语中，目录就被称为“文件夹”。

1. 数据本身存储在文件中，在UNIX系统中，文件都是字符串和字符。

2. 文件被组织成目录，目录就是文件和（或）其他目录的集合。目录和文件形成了树形结构，而文件处在树叶的位置3。图1-4中的树可以表示UNIX操作系统的目录结构。目录是用圆圈表示的。根目录/包含名为mnt、usr、bin等的目录。目录/usr含有目录ann和bob，而目录ann下含有3个文件：a1、a2和a3。

3不过，目录中的“链接”可能会让某个文件或目录看起来像是几个不同目录的一部分。

3. 进程是指程序的独立执行。进程接受流作为输入，并产生流作为输出。在UNIX系统中，进程可以通过管道连接，让一个进程的输出作为下一个进程的输入。这种进程组合可看作有着自己输入输出的独立进程。

{%}

图 1-4　具有代表性的UNIX目录/文件结构

示例1.2

想想如下UNIX命令行。

bc | word | speak

符号|表示管道，该操作使符号左边进程的输出成为符号右边进程的输入。程序bc是桌面计算器，接受算术表达式（例如2+3）作为输入，并生成答案5作为输出。程序word用来将数字转换成单词，而speak则将单词转换成音素序列，接着通过扬声器将语音合成器合成的声音播放出来。这三个程序通过管道连接起来，使这条UNIX命令行成为了一个进程，并表现为一个“会说话的”桌面计算器。它接受算术表达式作为输入，并产生说出来的答案作为输出。本示例还可以说明，将复杂的任务处理成多个简单功能的组合，实现起来可能会更加简单。

操作系统还有其他许多方面，比如它如何控制数据安全以及与用户的互动。不过，即便是通过这些简单的观察，也应该很容易看出，操作系统的数据模型和编程语言的数据模型是相当不同的。

文本编辑器中有另一种数据模型。文本编辑器的每种数据模型都结合了文本字符串的表示和对文本的编辑操作。这种数据模型通常会包含行的概念，行和多数文件一样，就是字符串。不过，与文件不同的是，行可能有着与其相关联的行号。行还可能被组织成更大的单元（比如段落），而且对行进行的操作通常适用于行内的任何位置，而不会像多数常见的文件操作那样，只是对前部进行操作。一般的文本编辑器会支持“当前”行（光标所在的那一行）的概念，还可能支持行内当前位置的概念。文本编辑器执行的操作包括对行的多种修改，比如在行内删除或插入字符、删除行，以及创建新行。在一般的文本编辑器中还可以在已编辑文件的行中搜索特定的字符串。

其实，如果看看其他熟悉的软件，比如电子表格或视频游戏，就会发现，每个调用程序都必须遵守被调用程序的数据模型。我们见到的各种数据模型通常彼此间截然不同，无论是用来表示数据的原语，还是向用户提供的数据操作方式，全都不同。而且各数据模型都是通过数据结构和使用它们的程序，用某种编程语言实现的。

1.3.3　电路的数据模型

在本书中我们还会看到计算机电路使用的数据模型。这种模型就是命题逻辑，在计算机设计中是最实用的。计算机是由称为门的基本元件组成的。每个门都有着一个或多个输入以及一个输出，输入或输出的值只能是0或1。门具有一个简单的功能，比如AND运算（与运算），就是如果所有输入为1，那么输出就是1，而如果至少有一个输入为0，那么输出就是0。从某个抽象层次来讲，计算机设计就是选择如何连接门来执行计算机基本运算的过程。当然也存在其他很多与计算机设计相关的抽象层次。

图1-5展示了常见的与门符号以及对应的真值表，该表指明了每对输入值搭配经过该门产生的输出值4。我们将在第12章中介绍真值表，并在第13章中介绍门及门的互相连接。

4请注意，若我们将1视为“真”，将0视为“假”，则与门执行的是和C语言中&&运算符相同的逻辑运算。

{%}

图 1-5　与门及其真值表

示例1.3

执行C语言赋值语句a=b+c，计算机会使用加法电路执行加法运算。在计算机中，所有数字都是以二进制的形式，使用0和1这两个数字（叫作二进制数字，或简称位）表示的。二进制加法计算也遵守十进制加法的法则，从右端的数字开始相加，如果产生进位，就将进位加到右起第二位上，如果这一位上相加的结果还产生进位，就继续加到右起第三位上，以此类推。

我们可以用几个门来组建一位加法器（one-bit adder）电路，如图1-6所示。两个输入位x 和y，一个进位输入位c，经过相加，形成一个和值位z，以及进位输出位d。更精确地讲，如图1-7所示，如果c、x 和y 中有不少于两个的值为1，那么d 的值就是1，而如果c、x 和y 中有奇数个（1个或3个）的值为1，那么z的值就是1。进位输出位后面跟上和值位（即dz）就形成了一个两位的二进制数，这就是x、y 和c 为1时的总值。在这种情况下，这个一位加法器就完成了输入的相加运算。

图 1-6　一位加法器：dz是x + y + c的和

{%}

图 1-7　一位加法器的真值表

行波进位加法算法
在进行十进制数的加法时，我们都使用过行波进位算法。拿456+829举例，相加的步骤应该如下所示。
也就是说，第一步，我们会将最右边的位相加，6 + 9 = 15。记下5，并将进位1放到第二列。第二步，我们将进位输入1与右起第二位的两个数字相加，得到1 + 5 + 2 = 8。记下8，进位是0。第三步，将进位输入0，与右起第三位上的数字相加，得到0 + 4 + 8 = 12。记下2，由于我们已经计算到了最左边的位，因此就不将1进位，而是将其作为结果中最左边的一位。
二进制行波进位加法也有着相同的原理。只不过，在每一位上，进位和要相加的“数字”要么是0，要么是1。因此一位加法器完整地描述了单个数位上的加法表。也就是说，如果三个位都是0，那么和就是0，就记下0以及进位0。如果三个位中有一个是1，那么和就是1，就记下1及进位0。如果三个位中有两个是1，那么和就是2，也就是二进制数10，就记下0以及进位1。如果三个位全是1，那么和就是3，也就是二进制数11，就记下1及进位1。例如，用行波进位加法将二进制数101和111相加的步骤如下所示。

很多计算机用32位数字来表示整数。所以加法器电路可由32个一位加法器组合而成，如图1-8所示。该电路通常称为行波进位加法器，因为进位是从右向左一次一位行进的。要注意，最右侧（最低位）一位加法器的进位总是0。位序列x₃₁x₃₀…x₀表示一个加数，而y₃₁y₃₀…y₀则表示另一个加数。和就是dz₃₁z₃₀…z₀，也就是说，和的第一位是最左侧一位加法器的进位输出，而接下来的位就是从左往右各加法器的和值位。

如图1-8所示的电路是由位数据模型以及门的原始运算形成的算法。不过这不是一种特别好的算法，因为要是不计算完最右侧那一位，就不能计算z₁或右起第二位的进位输出。不计算完右起第二位，就不能计算z₂或右起第三位的进位输出，诸如此类。因此，该电路花费的时间就是加数的位长（在本例中是32）乘上每个一位加法器执行运算所需的时间。

{%}

图 1-8　行波进位加法器：dz₃₁z₃₀…z₀=x₃₁x₃₀…x₀+y₃₁y₃₀…y₀

有人可能会认为，进位在每个一位加法器间“行进”的需求，是加法定义中固有的。要是这些读者知道计算机还有快得多的加法计算方式，肯定会大吃一惊的。我们将在第13章讨论电路的设计时，介绍一种改进过的加法算法。

1.3.4　习题

1. 解释数据模型静态方面和动态方面的差异。

2. 描述自己最喜欢的视频游戏的数据模型。区分其模型的静态方面和动态方面。提示：静态部分不仅是指计分牌上不会移动的部分。例如，在《吃豆人》游戏里，静态部分不仅包括地图，还包括“强化药丸”和“怪物”等。

3. 描述自己最喜欢的文本编辑器的数据模型。

4. 描述电子表格程序的数据模型。

1.4　C语言数据模型

在本节中，我们将重点介绍C语言所使用数据模型的重要部分。以图1-9所示的C语言程序为例，该程序使用变量num来计算其输入中所含的字符数。

#include <stdio.h>
main()
{
    int num;
    num = 0;
    while (getchar() != EOF)
        ++num; /* add 1 to num */
    printf("%d\n", num);
}

图 1-9　计算输出所含字符数的C语言程序

程序的第一行告诉C语言预处理器，将标准输入/输出文件stdio.h包含为源的一部分。该文件含有getchar及printf函数的定义，以及表示文件结束的符号常量EOF。

C语言程序本身也包含一系列的定义，既可以是函数的定义，也可以是数据的定义，其中必须要有main函数的定义。图1-9所示程序的函数体中，第一条语句声明了int类型的变量num（在C语言程序中，所有变量在使用前都必须先声明），下一条语句将num初始化为0，接下来的while语句则使用库函数getchar一次读入一个输入字符，并在每次字符读入后递增num变量，直到没有输入字符可供读入为止。输入中的特殊值EOF会提示文件已达末尾。printf语句则会将num的值以十进制整数之后加上换行符的形式打印出来。

1.4.1　C语言类型系统

首先介绍C语言数据模型的静态部分——类型系统，它描述了数据可能拥有的值。随后要讨论C语言数据模型的动态部分，也就是可以对数据进行的操作。

在C语言中，有着类型构成的无限集合，其中的任意元素都可以成为与某个特定变量相关联的类型。这些类型以及构成类型的规则就形成了C语言的类型系统。类型系统包含整数这样的基本类型以及一些类型构成规则（type-formation rule），利用这些规则，我们可以用已知的类型逐步构建更为复杂的类型。C语言的基本类型包括：

1. 字符（char、signed char、unsigned char）；

2. 整数（int、short int、long int、unsigned）；

3. 浮点数（float、double、long double）；

4. 枚举（enum）。

整数和浮点数称为算术类型。

类型构成规则假设我们已经有了一些类型，可以是基本类型或使用这些规则构建好的其他类型。以下是C语言中的一些类型构成规则。

1. 数组类型。可以用以下声明构建一个元素类型为T 的数组：

T A[n]

该语句声明了包含n个元素的数组A，其中每个元素都是T类型的。在C语言中，数组下标是从0开始的，所以数组的第一个元素是A[0]，而最后一个元素是A[n-1]。数组可由字符、算术类型、指针、结构体、共用体或其他数组构成。

2. 结构体类型。在C语言中，结构体是由称为成员或字段的变量构成的分组。在结构体中，不同的成员可以具有不同的类型，但每个成员都必须具有某一个类型的元素。如果T₁、T₂、…、T_n 是类型，而M₁、M₂、…、M_n 是成员名称，那么如下声明

struct S {
　　T₁ M₁;
　　T₂ M₂;
　　…
　　T_n M_n;
}

就定义了标记（即其类型的名称）为S而且具有n 个成员的结构体。对i = 1、2、…、n 来说，第i 个成员名称为M_i，且其值为T_i 类型。示例1.1就展示了一个结构体。该结构体的标记是CELL，并含有两个成员。第一个成员的名称是element，类型为整数。第二个成员名称为next，它的类型是指向某个同类型结构体的指针。

结构体标记S 是可选的，不过它可以在随后的声明中为表示类型提供方便的简写。例如，声明

struct S myRecord;

定义了变量myRecord是一个类型为S 的结构体。

3. 共用体类型。共用体类型允许一个变量在程序执行的不同时期具有不同的类型。声明

union{
　　T₁ M₁;
　　T₂ M₂;
　　…
　　T_n M_n;
} x;

定义了变量x，可以存放类型为T₁、T₂、…、T_n 中任意一种的值。成员名称M₁、M₂、…、M_n 用来指示x的值现在应该是哪种类型。也就是说，x.M_i 就表明x的值是类型为T_i 的值。

4. 指针类型。C语言的独特之处在于对指针的依赖。指针类型的变量包含某个存储区域的地址。可以通过指针，间接地访问另一个变量。声明

T *p;

定义了变量p是指向某个T 类型变量的指针。用p来表示指向T 的类型指针的框，框p的值就是个指针。我们往往将p的值表示成一个箭头，而不是将其表示成T 类型的对象本身，如图1-10所示。真正出现在p框中的是T 类型对象在计算机中存储的地址（或位置）。

{%}

图 1-10　变量p是指向T 的类型指针

考虑如下声明

int x, *p;

在C语言中，一元运算符&是用来获取对象地址的，所以声明

p = &x;

将x的地址赋值给p，也就是说，这让p指向x。

用在p前面的一元运算符*会获取p指向的框的值，所以声明

y = *p;

会将框p指向的内容赋值给y。如果y是int类型的变量，那么

p = &x;
y = *p;

就等价于赋值语句

y = x;

示例1.4

C语言的typedef结构可用来创建类型名称的同义字。

看一看图1-11中的4个typedef声明。依照对C语言中数据的传统看法，类型type1是有10个槽（slot）的数组，每个槽中都存放着一个整数，如图1-12a所示。同样，类型type2的对象是指向这类数组的指针，如图1-12b所示。而类型type3的结构体则被表现为图1-12c中所示的形式，每个字段都有一个槽与其对应。请注意，字段名称（例如field1）实际上并未与字段的值一起出现。最后，数组类型type4的对象将会有5个槽，每个槽都存放着类型type3的对象，即如图1-12d所示的结构体。

typedef int Distance;
typedef int type1[10];

typedef type1 *type2;

typedef struct {
    int field1;
    type2 field2;
} type3;

typedef type3 type4[5];

图 1-11　一些C语言typedef声明

图 1-12　图1-11中类型声明的形象化表示

类型、名字、变量和标识符
与数据对象相关的一些术语有不同的含义却又容易混淆。首先，类型描述了数据对象的“形状”。在C语言中，可以使用typedef结构为已有的类型定义一个新名字T。
typedef <类型描述符> T
这里的类型描述符是个表达式，告诉我们T 类型的对象是什么样子。
类型为T 的typedef声明实际上并没有创建T 类型的对象。要创建T 类型的对象，需要使用如下形式的声明
T x;
这里的x是个标识符，或者说是“变量名”。x有可能是静态的（不是任何函数的局部变量），在这种情况下，表示x的框在程序开始时就创建了。如果x不是静态的，那么它应该是某个函数F 的局部变量。在调用F 时，就会创建一个名为“与本次对F 的调用相关联的x”的框。更准确地说，该框的名称还是x，不过只在执行本次对F 的调用时，才使用标识符x来表示该框。
正如文中提到的，因为F 可能是递归函数，所以可能存在许多名称涉及标识符x的框。甚至可能会有其他函数使用标识符x命名自己的某个变量。此外，名字比标识符更具一般性，因为有很多种表达式可以用来为框命名。例如，我们提到过*p可以是指针p指向的某个对象的名字，而该对象的其他名字也可以是复杂的表达式，比如(*p).f[2]或p->f[2]。这两个复杂表达式是等价的，都表示指针p指向的结构体中f字段数组的第二个元素。

1.4.2　函数

函数也具有与之关联的类型，即使我们没有像处理程序变量那样，将框或“值”与函数相关联。对任意的一列类型T₁、T₂、…、T_n，我们可以定义一个函数，具有n 个类型依次为这些类型的参数。这一列类型后面带上函数返回的值（返回值）的类型，就是这个函数的“类型”。如果函数没有返回值，那么该函数就是void类型的。

一般情况下，可以应用类型构成规则任意地构建类型，不过也存在一些限制。比如，不能构建“函数数组”，不过构建由指向函数的指针构成的数组是可以的。在C语言中构建类型的完整规则可以在ANSI标准中找到。

1.4.3　C语言数据模型中的操作

C语言数据模型中的数据操作可分为以下三类。

1. 创建或销毁数据对象的操作。

2. 访问或修改数据对象某些部分的操作。

3. 将若干数据对象的值组合起来，为某个数据对象生成新值的操作。

1.4.4　数据对象的创建和销毁

对于数据的创建，C语言提供了几种简陋的机制。在函数被调用时，会创建对应每个局部参数的框，这些框都用来存放参数的值。

另一种数据创建机制是使用程序库例程malloc(n)，该例程可以返回一个指针，指向n 个未使用的连续字符位置，这些存储空间可被malloc的调用者用来存储数据。然后就可以在这一存储区域中创建数据对象。

C语言有着类似的方法来销毁数据对象。当函数返回时，该函数调用的局部参数将不复存在。例程free会释放malloc创建的存储空间。特别要说的是，调用free(p)的效果是释放p指向的存储区域。若使用free去销毁不是通过调用malloc创建的对象，会造成灾难性后果。

1.4.5　数据的访问和修改

C语言具有访问对象某些部分的机制。可以使用a[i]访问数组a的第i个元素，用x.m访问结构x的成员m，还可以用*p访问指针p指向的对象。

在C语言中，修改（或者说是写）值主要是由赋值运算符完成的，这让我们可以改变对象的值。

示例1.5

如果变量a的类型是示例1.4中所定义的type4，那么

(*a[0].field2)[3] = 99;

就把值99赋给了数组a第一个元素所代表的结构体中field2指向的数组的第4个元素。

1.4.6　数据的组合

C语言有着丰富的运算符，可用来对值进行操作和组合。主要运算符包括如下这些。

1. 算术运算符。C语言提供了以下几种算术运算符。

(a) 用于整数和浮点数的常规二元算术运算符+、-、*、/。整数除法会取整（4/3得1）。

(b) 一元的+和-运算符。

(d) 递增和递减运算符++和--，适用于单个整数变量反复从自身增加或减去1。这些运算符可以出现在它们的操作数之前，也可以出现在它们的操作数之后，取决于我们是想在改变变量的值之前还是之后计算该表达式的值。

2. 逻辑运算符。C语言中没有布尔类型，它使用“0”来表示逻辑值“假”，使用“非0”表示逻辑值“真”。5C语言使用以下几种逻辑运算符。

5我们将反复使用TRUE和FALSE作为已定义的常量1和0，来表示布尔值，详见1.6节。

(a) &&表示AND运算。例如，表达式x&&y在两个操作数都非0的情况下会返回1，否则返回0。不过，如果x的值为0，就不考虑y的值了。

(b) ||表示OR运算。表达式x||y在x或y非0的情况下会返回1，否则返回0。不过，如果x的值非0，就不考虑y的值了。

(d) 条件运算符是三元（三参数）运算符，用一个问号和一个冒号表示。表达式x?y:z在x为真（即x 为非0）的情况下会返回y的值，在x为假（即x=0）的情况下会返回z的值。

3. 比较运算符。对整数或浮点数使用6种关系比较运算符之一（==、!=、<、>、<=、和>=），如果关系不成立，结果就为0，否则结果为1。

4. 位运算运算符。C语言提供了一些实用的位逻辑运算符，将整数当作与它们的二进制形式相同的位字符串。这些运算符包括，用于按位与的&，用于按位或的|，用于按位异或的^，用于左移位的<<，用于右移位的>>，以及用于左移位的波浪字符（~）。

5. 赋值运算符。C语言使用=作为赋值运算符。除此之外，还允许将x=x+y;这样的表达式写为x += y;这样的简短形式。类似的格式也可以用于其他二元算术运算符。

6. 强制转换运算符。强制转换是指将某个类型的值转换成另一个类型的等价值的过程。例如，如果x是浮点数，而i是整数，那么x = i会导致i的整数值被转换成值相等的浮点数。在这里，强制转换运算符并未显式出现，不过C语言编译器会推断从整数到浮点数的转换是必要的，并自动执行所需的转换步骤。

1.4.7　习题

1. 解释C语言程序的标识符与名字（用于“框”或数据对象）之间的区别。

2. 举例说出有多个名字的C语言数据对象。

3. 如果熟悉C语言之外的编程语言，描述一下它的类型系统和操作。

1.5　算法和程序设计

对数据模型、它们的属性及其适当用途的研究是计算机科学的一大核心，而与其同等重要的一大核心便是对算法以及与其相关的数据结构的研究。我们需要了解执行常见任务的最佳方法，而且需要学习设计优秀算法的主要技术。此外，我们还需要了解如何将数据结构和算法的使用融入创建实用程序的过程中。数据模型、算法、数据结构，以及它们在程序中的实现，这些主题相互依存，而且每个主题都会在本书中出现多次。在本节中，我们将粗略地提到一些与程序的设计和实现有关的知识。

1.5.1　软件的创建

在程序设计课上，当我们拿到编程问题时，可能需要设计解决问题的算法、用某种语言实现该算法、编译程序并用一些示例数据运行它，然后提交该程序给老师打分。

而在商业背景中，编程环境则完全不同。算法通常只不过是完整程序的一小部分，至少对那些简单平常到信手可拾的算法来说是这样。而程序通常是涉及硬件和软件的更大系统的组件。程序及其所嵌入的完整系统，都是由程序员和工程师团队开发的，这样的团队可能有数百人的规模。

软件系统的开发过程通常要跨越多个阶段。虽然这些阶段表面上可能和解决课堂编程任务所涉及的步骤有相似之处，但是构建软件系统来解决特定问题的功夫多数并没有花在编程上。下面要讲的是一种理想化的场景。

问题的定义和需求说明。在创建软件系统的过程中，最难也是最重要的部分是定义真正的问题所在并指明解决问题所需的条件。通常，问题的定义始于对用户需求的分析，不过这些需求通常是不准确的，而且很难写下来。系统架构师可能要咨询系统未来的用户，并对需求说明进行迭代，直到详解者（specifier，拟定需求说明的人）和用户都对定义和解决手头问题的需求说明感到满意为止。在需求说明阶段，为最终系统建立简单的原型或模型是有好处的，因为这样可以深入了解系统的行为和可能的用途。数据建模也是问题定义阶段的一个重要工具。

设计。一旦完成需求说明，系统的上层设计就已成形，而且主要组成部分也确定了。开发人员会拟定一份概述上层设计已完成的文档，文档中还可能包含系统的性能要求。该阶段还可能引入有关某些主要组件的更详细的需求说明。高性价比的设计往往需要重用或修改以前构造的组件，诸如面向对象技术这样的多种软件方法论推动了组件的重用。

实现。一旦敲定设计，就可以开始实现组件了。本书中讨论的很多算法都能在实现新组件的过程中派上用场。一旦完成组件的实现工作，就要对其进行一系列的测试，以确保它能像需求说明所说的那样工作。

集成和系统测试。当组件得到实现而且已经单独测试过，就应该将整个系统组合起来并进行测试。

安装和现场测试。一旦开发人员觉得系统已经能以令客户满意的状态运转，就可以将系统安装到客户的办公地点，并进行最终的现场测试。

维护。至此，我们可能会认为已经完成了大部分的工作。然而，还需要有维护工作。在很多情况下，维护可能要占据超过一半的系统开发成本。维护可能涉及修改组件来消除不可预见的副作用、修正或提高系统性能，或增加新功能等目的。因为维护是软件系统设计中很重要的部分，所以编写的程序务要正确、耐用、高效、可修改，并且能从一台计算机移植到另一台计算机。

尽早地发现错误很重要，最好是在问题定义阶段就能发现错误。越到后面的阶段，修复设计错误或编程错误的成本越高，对需求和设计的独立审查有利于减少后续的错误。

1.5.2　编程风格

编写他人能够轻松阅读和修改的程序，便能够显著减轻维护负担。好的编程风格都是练习的结果，建议大家一开始就试着编写方便他人理解的程序。没有什么神奇公式能确保程序的可读性，不过还是有一些实用经验可介绍给大家。

1. 将程序分成相关的模块。

2. 为程序排版，使其结构清晰。

3. 编写易于理解的注释来解释程序。清晰准确地描述底层数据模型、用来表示数据模型的数据结构和每个例程所执行的操作。在描述例程时，要陈述对其输入作出的假设，并讲清输出和输入有什么关系。

4. 对例程和变量使用有意义的名称。

5. 尽可能避免使用明确的常数。例如，不要用数字7表示小矮人的个数，而是要使用诸如NumberOfDwarfs这样定义的常量，这样一来，如果决定再加上一个小矮人，就可以很方便地将该常量的值改为8。

6. 避免使用“全局变量”，即不要为整个程序定义变量，除非程序中的大多数例程都要使用该变量所表示的数据。

另一个编程好习惯就是拥有成套测试输入，可以在编程时对每行代码进行测试。每当为程序增加了新功能，就可以运行这套测试，以确保新程序在处理这些起作用的输入时能和老程序行动一致。

1.6　本书中用到的一些C语言约定

在说明与C语言程序相关的概念时，有一些实用的定义和约定。其中一些是在标准头文件stdio.h中也能找到的常规约定，而另一些则是为本书特别定义的，必须在使用它们的C语言程序中包含这些约定。

1. 标识符NULL是指针的值，可能在任何出现指针的地方出现，但它是个不能指向任何内容的值。因此，出现在示例1.1链表节点的next字段中的NULL，可以用来表示链表的结尾。我们还将看到NULL在其他的数据结构中也有着诸多类似的用途。NULL在stdio.h头文件中得到了恰当的定义。

2. 标识符TRUE和FALSE按如下方式定义

#define TRUE 1
#define FALSE 0

因此，在任何需要逻辑值“真”的情况中都可以使用TRUE，而在逻辑值为“假”的情况中都可以使用FALSE。

3. 类型BOOLEAN被定义为

typedef int BOOLEAN;

在强调要表示的是表达式的逻辑值而非数值时，就会使用BOOLEAN。

4. 标识符EOF是getchar()这样的文件读操作函数在无法继续从文件读出字节时返回的值。stdio.h文件为EOF定义了一个合适的值。

5. 我们还要定义一个宏，用来生成示例1.1中所用节点的声明。图1-13就展示了一种可取的定义。它声明单元具有两个字段：element字段的类型是由参数Type给定的，而next字段则指向具有本结构的单元。该宏提供了两项外部定义：CellName是该类型结构体的名字，而ListName则是指向这些单元的指针的类型名称。

#define DefCell(EltType, CellType, ListType)                  \
typedef struct CellType *ListType;                            \
struct CellType {                                             \
    EltType element;                                          \
    ListType next;                                            \
}

图 1-13　用来定义表中单元的宏

示例 1.6

通过使用宏

DefCell(int, CELL, LIST);

可以定义示例1.1中那种类型的单元。

该宏随后会扩展为

typedef struct CELL *LIST;
struct CELL {
    int element;
    LIST next;
}

这样一来，我们就可以使用CELL作为整数单元的类型，并使用LIST作为指向这些单元的指针的类型。例如

CELL c;
LIST L;

定义了单元c，以及指向单元的指针L。请注意，通常会用指向表第一个单元的指针来表示一列单元，如果表为空，则用NULL来表示。

1.7　小结

至此，大家应该已经从本章中了解到以下概念。

数据模型、数据结构和算法是怎样用来解决问题的。
数据模型“表”和数据结构“链表”之间的差别。
无论是编程语言、操作系统，还是应用程序，每种软件系统中都存在着某种类型的数据模型。
C语言所支持数据模型的关键要素。
大型软件系统开发过程的主要步骤。

1.8　参考文献

Kernighan and Ritchie [1988]是C语言的经典参考书。Roberts [1994]对使用C语言的程序设计进行了很好的介绍。

Stroustrup [1991]创造了C语言的面向对象扩展版——C++，C++已被广泛用于系统的实现。Sethi [1989]对几种主要编程语言的设计模型进行了介绍。

Brooks [1974]有力地描述了大型软件系统开发中存在的技术难题和管理难题。Kernighan and Plauger [1978] 针对改善编程风格提出了一些忠告。

American National Standards Institute(ANSI) [1990]. Programming Language C, American National Standards Institute, New York.

Brooks, F. P. [1974]. The Mythical Man Month, Addison-Wesley, Reading, Mass.

Kernighan, B. W.,and P. J. Plauger [1978]. The Elements of Programming Style, second edition, McGraw-Hill, New York.

Kernighan, B.W.,and D. M. Ritchie [1988]. The C Programming Language, second edition, Prentice-Hall, Englewood Cliffs, New Jersey.

Roberts, E .S. [1994].The Art and Science of C: A Library Based Introduction to Computer Science,Addison-Wesley, Reading, Mass.

Sethi, R. [1989]. Programming Languages: Concepts and Constructs, Addison-Wesley, Reading, Mass.

Stroustrup, B. [1991]. The C++ Programming Language, second edition, Addison-Wesley, Reading, Mass.

第 1 章 计算机科学：将抽象机械化

1.1 本书主要内容

1.1.1 数据模型

1.1.2 数据结构

1.1.3 算法

1.1.4 基本思路

1.2 本章主要内容

1.3 数据模型

1.3.1 编程语言数据模型

示例1.1

1.3.2 系统软件的数据模型

示例1.2

1.3.3 电路的数据模型

示例1.3

1.3.4 习题

1.4 C语言数据模型

1.4.1 C语言类型系统