01 为什么要学习数据结构与算法

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

一、问题提出

最早计算机的设计初衷主要用于军事上枪炮的弹道计算和火力表的测试，后来更多的用于科学计算，即数值类的计算，而现在，计算机深入到日常生活的各个方面，其计算的数据早已从数值数据扩展到字符、表格、图像、音视频等非数值型数据，而如何有效的组织这些数据、高效的处理这些数据，则成了计算机学科的一大研究重点，而这也是数据结构所研究的主要问题。

例如，实现一个学生管理系统，对于学生数据的组织就体现出了数据结构的作用。如何实现这个系统？

定义5个变量来描述这一个学生的5个信息，但是如果有100个学生，那就需要定义500个变量：

在这里插入图片描述

或者按照学生的信息类型定义5个数组：

在这里插入图片描述

又或者，定义一个结构体用来表示一个学生的信息，定义1个数组来存储100个学生的信息：

在这里插入图片描述

更进一步，可以实现一个链表来管理这些数据：

在这里插入图片描述

对学生信息的处理经过了以下的变化

在这里插入图片描述

再比如，我们需要完成跟省、市、地区相关的数据处理，那么可能会考虑采用树形结构：

在这里插入图片描述

选用一个合适的数据结构对程序设计是一件非常重要的事情。

确定了数据结构之后还不算结束，在完成一个常用的操作，比如说查找和排序上，还将有不同的实现方式，而不同的实现方式所带来的时间、空间成本则是完全不一样的，这些则是算法需要解决的。

算法是为了描述实现某种操作而设计的对数据的组织方式，对某一个操作可能会设计出很多种解决的方式。

比如一个经典问题：“从1累加到100，结果是多少？"

采用简单粗暴的方式，慢慢累加就可以了，但是这个过程是漫长枯燥的，我们可以交给程序来进行：

int i = 0, sum = 0;
for (i = 0; i < 101; i++) 
{sum += i;
}

或者优化一下：

int i = 0, j = 0, sum = 0;
for (i = 1, j = 100; i < j; i++, j--) 
{sum += (i + j);
}

观察这两种求和操作，虽然都能解决问题，但是比较一下就会发现，第一种循环中的求和语句共执行了100次，而第二种却只执行了50次，速度明显提高一半。

甚至我们可以采用数学王子高斯的解决方案：

int sum = (1 + 100) * 100 / 2;

只用执行一次，相比于第一种方法效率直接提升了百倍。

可以看出，采用不同的算法所花费的时间和计算过程是不一样的。这还仅仅是一个比较简单的示例，当我们学习过各种查找和排序算法后，我们就可以知道什么样的算法在什么样的数据结构下更合适，采取哪种算法对于成本的要求更低，等等，甚至可以设计和创造出新的更优秀的算法出来。

二、数据结构与算法是什么

早期计算机是因为方便数值计算而设计产生的，但是慢慢随着人们的研究，计算机也开始被应用到逻辑计算领域，并以强大的生命力飞速发展，对人类的生产活动和社会活动产生了极其重要的影响。

计算机解决问题时，先分析业务逻辑，从具体问题中抽象出适当的数据模型，然后提取算法，编写程序，最终得到一个现实项目应用软件。可随着大数据的处理问题、高效率的要求，简简单单地研发一个使用软件已不能满足时代发展要求，需要更加科学有效的手段给于辅助，“数据结构”的概念因此产生。

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合**。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。1968 年，美国的高德纳教授在其所写的《计算机程序设计艺术》第一卷《基本算法》中，详细阐述数据的逻辑结构和存储结构及其操作，开创了数据结构课程体系。同年，数据结构作为一门独立的课程，在计算机科学的学位课程中开始出现。

随着大型系统的诞生和使用，人们越来越重视数据结构，而且在结构确定后，程序执行的过程也被重视起来，人们将此称之为算法。算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

数据结构是处理数据存储的方式，而算法是处理数据执行步骤的方法，程序设计的实质就是对确定问题选择一个较合适的存储结构和一个合适的算法。因此也提出了这样的一个公式：

程序设计 = 数据结构 + 算法