武汉软件工程职业学院《数据结构讲义》第01讲数据结构的基本概念和术语

1、a-/t 弟一讲数据结构的基本概念和术语1. 掌握算法设计与分析的基本知识和基本概念，2. 从总体上了解基本数据结构及其应用，各种数据结构的优，以及如何选择常用的数据结 构，如何应用抽象数据结构类型进行数据抽象，高级语言对数据结构及抽象数据类型的支 持。从总体上了解基本数据结构及其应川，各种数据结构的优，以及如何选择常川的数 据结构，如何应用抽象数据结构类型述行数据抽象，高级语占对数据结构及抽象数据类型 的支持。教学重点：数据结构与算法的基本概念的理解。 教学难点：抽彖数据类型及其操作。授课内容计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，它是计算机町以直接处 理的最基本

2、和最重耍的对象。无论是进行科学计算或数据处理、过程控制以及对文件的存储和检索及数据 库技术等计算机应用领域中，都是对数据进行加工处理的过程。因此，要设计出一个结构好效率高的程序, 必须研究数据的特性及数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法 和程序。1. 1数据结构的基本概念和术语数据结构是计算机科学与技术专业的专业基础课，是十分垂要的核心课程。所冇的计算机系统软件和 应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握儿种计算 机程序设计语言是难以应付众多复杂的课题的。要想冇效地使用计算机、充分发挥计算机的性能，还必须 学习和拿

3、握好数据结构的有关知识。打好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他 课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。1.1.1引言在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们使用计算机來解决一 个貝-体问题时，一般需耍经过下列几个步骤：首先耍从该具体问题抽象出一个适当的数学模型，然后设计 或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。例如，求解梁架 结构中应力的数学模型的线性方程组，该方程组可以使用迭代算法来求解。rh于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者

4、的主要精力是集中 于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越來越显得重耍。据统计，当今处理非数值计算性问题占用了 90%以上的机器时间。这类问题涉 及至i的数据结构更为复杂，数据元素之间的相互关系-般无法用数学方程式加以描述。因此，解决这类问 题的关键不再是数学分析和让算方法，而是要设计出合适的数据结构，才能有效地解决问题。下面所列举 的就是属于这一类的具体问题。- 【例1】学生信息检索系统。当我们需要查找某个学生的有关悄况的时候；或者想查询某个专业或年级的学生的有关悄况的时候， 只要我们建立了相关的数据结构，按照某种算法编写了相关程序，

5、就可以实现计算机自动检索。由此, 可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的 索引表，如图l.i所示。由这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按 照某个特定要求(如给定姓名)对学生信息文件进行査询。诸如此类的还有电话自动查号系统、考试杏分系统、仓库库存管理系统等。在这类文档管理的数学模 型中，计算机处理的对象z问通常存在着的是一种简单的线性关系，这类数学模型可称为线性的数据结构。崔文靖8何文颖6李淑芳2刘丽3, 9石宝国5魏永鸣10吴承志1赵胜利7少4匕ja(b)姓名索引表计算机科学与技术1, 5, 6, 9信息与计

6、算科学2, 4, 8数学与应用粕学7. 10(c)专业索引表2000 级6, 7, 82001 级9, 1098级1, 2, 3(d)年级索引表学号姓名性别专业年级980001吴承志男计算机科学与技术98级980002李淑芳女信息与计算科学98级990301刘丽女数学为应用数学99级990302张会友男信息与计算科学99级990303石宝国男计算机科学与技术99级000801何文颖女计算机科学与技术2000 级000802赵胜利男数学打应用数学2000 级000803崔文靖男信息与计算科学2000 级010601划丽计算机科学与拈术2001 级(a)学生信息农图1学生信息查询系统中的数据结构-

7、 【例2计算机和人对奕问题在对奕问题中，计算机操作的对象是对奕过程中可能岀现的棋盘状态称为格局。例如下图1.2所 示为井字棋的一个格局，而格局之间的关系是由比赛规则决定的。通常，这个关系不是线性的，因为从一 个棋盘格局可以派牛出几个格局，例如从1.2所示的格局可以派生出五个格局，如下图所示，而从每一 个新的格局乂可派生出四个可能出现的格局。si-cuni*2iex01ml图1.2因此，若将从对奕开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一棵倒长的 “树”。“树根”是对奕开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对奕的过程就是从树根 沿树叉到某个叶子的过程。“树”

8、可以是某些非数值计算问题的数学模型，它也是一种数据结构。id聪i 【例3】多叉路口交通灯的管理问题通常，在十字交叉路口只需设红、绿两色的交通灯便可保持止常的交通 秩序，而在多交义路口需设儿种颜色的交通灯才能使车辆相互之间不碰撞, 乂能达到车辆的最大流通。假设有一个如图1. 3所示的五叉路口，其中c和e为单行道。在路 口有13条可行的通路，其中有的可以同时通行，如ab和ec,而有的 不能同时通行，女heb和ad。那末，在路口应如何设置交通灯进行车 辆的管理呢？通常，这类交通、道路问题的数学模型是一种称谓“图”的数据结构。例 如在此例题中，可以用图中一个顶点表示一条通路，而通路z间互相矛盾的 关系

9、以两个顶点z间的连线表示。设置交通灯的问题等价为对图的顶点的染色问题，耍求对图上的每个顶 点染-种颜色，并且要求有线相连的两个顶点不能具有相同颜色，i佃总的颜色种类应尽对能地少。综上三个例子可见，描述这类非数值问题的数学模型不再是数学方程，而是诸如表、树和图z类的数 据结构。因此简单说来，数据结构是一门研究非数值计算的程序设计问题屮计算机的操作对象以及它们z 间的关系和操作等等的学科。学习数据结构的冃的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中 表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练 来促进学生的综合应用能力和专

