大话数据结构 笔记 第一章
我的笔记均包含大量个人理解内容，存在一定偏差。如果您发现错误，请留言提出，谢谢！

数据结构是一门研究非数值运算的程序设计问题中的操作对象，以及他们之前的关系和操作等相关对象的学科。这意味着我们用计算机解决问题，首先要解决一些对象之前的关系与操作的问题。数据结构和算法，就是因由这些问题应用到计算机中的。总的说来，我们有一个比较概念化的公式如果下：

$$程序结构 = 数据 + 算法$$

1968年美国的 Donald E. Kunth 教授在其所写的《计算机程序与艺术》第一卷《基本算法》里首次较为系统的阐述了数据的逻辑结构、存储结构和这些数据的相关操作；这被视为数据结构课程的开端。

数据结构作为研究数据的一门学科，我们先得知道什么数据。 简单的来说：数据可以细致的分为：

• 数据：计算机用于描述客观事物的符号，可以输入计算机，并被计算机操作。
• 数据元素：组成数据的基本单位。数据元素对于数据来说，就像鸡对应于家禽一样，是数据的实例。
• 数据项：元素的组成部分，数据的最小元素，比如鸡爪子之于鸡。
• 数据对象：性质相同的数据元素集合，是数据的子集。
• 数据结构：现实世界中，不同元素之间存在特定的关系。我们用数据结构来描述计算机中相互存在一种或者多种特定关系的数据元素集合。

数据结构分为逻辑结构和物理结构。

逻辑结构表达了数据对象中数据元素之间的相互关系，大致分为四种类型：

1. 集合结构：集合结构中的数据元素除了同属一个集合外，没有任何其他的关系。他们的共同属性是“同属于一个集合”，这个概念源自于数学中集合的概念。
2. 线性结构：数据元素在线性结构中呈现出一对一的关系。
3. 树形结构：数据元素在树形结构中存在着一对多的关系。
4. 图形结构：数据元素在图形结构中存在着多对多的关系。

我们可以形象的用示意图来表示数据的逻辑结构：

• 把每一个数据元素看做一个节点，用圆圈表示。
• 元素之间的逻辑关系用节点之间的连线表示，如果是有向的，就用箭头连线表示：

物理结构（存储结构）表示了数据的逻辑结构在计算机中的存储方式。具体的说，就是怎么存储数据。对于不同的存储器，物理结构也有不同的描述；比如外部存储器，我们一般用文件结构来描述物理结构。

存储结构是从现实意义上来反映数据的逻辑结构的。因此，要实现存储结构，我们必须明白怎样将数据的逻辑结构用物理结构的方式表达出来。

存储结构大致可以分为两种：顺序存储结构和链式存储结构。

所谓顺序存储结构，就是把数据元素放到地址连续的内存单元里；数据间逻辑关系和物理关系是一致的。用生活中的描述来说，就是排队站位，挨个来。

这样的存储结构很好描述；但不方便操作。比如有人如果要插队，队伍中间有人要离开，这些行为都会造成队伍结构的变化。顺序存储的应变性比较低，不足以应付这样的情况。链式存储结构可以更好的解决这一问题。

而链式存储结构的关键点在于，逻辑上连续，而物理上并不一定连续；也就是说，存储结构是不能描述其逻辑结构的。为了保证逻辑上的连续，我们给数据添加指针，用指针来指向下一个逻辑连续的数据元素，就像链子一样，一环一环的来。

数据类型分为两部分：

• 拥有相同性质的数据元素的结合
• 操作这些数据元素的相关操作

为什么需要考虑数据类型呢？很显然是为了做好资源分配。比如商品房品种很多，因为每个人的消费水准不同，买的起的房也是不一样的。因此定义不同的商品房才能满足不同消费水平的人的需要。同理，在计算机里，资源也不是无限的；因此每个数据类型都有自己空间占用（取值）范围，对应不同的数据应用不同的数据类型，这样才能达到有效利用计算机资源的目的。

而为什么需要抽象数据类型呢？因为不同的计算机对应不同的硬件指令，比如在不同的硬件平台上实现 1 + 1 的命令都不一样。现实生活中我们要计算 1 + 1 不会去考虑什么平台用什么的。这就是抽象：抽取事物具有的普遍性。同理，如果我们要研究数据，必须要摆脱平台的困扰，把数据抽象为一系列的普遍操作；而数学则是抽象数据的最有效的工具。

抽象数据类型（Abstract Data Type, ADT），其本质就是一个数学模型（集合），和一系列应用到这个数学模型上的操作。因为类型是抽象的，所以我们只探讨抽象数据类型的逻辑性，而不会去讨论它在计算机内部如何实现。

事实上，抽象数据类型体现了程序设计（也可以想象成一般解决问题）几个特性：分解，抽象，信息隐藏：

1. 我们用抽象数据类型，把一个大问题分解成许多个小问题
2. 对于每个独立的小问题，建立一个计算机能够处理的功能模块来处理这个问题
3. 因为每个功能模块都是独立的，所以实现了彼此的信息隐藏（封装）

来看看下面的描述：

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

~~DISQUS~~