软件技术基础

第3章 CHAPTER 3 数 据 结 构 数据结构是研究非数值计算程序设计中计算机的操作对象以及它们之间关系和运算的科学。数据结构与数学、计算机硬件和计算机软件等有着密切的关系，数据结构与算法密不可分，是操作系统、编译原理、数据库、情报检索、人工智能等学科的重要基础。 3.1数据的逻辑结构与存储结构 3.1.1基本概念 数据是信息的载体，是描述客观事物的数、字符以及所有能被输入到计算机中并被计算机程序识别和处理的符号的集合，包括数值性数据和非数值性数据。 1. 数据元素、数据项和数据对象 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是在数据处理时不能再分割的*小单位。数据对象是性质相同的数据元素的集合。数据对象亦称数据元素类。数据元素是数据对象的一个实例。 例如，学生张强的学籍信息集合是数据元素，学生学籍信息表中的每一项，如学号、姓名、性别等各自为一个数据项。特征相同且具有共同数据项的众多学生数据可形成一个学生数据对象student。例如： student = { 张强，李兵，…… } 任何问题中，数据元素之间都不是孤立的，它们之间存在着某种关系，数据元素之间的关系称为结构。 2. 数据结构 数据结构是互相之间存在关系的数据元素的集合。数据结构将数据按某种逻辑关系组织起来，按一定的存储表示方式把它们存储在计算机存储器中，并在这些数据上定义一个运算的集合。数据结构与数据类型和数据对象不同，它不仅要描述数据类型的数据对象，还要描述数据对象各元素之间的相互关系。 数据结构通常包括逻辑结构和存储结构。逻辑结构用于描述数据之间的逻辑关系，存储结构描述数据如何在计算机内存储。 通常，用计算机解决一个具体问题时，可分为以下步骤。 (1) 从具体问题抽象出一个适当的数学模型。 (2) 设计一个解此数学模型的算法。 (3) 编出程序，进行测试、调试直至得到*终解答。 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。数值问题可以用诸如方程等描述。而非数值计算问题的数学模型则是用诸如表、树和图之类的数据结构描述。 3. 数据操作 数据操作亦称为数据运算。数据运算是数据结构的一个重要方面，对任何一种数据结构的研究都离不开对该结构上的数据运算及其实现算法的研究。*常用的数据操作有5种： 插入、删除、修改、查找、排序。例如针对线性表常见的基本操作如下。 (1) 线性表初始化。构造一个空的线性表。 (2) 求线性表的长度。返回线性表中所含元素的个数。 (3) 取表元。返回线性表L中的第i个元素的值或地址。 (4) 按值查找。在线性表L中查找值为x的数据元素，其结果返回在L中首次出现的值为x的元素的地址； 若未找到，返回一个特殊值表示查找失败。 (5) 插入操作。在线性表L的第i个位置插入一个值为x的新元素。 (6) 删除操作。删除线性表L中序号为i的数据元素。 基本运算并不是它的全部运算。数据结构的操作定义在逻辑结构层次上，而操作的具体实现建立在存储结构基础上。每个操作的算法只有在存储结构确立之后才能实现。 图31描述了数据结构的3个研究内容。 数据结构 逻辑结构线性结构线性表 线 队 非线性结构树 图 存储结构顺序存储 链式存储 数据运算： 检索、排序、插入、删除、修改等