第2章　数据结构与算法

2.1　引言

瑞士计算机科学家尼古拉斯·沃斯（Niklaus Wirth）提出了一个著名公式，即“算法+数据结构=程序”（Algorithms+Data Structures=Programs），算法与数据结构对于程序设计的重要性不言自明。

程序是计算机指令的各种组合，用于控制计算机的工作流程完成一定的逻辑功能，以实现某种任务；算法则可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成是按照要求设计好的有限且确切计算序列，并且这样的计算序列可以解决一类问题。算法是程序的逻辑抽象，是解决某类客观问题的数学过程。一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的，这种数据元素间的逻辑关系称为“数据的逻辑结构”。数据结构具有两个层面上的含义，即逻辑结构和物理结构，客观事物自身所具有的结构特点称为“逻辑结构”。例如，家族谱系是一个天然的树型逻辑结构；逻辑结构在计算机中的具体实现则称为“物理结构”，如树型逻辑结构具体是采用指针表示还是数组实现。

许多大型系统的构造经验表明系统实现的困难程度和系统构造的质量都严重地依赖是否选择了最优的数据结构。许多时候确定了数据结构后，算法就容易得到了。当然有些情况下事情也会反过来，即根据特定算法来选择数据结构与之适应。

总的来说，数据结构和算法并不是一门教授如何编程的课程。它们可以脱离任何计算机程序设计语言，而只需要从抽象意义上概括描述。说得简单一点，数据结构是一门教授数据在计算机中如何组织的课程，而算法是一门教授数据在计算机中如何运算的课程，前者是结构学；后者是数学。程序设计就像盖房子，数据结构是砖和瓦，而算法则是设计图纸。若想盖房子，首先必须要有原材料（数据结构）；其次必须按照设计图纸（算法）一砖一瓦地盖。数据结构是程序设计的基础，算法则是程序设计的灵魂，是程序设计的思想所在。在程序设计中，数据结构就像物质，而算法则是意识。双方相互依赖，缺一不可。