数据结构的基本概念

常用术语

数据

数据（Data）是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。例如：整数、字符串、图形、图像、声音和动画等

数据元素

数据元素（Data Element）是数据的基本单位，有时也可被称为元素、记录等。

在计算机中通常作为一个整体进行考虑和处理，数据元素用于完整地描述一个对象，如学生信息表中的一名学生记录

数据项

数据项（Data Item）是组成数据元素的、有独立含义的、不可分割的最小单位。例如，课程表中的课程号、课程名等

数据对象

数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2,…}

数据结构

数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合，也可以说数据结构是带“结构”的数据元素的集合，“结构”是指数据元素之间存在的关系。

数据结构包括逻辑结构和存储结构两个层次。

逻辑结构

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

数据的逻辑结构有两个要素：

• 数据元素
• 关系：关系是指数据元素间的逻辑关系

根据数据元素之间关系的不同特性，通常有四类基本结构，如图所示，其复杂程度依次递进

• 集合结构：数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一个员工是否为销售部员工，只需将销售部看作一个集合结构

  

• 线性结构：线性结构作为最常用的数据结构，其特点是数据元素只按先后次序连接，数据元素之间存在一对一的关系。例如，将学生的基本信息数据按照学号的先后顺序进行排列，将组成一个线性结构，如线性表、栈、队列和字符串等

  

• 非线性结构：非线性结构，数学用语，其逻辑特征是一个数据元素可能有多个直接前驱和多个直接后续。其中对于这种数据结构中的任意一个数据元素；与它相邻且在它之前的数据元素称为该数据元素的直接前驱；对于该结构中任意一个数据元素，与它相邻且在它之后的数据元素称为该数据元素的直接后续。非线性结构可分为树结构和图结构

  • 树结构：树结构的数据元素是分层次的纵向连接，数据元素之间存在一对多的关系。例如，经理管理多个组长，每位组长管理多个员工，这就构成树结构

    

  • 图结构或网状结构：图结构或网状结构的数据元素的有各种各样的复杂连接，数据之间存在多对多的关系。例如，一门课程同时有若干个学生选修，一个学生可以同时选修多门课程，从而构成图结构或网状结构

    

存储结构

数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构.

数据元素在计算机中有两种基本的存储结构

• 顺序存储结构：顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述
• 链式存储结构：为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后续元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型

顺序存储结构要求所有的元素依次存放在一片连续的存储空间中。链式存储结构无须占用一整块存储空间