第 2 章  

常用数据结构与算法

当初人们试图建造计算机的主要原因之一是用来存储和管理一些数字化的信息和数据，这也是最初数据结构概念的来源。当我们使用计算机解决问题时，必须以计算机能够了解的模式来描述问题，而数据结构是数据的表示法，也就是计算机中存储数据的基本结构，编写程序就像盖房子一样，要先规划出房子的结构图，如图2-1所示。

图2-1  编写程序就像盖房子一样，要先规划出房子的结构图

简单来说，数据结构所讲述的是一种辅助程序设计并进行优化的方法论，它不仅讨论数据的存储与处理的方法，同时也考虑数据彼此之间的关系与运算，目的是提高程序的执行效率与减少对内存空间的占用等。图书馆的书籍管理也是一种数据结构的应用，如图2-2所示。

图2-2  图书馆的书籍管理也是一种数据结构的应用

2.1    认识数据结构

在信息技术如此发达的今天，我们每天的生活已经和计算机密切不可分了。计算机与信息是息息相关的，因为计算机具有处理速度快和存储容量大两大特点，所以在数据处理中扮演着举足轻重的角色。所谓数据（Data），指的是一种未经处理的原始文字（Word）、数字（Number）、符号（Symbol）或图形（Graph）等，例如姓名或我们常看到的课表、通讯簿等都可称为一种“数据”。

当数据经过处理（Process），例如以特定的方式系统地进行整理、归纳，甚至进行分析后，就成为“信息”（Information）。这样处理的过程就称为“数据处理”，如图2-3所示。信息是使用大量的数据经过系统地整理、分析、筛选而提炼出来的，它具有参考价值，并可为决策提供所需的文字、数字、符号或图表。

图2-3  数据处理过程的示意图

数据结构加算法是指数据进入计算机内进行处理的一套完整逻辑，选定了数据结构就决定了在计算机中数据的存放顺序和位置。例如，在程序设计中需要存取某块内存的数据时，就可以直接使用变量（variable）名称num1与num2进行存取，如图2-4所示。

图2-4  变量在内存中的存取位置的示意图

使用数据结构，再通过程序设计语言所提供的数据类型、引用方法以及相应的操作就可以实现数据结构对应的算法。我们知道一个程序能否快速而有效地完成预定的任务取决于是否选对了数据结构，而程序是否能清楚而正确地把问题解决则取决于算法。因此，我们可以直接这么认为：“数据结构加上算法等于有效率的可执行程序”，如图2-5所示。

图2-5  数据结构加上算法等于可执行程序

程序设计人员必须选择各种数据结构来进行数据的添加、修改、删除、存储等操作。当数据存储在内存中时，根据数据的使用目的，对数据进行妥善的结构化，就可以提高使用效率，如果在选择数据结构时做了错误的决定，那么程序执行的速度将可能变得非常低，如果选错了数据类型，那么后果更是不堪设想。

以日常生活中的医院为例，医院会将事先设计好的个人病历表准备好，当有新的病人上门时，请他们填写好个人的基本信息，之后管理人员就可以按照某种次序（例如姓氏、年龄或电话号码）将病历表加以分类，然后用文件夹或档案柜加以收藏，如图2-6所示。

图2-6  病历表也是一种数据结构

日后当某位病人回诊时，只要询问病人的姓名或年龄，管理人员就可以快速地从文件夹或档案柜中找出病人的病历表，而这个档案柜中所存放的病历表也是一种数据结构的应用。

计算机化业务的增加带动了数字化数据的大量增长，如图2-7所示。数据结构用于表示数据在计算机内存中所存储的位置和方式，通常可以分为以下三种数据类型。

图2-7  计算机化业务的增加带动了数字化数据的大量增长

      基本数据类型（Primitive Data Type）

基本数据类型是不能以其他类型来定义的数据类型，或称为标量数据类型（Scalar Data Type）。几乎所有的程序设计语言都会为标量数据类型提供一组基本数据类型，例如Python语言中的基本数据类型包括整数、浮点数、布尔值和字符等。

      结构数据类型（Structured Data Type）

结构数据类型也被称为虚拟数据类型（Virtual Data Type），是一种比基本数据类型更高一级的数据类型，例如字符串（String）、数组（Array）、指针（Pointer）、列表（List）、文件（File）等。

      抽象数据类型（Abstract Data Type，ADT）

我们可以将一种数据类型看成是一种值的集合，以及在这些值上所进行的运算和所代表的属性组成的集合。“抽象数据类型”比结构数据类型更高级，是指一个数学模型以及定义在此数学模型上的一组数学运算或操作。也就是说，抽象数据类型在计算机中体现了一种“信息隐藏”（Information Hiding）的程序设计思想以及表示了信息之间的某种特定的关系模式。例如，堆栈（Stack）就是一种典型的抽象数据类型，具有后进先出（Last In First Out，LIFO）的数据操作方式。