前言

如何有效地组织数据和处理数据是软件设计的基本内容，直接关系软件的运行效率和工程化程度。早期计算机处理的对象多为简单的数值数据，而现在，计算机应用远远超出了单纯进行数值计算的范畴。

用计算机解决问题主要通过以下3个步骤：

1. 抽象求解问题中需处理的数据对象的逻辑结构；
2. 根据求解问题需要完成的功能特性实现存储结构表述；
3. 确定为求解问题而需要进行的操作或运算。

基本概念

数据

数据除了整数、实数等数值数据外，还包括字符串等非数值数据以及图形、图像、音频和视频等媒体数据。

数据项和元素

数据项是数据元素的组成部分，也可称之为字段和域。如书籍列表中的“书名”和“出版社”就是数据项（字段或域）。

数据元素又称元素、节点，是一个数据整体中可以表示和访问的数据单元。如书籍列表中的每一行就是一个数据元素，是数据项的集合。

逻辑结构

数据的逻辑结构是指数据元素之间存在的逻辑关系。数据的逻辑结构与数据的存储结构无关，独立于计算机，是从具体问题抽象出来的数学模型。

集合

集合中数据元素的关系极为松散，关系为“属于同一个集合”。

比如下图中有三个数据元素：databseTheory、databaseStructure和wxApplets，它们的性质都是教育类的书籍，而它们之间的关系极为松散，因此属于集合类型的逻辑结构。

线性结构

线性结构是数据元素中具有线性关系的数据结构，线性结构中的节点存在“一对一”的关系。开始节点和终端节点都是唯一的，除开始和终端结点外，每个节点有且仅有一个前驱节点和一个后继节点。

比如下图的字母表，a是开始节点，e是终端节点，而a与e两个节点之间的节点都有一个前驱节点和后驱节点。对于c节点来说，b是c的前驱节点，d是c的后驱节点。并且，b与c是一对一的关系，d与c也是一对一的关系。

树形结构

树形结构是数据元素之间具有层次关系的一种非线性结构，树形结构中的节点存在“一对多”的关系。除根节点外，每个节点有且仅有一个前驱节点，所有节点可以有零个或多个后驱节点。

比如下图的文件系统的组织方式，C盘是该结构的根节点，有且仅有一个根节点。文件夹1有3个后驱节点，而文件夹3没有后驱节点。

图形结构

图形结构是一种非线性结构，图形结构中的节点存在“多对多”的关系，所有的节点都可以有多个前驱结点和后驱节点。

存储结构

逻辑结构在计算机中的存储表示或实现叫数据的存储结构，也叫物理结构。数据的逻辑结构从逻辑关系角度观察数据，与数据的存储无关系，是独立于计算机的；而数据的存储结构是逻辑结构在计算机中的实现，依赖于计算机。

顺序存储结构

物理位置相邻的元素在逻辑上也相邻，每个元素（数据元素）与其前驱元素和后继元素的存储位置相邻，数组就是顺序存储结构。

链式存储结构

链式存储结构使用地址分散的存储单元存放数据元素，逻辑上向量的数据元素的物理位置不一定相邻，数据元素间的逻辑关系通常由附加的指针表示，指针记录前驱元素和后继元素的存储地址。数据元素由数据元素值和存放逻辑关系的指针共同构成，通过指针将相互直接关联的节点链接起来，结点间的链接关系体现数据元素之间的逻辑关系。

索引存储结构

索引存储结构在存储数据元素的基础上增加索引表。索引表的项由关键字和地址构成，其中关键字唯一标识一个数据元素，地址为该数据元素存储地址的首地址。

散列存储结构

散列存储结构也叫哈希存储结构，数据元素的具体存储地址根据该数据元素的关键字值通过散列函数直接计算出来。

算法

算法是有穷规则的集合，其规则确定一个解决某一特定类型问题的指令序列，其中每一条指令表示计算机的一个或者多个操作。

算法必须满足以下五个特性：

1. 有穷性：对于任意的合法输入值，算法必须在执行有穷步骤后结束，并且每一步都在有穷的时间内完成。
2. 确定性：算法对各种情况下执行的每个操作都有确切的规定，算法的执行者和阅读者都能明确其含义和如何执行，并且在任何条件下算法都只有一条执行路径。
3. 可行性：算法中的操作必须都可以通过以及实现的基本操作运算有限次实现，并且每一条指令都符合语法规则，满足语义要求，都能被确切执行。
4. 有输入：输入数据是算法的处理对象，一个算法具有零个或多个输入数据，既可以由算法指定，也可以在算法执行过程中通过输入得到。
5. 有输出：输出数据是算法对输入数据进行信息加工后得到的结果，输出数据和输入数据具有确定的对应关系，即算法的功能。一个算法有一个或多个输出数据。

算法建立在数据结构之上，对数据结构的操作需要使用算法来描述。算法设计依赖于数据的逻辑结构，算法实现依赖于数据的存储结构。

算法分析

算法分析技术主要是讨论算法的复杂度，评价算法的效率，以便在解决实际问题时根据实际情况和算法的优缺点对算法进行取舍。算法的优劣主要通过算法复杂度进行衡量，算法复杂度的高低反映了所需计算机资源（时间资源和空间资源）的多少。算法的复杂度通常以时间复杂度和空间复杂度来体现。

算法的时间复杂度

算法的时间复杂度是指算法的执行时间随着数据规模变化而变化的趋势，反映算法执行时间的长短。

算法的执行时间是用算法编写的程序在计算机上运行的时间，它是算法中设计的所有基本运算的执行时间之和。执行时间依赖于计算机的软、硬件系统，如处理器速度、程序运行的软件环境、编写程序采用的计算机语言、编译产生的机器语言代码等，因此不能使用真实的绝对时间来表示算法的效率，而应只考虑算法执行时间和问题规模之间的关系。

当问题规模为n时，T(n)表示算法的执行时间，称之为算法的时间复杂度，当n增大时，T(n)也随之增大。

T(n) = 指令序列(i)的执行次数 × 指令序列(i)的执行时间

由于算法的时间复杂度表示算法执行时间随数据规模的增大而增大的趋势，并非绝对时间，且与指令序列的执行次数成正比，所以在一个算法中，指令序列的执行次数越少，其运行时间也越少；指令序列的执行次数越多，其运行时间也越多。

大O表示法

算法的空间复杂度

算法的空间复杂度是指算法执行时所占用的额外存储空间量随问题规模的变化而变化的趋势。

在计算算法的空间复杂度时只考虑与算法相关的存储空间部分，算法本身占用的空间与实现算法的语言和描述语句有关，输入的数据元素与所处理的问题的规模有关，它们都不会随算法的改变而改变，所有将程序运行过程中额外的存储空间作为算法空间复杂度的量度。

大O表示法