10、业素质的提高。1.1.2有关概念和术语在系统地学习数据结构知识之前，先对一些基本概念和术语赋予确切的含义。数据(data)是信息的载体,它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料， 应用程序处理各种各样的数据。计算机科学中，所谓数据就是计算机加工处理的対象，它可以是数值数据, 也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等； 非数值数据包括字符、文字、图形、图像、语音、光和电等。数据元素(data element)是数据的基本单位。在计算机程序中作为一个整休竞相考虑和处理。在不 同的条件下，数据元素乂可称为元素、结点、顶点、记录等。

11、例如，学生信息检索系统中学生信息表中的 一个记录、人机对弈问题中状态树的一个状态、交通问题中的一个顶点等，都被称为一个数据元素。有时，一个数据元素可山若干个数据项(datalem)组成，例如，学籍管理系统中学生信息农的每一 个数据元素就兄二个季生记录。它包括学生的学号、姓名、性别、籍贯、出生年月、成绩等数据项。这些 数据项可以分为两种：一种叫做初等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再分割 的最小单位；另一种叫做组合项，如学生的成绩，它可以再划分为数学、物理、化学等更小的项。通常， 在解决实际应用问题时是把每个学牛记录当作一个基本单位进行访问和处理的。如下图学牛成绩表中所 示

12、：r 学号姓名,数学jc语言62®1uq1一怅一185>5492z>6201002李四址646201003王五8774 -一个数据元素6201004一个数据项数据对象(data object)或数据元素类(data eiement class)是具有相同性质的数据元素的集合。 在某个具体问题中，数据元素都具有相同的性质(元素值不一定相等)，属于同一数据对象(数据元素类), 数据元素是数据元素类的一个实例。例如，在交通咨询系统的交通网中，所有的顶点是一个数据元素类， 顶点a和顶点b各h代表一个城市，是该数据元素类屮的两个实例，其数据元素的值分别为a和b。据结构(data s

13、tructure)是指互木iiz间存在着一种或多种关系的数据元素的集合。在任何问题中,数据元索之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结 构。根据数据元索间关系的不同特性，通帘有下列四类基木的结构:集介结构。在集介结构中，数据元素间的关系是“属于同一个集介”。集合是元索关系极为松散的 一 种结构。线性结构。该结构的数据元素z间存在着一对一的关系。树型结构。该结构的数据元素之间存在着一对多的关系。图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。图1.4为表示上述四类基本结构的示意图。(a)集合结构(c)树型结构(d)图形结构图1

14、4四类基木结构的示意图由于集合是数据元素之间关系极为松散的一种结构，因此也可用其他结构來表示它。从上而所介绍的数据结构的概念中可以知道，一个数据结构有两个要素。二个是数据元素的集合，另一个 是关系的集合。数据结构包括数据的逻辑结构和数据的物理结构。数据的逻辑结构可以看作是从具体问题抽象出來的 数学模型，它与数据的存储无关。我们研究数据结构的目的是为了在计算机中实现对它的操作，为此还需 要研究如何在计算机中表示一个数据结构。数据结构在计算机中的标识（又称映像）称为数据的物理结构, 或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系 的表示。数据的存储结构

15、可采用顺序存储或链式存储的方法。顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元屮，由此得到的存储表示称为顺 序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段來 表示，由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言屮的指针类型来实 现。除了通常采用的顺序存储方法和链式存储方法外，有时为了查找的方便还采用索引存储方法和散列存 储方法。数据类型是利数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画（程序）操作对象的特性。在

16、用高级程序语言编写的程序屮，每个变量、常量或表达式都有一个它所属的 确定的数据类型。类型明显或隐含地规定了在程序执行期间变量或表达式所冇可能取值的范围，以及在这 些值上允许进行的操作。因此数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例如,c语言中的整型变量，其值集为某个区间上的整数（区间大小依赖于不同的机器），定义在其上的操 作为：力口、减、乘、除和取模等算术运算。数据类型的种类：特征例原子类型值在逻辑上不可分解int float结构类型值由若干成分按某种结构组成struct stu数据类型封装了数据存储9操作的具体细肖。抽象数据类型(abstract data type简称ad

17、t)是指一个数学模塑以及定义在该模塑上的一组操作,iftf向逻辑层次。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关, 即不论其内部结构如何变化，只要它的数学特性不变，祁不影响其外部的使用。抽象数据类型和数据类型 实质上是一个概念。例如，各个计算机都拥有的“整数”类型是一个抽彖数据类型，尽管它们在不同处理器上实现的方法可以 不同，但由于其定义的数学特性相同，在用八看來都是相同的。因此，“抽象”的意义在于数据类型的数学 抽象特性。另一方面，抽象数据类型的范畴更广，它不再局限于前述各处理器中已定义并实现的数据类型（也可称 这类数据类型为固冇数据类型），还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的复用 率，在近代程序设计方法学中指出，一个软件系统的框架应建立在数据z上，而不是建立在操作z上（后者 是传统的软件设计方法所为）。即在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据 上的一纟fl操作，并在模块内部给出这些数据的表示及其操作的细节，而在模块外部使用的只是抽象的数据 和抽彖的操作。显然，所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复用程度也就越高。如前所述，抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。和数据结构的形式定 义相对应，抽象数据类型可用以下