数据结构讨论的范畴

与数据结构相关的概念

数据

所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合。

是计算机操作的对象的总称。

是计算机处理的信息的某种特定的符号表示形式。

数据元素

是数据（集合）中的一个 “个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。

关键字

能识别一个或几个数据元素的数据项。若能起唯一识别作用，则被称为“主”关键字，否则称为“次”关键字。

数据对象

具有相同特性的数据元素的集合。
如:整数、实数等。

数据结构

有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。

从关系或结构分，数据结构可归结为以下四类:

  1. 线性结构
  2. 树形结构
  3. 图状结构
  4. 集合结构

数据结构包括“逻辑结构” 和“物理结构”两个方面(层次):

逻辑结构:是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;

物理结构:是逻辑结构在计算机中的表示和实现，故又称“存储结构” 。

存储结构是逻辑结构在存储器中的映象

“关系” 的两种映象方法：

顺序映象:

以 x 和 y 之间相对的存储位置表示后继关系

存储结构中只包含数据元素本身的信息

链式映象:

以附加信息(指针)表示后继关系

需要用一个和 x 绑定在一起的附加信息(指针)指示 y 的存储位置

抽象数据类型(ADT)

是指一个数学模型以及定义在该模型上的一组操作。

通常称语言中已经实现的数据类型为固有数据类型。

抽象数据类型有两个重要特征:

“数据抽象” 和“数据封装”

数据抽象:

用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。

数据封装:

将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节

抽象数据类型的描述方法

$ADT =（D，S，P）$

其中:

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

数据对象是特性相同的数据元素的集合，是数据的一个子集。

抽象数据类型的表示和实现

抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。

比如:

typedef  struct {
    float realpart；
    float imagpart；
}complex；

void Assign( complex &Z, float realval, float imagval )；
// 构造复数 Z,其实部和虚部分别被赋以参数
// realval 和 imagval 的值
float GetReal( cpmplex Z )；
// 返回复数 Z 的实部值
float Getimag( cpmplex Z )；
// 返回复数 Z 的虚部值
.
.
.

算法和算法的量度

算法的定义

算法是为了解决某类问题而规定的一个有限长的操作序列。

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

有穷性。

对于任意一组合法输入值，在执行有穷步骤之后一定能结束。算法中的每个步骤都能在有限时间内完成。

确定性。

对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

可行性。

算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。

有输入。

作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。

有输出。

它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。

算法设计的原则

设计算法时，通常应考虑达到以下目标：

正确性

首先，算法应当满足以特定的“规格说明”方式给出的需求。

其次，对算法是否“正确”的理解可以有以下四个层次：

  1. 不含语法错误；
  2. 对于某几组输入数据能够得出满足要求的结果；
  3. 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；
  4. 程序对于一切合法的输入数据都能得出满足要求的结果；
  • 通常以第 3 层意义的正确性作为衡量一个算法是否合格的标准

可读性

算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；

另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；

健壮性

当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

高效率与低存储量需求

效率指的是算法执行时间；

存储量指的是算法执行过程中所需的最大存储空间。

两者都与问题的规模有关。

算法效率的衡量方法和准则

通常有两种衡量算法效率的方法:

事后统计法

缺点：

  1. 必须执行程序
  2. 其它因素掩盖算法本质

事前分析估算法

优点：可以预先比较各种算法，以便均衡利弊从中选优。

算法的存储空间需求

算法的时间复杂度

和算法执行时间相关的因素：

  1. 算法选用的策略
  2. 问题的规模
  3. 编写程序的语言
  4. 编译程序产生的机器代码的质量
  5. 计算机执行指令的速度

一个特定算法的 “运行工作量” 的大小，只依赖于问题的规模（通常用整数量 n 表示），或者说，它是问题规模的函数。

假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：

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

称 T (n) 为算法的(渐近) 时间复杂度

估算算法的时间复杂度

算法 = 控制结构 + 原操作（固有数据类型的操作）

算法的执行时间$=\Sigma ($原操作$(i)$的执行次数$\times$原操作$(i)$的执行时间$)$

算法的执行时间与原操作执行次数之和成正比

从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。

“基本操作” 指的是，该操作重复执行次数和算法的运行时间成正比。

算法的空间复杂度

算法的空间复杂度定义为:

$S(n) = O(g(n))$

表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。

算法的存储量包括:

  1. 输入数据所占空间
  2. 程序本身所占空间
  3. 辅助变量所占空间

若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

若所需额外空间相对于输入数据量来说是个常量，则称此算法为原地工作。

若所需存储量依赖于特定的输入，则通常按最坏情况考虑。