1 基本概念和术语

1.1 数据

1.数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

2.数据不仅包含整型、实型等数值类型，还包括字符及声音，图像，视频等非数值类型。

3.这里的数据必须具备两个前提：

可以输入到计算机中
能被计算机程序处理

4.对于整型，实型等数值类型，可以进行数值计算。而对于字符数据类型，则可进行非数值的处理。

注：声音，图像，视频等其实是可以通过编码的手段变成字符数据来处理的

1.2 数据元素

数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称作记录。（人，牛，羊）

人类中的数据元素是人，畜类的数据元素是牛，羊·······

1.3 数据项

数据项：一个数据元素可以由若干个数据项组成。*(眼睛，姓名，性别)*

数据项是数据不可分割的最小单位。

对人这样的数据元素，数据项可以是眼睛，口，鼻子，姓名，年龄等

1.4 数据对象

数据对象：是性质相同的数据元素的集合，是数据的子集。（人类，畜类，坦克类）

性质相同：数据元素具有相同数量和类型的数据项。

在实际应用中，处理的数据元素通常具有相同的性质，在不产生混淆的情况下，我们一般将数据对象称为数据。

1.5 数据结构

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。（人甲，牛，羊，人乙，这四个数据元素一起，规定他们之间有特定关系）

结构，简单的理解就是关系，比如分子结构，就是说组成分子的原子之间的排列方式。

严格的说，结构是指各个组成部分相互搭配和排列的方式。

在现实世界中，不同的数据元素之间不是独立的，而是存在特定的关系的，我们将这些关系称为结构。

在计算机中，数据元素并不是孤立，杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系，这也就是数据的组织形式，即数据结构。

2 逻辑结构与物理结构

按照不同的角度来讨论，会有不同的分类，即逻辑结构和物理结构两种。

2.1 逻辑结构

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

逻辑结构是针对具体问题的，是为了解决某个问题，在对问题理解的基础上，选择一个合适的数据结构表示数据元素之间的逻辑关系。

2.1.1 集合结构

集合结构：集合结构中的数据元素除了同属于一个集合外，他们之间没有任何其他关系。

各个数据元素是“平等”的，他们的共同属性就是“同属于一个集合”。

数据结构中的集合关系就类似于数学中的集合。

2.1.2 线性结构

线性结构：线性结构中的数据元素之间是一对一的关系。

1后面是2，2后面是3,3后面是4······

2.1.3 树形结构

树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。

好像一个倒着的大树啊！！！

2.1.4 图形结构

图形结构：图形结构的数据元素是多对多的关系。

乱乱的，好多线。

2.2 物理结构

物理结构：是指数据的逻辑结构在计算机中的存储形式。（在我看来，是依照我们脑中的逻辑结构，按这种结构，依照相同的方式（即存储形式）在计算机的内存中寻找要获取的信息）

数据的存储结构应正确反映数据元素之间的逻辑关系，这才是最为关键的，如何储存数据元素之间的逻辑关系，是实现物理结构的重点和难点。

物理结构的基本目标就是把数据及其逻辑关系存储到计算机的内存中。

2.2.1 顺序存储结构

顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

如1后面是2，2后面是3，3后面是4······

2.2.2 链式存储结构

链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

如链表。

链式存储灵活很多，数据存在哪里不重要，只要有一个指针存放了相应的地址就能找到它。

3 抽象数据类型

3.1 数据类型

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

数据类型是按照值的不同进行划分的。在高级语言中，类型就用来说明变量或表达式的取值范围和所能进行的操作。

按取值不同，数据类型可分为以下两类：

原子类型：是不可以在分解的基本类型，包括整形，实型，字符型等。
结构类型：由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干个整形数据组成的。

抽象是指抽取出事物具有的普遍性的本质。

3.2 抽象数据类型

抽象数据类型：是指一个数学模型及定义在该模型上的一组操作。（抽象数据类型的定义仅取决于他的一组逻辑特性，而与其在计算机内部如何表示和实现无关。如抽象出来的整型）

“抽象”的意义在于数据类型的数学抽象特性

一个抽象数据类型定义了：一个数据对象，数据对象中各数据元素之间的关系及对数据元素的操作。

抽象数据类型体现了程序设计中问题分解，抽象和信息隐蔽的特性。