参考资料：

MyCodeSchool. (2013, March 26). Introduction to data structures [Video]. YouTube. https://youtu.be/92S4zgXN17o
程杰. (2011). 大话数据结构. 清华大学出版社.

数据结构的起源

数据结构本质上是人类处理海量信息时，摸索出的组织数据的智慧。

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

它经历了四个关键的阶段：

前计算机时期（20 世纪初期）：
最早的数据组织源自于图书馆分类法、人口普查表等现实需求；
计算机诞生初期（40 – 50 年代）：
早期计算机主要做数值计算，程序的数据往往就是若干数字。冯·诺依曼体系带来了“通过偏移量访问连续数据”的概念，即内存本身就是一串连续编号的存储单元，那么把同类型数据连续存储起来是一件非常自然的事，于是数组就作为最早的数据组织方式出现了；
数据结构真正成为科学的时期（60 年代）：
1968 年，美国科学家高德纳（Donald E. Knuth）教授在《计算机程序设计艺术》第一卷《基本算法》中，较为系统地阐述了数据的逻辑结构和存储结构及其操作，将链表、栈、队列、树、图等概念理论化，开创了数据结构的课程体系，使之成为一门独立的学科；
结构化编程诞生的时期（70 年代起）：
大型程序出现、软件开始相对独立。尼克劳斯·威尔特（Niklaus Wirth）提出 “程序 = 数据结构 + 算法”，即程序设计的实质是对确定的问题选择一种好的结构，加上一种好的算法。数据结构在程序设计中占据了越来越重要的地位。
标准化时期（90 年代起）：
面向对象和泛型编程愈加成熟，数据结构开始被封装为标准库（如 C++ 的 STL），实现了“拿来即用”，使程序员可以专注于“选择哪种结构来解决哪种问题”。

基本概念和术语

一、数据

数据 Data：
是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号的集合。
Data: The set of all the symbols can be processed or stored by a computer.
数据不仅包括整形、实型等数值类型，还包括字符、声音、图像等非数值类型。数据其实就是符号，但必须具备两个前提：可以输入到计算机中、能被计算机程序处理。

二、数据元素

数据元素 Data Element：
是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。
Data element: The term data element is an atomic unit of data that has:
- An indentification such as a data element name;
例如，每一个【人类个体】都是【人类】的数据元素，每一只牛、马、鸡、狗等动物都是【畜禽类】的数据元素。

三、数据项

数据项 Data Item：
是组成数据元素的最小单位，一个数据元素可以由若干个数据项组成；是数据不可分割的最小单位。
Data item: One smallest indivisible data units. One data element consists of one or many data items.
例如，一个【人类个体】是数据元素，他可以有眼睛、耳朵、鼻子、嘴巴等数据项，也可以有姓名、年龄、性别等数据项。一个数据元素具体有哪些数据项，要由程序应实现的功能来决定。

四、数据对象

数据对象 Data Object：
是性质相同的数据元素的集合，是数据的子集。
Data object: The collection of data elements.
例如，【人类】由大量的【人类个体】组成，人类个体是数据元素，由这些具有相同性质的数据元素组成的【人类】就称为数据对象。

五、数据结构

结构 Structure：
不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。
例如，分子结构就是组成分子的原子之间的排列方式；
数据结构 Data Structure：
是相互之间存在一种或多种特定关系的数据元素的集合。
例如，数组中的数据元素之间，是一前一后的关系，所以数组就是一种数据结构。研究数据结构，本质上就是研究数据元素之间的关系，以及如何有效地表示和操作这种关系。

逻辑结构和物理结构

逻辑结构是面向问题的，物理结构是面向计算机的；
其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

一、逻辑结构

逻辑结构 Logical Structure：是指数据对象中数据元素之间的相互关系。

逻辑结构分为以下的四种：

集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系；
线性结构：线性结构中的数据元素是一对一的关系；
树形结构：树形结构中的数据元素之间存在一种一对多的层次关系；
图形结构：图形结构中的数据元素是多对多的关系。

二、物理结构

物理结构（存储结构 Storage Structure）：是指数据的逻辑结构在计算机中的存储形式。

数据元素的存储结构形式有两种：

顺序存储结构：是把数据元素存放在连续的存储单元里，其数据间的逻辑关系和物理关系是一致的；
链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
1. 数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，通过地址寻找关联数据元素的位置；
2. 链式存储比顺序存储更灵活，适合时刻处于变化中的结构。

数据类型

数据类型 Data type：是指一组性质相同的值的集合，及定义在此集合上的一些操作的总称。

一、数据类型的定义

数据类型是根据值的不同进行划分的。在高级语言中，每个变量、常量都有各自的取值范围，类型就用来说明变量或表达式的取值范围和所能进行的操作。

在 C 语言中，按照取值的不同，数据类型可分为两类：

原子类型：不可再分解的基本类型，包括整型、实型、字符型等；
结构类型：由若干个类型组合而成，可再分解，例如整型数据。
例如，short 类型就比 int 类型使用更少的空间，同时取值范围也更小；变量声明 int a, b，就意味着 a 和 b 的值不能超出 int 的取值范围，a 和 b 之间的运算只能是 int 类型所允许的运算。

二、抽象数据类型

我们对已有的数据类型进行抽象，就有了抽象数据类型：

**抽象是指抽取出事物具有的普遍性的本质。**抽象是一种思考问题的方式，隐藏繁杂的细节，只保留实现目标所必需的信息。
抽象数据类型 Abstract Data Type, ADT：一个数学模型及定义在该模型上的一组操作。
- 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关；
- 抽象数据类型体现了程序设计中问题分解、抽象和信息隐蔽的特性。抽象数据类型把问题分解为多个小规模且容易处理的问题，然后建立一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。
描述抽象数据类型的标准格式：

Plaintext

ADT 抽象数据类型名
Data
    数据元素之间逻辑关系关系的定义
Operation
    操作 1
        初始条件
        操作结果描述
    操作 2
        ......
    操作 3
        ......
endADT

ADT 抽象数据类型名
Data
    数据元素之间逻辑关系关系的定义
Operation
    操作 1
        初始条件
        操作结果描述
    操作 2
        ......
    操作 3
        ......
endADT

[数据结构] 数据结构绪论