数据结构学习过程详解：从入门到精通的指南

几乎是所有最顶尖的互联网和软件公司都会用算法和数据结构来考察软件工程师，然而iOS开发培训并不打算在这里再讨论算法的重要性和对实际工作是否有用（我认为这对一个优秀的程序员是不可或缺的基本技能），也不讨论「Google式」的「算法面试」和「白板编程」的有效性和合理性，仅仅是作为一个非「竞技编程」背景的工程师，分享一点自己实践过的算法和数据结构学习过程，欢迎探讨批判。

结合我自己的学习经历，以及做「信息学竞赛」教练的教学实践，iOS开发培训我通常认为下面三件事情对于学习算法是至关重要的：

一. 先练好「表达能力」

经常碰到有考研的同学问，课本上的算法我都「懂」，选择题或者手工推导过程的题目我都能做对，但是就是没法写成「代码」或者「伪代码」，因此对算法题就更加不知所措了。这在我看来，首先是缺乏「表达能力」。

除非是有经验的程序员，否则我认为学习程序语言的语法时，一开始最重要的是要学会如何「表达」逻辑和流程。很多算法竞赛书中都会有一种方法叫「模拟法」，这种方法说白了就是把我们自然地处理问题的步骤「直白」地「程序化」。比如「寻找最大数」的过程 、「矩阵运算」的过程、「进制转换」或者「求最大公约数」时用到的「辗转相除法」、模拟竖式运算的「大整数加法」等等，我们可以很直白地通过程序「模拟」这种「流程」。大多数的编程书在介绍语法时，都会提供类似这些问题的习题，帮助我们增强语言的表达能力。如果你使用Python作为主要语言，「Learn Python the Hard Way」中有大量练习表达能力的题目，学完全程，一定收获不小。「hackerrank」上有专门的「domain」练习「程序表达」，阿三哥出的题目大多数还不错。

开发一些简单的应用型「demo」，也能学会一些语言表达，但是由于其逻辑往往过于简单，并不利于这种练习。

二. 先读书再刷题

实际上真正读完《算法导论》，做过上面练习的人并不多，我更多时候是把它当做工具书查找，断断续续也只精读过部分章节。我更建议算法基础并不好的入门者选用Robert Sedgewick的《算法》，这是一本更简单易懂的书。理解算法的原理、执行过程，然后学会手工模拟过程，再尝试自己实现，在配合练习一些题目，不断强化对算法的理解。

多练习书上的习题通常会比你自己从「OJ」上找题做效果更好，尤其是一些证明和分析题并不是让你直接写代码，这样能促进对算法本质的理解。比如「快速排序」的最坏和最佳情形到底是怎么产生的，使用随机和固定策略划分优劣性分析，以及为什么这个排序算法是「不稳定」的。在此基础上再进行「OJ」上的刷题训练，提高「Coding」实现能力，加深算法理解，更加有效。

通过这种训练，至少我们对于明确算法的问题，可以正确地写出代码，再通过「debug」来解决细节问题。

三. 问题的归约和转换

有时候明确地跟有些同学说，你写个「二叉树的层次遍历」吧，他可能能写出来。但是当iOS开发培训让他在一个「无权图」上求「最短路径」时，却不知所措。甚至有时候，「图」不是一个我们「数据结构」中所学的「邻接矩阵」或者「邻接表」表示时，便不知如何把一个问题转发为「图」。他们没有理解，这里的「图」可以是一个无形的图，我们需要把某个「结点」所有相连「结点」找出来，这个找出的过程可以是一条用指针指向的「有形的边」，也可以是经过某种数学运算或者变换后得到的一个值。而像「八皇后」问题，则是我们在深度优先遍历整个状态图时，不断地检查一种状态转换为另外一种状态时的合理性，从而得到一个正确的解。我们的计算机本质上是一个「状态机」，动态规划或者搜索，都是在从状态转换中找到正确的解。关于每种具体的算法，比如动态规划、贪心、递推的意义，「quora」和「知乎」上都有很多优质的解答分析，在学习的过程中阅读，也能帮助我们解惑。

问题归约和转化，需要不断的练习。所以除了之前说的《算法》，找一本配合练习刷题的书，也是非常有必要的。我自己的学习过程中使用的是秋叶拓哉的《挑战程序设计竞赛》和刘汝佳翻译的《挑战编程：程序设计竞赛训练手册》。对于基础不太好的同学，则可以选择刘汝佳的《算法竞赛入门经典（第2版）》。

我们的目的是学习算法，而不是刷题，训练成为一名「竞技编程选手」，所以我觉得只需要选择经典的题目练习即可。我自己也不是一名「竞技编程选手」，但是通过学习和练习，除非特别「tricky」的问题，否则「Leetcode」或者「CC150」或者研究生入学考试这种难度的题目都可以轻松应对。当然，我们学习算法的目的绝不是为了面试，这对我们工作的帮助也是巨大的，这里就不展开讨论了。

当你信心满满的时候，可以尝试去解决「Leetcode」上的经典面试题，美帝大厂面试题翻来覆去都是这些题，实在是太没有创意了。或者你也可以去「hackerrank」参加企业的「招聘目的」的比赛，说不定还能翻墙去美帝,iOS开发培训认为这完全不是梦。