1.2 数据结构

1.2.1 数据结构的核心地位

数据结构（data structure）在计算机学科中具有重要的地位，是操作系统、人工智能、计算机组成原理、程序设计、软件工程、数据库，以及编译原理等课程的重要基础。数据结构在计算机学科中的地位如图1.2所示。

图1.2 数据结构在计算机学科中的地位

1.2.2 数据结构的组成

计算机处理问题分为数值性问题和非数值性问题。随着计算机应用领域的扩大和软、硬件的发展，非数值性问题显得越来越重要。据统计，当今90%以上的计算机时间用来处理非数值性问题，这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决此类问题的关键不再是分析计算方法，而是要设计出合适的数据结构。

数据结构研究相关的各种信息如何表示、组织、存储与加工处理，研究数据的逻辑结构和数据的物理结构，以及它们之间的相互关系。数据结构通常由3个部分组成，即数据的逻辑结构、数据的物理结构和数据的运算结构。

（1）逻辑结构

数据的逻辑结构包括集合、线性结构、树形结构和图形结构，如下所述。

● 集合：数据结构中的元素之间除了“同属一个集合”的相互关系外，别无其他关系。

● 线性结构：数据结构中的元素存在一对一的相互关系。

● 树形结构：数据结构中的元素存在一对多的相互关系。

● 图形结构：数据结构中的元素存在多对多的相互关系。

（2）物理结构

数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。常用两种存储结构：顺序存储结构和链式存储结构。同一种逻辑结构可以有多种不同的物理存储方式。

● 顺序存储结构依据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

● 链式存储结构借助指示元素存储位置的指针来表示数据元素之间的逻辑关系。

（3）运算结构

数据的运算结构是指在数据逻辑结构上的操作算法，如检索、插入、删除、更新和排序等。