算法：2. 数据结构

数据结构的作用

算法有一种简单的定义，即算法是对某一数据结构进行的正确操作。数据结构是算法的关键之一。以二分法为例，二分法需要数据结构是有序的。

例子：

在0~10之间找到6，如果数据结构是无序的，如{2,5,10,3,0,7,8,9,6,1,4}。根据二分法，会选择7，发现偏大，那么就会在第1到第5个元素中选择10，发现又偏大，那么会在3和0中选择，而6并非在这个区间，最终查找失败。

相关链接：使用python进行简单的二分法操作

数据结构的类型

我们将数据结构想象成一个有无限格子的柜子。每个格子依次摆放且有序号，如0，1，2，3...

1.数组

数组需要一段连续序号的柜子放置数据。放置10个数据，那么数组需要连续10个序号的格子进行存放，可以存放在0~9这10个连续的格子里。

2.链表

同样存放10个数据，链表不一定需要连续10个格子。因为链表将一个数据存放在格子后，会指明下一个存放格子的序号。比如，链表的第一个数据放在序号10，然后指明下一个数据存放的地址是8，按照这样的方法存放10个数据。

两种数据类型的比较

表1 数组和链表的比较

(相关链接：算法：1. 算法复杂度)

解释：

1. 数组由于是连续存放，所以找到其中1个数据，就可以找到其他数据。但是，在进行插入和删除操作时，需要同时调整在插入或删除点之后的数据，这需要较多的操作数，所以数组比较适用于查找。

2. 链表是非连续存放，需要指明下一个序号，才能去查找。但是由于是非连续的，所以可以很好进行插入和删除，只需要表明插入或删除的序号即可，所以链表比较适用于操作。

我们的公众号：认知无线电

我们的网站：www.lolplayer.club

欢迎关注和指正