1.1　数据结构

数据结构是一门专门处理数据的学科，将数据元素相互之间的关联称为结构，描述的是存储和组织数据的方式。在本节中，将详细讲解数据结构的基本知识。

1.1.1　数据结构的核心技术

数据结构（Data Structure）是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

数据结构的核心技术是分解与抽象，通过分解可以划分出数据的3个层次，再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体（具体问题）到抽象（数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（数据结构）到具体（具体实现）的过程。

1.1.2　数据结构的起源和发展现状

“数据结构”起源于程序设计的发展。从20世纪60年代末到80年代初，人们逐渐认识到程序设计规范化的重要性。因而提出了程序结构模块化。与此同时，计算机也已经开始广泛地应用于非数值处理领域，操作系统、编译程序、数据库等系统软件的设计已进入方法化时期。人们注意到数据表示与操作的结构化，程序中常用的一些数据表示，如线性表、链表、广义表、栈、队、树、图等被单独抽出研究。在这种情况下，计算机类软件专业开始产生“数据结构”课程，对学生进行规范化程序设计起到了重大作用。

在国内外大学的计算机专业中，都把“数据结构”当成一门重要的专业基础课和必修课。在该课程的教学中，除了强调基本数据结构外，在学生先修了面向对象的程序设计基础上，还适当增加了一些数据结构和算法设计等新知识和新内容。同时，进一步精简存储管理、外部排序等属于“操作系统”和其他课程的内容。此外，在“数据结构”课程的教学、辅导、答疑、作业、讨论、测试、实验、实习等教学环节中，更多地利用网络教学资源和现代教育技术，从根本上提高了“数据结构”课程的教学质量。

1.1.3　数据结构中的基本概念

（1）数据

对客观事物的符号表示，是指所有能输入到计算机中并被计算机程序处理的符号的总称。

（2）数据元素

数据的基本单位，在计算机中作为一个整体进行考虑和处理。一个数据元素由多个数据项组成。例如，在保存学生信息的表中，每一条User记录就是一个数据元素。

（3）数据项

数据不可分割的最小单位，一个数据元素可由若干个数据项组成。

（4）数据类型

在计算机程序设计语言中，数据类型是变量所具有的数据种类，例如C、Java、Python等语言中的整型、浮点型、字符型等都是数据类型。通常将数据类型分为如下表2-1所示的四类。

（5）数据对象

性质相同的数据元素的集合，是数据的一个子集。这里要记住集合这个概念，所有的用户组合到一起是数据对象，所有的女性用户也是一组数据对象。

（6）逻辑结构

表示数据之间的相互关系，常见的逻辑结构类型如下表2-2所示。

注：数据的逻辑结构是基础，也是重点；这里先作简单了解，下一节我们会重点讲述。

（7）物理结构/存储结构

数据在计算机中的表示，是描述数据具体在内存中的存储方式，例如有顺序结构、链式结构、索引结构、哈希结构等。