数据结构基础教程.pptVIP

第一章绪论

计算机是一门研究利用计算机进行信息表示和处理的科学。

涉及：

•信息的表示

•信息的处理

而信息的表示和组织又直接关系到处理信息的程序的效率。随

着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统

程序和应用程序的规模很大，结构又相当复杂。因此，为了编写

出一个“好”的程序，必须分析待处理的对象的特征及各对象之

间存在的关系，这就是数据结构这门课所要研究的问题。

一般来说，计算机解决一个具体问题时，大致需要经过下列步骤：

一、建立数学模型:描述问题的共性（寻求数学模型的实质是分析问题，

从中提取操作对象，并找出这些操作对象之间含有的关系）；

二、构造求解方法:描述问题的求解方法；

三、选择存储结构:将问题涉及的数据存储到计算机中；

四、编写程序:提高编程的技术;

五、测试:数据测试;

在上述五阶段中，数据结构在第一阶段有助于更好地进行问题分析，在第

二阶段有助于进行更为复杂的算法设计，在第三阶段有助于选择合理的存储

结构，最终依据基于数据结构的设计，实现程序编写。

数据结构含义：

著名的瑞士计算机科学家尼古拉斯·沃斯（NiklausWirth）教授指出

，“算法+数据结构=程序”。算法是解决特定问题的步骤和方法，数据结

构是问题的数学模型，程序则是计算机处理问题编制的一组指令集。计算

机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结

构直接关系算法的选择和效率。运算是由计算机来完成的，这就要设计相

应的插入、删除和修改算法。也就是说，数据结构还需要给出每种结构类

型所定义的各种运算的算法。所以，数据结构是研究程序设计中计算机操

作的对象以及它们之间的关系和运算的一门学科。

以下是几种类型的数据结构实例。

下表一个学生选课系统中的课程信息表，其中，各个课程之间的关系

可以用线性的数据结构来描述。

下图是Unix文件系统目录结构和人机对弈问题，它表示的则是一种树形

的数据结构。

下图是一个由大量数据结点组成的连通网络拓扑图和城市煤气管道的铺

设示意图，它表示的是一种图状的数据结构。

数据结构相关概念

数据(Data):是对信息的一种符号表示。在计算机科学中是指所有

能输入到计算机中并被计算机程序处理的符号的总称。从计算机科

学的角度讲，数据的含义极为广泛，图像、声音等信息都可以通过

编码而归结到数据的范畴中。

数据元素(DataElement):是数据的基本单位,在计算机程序中通常

作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成

。如人机对弈格局的“树”的一个棋盘格局。

数据项是数据的不可分割的最小单位。数据元素具有广泛的含义

，一般来说，能独立、完整地描述问题的一切实体都是数据元素。

如在学生选课系统中，一个课程的信息作为一个数据元素，而课程

信息中的每一项（如课程号、课程名称、主讲教师等）都可以作为

一个数据项。

数据对象(DataObject)：是性质相同的数据元素的集合。是数据

的一个子集。在实际应用中处理的数据元素通常具有相同性质，例

如，学生选课系统中每个数据元素具有相同数目和类型的数据项，

所有数据元素（课程）的集合就构成了一个数据对象。

数据结构（DataStructure）是指相互之间存在一种或多种特定的关系

的数据元素的集合。从前面几个例子可以看出，数据元素都不是孤立存在的

，而是在它们之间存在着某种关系，这种数据元素之间的关系称为结构（

Structure）。根据数据元素之间关系的不同特性，通常有以下4类基本结构

：

（１）集合：数据元素之间就是“属于同一个集合”，除此之外没有任何

关系。

（２）线性结构：数据元素之间存在着一对一的线性关系。

（３）树形结构：数据元素之间存在着一对多的层次关系。

（４）图状结构或网状结构：数据元素之间存在着多对多的任意关系。

Data_StructureD,R

数据结构包括逻辑结构和物理结构两个层次。

逻辑结构（Logical

Structure）是指数据元素之间逻辑关系的整体。

所谓的逻辑关系是指数据元素之间的关联方式或邻接关系。数据的逻辑结构

可以看做是对操作对象的一种数学描述，换句话说，是从具体问题中抽象出

来的数学模型，它与数据自身的存储无关。研究数据结构是为了在计算机中

实现对它的操作，为此还需要研究如何在计算机中存储表示数据的逻辑结构

。

物理结构（Structure）

是