基本概念和术语

数据（data）：是对客观事物的符号表示，只要是能抽象成符号并被计算机处理的客观对象，都称为数据，并且随着科学技术的发展，数据的范围在不断的扩大。

数据元素（dada element）:数据的基本单位，在计算机中通常被当成一个整体来进行考虑和处理。有时一个数据元素有多个属性，这些属性就称为数据元素的数据项。数据项是数据的不可分割的最小单位。

数据对象（data object）:性质相同的数据元素的集合，是数据的一个子集。数据项组成数据元素，数据元素表示数据，而数据对象像是按照某个标准对数据进行的分类。

数据结构（data structure）：是相互之间存在一种或多种特定关系的数据元素的集合，数据元素不是孤立存在的，这点想到哲学上联系具有普遍性：

  1. 整个世界是由各种事物相互联系构成的统一体。

  2. 每个事物内部诸要素相互联系构成统一的整体。

  3. 每个事物对外要同其他事物相联系才能够存在。

数据结构的基本类型：

  1. 集合

  2. 线性结构

  3. 树形结构

  4. 图状结构或网状结构

线性结构：线性表，栈，队列

非线性结构：树，图，集合

数据结构的形式定义为：数据结构是一个二元组 Data_Structure = (D,S)

其中，D是数据元素的有限集（即有限个数据元素），S是D上关系的有限集（即S描述的是数据元素之间的关系）

结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。数据结构在计算机中的表示（又称为映像）称为数据的物理结构，又称为存储结构。在计算机中表示信息的最小单位是二进制数的一位，叫做“位（bit）”

数据元素之间的关系在计算机中有两种不同的存储结构（又称物理结构），主要有顺序存储，炼石存储，索引存储，散列存储。

  1. 顺序映像→顺序存储结构

    特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

  2. 非顺序映像→链式存储结构

    特点是借助元素存储地址的指针表示数据元素之间的逻辑关系。

运算：数据的运算是在数据的逻辑结构上定义的操作算法（例如增删改查）

数据类型（data type）：描述的是一个值的集合和定义在这个值集上的一组操作的总称。

按照值的不同，高级程序语言中的数据类型可分为两类

  1. 非结构的原子类型：值是不可分解的，例如C语言中的基本类型（整型，实型，字符型和枚举型）

  2. 结构类型：结构类型的值是由若干成分按某种结构组成的，是可以分解的，看起来像是后面会学的结构体，

抽象数据类型（abstract data structure）：是指一个数学模型以及定义在该模型上的一组操作。

抽象数据类型按其值的不同特性，细分为下列3种类型：

  1. 原子类型：属原子类型的变量的值是不可分解的。

  2. 固定聚合类型：属该类型的变量，其值由确定数目的成分按某种结构组成。

  3. 可变聚合类型：和固定聚合类型相比较，构成可变聚合类型“值”的成分的数目不确定。

抽象数据类型通常用三元组表示：（D,S,P）

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

抽象数据类型定义：

ADT 抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

}ADT抽象数据类型名

其中，数据对象和数据关系的定义用伪码描述，基本操作为

基本操作名（参数表）

初始条件：<初始条件描述>

操作结果：<操作结果描述>

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

见严蔚敏《数据结构》P9-P13

算法和算法分析

算法（algorithm）:是对特定问题求解步骤的一种描述

算法的特点：

  1. 有穷性，步骤有穷，时间有穷
  2. 确定性，指令明确，没有二义
  3. 可行性，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
  4. 输入，一个算法可以有零个或多个输入。
  5. 输出，一个算法可以有一个或多个输出。

口诀：出入确可穷

算法设计的要求

1.正确性

2.可读性

3.健壮性

4.效率与低存储量需求（快速性和节省性）

口诀：正确快读建节（正确快读见解）

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

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

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

alt

算法的存储空间需求——空间复杂度：类似于算法的时间复杂度，将空间复杂度作为算法所需存储空间的度量，记作

S（n） = O(f(n))

一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 错题： alt

错选了A，数据项是数据的最小单位，数据的基本单位是数据元素，数据结构是指相互之间具有特点关旭的数据的集合。

alt alt