1.1　重点难点指导

数据是计算机化的信息，是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数据处理、过程控制，还是文件的存储和检索及数据库技术等计算机应用，都是对数据进行加工处理的过程。

1.1.1　相关术语

1.数据、数据元素、数据项和数据对象

数据：信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。

数据项：具有独立含义的最小单位。有些数据元素是由若干数据项组成的。数据项有名和值之分：数据项名是一个数据项的标识，用变量定义；数据项值是它的一个可能取值。数据项具有一定的类型，依数据项的取值类型而定。

数据元素：数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。一个数据元素可由若干数据项组成，这些数据项可以分为两种：一种称为初等项，这些数据项是在数据处理时不能再分割的最小单位；另一种称为组合项。

数据对象或数据元素类：具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类）。数据元素是数据元素类的一个实例。

2.数据类型

数据类型是一个值的集合以及在这些值上定义的一组操作的集合。

在高级程序设计语言中，数据类型可分为如下两类：

①原子类型：其值是不可分解的。例如，C++语言中的整型、字符型、浮点型、双精度型等基本类型，分别用关键字int、char、float、double标识。

②结构类型：其值是由若干成分按某种结构组成的，是可分解的，并且它的成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。

3.抽象数据类型

抽象数据类型是指抽象数据的组织和与之相关的操作。它可以看作数据的逻辑结构及其在逻辑结构上定义的操作。

抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。也就是说，在设计抽象数据类型时，把类型的定义与其实现分离开。

4.数据结构

数据结构是指互相之间存在着一种或多种关系的数据元素的集合，是指数据元素之间的相互关系，即数据的组织形式。它包括以下3方面的内容：

①逻辑结构：数据之间的逻辑关系。

②存储结构：数据元素及其关系在计算机存储器内的表示。

③数据的运算：对数据对象施加的操作。

5.两类逻辑结构

（1）线性结构

线性结构的逻辑特点：若结构为非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和直接后继，如线性表。

（2）非线性结构

非线性结构的逻辑特点：一个结点可能有多个直接前驱和直接后继，如树形结构和图形结构。

6.数据逻辑结构的4种基本形态

①集合结构：数据元素间的关系是“属于同一个集合”。

②线性结构：数据元素之间存在着一对一的关系。

③树形结构：数据元素之间存在着一对多的关系。

④图形结构：数据元素之间存在着多对多的关系。

7.4种常见的存储结构

（1）顺序存储

顺序存储方法是将逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。

（2）链式存储

链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，由此得到的存储表示称为链式存储结构。链式存储结构通常借助于程序设计语言中的指针类型来实现。

（3）索引存储方式

索引存储方式是通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地址信息，可通过该地址找到结点的其他信息。

（4）散列存储方式

散列存储方式是根据结点的关键字直接计算出该结点的存储地址的方法。

1.1.2　算法的描述和分析

1.算法

算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：

①有穷性：一个算法必须在有穷步之后结束，即必须在有限时间内完成。

②确定性：算法的每一步必须有确切的定义，无二义性。

③可行性：算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。

④输入：一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。

⑤输出：一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。

2.对算法的设计要求

①正确：算法的执行结果应当满足预先规定的功能和性能要求。

②可读：一个算法应当思路清晰、层次分明、简单明了、易读易懂。

③健壮：当输入不合法数据时，应能进行适当处理，不至于引起严重后果。

④高效：有效地使用存储空间和有较高的时间效率。

3.算法的性能分析与度量

（1）时间复杂度

①某算法的时间复杂度是执行该算法所耗费的时间。通常某算法的时间复杂度是问题规模n的函数T（n）。

②大Ο记法：表示算法的渐近时间复杂度。

③常见的渐近时间复杂度有：

O（1）＜O（log2n）＜O（n）＜O（nlog2n）＜O（n2）＜O（n3）＜O（2n）

（2）空间复杂度

一个算法的空间复杂度是指该算法所耗费的存储空间。它通常也是问题规模n的函数T（n）。