数据结构与算法的魅力（一）

一、数据结构

1、概述

数据结构是是带有结构特性的数据元素的集合。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

数据结构中最基本的五个概念：数据,数据元素,数据项,数据对象,数据结构;

1.1数据：

是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

1.2数据元素:

是组成数据的,且有一定意义的基本单位,在计算机中通常作为整体处理. 也被称作"记录"

1.3数据项

 一个数据元素可以由若干数据项组成。数据项是数据不可分割的最小单位

1.4数据对象

是性质相同的数据元素的集合,是数据的子集.

1.5数据结构

结构,简单理解就是关系. 比如分子结构,就是说组成分子原子的排列方式. 不同数据元素之间不是独立的,而是存在特定的关系.我们将这些关系成为结构. 那么数据结构是什么? 数据结构是相互之间存在一种或多种特定关系的数据元素的集合.

2、逻辑结构和物理结构：

数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。

数据的逻辑结构：

指反应数据元素之间的逻辑关系的数据结构，其中的逻辑结构是指数据元素之间的前后关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

1、集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

2、线性结构：数据结构中的元素存在一对一的相互关系；（例如：线性表，栈，队列等）

3、树形结构：数据结构中的元素存在一对多的相互关系；（例如：二叉树，哈夫曼树等）

4、图形结构：数据结构中的元素存在多对多的相互关系。（例如：邻接矩阵）

数据的物理结构：

指数据的逻辑结构在计算机存储空间的存放形式

通常包括：顺序存储结构和链式存储结构

设计好逻辑数据结构之后,数据的存储也是非常重要的. 数据存储结构应该正确反映数据元素之间的逻辑关系.这才是关键! 如何存储数据元素之间的逻辑关系,是实现物理结构的重点和难点.

抽象数据类型：

1.1数据类型

在C语言中,按照取值不同,数据类型可以分为2类:

原子类型: 是不可以在分解的基本数据类型,包含整型,浮点型,字符型等;

结构类型: 由若干类型组合而成,是可以再分解的.例如,整型数组就是由若干整型数据组成的.

1.2抽象数据类型

是指一个数学模型以及定义在该模型上的一组操作; 例如,我们在编写计算机绘图软件系统时,经常会使用到坐标. 也就是说,会经常使用x,y来描述横纵坐标. 而在3D系统中,Z深度就会出现. 既然这3个整型数字是始终出现在一起. 那就可以定义成一个Point的抽象数据类型. 它有x,y,z三个整型变量. 这样开发者就非常方便操作Point 数据变量.

二、算法

1、什么是算法？

算法是指解题方案的准确而完整的描述，在计算机中表现为指令的有限序列列,并且每个指令表示⼀一个或多个操作。

2、算法的特性

1、输入输出

2、有穷性

3、确定性

4、可行性

5、正确性

6、可读性

7、健壮性

8、事件效率高和存储量低

3、算法的评估

同一个问题可用不同的算法解决，而不同的算法，也可能可以解决多个问题。而一个算法的质量优劣将影响到算法乃至程序的效率问题。我们对算法的分析的目的就是选择合适算法和改进算法。

一个算法的评价主要从时间复杂度和空间复杂度来考虑

时间复杂度：

指算法需要的计算工作量，通常我们所遇见的时间复杂度包括：

其中：O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

空间复杂度：

算法的空间复杂度是指算法需要消耗的内存空间

通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句句关于n所占存储空间的函数

算法就简单介绍到这里！

转载至：

https://juejin.im/post/5d6a2fa85188255eef1a7199

https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450?fr=aladdin