数据结构算法及应用(第2版普通高等教育十二五重点规划教材)/计算机系列

作者简介

内容简介

第1章 绪论
　　辩证唯物主义的认识论指出，认识产生于实践的需要，实践的发展为人们提供日益完备的认识工具。计算机的发明使我们人类认识和改造世界的能力得到无限延伸。在计算机的世界里，一切都是数据，数据是人们通过计算机认知世界的基础。客观世界是普遍联系的，不同的联系方式产生了不同的数据组织形式。数据的组织形式就是数据结构，在数据之上运行的各种客观规律就是计算机算法。如果我们从连续的角度认知世界，体现出来的往往是各类数学方程，在计算机上就是数值计算；如果我们从离散的角度认知世界，在计算机上就是非数值计算。数据结构与算法主要讲的是非数值计算以及数值和非数值混合计算的数据组织和算法。
　　1.1 数据结构的概念
　　认识从实践中来，最终还要回到实践中去。在计算机的世界里，一切的实践都是通过程序来体现的。瑞士计算机科学家Niklaus Wirth提出了著名的公式“程序=数据结构+算法”，该公式说明了数据结构和算法对于程序设计是至关重要的，同时也说明了数据结构与算法的关系是密切的。程序可以被看作计算机指令的组合，用于控制计算机的工作流程，完成一定的逻辑功能，实现某种任务。算法是程序的逻辑抽象，是解决一些客观问题的过程。数据结构是对现实世界中数据及其关系的某种映射，数据结构既可以表示数据本身的逻辑结构，也可以表示计算机中的物理结构。下面通过例子来了解什么是数据结构。
　　【例1.1】图书馆的查询系统。当用户使用图书馆的查询系统时，用户会发现查询系统给出了很多查询条件，可以通过索引号、图书名称、作者姓名和出版社等信息进行查询。每一本书都有唯一的索引号，不同的图书之间可以有相同的名字，或相同的作者名，或相同的出版社。为了方便用户查询，在计算机内部是通过建立数据库表来实现图书信息存储的。如表1.1所示，共有四张索引表。其中，表1.1（a）是所有的图书信息，表1.1（b）是按照书名进行索引的表格，表1.1（c）是按照作者姓名索引的表格，表1.1（d）是按照出版社索引的表格。每个索引表的每一行就是一个最简单的线性数据结构。
　　表1.1 图书索引表
　　【例1.2】家族谱的存储。A姓家族谱如图1.1所示，其中“'”为配偶。和是A和A'的孩子，是和的孩子。若将A姓家族谱存储在计算机中，可以选择“树”这种数据结构进行存储。
　　图1.1 A姓家族谱
　　【例1.3】道路选择问题。如图1.2所示，A、B、C、D、E分别代表5个城市，边的数字代表从一个城市到达另一个城市的花费。现在一个人想要从城市A到达城市C，要求经过不同的城市，可以选择的路径见表1.2。
　　图1.2 城市道路图
　　表1.2 路径花费表
　　从表1.2的路径花费上可以看出，如果从城市A到达城市C，最好的选择是A→D→E→C，花费最小，为4。这种数据结构称为“图”。
　　数据结构（data structure）描述的是按照一定的逻辑关系组织起来的待处理数据的表示及相关操作，涉及数据之间的逻辑关系、数据在计算机中的存储和数据之间的操作（运算）。
　　1.1.1 数据的逻辑结构
　　数据的逻辑结构（logical structure）是从具体问题中抽象出来的数学模型，体现了事物的组成和事物之间的逻辑关系。
　　从集合论的观点来看，数据的逻辑结构由数据结点（node）和连接两个结点的边（edge）组成。一个逻辑结构可以用一个二元组(K， R)进行表示。其中，K是由有限个结点组成的集合，R是一组定义在集合K上的二元关系r，其中的每个关系是K×K上的二元关系（binary relation），用来描述数据结点之间的逻辑关系。例如图1.1中的家族关系。
　　讨论逻辑结构(K，R)的结构分类，一般以关系集R的分类为主。本书中所讨论的关系R集合仅包含一个关系r，用r的性质来刻画数据结构的特点，进行分类。
　　（1）线性结构（linear structure）。这种结构是程序设计中最常用的数据结构。线性结构中的关系r称为线性关系，也称前驱关系。结点集合K中的每个结点在关系r上最多只有一个前驱结点和一个后继结点。如图1.3所示，A是结点集合K在关系r上唯一的开始结点，A没有前驱结点，但是具有后继结点B；结点B和结点C既有前驱结点又有后继结点；结点D为终止结点，只存在前驱结点C，而不具有后继结点。
　　（2）树形结构（tree structure），又称树结构或层次结构，其中关系r称为层次关系。如图1.4所示的树形结构图，结点在关系r中没有前驱结点，该结点被称为树根（root）。结点C、结点D和结点E在关系r中具有唯一的前驱结点，但是没有后继结点，称这样的结点为叶子（leaf）。除了根结点和叶子结点以外，内部结点有且只有唯一的前驱结点，但可以具有多个后继结点，例如结点B。
　　（3）图结构（graph structure），也称为网络结构。互联网（Internet）的网页链接关系就是一个非常复杂的网络结构。图结构的关系r对于集合K中结点的前驱或后继数目不加任何约束。图1.2就是一个典型的图结构。
　　图1.3 线性结构
　　图1.4 树形结构
　　从数学上看，线性结构和树形结构的主要区别是“每个结点是否具有一个直接后继”，而树形结构和图结构的主要区别是“每个结点是否仅仅从属于一个直接前驱”。以上几种数据结构分类揭示出数据之间的相互关系，给出关系本身的一种性质。这对于理解数据结构以及设计算法都是至关重要的，后续章节将对以上的数据结构进行详细的讲解。
　　1.1.2 数据的存储结构
　　数据的存储结构要解决各种逻辑结构在计算机中物理存储表示的问题。计算机主存储器为其存储提供了一种具有非负整数地址编码的、在存储空间上相邻的单元集合，其基本的存储单元是字节。计算机指令具有按地址随机访问存储空间内任意单元的能力，访问不同地址所需要的访问时间相同。
　　数据结构研究数据之间的内在结构关系，所以可以把组成结构的那些元素看作数据结点。结点的数据类型可以是基本的数据类型，也可以是复杂的数据类型。
　　在程序设计语言中常使用5种基本数据类型。
　　（1）整数类型（integer）：该类型规定了整数所能表示的范围，由于计算机中一般使用1~4字节来存储，所以整数类型的缺陷在于限制了存储字节所能表示的范围。
　　（2）实数类型（real）：计算机的浮点数数据类型所能表示的数据范围和精度是有限的，一般使用4~8字节来存储浮点数。
　　（3）布尔类型（boolean）：取值为真（true）或假（false），在C++语言中一般使用0表示假，非0表示真。
　　（4）字符类型（char）：用单个字节表示ASCII字符集中的字符，字符类型不包括汉字符号。
　　（5）指针类型（pointer）：该类型表示机器内存地址，即表示指向某一内存单元的地址。
　　复合类型是由基本数据类型组合而成的数据结构类型。例如，在程序语言中的类类型、结构体类型等都属于复合数据类型。复合数据类型本身又可以参与定义更为复杂的结点类型。总之，结点的类型不限于基本的数据类型，可以根据实际需要来灵活定义。
　　对逻辑结构而言，其数据的存储结构就是建立一种逻辑结构到物理结构的映射。一方面，需要建立一个从结点集合K到存储器M的映射，即 ，其中每一个结点都对应一个唯一的连续存储区域。另一方面，还要把每一个关系元组（其中）映射为相应的存储单元的地址间的关系（顺序关系或指针的地址指向关系）。
　　下面介绍4种常用存储映射的方法：顺序方法、链接方法、索引方法和散列方法。
　　1．顺序方法
　　顺序方法把一组结点存放在一片地址相邻的存储单元中，结点间的逻辑关系用存储单元间的自然关系来表达。顺序方法为使用整数编码访问数据结点提供了便利。程序设计语言内提供的数组是顺序方法的一个具体实例。
　　顺序存储结构通常也被称为紧凑存储结构。其紧凑性是指其存储空间除了存储数据本身之外，没有存储其他附加的信息。紧凑性可以用“存储密度”来度量：所存储的“数据”占用的存储空间和该结构（包括附加信息）占用的整个存储空间大小之比。显然，存储密度太小的存储结构的空间效率比较低。
　　除线性结构外，部分非线性数据结构也可以采用顺序方法。例如，树形结构也可以采用顺序方式来存储，前提是同时存储一些附加信息来表示结点之间的逻辑关系。
　　2．链接方法
　　链接方法是在结点的存储结构中附加指针域来存储结点间的逻辑关系。链接方法中数据结点由两部分组成：数据域存放结点本身的数据，指针域存放指向其后继结点的指针。
　　根据应用的需要，结点的指针域也可存储多个指针来表达一个结点同时链接多个结点的情况。例如，非线性结构中一个结点可能会有多个后继结点的情况。
　　链接方法适用于那些需要经常增删结点而动态变化的数据结构。链接方法的缺陷在于：为了访问结点集K中的某个结点，必须使用指向该结点的指针。当不知道结点指针时，为了在结点集K中寻找某个符合条件的结点，就要从链头开始沿着链接结点的指针，通过逐个结点的比较来搜索。
　　3．索引方法
　　索引方法是顺序存储的一种推广，通过建造一个由数据域Z映射到存储地址域D的索引函数 ，把数据索引值z映射到结点的存储地址 ，从而形成一个存储了一组指针的索引表，其中每个指针指向存储区域的一个数据结点。索引表的存储空间是附加在结点存储空间之外的，每一个元素就是指向相应数据结点的指针，即结点存储单元的开始地址。作为一种存储机制，索引的主要作用是提高检索的效率。如果数据量很大，对数据的检索可能涉及大量读/写磁盘的操作，会影响效率。通过索引则可以降低读/写的数据量，根据检索码确定被检索数据的存储地址之后再进行相应的读/写。
　　4．散列方法
　　作为索引方法的一种延伸和扩展，散列方法利用散列函数（hash function）进行索引值的计算，然后通过索引表求出结点的存储地址。其主要思想是根据结点的关键码值来确定其存储地址，利用散列函数计算出结点的关键码映射到的存储地址，然后把结点存入此存储单元中。
　　散列技术的关键问题是如何选择和设计恰当的散列函数、构造散列表、研究散列表存储的碰撞解决方案等。
　　一个散列函数把一个给定的关键码映射为一个小于K的非负整数，K的大小取决于具体的应用。散列函数应该满足一些重要的散列性质：散列函数计算出的地址尽可能均匀地分布在构造的散列表地址空间，散列函数的计算应该简单化，以便提高地址计算速度。
　　在一个具体的应用中，可以根据需要选用以上4种存储方法或其组合。例如，树形结构的子结点表示方法就是顺序和链接的结合。另外，一个逻辑结构可以有多种不同的存储方案，在选择存储方法时，还要综合考虑定义在其上的运算及其算法的实现。
　　1.2 算法与算法设计
　　1.2.1 算法的概念
　　算法（algorithm）是对特定问题求解过程的描述，是指令的有限序列，即为解决某一特定问题而采取的具体而有限的操作步骤。英文的algorithm（算法）一词来源于9世纪的波斯，中文的“算法”一词至少在唐代就出现了，在此之前也有“术”“算术”等词，最早出现在《周髀算经》《九章算术》等。约公元前300年记载于《几何原本》中的辗转相除法（欧几里得算法）被人们认为是史上第一个算法，可以求两数的最大公约数。《九章算术》给出了四则运算、最大公约数、最小公倍数、线性方程组求解等算法。程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解。
　　求解最大公因子的辗转相除法，以及求解联立线性方程组的主元素消去法都是算法的典型例子。一个求解问题通常用该问题的输入数据类型和该问题所要求解的结果（算法的输出数据）所应遵循的性质来描述。以求最大公因子算法为例，它的输入是整数类型，输入数据是任意给定的两个正