- 注意：本文部分内容来自菜鸟教程
- 下一节内容讲时间和空间复杂度：(王道408考研数据结构)第一章绪论-第二节2：算法的时间复杂度和空间复杂度
一：数据结构
（1）什么是数据结构
A：基本术语
①：数据
数据：所谓数据，是指信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合
比如我们现在常常使用到的搜索引擎，一般会有网页、音乐、图片、视频等分类，他们分别对应了声音、图像等数据。这里所说的数据实则是一些符号，这些符号必须具备两个前提条件
- 可以输入到计算机中
- 能被计算机程序处理
其中对于整型、浮点型这类的可以进行数值运算，而对于字符这类的数据则需要进行非数值运算，而像图像、视频这类数据则可以通过编码的手段转换为其他类型数据进行运算
②：数据元素和数据项
数据元素：数据元素是数据的基本单位，用于描述一个个体，通常作为一个整体进行考虑和处理。一个数据元素可以由若干数据项组成，它是构成数据元素的不可分割的最小单位
- 人类世界中，数据元素就是单个的人
- 畜类中，像牛、马、羊等就是禽类的数据元素
数据项：一个数据元素可以由若干数据项组成，数据项是数据不可分割的最小单位
对于人这样的数据元素，可以有眼、耳、鼻、嘴、手这些数据项，也可以有姓名、年龄、性别、出生地址、联系电话这些数据项。具体有哪些数据项，要视情况而定
③：数据对象
我们用数据描述这个世界，用数据元素对应某个逻辑个体，对于个体的种种描述又可以拆分为一个一个的数据项
数据对象：我们把属性相同的数据元素所组成的对象称之为数据对象，是数据的子集
- 比如正整数这个数据对象,所反映了这样一个集合$N={0,1,2,3,4,5,......}$
数据对象是数据的子集，而在实际应用中，处理的数据元素通常具有相同性质，在不产生混淆的情况下，我们把数据对象简称为数据
④：数据结构
所谓结构，是指各个组成部分相互搭配和排列的方式
- 高中化学中的晶型和这个类似
在现实世界中，不同数据元素之间不是独立的，而是存在某种特定的关系，我们就把这个关系称之为结构
- 开门见山，比如链表结构，树结构，图结构等
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
- 数据结构强调数据与数据之间必须具有某种对应关系。就像财富排行榜，马斯克下面必须是贝索斯，因为马斯克比贝索斯钱多
- 数据对象强调数据与数据之间必须具有相同的属性
数据结构研究的重点并不在于数据本身，而是在研究这些数据在某种结构下的关系！！！
（2）数据结构三要素
A：逻辑结构
逻辑结构：是指数据对象中数据元素之间的相互关系。是从逻辑上描述数据关系，或者说这种关系是人假想的，对于计算机来说不过就是一个存储单元罢了
逻辑结构主要分为线性结构和非线性结构
- 线性结构：一对一
- 非线性结构：不是一对一
①：集合
集合：该结构中的数据元素除了同属于一个集合外，他们之间没有任何关系
- 各个数据元素关系平等，类似于数学中的集合
②：线性结构
线性结构：该结构中的数据元素之间是一对一的关系
- 除了第一个元素外，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继
③：树形结构
树形结构：该结构中的数据元素之间存在一对多的关系
- 像操作系统的文件目录结构，思维导图都是典型的树形结构
④：图形结构
图形结构：该结构中的数据元素之间存在多对多的关系
B：物理结构（存储结构）
逻辑结构 相当于“纸上谈兵”——是指“这个数据应该这样存，他们之间应该具有这样、那样的关系”，但是计算机可不管这么多，因为它就那么一个硬盘，还能玩出什么花样？
物理结构（存储结构）：是指数据的逻辑结构在计算机中的存储形式
数据的物理结构应该正确的反映数据元素之间的逻辑关系，这是实现物理结构的重点和难点。主要分为：顺序存储和链式存储
- 比如完全二叉树，它逻辑结构上很明显是树，但是在存储上可以用顺序存储（数组）也可以用链式存储（链表）
①：顺序存储结构
顺序存储结构：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中。元素之间的关系由存储单元的邻接关系体现
- 你可以这样理解，有10个人排队坐位置，规定好了A后面是B，那么B在坐的时候一定要坐到与A相邻的位置
- 最典型的就是数组
②：链式存储结构
链式存储结构：不要求逻辑上相邻的元素也存储在物理位置也相邻的存储单元中。元素之间的关系借助指示元素存储地址的指针来表示
- 上例中这些元素逻辑上相邻，但所存放的存储单元并不是连续的
③：索引存储结构
顺序存储结构：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称之为索引项，索引项一般形式是关键字+地址
④：散列存储结构（哈希）
散列存储结构：根据元素的关键字直接计算出该元素的地址。计算依靠的方式称之为哈希函数
| 物理结构 | 优点 | 缺点 |
|---|---|---|
| 顺序存储 | 支持随机存取、占用空间最少 | 要求必须整块存储单元、外部碎片多 |
| 链式存储 | 不会产生碎片 | 额外空间占用大，只支持顺序存取 |
| 索引存储 | 检索速度快 | 附加信息太多，占用空间多 |
| 散列存储 | 检索、增加和删除结点速度极快 | 会出现哈希冲突，解决冲突又会增加额外成本 |
C：数据运算
数据运算：施加在数据上的元素包括运算的定义和实现
- 运算的定义是针对逻辑结构的，指出运算的功能
- 运算的实现是针对存储结构的，指出运算的具体步骤
二：算法
（1）算法的基本概念
A：数据结构和算法的关系
“数据结构”，“数据结构与算法”这样的词我们经常提到，甚至有的书就以它们作为名字，那么数据结构和算法究竟具有怎样的关系呢？
事实上，只谈数据结构是完全可以的，我们只需要用屈指可数的几篇文章就能全部讲解完毕，但是听完之后你可能没有任何感觉，甚至感觉学了没用。但是如果我们再把相应的算法拿出来讲一讲，你就会感叹到这些大佬怎么这么聪明。因此在数据结构中讲算法是为了帮助我们更好的理解，纯讲算法也会有相应的课程。当然算法要比数据结构难多了，从某种方面来讲它其实是数学问题，可能受限于学习者的智商水平（别气馁，大家都一样，我们并不是大佬）
那什么是算法呢？ 我觉得历史上的一位大佬——高斯，就展现了算法的魅力
接触过C语言的同学都知道，计算1+2+....+100的程序应该这样编写
#include <stdio.h>
int main()
{
int sum=0
int n=100;
for(int i=1;i<=n;i++)
{
sum+=i;
}
printf("%d\n",sum);
}
我们认为它就是一种算法，因为它很明显已经解决了问题，但是高效吗？我认为高斯已经给出了答案
他的方法是
对应程序为
#include <stdio.h>
int main()
{
int i,sum=0
int n=100;
sum=(1+n)*n/2;
printf("%d\n",sum);
}
这很明显也是一种算法，而且相较于之前的哪种方法来说，效率得到了很大的提升
B：算法(Algorithm)的定义
算法(Algorithm)：是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
- 王道视频课中讲到了一个例子，展示了算法就是解决问题的特定步骤的描述
从之前求和的例子我们可以看出：对于给定的问题可以有多种多样的算法来解决，只不过这些算法有各自的优点和缺点
（2）算法的特性
有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可以在有穷时间内完成
- 注意区别程序，程序可以是无穷的
确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得到相同的输出
- 例如排序算法有很多种，但不论采用何种排序算法，最终结果是唯一确定的
可行性：一个算法所描述的操作都可以通过已经实现的基本运算执行有限次数来实现
- 可行性意味着算法可以转化为程序并上机运行并得到正确结果
输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合
输出：一个算法有一个或多个输出，这些输出是与输入有某种特定关系的量
（3）算法设计要求
正确性：是指算法至少具有输入、输出和加工处理且无歧义并能正确反映问题的需求，能够得到问题的正确答案。大体分为如下四个层次
- 算法程序没有语法错误
- 算法程序对于合法的输入数据能够产生满足要求的输出结果
- 算法程序对于非法的输入能够得出满足规格说明的结果
- 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果（最难达到）
可读性：算法设计的另一个目的就是为了便于阅读、理解和交流
- 可读性有助于人们理解算法，晦涩难懂的算法往往隐含错误，不容易被发现，并难于调试和修改，这一点在递归类的算法身上体会非常明显
健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或其它莫名其妙的结果
时间复杂度和空间复杂度较低：也就是说花的时间少而且占用内存空间小
二：Java集合框架
（1）什么是Java集合框架
Java集合框架：类似于C++中的STL，Java中有关数据结构的一些类称之为集合框架（Java Collection Framework），它是定义在java.util包下的一组接口和其实现类，是一个用来代表和操纵集合的统一架构。如下图，Java集合框架主要包括两种：集合（Collection）和图（Map），分别用于存储元素集合和键值对映射
所有的集合框架都包含以下内容
- 接口：是代表集合的抽象数据类型，例如
Collection、List、Set、Map等。定义这么多接口是因为不同的集合对象有各自的特点，操作方式也有不同 - 实现（类）：是集合接口的具体实现。从本质上讲，它们是可重用的数据结构，例如
ArrayList（顺序表）、Stack（栈）、LinkedList（双向链表）、HashSet（哈希表）等 - 算法：是实现集合接口对象里方法执行的一些有用计算。例如搜索和排序
集合框架体系如下图所示
（2）各接口、类、概述
这里对Java集合框架中的接口和实现进行简单描述，后续文章将会重点学习
A：接口
B：实现
（3）集合框架重要性
非常重要！非常重要！非常重要！
- Java集合框架体现出的编程思维（尤其是面向对象）非常值得借鉴
- 笔试、面试比重很高
- 日常工作中经常会使用
- 一些算法竞赛中也会使用
- ...
评论区