数据结构是一门研究非数值计算的程序设计学科，曾获图灵奖的Pascal之父Nicklaus Wirth提出过一个有名的公式：

算法 + 数据结构 = 程序

由此可见在计算机程序中，数据结构是占有很重要的位置的。一般通过计算机解决问题时，大致需要经过以下几个步骤：

（1）从具体问题中抽象出数学模型；

（2）根据数学模型设计算法；

（3）将算法用程序语言实现。

算法是人脑进行逻辑思考以后的产物，那么如何高效的实现算法，就需要一个好的数据结构来对数据进行存储及操作。

私以为对程序语言和数据结构的掌握就相当于是程序员的“内功”，虽然具体产品功能不会涉及到这些内容，但是在实际写代码的时候就关乎一个程序员代码的好坏及日后的可维护性，当我们从别人手里接过一个项目再进行维护或者修改的时候常常会吐槽“祖传屎山”，不论是代码结构还是编程风格总有一点让你很不爽，这就是我在日常工作中经常遇到的问题，相信很多程序猿/媛都会有这种感觉，所以如果你是一个有理想的程序猿/媛，尽量还是不要做被吐槽的对象哈。[手动狗头]

1 基本概念

（1）数据（Data）

数据是计算机程序处理对象的总称。例如在计算微分方程的时候处理对象就是一些数据，在图像处理中对象就是可编码的图像信息等。

（2）数据元素（Data Element）

数据的基本单位，可分为若干数据项，数据项为数据的最小单位。例如在一个学生成绩管理系统中，每个学生的成绩可以看成一个数据元素，而每个科目的成绩就可以看作不同的数据项。

（3）数据对象（Data Object）

是性质相同的数据元素的集合，是数据的一个子集。如实数的数据对象是实数集R。

（4）数据结构（Data Structure）

是相互之间存在一种或多种特定关系的数据元素的集合。

数据元素之间通常分为以下4种基本结构：

数据结构的形式定义为：

Data Structure = （D，S）

其中，D是数据元素的有限集，S是D上关系的有限集。

数据结构在计算机中的映像称为数据的物理结构，又称存储结构。数据元素在计算机中有两种存储结构：顺序存储结构和链式存储结构。在高级程序语言例如C语言中可以通过“数据类型”来描述这种存储结构，例如用“数组”来描述顺序存储结构，用“指针”来描述链式存储结构。

（5）数据类型（Data Type）

在高级程序语言中用来描述数据的特性，根据属性不同可以分为：

原子类型：例如C语言中的数据类型整型，实型，字符型，枚举类型，指针类型等。

结构类型：例如数组。

（6）抽象数据类型（Abstract Data Type，ADT）

指数学模型以及定义在该模型上的一组操作。为提高软件复用率，近代程序设计方法学中指出，一个软件系统的框架应该建立在数据之上，而不是建立在操作之上，即在软件系统每个相对独立的模块上，定义一组数据和数据的操作，并在模块内部给出这些数据及操作细节，而在模块外部使用抽象的数据和抽象的操作。

根据抽象数据不同特性，可以细分为3类：

抽象数据类型的表示：（D，S，P）

其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

抽象数据类型定义如下：

（7）多形数据类型（Polymorphic Data Type）

指其值成分不确定的数据类型。从抽象数据类型角度看，虽然数据元素类型不确定但是具有相同数学抽象特性。

2 抽象数据类型的表示与实现

本章节涉及C语言基本知识，不展开讲，只提供一个大纲供读者自行梳理。

（1）预处理

（2）结构体

（3）函数的描述

（4）赋值语句

（5）选择语句

（6）循环语句

（7）逻辑运算

3

算法及算法分析

1.算法（Algorithm）

是对特定问题求解步骤的描述，具有以下性质：

（1）有穷性：对合法输入值进行有穷步骤，且每一步都在有穷时间内完成；

（2）确定性：每条指令含义确切，对相同输入只能得出相同输出；

（3）输入：一个算法有0个或多个输入；

（4）输出：一个算法有1个或多个输出。

算法设计要求如下：

（1）正确性：算法应当满足需求；

（2）可读性：好的算法便于理解；

（3）健壮性：处理异常的能力；

（4）效率与低存储：效率指算法执行时间，用最短的时间和最少的内存来执行一个算法当然是最好的。

2.算法的复杂度

一般情况下，算法中基本操作重复执行次数是问题规模n的某个函数f(n)，算法的时间度量记作：

T(n) = O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率和f(n)增长率相同，这就叫做算法的渐近时间复杂度，简称时间复杂度。

举例

程序段1：

程序段2：

程序段3：

上面3段程序中，“x增1”的频度分别为1，n，和n^2，则这3段程序的时间复杂度分别为O(1)，O(n)，O(n^2)。

算法还会呈现更多时间的时间复杂度如下图所示：

图1 算法的时间复杂度（图源网络）

在算法设计中，尽可能使用多项式阶O(n^k)的算法，而避免使用指数阶算法。

用空间复杂度来度量算法所需存储空间，记作：

S(n) = O(f(n))

其中n为问题的规模（或大小）。

以上就是这期的文章，看完了听首歌休息一下吧。(づ￣ 3￣)づ