参考教材：数据结构C语言版（严蔚敏，杨伟民编著）
参考课程：青岛大学王卓老师：数据结构与算法基础
思维导图：XMind、幕布
不定时更新，会在里面加入一些真题
第一章：绪论
1.1基本概念和术语
数据（data）：
什么是数据？
1.数据是信息的载体，是对客观事物的符号表示。
2.能输入到计算机并被计算机程序处理的符号的总称（能被计算机识别、存储和加工）。
数值型数据：整数、实数。
非数值型数据：图像、声音、文字等。
数据元素（data element）：
定义
数据元素是组成数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据元素也称元素、记录、结点、顶点。
数据元素与数据的关系
数据元素是集合（数据）的个体。
数据项
一个数据元素可由若干个数据项组成。数据项是构成数据元素不可分割的最小单位。
数据对象（data object）：
数据对象是性质相同的数据元素的集合，是数据的一个子集。例：
数据对象与数据的关系
数据对象是集合（数据）的子集。
数据、数据对象、数据元素、数据项四者关系：
数据 ≥ 数据对象 > 数据元素 > 数据项
数据是由数据元素组成，数据元素是由数据项组成
数据结构（data structure）：
定义
Data Structure=（D,S）：D是数据元素的有限集，S是D上关系的有限集
（2015中国石油大学）数据结构的定义为（D,S），其中D是（数据元素）的集合。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合
结构：数据元素之间的关系
（2013中科大）数据结构是具有结构的数据对象（X）
解析：这个说法有些模糊，通常数据结构是计算机存储、组织数据的方式，它不仅仅是一个“具有结构的数据对象”，还涉及到数据的运算和操作。数据结构包括数据的逻辑结构、数据的物理存储结构以及数据上定义的操作。所以，仅仅说数据结构“数据结构是具有结构的数据对象”是不全面的。
数据结构的三要素
一、逻辑结构
数据的逻辑结构：数据元素之间的逻辑关系（2013中科大）。逻辑结构独立于计算机，与数据的存储无关。
（2019广东工业大学）与数据元素本身的形式、相对位置和个数无关的是：数据逻辑结构
解析：所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构；
所谓数据的存储结构，是指数据的逻辑结构在计算机存储空间中的存放形式，与数据元素本身的形式、相对位置和个数有关，逻辑结构与物理存储无关
逻辑结构的种类
（一）线性结构：线性表，栈，队列，双队列，串（一维数组)
一对一：结构中的数据元素之之间存在一个对一个的关系，有且仅有一个开始和一个终端点。
除第一个元素外，其他元素有且只有一个前趋；
除最后一个元素外，其他元素有且只有一个后继！
（二）非线性结构：树形结构、图状结构（网状结构）、二叉树
一个结点可能有多个直接前趋和直接后继
①树形结构：一对多
结构中的数据元素之间存在一个对多个的关系。
②图状结构（网状结构）：多对多
结构中的数据元素之间存在多个对多个的关系。
（三）其他结构：集合
①集合：也可用其他结构来表示
结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。
（2013中科大）数据的逻辑结构与数据元素本身的内容和形式无关。
数据的逻辑结构只关心数据之间的逻辑关系，而不关心数据元素本身的内容和形式。
二、物理结构（存储结构）
数据元素及其关系（数据结构）在计算机中的表示（又称映象）称为数据的物理结构或存储结构
四种基本的存储结构
（一）顺序存储结构（重点）
用一组地址连续的存储单元依次存储线性表的各个数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
C语言中用数组来实现顺序存储结构
优点：节省存储空间。
缺点：不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。
（二）链式存储结构（重点）
用一组任意的存储单元存储线性表的数据元素，各个元素之间的关系用指针来表示(这组存储单元可以是连续的,也可以是不连续的)。指针————地址
（三）索引存储结构（了解）
在存储结点信息的同时，还建立附加的索引表。索引——index
索引表的每一项都是索引项
索引项的一般形式是：（关键字、地址）
关键字：可以区分不同数据元素的数据项
例：下方的通讯录就是一个索引表
（四）散列存储结构（哈希存储）（了解）
根据元素的关键字直接计算出该元素的存储地址，也称哈希（Hash）存储
三、逻辑结构与存储结构的关系
1.存储结构是逻辑关系的映象与元素本身的映象。
2.逻辑结构是数据结构的抽象，存储结构是数据结构的实现。
3.两者综合建立了数据元素之间的结构关系
四、数据的运算和实现
施加在
运算：针对逻辑结构，指出运算的功能
运算的实现：针对存储结构，指出运算的具体操作步骤。
针对不同的存储结构，对应的运算实现方式也不一样。
数据类型：
数据类型就是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
数据类型=值的集合+值集合上的一组操作
C语言中基本数据类型：
整型：int 长整型：long int 短整型：short int
浮点型（单精度）：float 浮点型（双精度）：double 字符型：char 布尔型：bool
不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。
例如：bool类型的值为：true、false。可进行的操作：与、或、非...
作用：
约束变量或常量的取值范围；约束变量或常量的操作
抽象数据类型（ADT）：
抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作。
抽象数据类型的形式定义
用三元组表示（D，S，P）：D是数据对象，S是D上的关系集，P是对D的基本操作集。
定义抽象数据类型：
ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>
}ADT抽象数据类型数据对象和数据关系的定义用伪码（伪代码）描述。
基本操作的定义格式为：
基本操作名（参数表）初始条件：<初始条件描述>操作结果：<操作结果描述>赋值参数只为操作提供输入值；
引用参数以&打头，除了可以提供输入值，还将返回操作结果。
