02.预备知识：概念和存储结构

大家好，我是王有志。今天是非常简单的两部分内容：

• 数据结构和算法的概念
• 数据的物理存储结构

数据结构和算法是什么？

我们先来看数据结构的定义：

在计算机科学中，数据结构（英语：data structure）是计算机中存储、组织数据的方式。

通常意义上，我们所说的数据结构指的是组织数据的方式，是逻辑关系，并且对大部分数据结构来说，数据的逻辑组织形式和物理存储结构是大相径庭的。

接着我们来看算法的定义：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

从定义中，我们可以看到，算法是解决问题的清晰指令。

再来补充下邓俊峰老师的解释：

所谓算法，是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。

邓俊峰老师指出了很重要的一点，算法是基于特定计算模型的，而这个特定计算模型就是我们所说的数据结构。

结合以上的解释，我们不难得出以下结论：

数据结构是数据的逻辑组织形式，算法是作用在特定数据结构上，用于解决问题的准确完整的程序指令。

物理存储结构

这部分知识涉及到《计算机组成原理》的内容，因此只做一个简单的说明，方便理解后面的内容。

内存地址

内存地址是为了定位内存中的数据而给每块内存分配的编号，使用十六进制数字表示，如：0xf0000000。在计算机中，容量以字节为基本单位，每个字节都有自己的地址编号，每4个字节的内存空间为一个单元。

实际上，内存地址可以分为：逻辑地址，线性地址和物理地址。不过在数据结构和算法的内容中，我们统一看做是内存地址就好了。

物理存储结构

假设有一块20个内存单元的空闲内存空间：

xjczSLMrdGEjMbIL_9QkgsgNheGNyPcdDR66DgDsfqc.png
此时我们为数组分配5个内存单元（因为数组的特殊性，需要每个内存空间连续）：
BVMfaNPJMoEFj6qGRQJT_md_ohE9B1h5ZVPKsTePyGk.png
因为内存空间充足，很容易就分配了5个地址连续的内存单元给数组，我们把逻辑上相连，且物理位置上相连的存储方式称为顺序存储结构。
如果内存已经被使用过了呢？
WnYsBMtQsBnbhkTVdno-IRsSnhpAnvsfiY2cuYrABZ0.png
虽然剩余了9个内存空间，但因内存空间物理位置上不连续，所以无法在这块内存上分配数组。那么这块内存就要“浪费掉”吗？

克里夫肖（Cliff Shaw）和赫伯特西蒙（Herbert Simon）想到了一种“链式”的方式，来达到逻辑上“连续”。

uMt6ffq8l87FxbnsowwJZyHHQa44LUAcyE9mTfVprqk.png

可以将5个空闲的内存空间“串”起来，这种逻辑上相连，物理位置上不相连的存储方式称为链式存储结构。

结语

今天的内容到这里就结束了，我们来回顾下都聊了哪些内容：

简单的了解了数据结构和算法的概念，需要再次说明的是，通常我们说到数据结构，指的是数据逻辑上的组织形式，最后了解了数据在内存上的物理存储形式，实际上我们之后所见到的数据结构，主要是链式存储结构。

---

好了，今天就到这里了，Bye~~