文章目录
前言
提示：这里可以添加本文要记录的大概内容：
假设你是一个郁郁不得志的游侠儿，被人暗算坠入山崖后没死，还得到一本秘笈《数据结构与算法图解》，那么剧情如何发展：
- A 垃圾东西，焚书取暖
- B 视若珍宝，日夜苦修
人生不是小说，但是我们都是自己世界的主角，不妨给自己一点时间，一点希望，静下来认真看，认真学…（我的剑，就是你的剑）
提示：以下是本篇文章正文内容，下面案例可供参考
一、第一章：数据结构为何重要
目的：
- 了解什么是数据结构
- 读取，查找，插入，删除（都做了哪些步骤/事情）
1.概念(步数，时间复杂度)
什么是
数据：数据是一个广义的术语，可以指代各种类型的信息，包括最基本的数字和字符串。
什么是
数据结构：数据结构则是指数据的组织形式。
【备注】：书中用了两种数据结构来进行分析（数组，集合）
【第一个理论】 ：书中的第一个重要理论：操作的速度，并不按时间计算，而是按步数计算。
-
其实很好理解：假设一个查询操作在配置高的A机器上用1秒，在配置低的B机器上可能需要用3秒，因为存在硬件因素所以按时间来计算并不可靠。
-
如果按照操作步数来计算，假设其他条件一至的情况下，两个查询操作：A需要5步，B需要500，显而易见A比B快
-
操作的速度也被称为：
时间复杂度 -
这里的
步数概念需要理解，因为后面需要引入大O的概念
2，了解数组
# 一个允许用户创建和使用购物清单的食杂店应用软件，其源代码可能会包含以下的片段。
array = ["apples", "bananas", "十三香", "面包", "牛奶"]
2.1 通过（读取，查找，插入，删除）来分析
读取：查看数据结构中某一位置上的数据。
查找：从数据结构中找出某个数据值的所在。
插入：给数据结构增加一个数据值。
删除：从数据结构中移走一个数据值。
2.1.1 读取（看任意索引上的值）
- .索引取值
array = ["apples", "bananas", "十三香", "面包", "牛奶"]
# 当我们通过索引取值(bananas)，只需要一步就行
print(array[1])
- 原理：
当我们定义一个数组/列表（5个元素的array）时，计算机会在内存中分配一个空间（5个空位的格子）
所有的格子都是有一个地址的：
内存地址
当我们要取索引 2 位置的值“十三香”时，计算机会有一下的演算：
1，array索引从 0 开始，其内存地址为145
2，索引 2 在 0 索引后面的第 2 个格子上
3，于是所以索引 2 的内存地址为 145+2=147
4，计算机获得内存地址后就可以一步跳到对于的位置，就像你知道足浴店的地址一样，直接冲过去。
**【思考】**当我们不是要看“索引2上的值”时，而是想知道“十三香”在不在array里，那就要进行下面的查找操作了。
2.1.2 查找（看数组/列表中有没有该值）
当我们需要判断array里有没有“十三香”时，肉眼一扫就可以知道，但是计算机不行，他需要对里面的元素一个一个进行比较。
1，首先会总0号索引开始，检查其对应的值
2，第一个值不匹配时就继续取值比较，直到找到或者查完整个数组
当我们找到“十三香”时，此次操作步骤总计是3步，这就是最基本的查找方法：
线性查找
那可以思考一下：在数组上进行线性查找最多需要多少步呢？
假设是一个最坏的情况，你要找的元素刚好是数组的最后一个，那么就需要N步（N为数组的元素个数）
2.1.3 插入（往数组/列表中插入该值）
- 第一种情况：追加一个值（在数组最后添加一个值）
由于计算机知道数组开头的内存地址，也知道元素个数，当你要追加一个值时，只需要一步即可，直接跳到最后的位置
- 第二种情况：在数组的开头或者中间插入
在这种情况下就像你插队一样，你后面的人都会往后退一步，在内存中就是后面的元素都需要往后退一格，空出位置来
假设你要在索引2的位置插入“黑丝”
在内存中会为该数组加一个空格子，并且从最后一个元素开始到索引2的位置，所有值都需要依次往后挪动一格
如上图所示，整个插入过程需要4步：移动3个元素为3步，插入1个元素为1步
【思考】 对一个数祖进行插入，最坏的情况为多少步？
- 最坏的情况为插入在0号索引位置，这意味着需要把整个数组中的元素都挪动一遍为N步，在加上最后一步插入新元素，所以为N+1步
2.1.4 删除（删除数组/列表中的值）
如果你理解了插入的操作，那么删除就很好理解了
- 第一种情况：删除数组中最后一个元素，是需要一步
- 第二种情况：删除开头或者中间的元素：
当我们删除索引2的值时，该位置变成空的格子，数组不允许有空格子，所以从原索引3的元素开始到最后一个元素，依次往前（原索引2的位置）挪动一格
【思考】 对一个数祖进行删除，最坏的情况为多少步？
- 最坏的情况为删除在0号索引的元素，第一步删除元素为1步，还需要把数组中剩余的元素都挪动一遍为N-1步，所以为N步。比如：5个元素，删除0号索引的元素为1步，剩余4个元素都一次挪动一格为4步，所以是5步。