第十二章计算机文化基础 数据结构.pdf

第十二章 数据结构 主要内容： 12.1数据结构的主要研究内容 12.2数据结构基本概念 12.3 数据的逻辑结构 12.4 线性表及其顺序存储结构 12.5栈和队列 12.6 树与二叉树 12.7 查找技术 12.8 排序技术 12.1数据结构的主要研究内容 ■ 12.1数据结构的主要研究内容 数据结构是相互之间存在一种或多种特定关系的数据元素 的集合。数据结构作为计算机的一门学科，主要研究和讨 论以下三个方面的问题： 1．数据集合中各数据元素之间所固有的逻辑关系，即数 据的逻辑结构。 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储 无关，是独立于计算机的。数据的逻辑结构可以看作是从 具体问题抽象出来的数学模型。数据的逻辑结构包含： （1）表示数据元素的信息； （2 ）表示各数据元素之间的前后件关系。 2 ．各数据元素在计算机中存储关系，即数据的存储结 构。 数据的存储结构有顺序、链接、索引等。数据的存储结 构是逻辑结构用计算机语言的实现（亦称为映象）， 它依赖于计算机语言。对机器语言而言，存储结构是 具体的。一般只在高级语言的层次上讨论存储结构。 对各种数据结构进行的运算。 3. 数据的运算定义在数据的逻辑结构上，每种逻辑结构 都有一个运算的集合。最常用的检索、插入、删除、 更新、排序等运算实际上只是在抽象的数据上所施加 的一系列抽象的操作。所谓抽象的操作，是指只知道 这些操作是“做什么”，而无须考虑“如何做”。只有确 定了存储结构之后，才考虑如何具体实现这些运算。 12.2数据结构基本概念 ■ 12.2.1数据 数据是指所有能输入到计算机中并被计算机程序 处理的符号的总称。数据是信息的载体，它能够被 计算机识别、存储和加工处理，是计算机程序加工 的“原料” 。随着计算机应用领域的扩大，数据可以 分为两大类：一类是整数、实数等数值数据；另一 类是图形、图像、声音、文字等非数值数据。这里 要注意数据并不等于数字，数字是隶属于数据的。 ■ 12.2.2数据元素与数据项 数据元素也称为元素、结点、顶点或记录，是数据 的基本单位，在计算机程序中通常作为一个整体进行考 虑和处理。一个数据元素可由若干个数据项组成，数据 项是数据的最小单位。数据元素具有广泛的含义，一般 来说，现实世界中客观存在的一切个体都可以是数据元 素。例如在表12-1中，整个表记录的是学生成绩数据， 每个学生的记录行是其中一个数据元素，即该表由4个 数据元素构成，而某一个数据元素（记录行）又是由5 个数据项组成。例如语文成绩67则是表中第一个数据元 素（记录行）中的数据项。数据项是不可再分的数据内 容。 学号 姓名 语文 数学 英语 李丽 67 87 83 张鹏 92 82 64 刘海 78 72 76 金玉 56 68 71 数据对象是性质相同的数据元素的集合。如上例中 一个班级的成绩表可以看作一个数据对象。一般来 说，人们不会同时处理特征完全不同且互相之间没 有任何关系的各类数据元素，对于具有不同特征的 数据元素总是分别进行处理。 ■ 12.2.3数据结构 数据元素都不是孤立存在的，而是在它们之间存在着某种特 定的关系，这种数据元素相互之间的关系称为结构。在数据 处理领域中，通常把数据元素之间这种固有的关系简单地用 前后件关系(或直接前驱与直接后继关系)来描述。 例如，在考虑一年四个季节的顺序关系时，则“春”是“夏”的 前件（即直接前驱），而“夏”是“春”的后件（即直接后 继）。同样，“夏”是“秋”的前件，“秋”是“夏”的后件；“秋” 是“冬”的前件，“冬”是“秋”的