计算机思维: 计算机的数据结构

引言

工具的发明是针对问题来的:

a、在数学上要计算数字，人类就发明了算盘。b、在物理学上，要测量绝对的数值，人类就发明了各种度量长度的尺子、计时的钟、称重量的天平和秤等等。c、在化学上，要测量化学反应的当量，人类就发明了各种有刻度的量器。

在计算机科学中，数据的相对大小比绝对的数值重要，出于很多数据比大小的需求以及其他一些需求，就产生了一个抽象的数据结构——二叉树。

I 计算机的数据结构

数据结构+ 算法 = 程序

理解搭建计算机软件的模块——数据结构和算法。

• 把数据结构理解为盖房子的钢筋、门窗和大梁。
• 把算法理解成盖房子的结构原理。

1.1专业画家画金鱼的方法

1. 把金鱼分解成几个简单的几何图形，比如头是一个大圆和两个小圆（即两个眼睛），身子是一个椭圆，鳍和尾巴是几个三角形。
2. 如果是几条金鱼，先把位置安排好，为了画面美观，主要景物的布置要符合一些几何图形的形状。这些都用淡淡的铅笔或者淡墨勾好了，才把圆、椭圆和三角形经过平滑过渡，画成金鱼。

1.2 数据就等同于点，数据结构就是数据中常用的具体关系

写一个能够完成特定功能的程序，就相当于是作一幅画。

一幅画是点的有机组合，几何图形反映出点之间常用具体的关系。在计算机科学中，数据就等同于点，数据结构就是数据中常用的具体关系。

1.3 线性表

线性表相当于几何图形中的直线，是最基本的数据结构，概括所有顺序排列和储存的数据。

具有线性表性质的例子：

1. 报表、物资的记录可以被抽象为线性的数据，然后按照1、2、3、4、5的顺序排列出来。
2. 电商交易的日志记录是按照所发生的时间顺序，一条条线性地记录下来。

计算机中线性表的实现方法

• 数组：一组编了号的固定大小的单元 。

数组的好处：给定一个序号，可以直接找出里面的内容。 缺陷：插入新数据非常困难

• 链表: 如同买东西时排队一样，每个人只要记得前面或者后面的一个人是谁。

为了优化数组的新增数据带来的大量的位置移动，而产生的。 好处：新增数据的时候，只要修改对应的指针即可 缺点：查找效率不高

II 数组、链表和哈希表

数组、链表和哈希表，它们有一些相关性，但是使用的目的有区别。

2.1 数组

是为了便于直接查找访问，它要求数据项基本上是整齐的.

2.2 链表

强调的是前后的依赖关系，一个连着一个，比如某个学位选课的次序，一门课和它的先修课就是这种链接关系。

2.3 哈希表

本质是通过随机化，把一个比较大的、稀疏的空间，映射到一个比较小的、紧密的空间中。在计算机中，它通常是通过数组实现的。相比一般的数组，它有三个优点：

1. 动态增加或者删除一个数据项比较快。
2. 数组只能根据下标直接查找，下标和数据内容无关，如果要根据内容查找，效率就比较低，哈希表的下标是根据数据内容计算出来的，因此根据内容查找比较快。
3. 数组在处理多个维度时变得很复杂，哈希表可以将多个维度的数据映射到一个维度。但是，哈希表是需要额外成本的，它其实是以空间换时间。其次，数组可以一次顺序存取很多项数据，而哈希表存取数据只能一个个进行。

2.4 小结

1. 使用基本图形、结构和组成部分来构建复杂设计和产品的方法：

要想完成复杂的工作，必须掌握所谓科班出身人士掌握的工具和方法。另外，专业人士会把复杂的东西分解为简单的基本单元。

1. 在计算机领域，数据结构则相当于设计中的基本几何图形，它们大多是从具体的应用中抽象出来的;

一个从业者水平的高下，首先在于灵活使用这些数据结构的本领。

1. 凡事有一利就有一弊

III 索引带来搜索的效率、灵活性

Google在建索引时，是对所有的词建索引的，而不仅仅是对于一些重要的词建立索引

一般索引只会根据一个维度的信息建立，而不会用几个维度的组合信息建立，比如，不会建立“人名＋毕业学校”这样的索引。

对索引进行查询的公式：将关键词变成一个编号，然后再取尾数（火车安排座位，座位号重合的，就就近坐下）-> 伪随机数 -> 数据加密->公开密钥

Google是如何找到和下载所有网页的？（如何构建一个网络爬虫？）

IV 二叉树的来源

1. 二叉树的来源:https://blog.csdn.net/z929118967/article/details/123693521?spm=1001.2014.3001.5501
2. 二叉树的应用:https://kunnan.blog.csdn.net/article/details/115935678

在计算机中，由于经常要做的事情是判断真假、比较大小、排序、挑选最大值这类的操作，而它们在计算机的世界里又如此重要，当然也就值得为这些事情专门设计一种数据结构，这种数据结构被称为二叉树。