# 基本概念和术语 1

# 数据（Data）

1. 数据：是能够输入计算机且能被计算机处理的各种符号的集合
   1. 信息的载体
   2. 是对客观事物符号化的展示
   3. 能够被计算机识别、存储和加工
2. 包括：
   1. 数值型数据：整数、实数等
   2. 非数值类型：文字、图像、图形、声音等

# 数据元素（Data element）

# 数据元素

1. 是数据的基本单位，再计算机程序中通常作为一个整体进行考虑和处理
2. 也称为元素，或称为记录、节点、定点

# 数据项

构成数据元素的不可分割的最小单位

数据 & 数据元素 & 数据项三者关系图

# 数据对象（Data Object）

1. 数据对象：是性质相同的数据元素的集合，是数据的一个子集

# 数据元素与数据对象

1. 数据元素：组成数据的基本单位
   1. 与数据的关系：是集合的个体
2. 数据对象：性质相同的数据元素的集合
   1. 与数据的关系：集合的子集

# 基本概念和术语 2

# 数据结构（Data Structure）

1. 数据结构：数据元素不是孤立存在的，他们之间存在某种关系，数据元素相互之间的关系称为结构（Structure）
2. 指的是相互之间存在一种或多种特定关系的数据元素集合
3. 数据结构是带结构的数据元素的集合

# 数据结构包括三方面内容

1. 数据元素之间的逻辑关系，也称为逻辑结构
2. 数据元素及其关系再计算机内存中的表示（又称为映像），称为数据的物理结构或者数据的存储结构
3. 数据的运算和实现，即对数据元素可以施加的操作以及这些操作再相应的存储结构上的体现

# 数据结构的两个层次

# 逻辑结构

1. 描述数据元素之间的逻辑关系
2. 与数据的存储无关，独立于计算机
3. 是从具体问题抽象出来的数学模型

# 物理结构（存储结构）

1. 数据元素及其关系在计算机存储器中的结构（存储方式）
2. 是数据结构在计算机中的表示

# 逻辑结构与存储结构的关系

1. 存储结构是逻辑关系的映像与元素本身的映像
2. 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
3. 两者综合起来建立了数据元素之间的结构关系

# 逻辑结构的种类

划分方式一

# 线性结构（一对一）

有且只有一个开始和一个终端节点，并且所有节点都最多只有一个直接前驱和一个直接后继，例如：线性表、栈、队列、串

# 非线性结构（一对多、多对多）

一个节点可能有多个直接前驱和直接后继，例如：树、图

划分方式二

# 集合结构

结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系

# 线性结构

结构中数据元素之间存在一对一的线性关系

# 树形结构

结构中的数据元素之间存在一对多的层次关系

# 图状结构或网状结构

结构中的数据元素之间存在多对多的任意关系

# 存储结构的种类

# 顺序存储结构

用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑单元由元素的存储位置来表示

# 链式存储结构

用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示

# 索引存储结构

1. 在存储节点信息的同时，还建立附加的索引表
2. 索引表中的每一项称为索引项
3. 索引表的一般形式：（关键字，地址）
4. 关键字是能唯一标识一个节点的那些数据项目
5. 若每个节点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index），若一组节点在索引表只对应一个索引项，则该索引表称之为稀松索引（Sparse Index）

# 散列存储

根据节点的关键字直接计算出该节点的存储地址

# 基本概念和术语 3

# 数据类型（Data Type）

定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称

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

指的是数学模型及其定义在此数学模型上的一组操作，例如 c 的结构体

# 概念小结

# 算法和算法分析

# 算法与程序

1. 算法：对待定问题求解方法和步骤的一种描述，它是指令的有限序列，其中每个指令表示一个或多个操作
2. 程序：程序是用某种程序设计语言对算法的具体实现

# 算法特性

1. 有穷性：一个算法必须在执行有穷步之后结束，且每一步都在有穷时间内完成
2. 确定性：算法中每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路劲，即对于相同的输入只能得到相同的输出
3. 可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现
4. 输入：一个算法有零个或多个输入
5. 输出：一个算法有一个或多个输出

# 算法设计的要求

1. 正确性（Correctness）：算法满足问题要求，能够正确解决问题
2. 可读性（Readability）：
   1. 算法主要是为了人的阅读和交流，其次才是为计算机执行，因此算法应该更易于人的理解
   2. 另一方面，晦涩难懂的算法易于隐藏较多错误而难以调试
3. 健壮性（Robustness）：
   1. 指的是输入非法数据时，算法恰当的做出反应或者进行相应处理，而不是产生莫名其妙的输出结果
   2. 处理出错的方式，不应该是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理
4. 高效性（Efficiency）：要求花费尽量少的时间和尽量低的存储需求

# 算法的时间效率的度量

1. 算法时间效率可以用依据算法编制的程序在计算机上执行所消耗的时间来度量

2. 两种度量方法

   1. 事后统计
      1. 将算法实现，测算其时间和空间开销
      2. 缺点：编写程序实现算法将花费较多的时间和精力；所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣
   2. 事前分析
      1. 对算法所消耗资源的一种估算方法
      2. 一个算法的运行时间指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作所需的时间与算法进行简单操作次数乘积

   $$算法运行时间 = 一个简单操作所需时间 \times 简单操作次数$$

# 算法时间复杂度的渐进表示

若有某个辅助函数$f(n)$，使得当 n 趋近于无穷大时，$T(n)/f(n)$ 的极限为不等于零的常数，则称$f(n)$ 是$T(n)$ 的同数量级函数，记作$T(n)=O(f(n))$，称$O(f(n))$ 算法的渐进时间复杂度，简称时间复杂度

例：如果$T(n)=2n^3 + 3n^2 + 2n + 3$，所以$T(n) = O(n^3)$

# 算法的时间复杂度定义

算法中基本预计重复执行的次数是问题规模 n 的某个函数$f(n)$，算法的时间量度记作：$T(n)=O(f(n))$

它表示随着 n 的增大，算法执行的时间增长率和$f(n)$ 的增长率相同，称渐进时间复杂度

# 算法的空间复杂度定义

1. 空间复杂度：算法所需存储空间的度量：$S(n)=O(f(n))$
2. 算法要占据的空间：
   1. 算法本身要占据的空间，输入 / 输出，指令，常熟，变量等等