数据结构与算法的奥秘

一、为什么要学数据结构与算法

在实际开发过程中你会发现，如果你不是追求极致的性能，而是单单实现需求的话，你会很少用到那些精妙数据结构与算法，你只需要掌握编程语言本身，学框架，学习一些 IT 工具的使用，至于背后的底层原理，技术实现没人关心，等你熟练掌握某种编程语言，框架，技术工具，你会发现就算你已经写了许多代码，但自己还是没有太大的进步。毕竟基本上就是对需求的实现，就好比数据库的增删改查，假以时日出现一个熟练掌握这些技术的年轻人，将会很快的替代你，毕竟更便宜更高效的谁不喜欢呢。

学习算法与数据结构还有其他方面的原因：

面试大厂

　 无论是校招还是社招，大厂都喜欢让人手撕算法代码。

理解类库的原理

想要用好开源的类库，你必须要了解和熟悉其类库实现的原理，如果你不懂如何分析时间和空间的复杂度分析，你又如何能用好它们

理解基础框架

如Spring，rpc框架，消息中间件，redis等等基础框架中，一般都融合了许多的基础数据结构和算法的设计思想

编程能力

性能好坏是该能力的一个非常重要的评判标准，如果连程序的时间、空间复杂度都不会分析，很难写出性能较优的代码。

二、什么是数据结构​​

公司开发一个客服电话系统，小菜需要完成客户排队模块的开发，经过三次修改：

　　第一次：小菜使用了数据库设计了一张客户排队表，并且设置了一个自动增长的整型 id 字段，来一个用户，就在这张表的末尾插入一条数据，等客服系统一空闲，就将表中最前的的客户提交，然后删除这条记录。

　·实时排队模块，在内存中实现即可，无序用数据库

　　第二次：小菜用数组变量重新实现了这个功能，害怕数组不够大，选择远大于实际情况的 100 作为数组长度

　　·数组虽然可以满足一定需求，但是需要考虑溢出问题，以及新增和删除后的数据移动，显然不是很方便

　　第三次：小菜使用了数据结构中的 “队列结构” 终于满足了需求

　　说明：此例子归纳参考自《大话数据结构》

传统上，我们把数据结构分为逻辑结构和物理结构。

　　逻辑结构：是指数据对象中数据元素之间的互相关系，也是我们今后最需要关注和讨论的问题。

　　物理结构：是指数据的逻辑结构在计算机中的存储形式。

　　数据：是描述客观事物的数值，字符，能被输入机器并且被处理的各种符号集合

　　数据项：是不可分割的最小数据，具有原子性

　　数据元素：是数据的基本单位，是数据集合的个体，通常由数个数据项组成，在程序中作为一个整体来处理

　　数据对象：是性质相同的数据元素的集合，是数据的子集

　　数据结构：是数据元素相互之间的某种特定关系，即一个数据是以什么方式构成的，什么结构构成

　　数据结构=逻辑结构+存储结构+操作/运算

三、什么是算法

小菜公司因为某种原因资金运转不过来需要裁员，小菜因为队列业务出现问题被裁了，小菜不甘心来到了图书馆，想学习算法提示自己。

小菜向管理员提出要借看计算机算法概论这一本书。管理员从头开始一步一步查找，找了两个小时小菜心想不对呀，这么找下去什么时候是个头。小菜打算自己去找。

小菜先来到计算机类的书架上，再查找想要的书的首字母拼音以及类别结果不到十分钟就找到了。

毫无疑问，从上面例子可以看出无论是图书管理员的顺序查找还是小菜的分类查找都是算法的一种。

怎样选择合适的方法解决需求就是我们学习算法的原因。

　　算法的五个基本特征：

　　输入、输出、有穷性、确定性和可行性。

　　输入：算法具有 0 个或多个输入。

即小菜提出想要一本计算机算法概论

　　输出：算法至少有一个或多个输出

即返回有与没有

　　有穷性：算法在执行有限步骤后，自动结束而不会出现无限循环。

即如果没有图书管理员不会重复查找

　　确定性：算法的每一个步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。

即图书管理员不会去其他地方找到这本书，只会在本图书馆内。

　　可行性：算法的每一步都必须是可行的，也就是每一步都能通过有限次执行完成。

即图书管理员查找方式是合理的，不会一直重复某一步骤。

算法设计的要求：

　　正确性：算法至少应该具有输入、输出和加工处理无歧义性、能正确反应问题的需求、能够得到问题的正确答案。

　　大体可以分为以下四个层次：

　　算法程序没有语法错误

　　算法程序对于合法输入能够产生满足要求的输出。

　　算法程序对于非法输入能够产生满足规格的说明

　　算法程序对于故意刁难的测试输入都有满足要求的输出结果。

　　可读性：算法设计要便于阅读、理解和交流

　　健壮性：当输入数据不合法时，算法也能做出相关处理，而不是抛出异常或者崩溃。

　　时间效率高和存储量低　

四、算法与数据结构

　　数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

　　数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。 因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。

　　数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构就是没用的。

下图是算法与数据结构的思维导图。

最后

经过上面的描述，可以看出为什么算法与数据结构会成为计算机专业的核心课程，数据结构就好比是躯壳，算法就像是灵魂。好的躯壳能让你吸引到其他人，有趣的灵魂会让人对你着迷。二者相辅相成，缺一不可无论是缺少灵魂的肉体亦或者是没有躯壳的灵体对人来说绝对不是值得吸引的东西。

扎实的数据结构与算法基础，能大大提升面试通过率，大大提升对语言、框架和工具的理解层次，大大提升编程和设计能力。

因作者水平有限，部分地方出现纰漏在所难免，望读者指正批评。