数据结构(第二版)

第1章绪论 本章主要介绍数据结构的研究对象、概念术语、算法描述与评价等基础知识。 1.1数据结构的研究对象 过去，计算机解决的问题主要是以数值计算问题为主。但随着计算机技术的发展，现在计算机所处理的问题大多是如字符、字符串、文本、表格、声音、图形、图像、视频等非数值计算问题为主。为了提高数据处理在查找、插入或删除等操作上的效率，为了提高计算机对现有非数值计算问题的处理能力，需要对其中所出现的数据加以认真分析，提取数据的组织结构，选择合理相应的存储结构，设计相应的算法并加以实现，以求解现实问题。 数据是计算机加工处理的对象。数据的外在表现形式称为数据的逻辑表示，又称为机外表示。数据在计算机存储器中的表示则称为机内表示。数据要能被计算机加工处理，首先必须要能够存储在计算机中，然后才能被计算机程序处理。 数据结构于1968年成为计算机专业一门独立的专业基础课程，主要探讨数据及数据之间的关系、数据上的操作以及数据和数据结构的物理存储表示和操作算法。也就是说，数据结构探讨的是数据的逻辑表示和存储表示，以及相关操作算法的设计和实现。学习数据结构的目的是提高计算机程序处理的效率。 为了说明数据结构研究的数据对象是什么，先看几个例子。 例1-1　学生成绩管理　一个学生成绩信息由学号、姓名、性别、出生曰期和总分等数据组成。通常以表格的形式呈现，如表1-1。每一个学生成绩信息构成一条记录，在表中占一行。若要查看某学生的姓名，需要先给出具有唯一性的学号，然后找到相应的记录，*后才能看到该学号学生相应的姓名。 像这样一类的问题很多，如图书管理、饭卡管理、银行账户管理，等等，这类问题的数学模型都是表格数据的管理，对表格数据进行查、删、改等操作。 在这样的问题中，每个基本单位的数据都是一条一条的记录，数据之间的关系呈现为自然的顺序关系。这种数据对象都称为线性表。 例1-2　人机对弈　在3x3=9的方格棋盘中，甲乙双方轮流落子，当某一方三个棋子同时占有一行、一列或一对角线时为臝，称为二人井字棋对弈。每方在落子时都面对当前的一种棋盘格局，可选不同的落子方案。一旦选定某个落子方案后，对方就面对一个新的格局。每方在对方落子后，相当于在当前格局下选择对己方*有利的格局演化落子。格局之间的演化的关联结构是非线性的：由一个格局可以派生出几个格局，即一方落一个棋子后，对方可选不同的落子方案，不同的走法又形成不同的格局，见图1-1（a），其中，X表示黑方，0表示白方，黑方先行。人机对弈就是让计算机模仿某一方下棋，向获胜方向生成格局。计算机实际生成了一棵对弈解树。格局就是数据元素，数据元素间关系形成一种树形结构。 此外，行政上高校管理机构的设置（见图1-1（b）），数学上算术表达式W*S+（C-D）的图形表示（见图1-1（c）），都是树形结构。 例1-3　教学安排　在学习多门课程时，由于课程之间有一定的先后修次序，所以， 在学习后续课程时，要保证其先导课程已修过，这样，学习起来就比较不费力。表1-2给出了部分课程之间的先后修次序关系。课程之间先后修次序关系可用图1-2中的有向图表示。在学习时，若从课程C，到课程C]之间存在一条有向路径，则C，必须在C]之前先学习。这种问题的解决，对应于为有向图（应该无回路存在）的顶点（表示课程）安排一个符合要求的拓扑序列。 由上述三个例子可见，数据结构的研究对象大多是线性表、树和图等带有一定结构关系的数据模型。 1.2　概念术语 数据结构中涉及的主要概念术语解释如下。 （1）数据（data）　能被计算机接收并处理的对象集合称为数据。因为能被计算机接收并处理的一个对象集合既可以含有一个元素，也可以含有多个元素，所以，数据的概念既可指一个具体的对象，也可指由多个对象组成的对象集合，甚至是所有对象所构成的集合。如一个整数、一个字符、一个字符串、一段声音、一幅图像等都分别是数据；而一个整数集、一个字符集、一个字符串集、多段声音集、多幅图像集甚至视频或者它们全部放在一起组成的集合都是数据。也就是说，数据是个单复数同形的词。一般我们假定数据是由多个对象组成的集合：集口。 （2）信息（information）　具有一定含义或内涵的数据称为信息。数据是信息的载体，信息是数据的表现形式。如图表或图形，它们都是数据加工后的结果，具有一定的含义，通常称之为信息。 （3）数据元素（dataelement）数据中的每个个体或对象称为数据元素。数据元素是数据的基本单位。数据元素既可以是原子数据元素，也可以是结构化数据元素。原子数据元素指该数据元素不可再分，而结构化数据元素则可认为其还能分为若干个组成部分。 （4）数据项（dataitem）　结构化数据元素中所含的有一定意义的成分称为数据项。如学生成绩登记表中，每条记录可看成一个数据元素。一个学生的记录含学号、姓名、各科成绩等成分，这些成分都称为数据项。结构化数据元素由若干个数据项组成。数据项是数据的*小单位。数据项不可再分。能唯一标识数据元素的数据项称为关键字。 （5）数据对象（dataobject）　具体分析研究某个数据结构时所涉及的具有相同性质的数据元素的集合称为数据对象。它是数据的子集。数据对象中的数据元素一般具有相同的类型。例如，一定范围内的整数集合可构成一个数据对象，英文字母的集合也可构成一个数据对象，学生成绩登记表中记录的集合也是一个数据对象。数据对象也简称为数据。 （6）数据结构（datastructure）　由数据对象、数据的逻辑结构、数据的存储结构和操作构成的整体称为数据结构。主要从数据的逻辑结构和数据的存储结构（有时也称为物理结构）两方面来定义数据结构。但人们更多地只从数据的逻辑结构来给出数据结构的定义描述。因而，逻辑上。就把相互之间具有一定联系的数据元素的集合称为数据结构。此时，数据结构就是指数据及其逻辑结构。 ①数据的逻辑结构　指数据结构所用的数据对象中数据元素之间的逻辑关系的整体。逻辑关系通常指数据元素之间的某种邻接关系。数据元素之间可能存在多个逻辑上的联系或关系，例如，在一群人中，可能存在“同学”“朋友”“同事”“同龄”等关系。每一个这种关系都可理解为是某种邻接关系。在研究某个数据结构时，通常只研究某一个具体逻辑关系，暂时不考虑其他逻辑关系。如在研究一群人的逻辑关系时，只考虑“朋友”关系。这样可突出某个重点逻辑关系，忽略次要关系，降低问题的复杂程度。 数据结构逻辑上描述为一个二元组的形式： Data_Structure=（D，R）（1-1） 其中，D表示数据对象，是数据的子集；R表示D上逻辑关系的集合（可能是多个关系），R中的每一元素都表示数据对象D中数据元素之间的一种逻辑关系。一种逻辑关系一般指数据元素逻辑上所遵循的一种“邻接”关系。 ②数据的存储结构　又称数据的物理结构，指数据对象D中数据元素及选定的一个逻辑关系在计算机内存中的映象。数据结构在计算机中的映象包含数据元素的映象和该选定逻辑关系的映象。数据元素的映象称为结点或元素。结构化数据元素中的数据项的映象称为数据域、字段或数据成员。而逻辑关系的映象则取决于所采用的存储方式。 （7）数据结构的映象　数据元素之间的逻辑关系在内存储中的表示称为数据结构的映象。数据结构的映象（mapping）主要有2种：顺序映象和非顺序映象。 ①顺序映象（sequential　mapping）　指把逻辑上相邻元素在物理上也相邻存储。 ②非顺序映象（non-sequential　mapping）　指把逻辑上相邻元素在物理上不一定相邻存储。有时也可相邻存储。 两种映象对应两种存储结构：顺序存储结构和非顺序存储结构。 （8）数据结构的逻辑结构分类　数据结构按所考虑的数据之间的一种主要逻辑关系可将其划分为4类：集合、线性表、树、图。如图1-3所示。 ①集合　集合是数据元素间没有任何联系的一种数据结构。集合大多都被看成线性结构的一个特例。也可看成树或图结构中任意一种的特例。 ②线性表　在线性表中，每个数据元素至多只有一个直接前驱数据元素和一个直接后继数据元素。一般认为集合、栈、队列和字符串都是特殊线性表。 ③树　在树结构中，根结点无直接前驱数据元素，其他的每个数据元素至多只有一个直接前驱数据元素，但可能有多个直接后继数据元素。树结构是一种层次结构。 ④图　在图结构中，每个结点可能有多个直接前驱数据元素和多个直接后继数据元素。树也可看成是图的特例。 这4种数据结构又可被分成2大类：线性结构和非线性结构。 ①线　性结构在线性结构中，若数据集非空，则数据集中的数据元素可按某种方式一个接一个地排列成唯一的一种有次序的序列。线性表属于线性结构。 ②非线性结构　在非线性结构中，每个数据元素若有的话，可有一个或多个直接前驱数据元素以及一个或多个直接后继数据元素。树、图属于非线性数据结构。 （9）数据结构的存储结构分类　数据结构按存储结构可分为4类：顺序、链式、散列和索引存储结构。 ①顺序存储结构（sequential　storage　structure）　在顺序存储结构中，逻辑上相邻的数据元素存储在物理上相邻的存储单元里，即用物理存储单元的相邻关系直接体现数据元素之间的逻辑上的邻接关系。在使用时，借助于程序设计语言中的数组（如C++语言中的简单数组、结构数组等）来实现。 ②链式存储结构（linked　storagestructure）　在链式存储结构中，逻辑上相邻的数据元素存储在物理上不一定相邻的存储单元里，数据元素之间逻辑上的相邻关系是通过存储单元中附设的指针进行表示的。使用时，借助于程序设计语言中的结构指针来表示。当然，有时也会物理相邻存储。 ③散列存储结构（hash　storage　structure）　又称哈希存储结构或杂凑存储结构。该结构事先借助程序设计语言开辟一块逻辑上相邻的地址范围连续的存储空间，再建立一个数据元素的关键码到地址的映象函数，称为散列函数或哈希函数。数据元素的存储地址直接由数据元素的关键码计算得到。它在存储数据元素时不考虑数据元素之间逻辑上的相邻关系。逻辑上相邻的数据元素存储在物理上不一定相邻的存储单元里（有时也可相邻）。 ④索引存储结构（indexed　storage　structure）　在索引存储结构中，它在以主表存储数据元素的同时，还建立主表的附加索引表。数据元素存储的主表称为基本表。基本表中的元素通常“分块有序”，即块内元素按关键字不一定有序（既可有序，也可无序），但块间有序（前一块的*大关键字都小于后一块的*小关键字）。 索引表中每一索引项由基本表所得到的分块中的信息构成，存放的是块内*大关键字和块的起始地址，图1-4给出了一个索引存储结构示意图，其中，基本表分成3块，第0块由下标0、1、2三个元素（记录）构成，第1块由下标3、4、5三个元素（记录）构成，第2块由下标6、7两个元素（记录）构成。块的大小，即所含元素的个数，又称为块的长度，简称为块长。前面两块的块长相同，但*后一块的块长不一定与前面的相同。对于块不等长的情况，索引表的每个索引项在保留块内*大关键字下，相应地要存储块的起始地址和块的终止地址，或者改为块的起始地址和块长。 在这4类存储结构中，顺序存储结构和链式存储结构相对常用，数据结构大多要考虑用这两种存储结构加以存储表示和实现。而散列存储结构和索引存储结构则在较为高级的数据结构应用场合下使用。 这4类存储结构可分为2大类：顺序存储结构和非顺序存储结构。这里所指的顺序主要强调的是，数据之间的逻辑相邻关系在存储位置上是否物理相邻（每个数据元素的存储映象看成