算法篇：什么是数据结构和算法

大家好，欢迎来到IT知识分享网。

一、什么是数据结构

官方定义：数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。
程序设计=数据结构+算法

二、数据结构中结构的概念

数据结构包括逻辑结构和物理结构

逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后关系，而与他们在计算机中的存储位置无关。逻辑结构分为以下四类：

1.集合结构
集合结构中的数据元素同属于一个集合，他们之间是并列的关系，除此之外没有其他关系。

2.线性结构
线性结构中的元素存在一对一的相互关系。

3.树形结构
树形结构中的元素存在一对多的相互关系。

4.图形结构
图形结构中的元素存在多对多的相互关系。

物理结构

1.顺序存储结构
顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。数组就是顺序存储结构的典型代表。

2.链式存储结构
链式存储结构：是把数据元素存放在内存中的任意存储单元里，也就是可以把数据存放在内存的各个位置。这些数据在内存中的地址可以是连续的，也可以是不连续的。和顺序存储结构不同的是，链式存储结构的数据元素之间是通过指针来连接的，我们可以通过用指针来找到某个数据元素的位置，然后对这个数据元素进行一些操作。

三、算法

算法就是求解一个问题所需要的步骤所形成的解决方法，每一步包括一个或者多个操作。无论是现实生活中还是计算机中，解决同一个问题的方法可能有很多种，在这N多种算法中，肯定存在一个执行效率最快的方法，那么这个方法就是最优算法。

算法的特性
算法具有五个基本特征：输入、输出、有穷性、确定性和可行性。

输入
一个算法具有零个或者多个输入。以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。

输出
算法至少有一个输出。也就是说，算法一定要有输出。输出的形式可以是打印，也可以是返回一个值或者多个值等。也可以是显示某些提示。

有穷性
算法的执行步骤是有限的，算法的执行时间也是有限的。

确定性
算法的每个步骤都有确定的含义，不会出现二义性。

可行性
算法是可用的，也就是能够解决当前问题。

四、算法的设计要求

要设计一个好的算法，需要考虑以下4个特性。

正确性
废话，谁会设计一个不能够解决问题的方法。

可读性
指算法无论是从设计思路上，还是从注释方面，都要能够保证算法是可读的，也就是可以被其他人员能够读懂的。

健壮性
通俗的讲，一个好的算法应该具有捕获异常/处理异常的能力。另外，对于测试人员的压力测试、边界值测试等刁难的测试手段，算法应该能够轻松地扛过去。

时间效率高和存储量低
这其实是两个概念，时间效率就是指的时间复杂度，存储量就是指的空间复杂度。翻译过来就是一个好的算法应该考虑时间复杂度和空间复杂度。而往往时间复杂度和空间复杂度是相互弥补的。也就是从某些角度，我们可以了通过牺牲算法运算时间的方式来减少对内存的占用，反之亦然。