数据结构

第1章绪论 数据结构是计算机学科知识结构的核心和技术体系的基石，也是计算机及相关专业研究生考试和水平等级考试的必考科目。通过该课程的学习，培养数据抽象能力，在实际应用中有效合理地组织、存储和处理具有复杂关系的数据，正确、高效地设计并实现算法，具备分析和评价算法的能力。 1.1 为什么要学习数据结构 数据存储的主要目的是方便后期对数据的使用。比如我们使用数组存储某个学生的成绩 96， 82， 61， 54， 73}是为了后期对这些成绩再加工、分析和处理。无缘无故的数据存储行为是对存储空间的不负责任。 计算机在用于数值计算时，其解题过程通常是这样的：首先从实际问题或者具体情境中抽象出数学模型，然后设计求解该数学模型的算法，*后编写程序，进行调试、测试，直至解决问题。然而在现实社会中还存在着许多非数值计算问题，其数学模型难以用数学方程描述。我们先来看下面几个例子。 例 1-1员工信息管理系统。 人事部门使用计算机对公司的所有员工信息统一管理。员工的基本信息包括工号、姓名、性别、籍贯、部门、入职日期等，如表 1-1所示。每个员工的基本信息按照不同的顺序号，依次存放在“员工基本信息表”中，可根据需要对这张表进行查找。每个员工的基本信息记录按顺序号排列，形成了员工基本信息记录的线性序列，呈一种线性关系。 表 1-1 员工基本信息表 诸如此类的线性表结构还有学生学籍管理系统、图书馆书目管理系统等。在这类问题中，计算机处理的对象是各种表，表中元素之间存在简单的一对一的线性关系，因此这类问题的数学模型就是各种线性表，施加于对象上的操作有插入、删除、修改、查找和排序等。这类数学模型称为“线性”的数据结构。 例 1-2家谱管理系统。 假如要存储这样一组数据：“岑夫子”“岑守仁”“岑守义”“岑守礼”“岑守信”“岑克勤”“岑克俭”。数据之间具有这样的关系：岑夫子是岑守仁、岑守义、岑守礼和岑守信的父亲，岑守义又是岑克勤和岑克俭的父亲，数据之间的关系如图 1-1所示。 对于这类具有复杂关系的数据，用变量或数组来存储数据也是可以的，比如定义数组： char name[7][20] = {“岑夫子” ， “岑守仁” ， “岑守义” ， “岑守礼” ， “岑守信” ， “岑克勤”， “岑克俭” }; 但是这样做无法体现数据之间的逻辑关系，也会给后期的数据使用和维护带来极大的不便，甚至导致数据无法使用，显然这并不是一种有效合理的数据存储方式。此类数据对象的元素之间是一对多的层次关系，施加于对象上的操作有插入、删除、修改、查找和排序等。这类数据模型称为“树”的数据结构。 例 1-3自驾游路线规划。 A、B两个城市之间有多条线路，且每条线路耗时不同，那么，如何选择一条线路，使得从城市 A到城市 B的耗时*短呢？这类问题可抽象为图的*短路径问题。如图 1-2所示，图中顶点代表城市，边代表两个城市之间的通路，边上的权值代表从一个城市到另一个城市的耗时。求解 A到达 B的*短耗时，就是要在图中 A点到 B点的多条路径中，寻找一条各边权值之和*小的路径，即*短路径。很显然，图中的这些数据绝不能简单地使用变量或数组进行存储，那样对于数据的使用无疑是一个灾难。 图 1-1 数据及数据之间的关系 图1-2自驾游路线规划 诸如此类的图结构还有通信线路图、网络拓扑图和施工进度计划图等。此类问题的元素之间是多对多的网状关系，施加于对象上的操作同样有插入、删除、修改、查找和排序等。这类数学模型称为“图”的数据结构。 从以上例子我们可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图的数据结构。因此，简单地说，“数据结构”是一门研究非数值计算的程序设计问题中计算机的操作对象以及这些对象之间的关系和操作的学科。 因此，数据在计算机存储空间中的存放，不应该是随意的、杂乱无序的，需要我们选择一种合适的方式来存储数据，才能对它们进行有效的处理，设计出高效的算法。如何合理地组织数据、高效地处理数据，这正是数据结构的核心研究内容。 1.2 基本概念和术语 接下来，我们先介绍数据结构中常用的一些概念和术语。 数据(Data)：指所有能输入计算机中的描述客观事物的符号。数据是计算机存储、加工和处理的对象，它不仅仅包括整型、实型等数值类型，还包括文本、声音、图形、图像、视频等非数值类型。 数据元素(Data Element)：数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在某些情况下，数据元素也称为元素、记录、结点、顶点。例如，表 1-1中，每一行即每个员工的基本信息都是一个数据元素，也称为一条记录。有时，数据元素可以由若干个数据项(Data Item)组成。数据项是数据的有独立含义的*小标识单位，也称为字段、域、属性。例如，表 1-1中，每一列如“工号”“姓名”“性别”“籍贯”“部门”“入职日期”等均为数据项。 数据对象(Data Object)：性质相同的数据元素的集合，是数据的一个子集。例如，表 1-1中，所有员工记录的集合就是数据对象。 数据结构(Data Structure)：相互之间存在一种或多种特定关系的数据元素的集合。不同数据元素之间不是孤立的，而是存在特定的关系，这些关系称为“结构”。因此，数据结构是带“结构”的数据元素的集合。数据结构包含逻辑结构、存储结构和运算三个要素。其中，运算即对数据施加的操作。 1.2.1 逻辑结构 逻辑结构是指数据对象中数据元素之间的相互关系。它与数据的存储无关，独立于计算机，是从具体问题中抽象出来的数学模型。逻辑结构分为以下四种。 1．集合结构 集合结构：数据元素间除了同属于一个集合外，没有其他关系。集合中的元素是离散的、无序的，它们之间没有什么关系。而数据结构重点研究的是数据之间的关系，因此，集合虽然是一种数据结构，但在该课程中却不予讲述。 2．线性结构 线性结构：数据元素之间是一对一的关系，如线性表(典型的线性结构)、栈和队列(操作受限的线性表)、数组(线性表的推广，它的数据元素是一个线性表)、串、广义表(线性表的推广，它的数据元素是一个线性表，但不同构，或是单元素，或是线性表)。非空的线性结构有唯一的开始结点和唯一的终端结点，除了**个元素外，每个元素都有唯一的直接前驱；除了*后一个元素外，每个元素都有唯一的直接后继。 3．树形结构 树形结构：数据元素之间存在一对多的层次关系，好像一棵倒立的树。 4．图状结构 图状结构：数据元素之间存在多对多的关系。 其中，集合结构、树形结构(树和二叉树)和图状结构(有向图和无向图)都属于非线性结构。 从以上例子可以看出，逻辑结构是针对具体问题的，为了解决某个问题，在对问题理解的基础上，选择一个合适的数据结构(线性表、树或图)来表示数据元素之间的逻辑关系。可以说，算法的设计取决于数据的逻辑结构。 1.2.2 存储结构 存储结构又称为物理结构，是指数据元素及其关系在计算机中的存储表示。除了存储各数据元素的数据，数据的存储结构还应该正确反映数据元素之间的逻辑关系。如何存储数据之间的逻辑关系，是实现物理结构的重点和难点。 数据元素在计算机中有四种存储结构：顺序存储、链式存储、散列存储和索引存储。 1．顺序存储 顺序存储是指逻辑上相邻的元素在计算机内的存储位置也是相邻的。数据元素存放在地址连续的存储空间中，元素间的逻辑关系是由元素在存储空间中的相对位置来表示的。通常借助于程序设计语言的数组类型来描述。 2．链式存储 链式存储是把数据元素存放在任意的存储单元里，这些存储单元可以是连续的，也可以是不连续的。数据元素在存储空间内的相对位置并不能反映其逻辑关系，因此需要给每个元素附加指针域，用于存放相关联数据元素的地址。通常借助于程序设计语言中的指针类型来描述。 3．散列存储 散列存储又称为哈希( Hash)存储，是把数据元素存放在一块连续的存储空间中，由元素的关键字( Key)值来决定该元素的存储地址。用散列函数确定数据元素的存储地址与关键字值之间的对应关系。 4．索引存储 索引存储是指除存储元素信息外，还建立附加的索引表来标识元素的存储地址。索引表由若干索引项组成。若每个元素在索引表中都有一个索引项用于指示该元素所在的存储位置，则该索引表称为稠密索引。若一组元素在索引表中只对应一个索引项，该索引项指示这一组元素的起始存储位置，则该索引表称为稀疏索引。索引项的一般形式是关键字、地址，如图 1-3所示。 其中，关键字是数据元素中某个数据项(字段)的值，又称为键值，用它可以标识一个数据元素或该数据项，该数据项称为关键码。若此关键字可以唯一地标识一个数据元素，则称此关键字为主关键字( Primary Key)。这也就意味着，对于不同的数据元素，其主关键字必然不同。主关键字所在的数据项称为主关键码。而对于可以识别多个数据元素的关键字，我们称为次关键字( Secondary Key)，它不能唯一标识一个数据元素，它对应的数据项就是次关键码。例如，表 1-1中，“工号”就是主关键码，“ 20080801”是主关键字，它可以唯一标识一条记录。“性别”就是次关键码，“性别”为“女”(次关键字)的记录在表中有两条。换句话说，“字”是数据项的值，而“码”是数据项(或称为字段)，是值的“统一名称”。 在实际应用中，往往需要根据具体的数据结构来决定采用哪种存储方式。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空复杂度要求。也就是说，算法的实现依赖于采用的存储结构。 1.2.3 数据类型和抽象数据类型 1．数据类型 数据类型(Data Type)是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。例如，C语言中的整型和实型。 数据类型可分为两类：原子类型和结构类型。原子类型是不可再分解的基本类型，如整型、实型、字符型等；结构类型是由若干个类型组合而成的，是可以再分解的，如整型数组是由若干个整型数据组成的。 2．抽象数据类型 抽象是指抽取出事物所具有的普遍性的本质，是计算机求解问题的基本方式和重要手段，它使得一种设计可以应用于多种场景。通过抽象可以屏蔽底层的实现细节，使设计更加简单、理解更加方便。 抽象数据类型( Abstract Data Type，ADT)一般指用户定义的、表示应用问题的数学模型，以及定义在该模型上的一组操作的总称。可以理解为将数据对象、数据对象之间的关系和对数据对象的基本操作封装在一起的一种表达方式。 抽象数据类型的定义格式如下： ADT抽象数据类型名 { 数据对象 D(Data Object)：数据对象的说明 数据关系 S(Structure)：数据元素之间逻辑关系的描述 基本操作 P(Perform)：基本操作的定义 基本操作 1： 初始条件描述 操作结果描述 基本操作 2： 基本操作 n： } “抽象”描述数据类型的方法是不依赖于具体实现的，即数据对象、基本操作的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。简而言之，抽象数据类型独立于具体实现，它只是描述数据对象和基本操作“做什么”，并不涉及