第1章-数据结构与算法是什么

在计算机科学中，数据结构（Data Structure）是计算机中存储、组织数据的方式。为什么数据结构和算法经常放在一起讨论？算法用来设计一种使用计算机来解决问题的方法。设计高效的算法又是怎么来实现的？在我们学习了计算机编程后，也要学习数据结构与算法这些基础内容。

一、数据结构

人们常说： 程序 = 数据结构 + 算法 ，当遇到一个问题，或有一个需求时，在设计程序来解决问题时，其中重要一步就是设计数据结构，数据结构在问题解决中主要用来：

• 存放要处理的数据
• 实现算法策略

数据结构可以用一个四元组来表示：

DataStructure = (D, L, S, O)

它包括数据元素（D）、数据元素之间的逻辑关系（L）、逻辑关系在计算机中的存储结构（S）和所规定的操作（O）这四部分。

1. 逻辑结构

逻辑结构是指数据元素之间客观存在的关系，和数据在计算机中怎么存储无关，主要用于人们理解和交流以及指导算法的设计。逻辑结构分为四类：

• 线性结构 ：数据元素之间存在一对一的关系
• 树形结构 ：数据元素之间存在一对多的关系
• 图形结构 ：数据元素之间存在多对多的关系
• 集合结构 ：数据元素属于同一个集合

学习研究了这四种逻辑关系是如何存储与操作后，以后我们要解决任何问题，只要分析出要解决问题的数据关系，都可以通过这四种逻辑关系来思考，如果关系比较复杂，也是由这四种关系组成的，只要一层一层地分析就可以了。

2. 存储结构

逻辑结构主要用于算法设计，而存储结构用于指导算法编程实现。存储结构有基本的两种结构：

• 顺序存储 ：逻辑上相邻的元素存储在物理位置相邻的存储单元中
• 链式存储 ：在数据元素中添加一些地址域或辅助结构，用于存放数据元素之间的关系

顺序存储结构在内存中的地址是连续的，所以存取速度很快，但是在插入或删除操作效率低，因为插入或删除操作会移动数据元素。

链式存储结构在内存中地址可以是不连续的，插入和删除操作效率高，因为增加了寻址的操作，所以查找和遍历效率低。

同样的逻辑结构（线性、树形、图形、集合）既可以采用顺序存储结构也可以采用链式存储结构来存储数据和关系。 存储结构的选择主要考虑算法的效率，算法的时间和空间哪个更好，具体选择哪种和需求有关， 基本存储结构既可以单独使用，也可以组合使用。

3. 运算操作

数据结构中的操作主要是指数据元素的查找、插入、删除、遍历和排序等等，具体需要实现的操作根据业务需求确定。

二、算法

算法用来设计并实现一种用计算机来解决问题的方法。它满足下列性质：

• 输入 ：有零个或多个输入量
• 输出 ：产生至少一个输出量
• 确定性 ：算法的指令清晰、无歧义
• 有限性 ：算法的指令执行次数有限，执行时间有限

在使用计算机解决问题的过程可以分为下面五个步骤：

1. 问题的理解 ：搞清楚问题的输入、要求和输出
2. 数据结构设计 ：设计能处理问题中数据的数据结构，还要设计能支持算法策略的数据结构
3. 算法设计 ：选择算法策略，用适当的方式描述和逐步细化算法步骤
4. 算法分析 ：发现有优化的地方，返回第二步，重新设计数据结构和算法
5. 程序实现 ：用计算机编程，定义数据结构，编写代码实现，并调试和运行

一个需求问题有多种解决方案，我们经常需要通过不断尝试和积累经验才能找到最好的方案，如果熟练掌握了基本的数据结构和算法，对于在设计高效算法中是有很大帮助的，能更高效地解决需求问题。