数据结构+算法=程序
数据结构是程序的骨架，算法是程序的灵魂

1.1 数据结构的基础知识

1. 数据

数据是指所有能输入到计算机中描述客观事物的符号，包括文本、声音、图像、符号等。“二维码”

2. 数据元素

数据元素是数据的基本单位，也称节点或记录。

3. 数据项

数据项表示有独立含义的数据最小单位，也称域。若干个数据项构成一个数据元素。数据项是不可分割的最小单位。如图学号。

4. 数据对象

数据对象是指相同特性的数据元素的集合，是数据的子集。

5.数据结构

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构是带“结构”的数据元素的集合，“结构”是指数据元素之间存在的关系。数据结构研究的问题是将带有关系的数据存储在计算机中，并进行相关操作。数据结构包含逻辑结构、存储结构和运算结构三个要素。

6. 数据结构和存储结构

逻辑结构是数据元素之间的关系，存储结构是数据元素及其关系在计算机中的存储方式。
例如：小明和小勇是表兄弟，这是他们之间的逻辑关系；他们在教室的位置是他们的存储结构。无论他们的座位怎么坐，都不影响他们表兄弟关系。
逻辑结构：数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机。它是从具体问题中抽象出来的数学模型。
数据的逻辑结构共有：
（1）集合——数据元素间除“同属于一个集合”外，无其他关系。
（2）线性结构——一个对一个，如线性表、栈、队列、数组、广义表。
线性结构就像穿珠子，一条线，不会分叉，有唯一的开始和唯一的结束，除了第一个元素外，每个元素都有唯一的直接前驱，除了最后一个，每个元素都有唯一的直接后继。

（3）树形结构——一个对多个，如树。
树形结构就像一颗倒立的树，树根可以发出多个分支，每个分支也可以继续发出分支，树枝和树之间是不相交的。

（4）图形结构——多个对多个，如图、网。
图形结构就像我们经常见到的地图，任何一个节点都可能和其他节点有关系，就像一张错综复杂的网。

存储结构：数据元素及其关系在计算机中的存储方式。
（1）顺序结构
顺序存储是指逻辑上相邻的元素在计算机内的存储位置也是相邻的。
例如：小明是哥哥，小安是弟弟，他们逻辑上是兄弟，他们的房子是前后院也是相邻的，就可以说他们是顺序存储。
顺序存储采用一段连续的存储空间，将逻辑上相邻的元素存储在连续的空间内，中间不允许有空，顺序存储可以快速定位第几个元素的地址，但是插入和删除时需要移动大量元素。

(2)链式存储
链式存储是指在逻辑上相邻的元素在计算机内的存储位置不一定是相邻的。
例如：弟弟小安去南京了，哥哥还住在原来的位置，他们的位置不相邻，但是哥哥有弟弟的地址，很容易可以找到弟弟，就可以说他们是链式存储。
链式存储就像一个铁链子，一环扣一环才能连在一起。每个节点除了数据域，还有一个指针域，记录下一个元素的存储地址

（3）散列存储
又称为哈希（Hash）存储，由节点的关键码值决定节点的存储地址。用散列函数确定数据元素的存储位置与关键码之间的对应关系。

例如：
假设散列表的地址范围为0~9，散列函数为H(key)=key%10.输入关键码序列：（24，10，32，17，41，15，49），构造散列表，如下：

散列存储可以通过把关键码值映射到表中的一个位置来访问记录，以加快查找速度。如果有冲突，则有多种处理冲突的办法。
（4）索引存储
索引存储是指除建立存储点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。如果每个节点在索引表都有一个索引项，则称该索引表为稠密索引。若一组节点在索引表中只对应一个索引项，则该索引表称为稀疏索引。索引项的一般形式为关键字、地址。

7. 抽象数据类型

抽象数据类型（Abstract Data Type，ADT）是将数据对象、数据对象之间的关系和数据对象的基本操作封装在一起的一种表达方式，它和工程中的应用是一致的。在工程项目中，开始编程序之前，首先列出程序需要完成的功能任务，先不管具体怎么实现，实现细节在项目后期完成，一开始只是抽象出有哪些基本操作。把这些操作封装为抽象数据类型，等待后面具体实现这些操作。而其他对象如果像调用这些操作，只需要按照规定好的参数接口调用，并不需要知道具体是怎么实现的，从而实现了数据封装和信息隐藏。在C++中可以用类的声明表示抽象数据类型，用类的实现抽象数据类型的具体操作。
抽象数据类型可以用以下三元组来表示。
ADT=(D,S,P)|D数据对象.S,D上的关系集.P，D上的操作集

ADT抽象数据类型名{
    数据对象：<数据对象的定义>
    数据关系：<数据关系的定义>
    基本操作：<基本操作的定义>
}ADT抽象数据类型名

为什么要使用抽象数据类型？

抽象数据类型的主要作用是数据封装和信息影藏，让实现与使用分离。数据及其相关操作的结合称为数据封装。对象可以对其他对象影藏某些操作细节，从而使这些操作不会受到其他对象的影响，这就是信息隐藏。抽象数据类型独立于运算的具体实现，使用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，实现了信息隐藏。
数据结构和算法相辅相成，密不可分。