数据结构与算法原理基本关系和原理

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

那我们计算机中有哪些常见的数据结构了？数据结构与算法又有什么关系？数据结构和计算机底层联系是否非常紧密？基于这些问题，同时为了方便的理解数据结构，我们尽量使用高级一些的语言（python、Java、C++、C）虽然数据结构与堆栈、甚至用汇编中的概念会更深入理解一点，但实际上我们实践操作是不需要这么深入了解到这么细致的。（当然这里我会将汇编和各种高级语言混合在一起进行操作，这样的话，理解起来就轻松一点，强调一点，写博客喜欢从原理性的东西说起，所以要是有大佬精通这一块的跳过，或者指出错误，(*￣)￣））

首先我们知道CPU是控制整个计算机的运作和计算的，所以CPU在物理上是不进行数据的存储（CPU也可以寄存少量数据）。数据一般存放到内存这样的存储器中，而CPU只负责写入或者读取内存上的数据（实际上内存上的可能不是数据也有可能是指令）CPU主要通过地址线和数据线去读取内存（内存在物理上是一个一维的线性空间），那这里我通过汇编（因为汇编语言和机器语言是一对一的关系）演示一下,我们看看平常的数据结构在物理内存上的表示和我们的有什么不一样（当然数据结构可以不需要了解底层，但是深入了解后我们印象可以更深）

首先我们假设在python中写了如下程序（这里会将python 中的程序用汇编解释）：

以上程序在高级语言中的数据结构很简单

1.将数据存到数组中

2.进行求和存到一个变量中

那计算机中操作怎样将数据存到内存并运算的了，数据在内存中怎样保存的了？

我们现在一步步来，首先我将如上步骤翻译成汇编语言如下（看不懂汇编没关系，后面再说这个数据的结构的原理和特性）：

这里的汇编语言是直接运行在intel x86环境（64位不容易观看）我们直接用vs2015打开（在校企的的那段时间学的是C#，但是这个工具编写汇编也是很友好和强大的），现在一步步讲解那段代码的一个运行过程。

汇编运行过程是：汇编语言-编译成机器语言（即0-1用来驱动计算机电子元件）-通过链接器-cpu执行这段程序。

大家可以看到首先，我们的程序会向CPU发送指令（不同的计算机厂商，会有不同的内存指令操作）申请一段内存，这段内存段没有程序使用，并是空闲的，并将数据写入到内存中。

这里用的是16进制表示法，实际在计算机硬件中是二进制高低电平表示，但是一般我们书写表示方法都习惯用16位进制表示。

我们取到getMoney钱这个数组内存地址的起始位置，并放到寄存器（cpu运算数据都是直接读写到寄存器，实际上在高级语言中这个地址就是我们说的指针，只是这个内存地址我们没有用变量存起来）

由于内存地址在物理空间上是一维的（据说目前打算用二维的甚至三维的内存，咳咳，废话说多了）

所以我们需要知道数组大小，和这个数据每个所占用的字节（所以一般高级语言显示或者隐式的声明这个数据类型，就是想知道这个数据在内存中占用多少字节）用于循环累加，这里的累加使用的是硬件上的加法器如下格式：

我们可以看到如下图中执行的过程

很明显最后CPU加法器运算出来的结果和我们在python中输出的结果是一致的：

我们通过上述的例子可以看到数据就存储在这个内存上，复杂的数据结构表示也仅仅是在内存上存指向某个内存块的地址，所以我们可以将数据结构抽象出来，我们不用去关心这个数据怎样在计算机中何种实现，只关心数据集怎样进行组织存储。

以下是我们常见的数据结构：

我们可以举一个数据结构影响效率的例子。

如下：

同样的字符串相加的操作前者比后者慢了上百倍，导致这个的原因是因为字符串的数据结构是堆栈，而字符生成器使用的数据结构是链表，这样说可能很抽象，我这边画一个图形就好理解了。

第一个使用字符相加的时候，每次相加就重新申请一个可以容纳该字符加上已有字符的内存空间：

第二个使用字符生成器时，每追加一个字符，就申请一个可以容纳该字符的内存空间，并使末尾存入指向该字符的内存地址：

从效率上将第二个是非常高的。

除了数据结构外，算法（实际上算法就是解决问题明确而有限的步骤，不要想的有多高大上）也在程序中对效率影响很高，这里我直接用python举一个例子（这个例子是1+2+3…+100000 算出结果）：

如上程序我们严格按照一般算法RAM模型指令代价

第一个累积函数执行的这几条语句所需的指令代价为：

S1=n*c1+n*c2+n*c3 (这里的n=1000，c1、c2、c3为每条语句执行的代价常量---计算机使用时钟震荡一般是固定的，我们这里不考虑内存访问层次需要的时间)

提取公因式

S1=n(c1+c2+c3)很明显消耗时间是线性的。

第二个相加之和执行语句所需要的代价为：

S2=c1

从该模型理论上来讲S2耗时应该来说是非常短的，我们实际运行一下：

那算法和数据结构又怎样联系了，事实上我们知道qq空间中的评论这种数据像一颗树如下:

我们常规的数据库是关系型数据库，这样存放评论信息也可以做到评论与评论和回复之间相关联。

但是我们要进行用户相关性计算的时候，除了考虑相似度算法，还需要考虑合理的数据结构，这样用于分层或者别的计算时，算法可以不仅可以节省指令运算的时间，同时取数据，存数据的时间或者空间也大大节省，这样程序在性能上会有飞速的提升。

所以以上回答了所有问题，接下来写的文章大多是与数据结构和算法相关的，这样不仅仅对自己深入理解，也可以和大家讨论。