数学和计算机科学板块_辛酸网

数据结构与算法1

BY TSherry

什么是数据结构

在计算机中（当然也包括但不限于手机）我们要存储各种数据，有真正意义上我们要保存的东西，放在硬盘、光盘、作为文物的软盘、储存卡等。同时也有在计算机工作过程中需要临时存储的内容，就比如说你要计算两个数的加法，在得知两个加数以后就得写在草稿纸上，这时的草稿纸就起到寄存器和内存的作用。不过，内存的空间要远远大于寄存器。而我们要临时存储的数据，相互之间往往是有关联的。如何存储数据，具体的数据放在什么地方，数据和数据之间是什么关系，这就是数据结构的问题。数据结构，就是内存里数据的内容和关系，整体上存在着的一种结构。不过，这个结构既是逻辑性的，也是物理性的。毕竟内存里的每一个字节都是有编号的，给定数据以后怎么确定放在内存里的什么地址，这还真的是一个值得思考的问题。

这些资料是假设读者知道什么是指针而编写的，如果不知道什么是指针，建议先去看看相关内容。

数据结构的分类

数据结构的分类，说到底就是物理和逻辑关系的分类。很多东西我们知道是有顺序的，但是也有很多东西是没顺序的；很多东西是挨着的，但是也有不少东西相互之间是隔开的；很多东西和其它几个玩意可能具备某种关系，然而很多东西却可能只和一个玩意才有某种关系。所以，各种各样的东西在内存中的存放，是大不一样的。如果我们把一些东西一个接一个地在内存真的就紧挨着存放了，那就是顺序存储；如果这些东西分开了放，为了追踪其它东西到底在什么地方就要用指针，那就是链式存储；如果这些指针不是在数据元素之内而是另外搞了一个表格记下来，那就是索引存储；如果地址和元素的值（其实就是特征关键字）之间有函数关系，那就是哈希。

一方面数据和数据之间的关系不一样，另一方面数据在的内存中的存储方式也不一样，所以你看数据结构是有很多很多种类的。学过C语言的都知道有一个玩意叫数组，对于Python而言它分裂为集合、元组、列表和字典等好几个概念（除了Numpy）。在C语言的数组中，不同的东西我们可以发现是一个一个紧挨着的。要是一维数组的话，最前面那个元素的地址同时也是数组这样一个整体的地址。要是指针往后面一滑，就可以访问到后面的元素。至于这数据元素是什么东西，管它是什么东西，反正就是东西。

上图描绘了几种比较常见的数据数据结构，但是也有几种常见而没画上去的，~~不要问为什么，问就是我懒得画。~~一般来说，我们接触到的数据结构大致有线性表、树、图、哈希四类。其中线性表按照元素之间是否在物理上挨着，分为顺序表和链表；按照具体操作在什么地方分为一般意义的线性表、栈、队列三类。其中只能在一头插入，同一头弹出的叫栈，一头插入，另一头弹出的叫队列。我们在C语言等语言中涉及的数组就是最基本的顺序表的形式。

树，有一般的树，有不一般的树。其中如果边有方向的就是有向树，没方向的就是无向树；有根节点的叫有根树，没根的叫无根树。通常而言在中国大陆的大学本科教育体系中，专门讲数据结构的课程里，涉及到的树都是有根无向树。不过在离散数学里就不一样了，老师应该会强掉离散数学的研究范围比数据结构在某些方面大些。

对于图而言，边有方向的叫有向图，没方向的叫无向图；如果边上带了一种特别的值，不同边上的这种值可以相加，那么这种值就叫做权，有权的叫有权图或者带权图，没权的就是无权图。如果任意两个结点都是直接连起来的，就是完全图，不是完全图的，和对应的完全图对比一下，从完全图中去掉自身的边和结点，剩下的就是补图。现在我们再看图的连通性问题：不管它有没有方向先当成无向图看看，要是任意两个结点之间都能过去，管它直接还是间接过去，都是弱连通图；要是有向图的话就要再看看边的方向，沿着这些方向看看能不能过去，要是任意两个结点之间都能过去那就是强连通图。

没错，所有的强连通图，都是弱连通图。