写在前面
关于本文，被收集在我的专栏《数据结构与算法教程笔记》中，笔记整理来自李春葆老师的《数据结构教程第六版》。更多章节可参考该专栏。【该专栏目前处于持续更新状态 -2022/9/11 】
1.数据结构总览
1.1 内容
基本数据组织和数据处理方法
各种数据的逻辑结构描述
各种数据的存储结构表示
各种数据结构的运算定义
设计实现运算的算法
分析算法的效率
1.2 数据结构在计算机课程体系（偏软）中的地位
计算机基础C语言
C语言
数据结构
算法设计与分析操作系统
编译原理
数据库原理
软件工程
1.3 数据结构与程序设计类课程的关系
基本编程
以数据机构为中心的算法设计
基本算法设计方法
通用算法设计
算法设计方法学
程序设计语言
数据结构
算法设计与分析
识字
写小作文
写大文章
1.4 数据结构的学习目标
- 掌握数据结构的基本概念、基本原理和基本方法。
- 掌握数据的逻辑结构、存储结构及基本运算的实现过程。
提炼
设计
实现
求解问题
数据运行-->数据
数据逻辑结构
数据存储结构
数据基本运行：算法 - 掌握算法基本的时间复杂度与空间复杂度的分析方法，能够设计出求解问题的高效算法。
✏️ 同一求解问题通常有多种实现算法，通过时间复杂度与空间复杂度的分析，找出最好的实现算法。
1.5 数据结构的学习方法
- 理解各种数据结构的逻辑特性和存储结构设计
映射：计算机中的表示
逻辑特性
存储结构
线性表
栈
队列
串
数组
树
二叉树
图 - 掌握各种数据结构算法设计的基本方法
✏️ 只有掌握了数据的存储结构表示，才能在此之上设计算法
映射：计算机中的表示
运算实现
逻辑特性
存储结构
算法设计 - 利用各种数据结构来求解实际问题
求解问题
数据如何表示(选择合适的数据结构)
数据运算如何实现
数据运算如何高效实现 - 演绎和归纳相结合
演绎学习
训练
归纳总结
数据结构
鱼(内容)：基本概念，基本原理和基本方法
练习(作业和编程)
渔(方法)：求解问题的能力
2.什么是数据结构
2.1 数据结构的定义
2.1.1 数据结构中的几个概念
- 数据：所有能够输入到计算机中，且能被计算机处理的符号的集合。数据结构中主要讨论结构化数据。
- 数据元素：是数据（集合）中的一个“个体”，它是数据的基本单位。
- 数据项：数据项是用来描述数据元素的，它是数据的最小单位。
- 数据对象：具有相同性质的若干个数据元素的集合，如整数数据对象是所有整数的集合。默认情况下，数据结构中讨论的数据都是数据对象。
- 数据结构：是指带结构的数据元素的集合。
数据结构
数据对象：相同性质的数据元素的集合
结构：数据元素之间的关系构成结构
2.1.2 一个数据结构的构成
逻辑结构
存储结构
数据运算
- 数据的逻辑结构：数据元素之间的逻辑关系
- 数据的存储结构（或物理结构）：数据元素及其关系在计算机存储器中的存储方式
- 数据运算：施加在该数据上的操作
2.1.2.1 数据的逻辑结构表示
- 数据的逻辑结构是面向用户的，它有多种表示形式。
- 二元组是一种通用的逻辑结构表示方法。
- 每个关系的用若干个序偶来表示
2.1.2.2 数据的存储结构表示
1️⃣ 数据在计算机存储器中的存储方式就是存储结构。它是面向程序员的。逻辑结构映射存储结构。
2️⃣ 设计存储结构的这种映射应满足两个要求：
- 存储所有元素
- 存储数据元素间的关系
- 结构体数组(顺序存储结构)
- 所有元素占用一整块内存空间
- 逻辑上相邻的元素，物理上也相邻。
- 链表(链式存储结构)
- 一个逻辑元素用一个结点存储，每个结点单独分配，所有结点的地址不一定是连续的。
- 用指针来表示逻辑关系。
2.1.2.3 数据运算
数据运算是对数据的操作。分为两个层次：运算描述 和 运算实现。
- 同一逻辑结构可以对应多种存储结构。
- 同样的运算，在不同的存储结构中，其实现过程是不同的
2.2 逻辑结构类型
各种各样的数据呈现出不同的逻辑结构，归纳为4种。
2.2.1 集合
- 元素之间关系：无。
- 特点：数据元素之间除了“属于同一个集合”的关系外，别无其他逻辑关系。是最松散的，不受任何制约的关系。
2.2.2 线性结构
- 元素之间关系：一对一。
- 特点：开始元素和终端元素都是唯一的，除此之外，其余元素都有且仅有一个前驱元素和一个后继元素。
2.2.3 树形结构
- 元素之间关系：一对多。
- 特点：开始元素唯一，终端元素不唯一。除终端元素以外，每个元素有一个或多个后继元素；除开始元素外，每个元素有且仅有一个前驱元素。
2.2.4 图形结构
- 元素之间关系：多对多。
- 特点：所有元素都可能有多个前驱元素和多个后继元素。
2.3 存储结构类型
在软件开发中，人们设计了各种存储结构。 归纳为4种基本的存储结构。
- 顺序存储结构
- 链式存储结构
- 索引存储结构
- 哈希（散列）存储结构
2.4 数据类型和抽象数据类型
2.4.1 数据类型
1️⃣ 在高级程序语言中提供了多种数据类型。不同数据类型的变量，其所能取的值的范围不同，所能进行的操作不同。
2️⃣ 数据类型 是一个值的集合和定义在此集合上的一组操作的总称
3️⃣ 数据类型和数据结构的关系：数据类型就是已经实现了的数据结构。
2.4.2 抽象数据类型
1️⃣ 抽象数据类型（ADT）指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算（抽象运算），而不考虑计算机的具体实现。
2️⃣ 抽象数据类型 = 逻辑结构 ＋ 抽象运算
3️⃣ 抽象数据类型实质上就是对一个求解问题的形式化描述（与计算机无关），程序员可以在理解基础上实现它。
3.算法及其描述
3.1 什么是算法
数据元素之间的关系有逻辑关系和物理关系，对应的运算有基于逻辑结构的运算描述和基于存储结构的运算实现。
1️⃣ 数据是各种信息的表现形式
2️⃣ 算法表现为“处理”和“数据”的结合
通常把基于存储结构的运算实现的步骤或过程称为算法。更一般地，算法是 解决问题的处理步骤
✏️ 算法的五个重要的特性
有穷性：在有穷步之后结束，算法能够停机。确定性：无二义性。可行性：可通过基本运算有限次执行来实现，也就是算法中每一个动作能够被机械地执行。输入：0个或多个输入【表示存在数据处理】输出：1个或多个输出【表示存在数据处理】
✏️ 算法和程序的区别
程序是指使用某种计算机语言对一个算法的具体实现，即具体要怎么做。
程序不一定满足有穷性算法侧重于对解决问题的方法描述，即要做什么。
算法一定满足有穷性- 算法用计算机语言描述 --> 程序
3.2 算法描述
❓ 如何描述输出型参数
📍 C++语言中提供了一种引用运算符“&”用于描述输出型参数。
✏️ 算法可以采用自然语言、流程图或者表格方式等来描述。但是，一个学习计算机的学生应该使用某种计算机语言来描述算法。
