包邮数据结构(面向信息学竞赛)

第1章 概述 什么是数据结构？为什么要学习它？ 计算机和互联网已经成为社会生活的重要组成部分，人们对各种计算机术语也越来越熟悉。因此，大部分计算机专业课程只听名字就大概能知道或者猜到课程要讲什么，如“计算机网络”、“操作系统”、“数据库”或者“人工智能”。 但“数据结构”这个词平常很少见，即使是科技时讯节目，也不会有“近日某国科学家发现了一种新型的数据结构”之类的报道。 既然如此，*好先通过几个例子了解一下什么是数据结构。 假设你是某个生活在几十年前的“化石级”程序员，你和你周围所有人掌握的计算机知识就是C语言，或许还有某个简单的图形库。通过你们的不懈努力和艰苦攻关，你们先后完成了图书管理系统、人事管理系统、飞机订票系统和产品销售系统等系统。这时你突然发现一个问题，这些系统要求的功能其实差不多，都是对图书、员工、票据或产品组成的集合的增加、删除、查询、排序等操作。如果把图书、产品等具体内容分离出来，而专门对数据集合和对数据集合的操作进行深入的研究，就可以得到一套系统的开发方法，甚至可以把这套方法写成库函数，以后开发类似系统时只需按图索骥即可。 将具体问题抽象化之后，你会发现，一些看上去并不相关的领域其实需要解决的问题本质上是完全相同的，如以下两个问题： (1) 对于物流运输行业，并不是总是直接从出发地到目的地，中间通常会经过若干个城市。如何设计一个系统，只要将所有城市之间的运力和运输成本等信息输入，就可以计算出任意出发地到目的地的*优运输路线(许多大型物流、快递公司都有类似的系统，有些甚至精确计算到街道和十字路口)。 (2) 对于计算机网络，信息发送者和接收者通常都不是直接相连的，而是经过若干个路由器。如何设计一种方法，只要能获取所有路由器之间的传输时延和带宽限制，路由器就会自己选择*优路径，并向*优路径上的下一个路由器发送数据包(现在的互联网路由就是建立在这种方法上的)。 只要稍加思考，就会发现这两个问题的实质是一样的：已知一个由许多顶点连接而成的网状结构，并且已知这些顶点间的连接成本，要求设计一种方法，能让计算机替我们找出任意两顶点间成本*低的路径。 数据结构学习和研究的主要目的是：对一些常见的具体问题进行抽象，并加以学习研究，以便今后碰到类似问题可以举一反三。有些时候这门研究也被称为算法研究。“算法”应该听起来比“数据结构”稍微亲切一些，毕竟这个词在科技新闻和网络文章里经常出现。 1968年，美国的高德纳(Donald E. Knuth)教授开创了数据结构和算法的*初体系，他的著作《计算机程序设计艺术》是**部系统阐述数据结构和算法的著作。1971年，沃斯(Niklaus Wirth)进一步提出了“算法+数据结构=程序”的结构化程序设计理念，他反对拿到问题就直接编写代码，而是分若干步进行，逐步求精。**步先确定所需要的数据结构、写出算法的大致框架，第二步编写出的程序抽象度有所降低，直至*后编写出可执行的程序。随着计算机硬件和编程工具的快速发展以及软件需求者群体的改变，今天的软件开发模式已经发生了很大变化，面向对象、测试驱动开发、重构、设计模式和迭代式开发等新的软件工程方法开始取代结构化程序设计理念，但“算法+数据结构=程序”这一公式仍被称为计算机科学中的“E = mc2”。在计算机发明以来的短短数十年间，计算机领域的无数科学家和工程师对各种数据结构和算法进行了非常深入及广泛的研究，研究成果应用于计算机科学和工程的各个领域，成为计算机程序设计的基石。经过数十年的研究和探索，传统意义上的数据结构体系已经完整地建立，各种相关研究也基本完成，各种数据结构和算法作为程序设计的基石，被许多语言吸收为它们基本类库、函数库或扩展工具包的一部分。 1.1 数据结构 1.1.1 数据与数据结构的定义 数据(data)是计算机可以存储和处理的所有内容的统称。计算机中的各种文件，包括文字、图像、声音和视频等，都是数据；计算机内存和缓存中所有的内容，都是数据；甚至计算机的源代码和可执行代码，也属于数据。 数据元素(data element)是数据的基本单位。例如，学生信息表中的一个学生，图书管理系统中的一本图书，互联网上的一台路由器，在程序设计或数据结构分析中通常作为一条数据进行考虑，或者说是一个数据元素。但是一个学生又可以包括姓名、学号、专业等信息(表1-1)，这些信息称为数据项。 表1-1 学生信息表 数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合。根据元素间关系的不同，可以大致将数据结构分为三大类：线性结构、树形结构和图状结构。如果用圆圈(又称结点)表示一个数据元素，用结点间的连接线表示两个数据元素之间的关系，那么可以将这三种结构画成类似图1 1所示的示意图。 图1-1 三种基本数据结构 结合示意图，这里先简要说明三种基本数据结构的特点，本书后面还会分别进行详细介绍。 线性结构中，除了开始和末尾结点，每个结点只有**的前驱(左侧)结点和后继(右侧)结点。 树形结构中，除了开始结点(*上方的结点)，每个结点只有**的前驱(上层)结点；除了终端结点(没有下层结点的结点)，每个结点有一个或多个后继(下层)结点。整个结构像一棵反向的树，*上面是树根，*下面是树叶，中间是树枝，因此称为树形结构。 图状结构中，每个结点可以有多个前驱结点和多个后继结点。图状结构也是数据结构基本关系中*复杂的一种。 这里“前驱”和“后继”是为了分析问题的需要而临时定义的两结点间的关系，有些问题中数据元素存在前后关系，有些问题中数据元素不存在前后关系，读者不必过分纠结这一概念。 1.1.2 逻辑结构、物理结构和抽象数据类型 另外两个经常会用到的概念是逻辑结构和物理结构。 逻辑结构是使用自然语言去描述只存在于想象中的数据之间的关系，或者用更规范的方式来描述——为数据间的关系建立数学模型。 物理结构是数据在计算机中实际存储的情况，所以也称为存储结构。 逻辑结构用于说明“做什么”，而物理结构旨在说明“如何做”。它们的关系有点像两位计算机创始人图灵(Alan Turing)和埃克特(J. Presper Eckert)各自眼中的计算机。在图灵眼中，计算机只不过是一条无穷的纸带，它记录和保存状态，并根据输入内容和当前状态进行输出。在埃克特眼中，计算机是一个占地170m2，由数万个电子管、电阻器和电容器组成的耗电大户，每一次加法都需要一组电气元件齐心协力才能完成。 举个例子，可以把线性结构描述为如下数学形式： 对于数据元素构成的集合，存在数据关系。 D是一个集合，它定义了之前线性结构示意图中的所有结点。关系R也是一个集合，它定义了之前示意图中所有结点间的连接。 但是这一定义并没有为我们用代码实现这种数据结构提供太多有用的信息。如图1 2所示，如果用加以限定的数组来实现线性表，那么在内存中ai确实刚好紧跟在ai1后面；如果用链表来实现，那么在内存中ai可能在ai-1后面，也可能在它前面，ai与ai-1间可能会跳过很多内存空间。如果我们去推敲计算机中存储数据的细节，那么就属于分析存储结构了。 图1-2 逻辑上的线性结构可以对应不同的物理结构 逻辑结构定义了数据集合与数据关系，但即使对于一个抽象的问题，仅仅定义集合和关系也是不够的，至少还需要定义对数据集合的基本操作。 举例来说，如果需要抽象学生管理系统、图书管理系统、产品管理系统的主要特征，那么除了定义一个并列、有序关系的集合，还应该定义包括对集合内的数据进行增加、删除、排序和检索等基本操作，之后就可以根据这些定义来逐一实现这些基本操作，*后把研究的结果用于各种具体的系统。只有这样，我们对抽象问题的研究才有意义。 定义一个数据集合、集合中各元素间的数据关系以及对数据集合的基本操作，称为定义一种抽象数据类型(abstract data type)。 数据结构的研究基本上围绕抽象数据类型展开：首先找到一类具有共同特征的问题，将这种问题定义为一种抽象数据类型，然后分析和实现这种抽象数据类型的各种基本操作，从而得到一种具有通用性的数据结构或算法。 从C语言实现的角度来看，可以认为抽象数据类型是定义了一个结构体和一系列以这个结构体类型的变量为参数的函数。从C++或者Java等面向对象的程序设计语言实现的角度来看，抽象数据类型定义了一个类或模板类。 1.2 算法与算法分析 有了数据结构，还要有用数据结构具体解决问题的方法，也就是算法。算法和数据结构密不可分，离开算法，数据结构没有存在的价值。因此，在学习数据结构的过程中一般都会同时学习相关算法。 1.2.1 算法 算法(algorithm)是使用计算机求解特定问题步骤的一种描述，它是一系列解决问题的清晰指令。 算法并不限定描述语言，甚至可以用自然语言描述算法。但算法终究是要指挥计算机解决问题的，而计算机又不像人一样能主动对问题进行界定、补充、分析和尝试，为确保算法没有超出计算机的理解能力，*好是用一种程序设计语言来描述它。 因为算法的读者是人而不是计算机或编译器，所以算法描述不需要像源代码那么精确，只要作者和读者能理解彼此的意思即可，有时候算法会用不标准的语言来描述，忽略一些不太重要的细节和步骤，这些语言称为伪代码。 1.2.2 算法的性质和判断算法优劣的标准 一个算法应该具备以下五条性质： (1) 有穷性，即算法必须能在执行有限个步骤之后终止。 (2) 确定性，即算法的每一步骤必须有确切的定义，读者理解时不会产生歧义。 (3) 可行性，即算法的任何步骤都可以分解为有限次基本的可执行操作，不会超出程序设计语言语法可以实现操作的范围。 (4) 有输入，一个算法有0个或多个输入。 (5) 有输出，一个算法有1个或多个输出。 除了这些基本性质，算法还应该具备以下特点，这些特点有时不是必需的，而是用来判断一个算法优劣的标准。 (1) 正确性。这条标准看上去非常可笑，难道还能允许错误的算法存在吗？对于绝大部分程序，理论上确实不应该出现任何错误，尤其是一些事关国计民生、人命关天的程序，如航天、军事、银行、电力和通信行业，程序一旦出现了错误(称为bug)，可能导致难以弥补的重大损失。至于同学们做练习的程序出了错，那更是不要怪机器不给力，要认认真真分析问题。 然而，在统计科学和人工智能领域，少量错误不可避免，必须接受。举个例子，即使是*先进的人脸检测算法，也不能保证100%的正确率，在复杂的光照、遮挡、阴影和混杂背景下，正确率甚至更低。自然语言理解、语音识别、目标跟踪、垃圾邮件过滤和信息检索等领域都存在类似的问题，科学家和工程师为减少1%的错误而欢欣鼓舞。对于这些算法，正确率是判断程序好坏*重要的性能指标。 (2) 可读性。即使算法设计的目标是让机器去执行命令，算法本身仍然是作者和读者交流的重要工具，也可以让作者清晰记录下自己的设计思路以备将来查询和修改，因此良好的书写和描述方法有助于人对算法的理解。这一原则对于源代码同样适用，源代码不仅仅要作为给机器的指令，也是程序员之间相互交流的重要手段。如何书写可读性强的源代码，可以参考林锐博士等所著的《高质量程序设计指南——C++/C语言》。 (3) 健壮性(robustness)。健壮性是指当输入数据的取值不在合理范围内时，算法也能做适当处理，而不是崩溃或出现逻辑错误。例如，一个计算器程序，当输入的除数为0时，应该给出相应的出错信息，而不是毫无知觉地进行计算。又如，当