一、基本概念和术语

1、数据

数据是对客观事物的符号表示，是所有能输入到计算机中并能被计算机程序处理的符号的总称。 除整型、浮点型等数值类型，布尔型、字符串型等非数值类型外，图片、视频、音频也可以经过编码进行处理。

2、数据元素和数据项

数据元素 ： 数据元素是数据的基本单位，计算机程序中通常作为一个整体进行考虑和处理。

数据项： 一个数据元素可以由多个数据项组成，数据项是数据的不可分割的最小单位。

3、数据对象

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

4、数据结构

数据元素之间不是孤立存在的，他们之间存在某种关系，这种数据元素相互之间的关系称为结构。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构强调数据与数据之间必须具有某种对应关系 数据对象强调数据与数据之间必须具有相同的属性

二、数据结构的三要素

1、逻辑结构

指数据对象中数据元素之间的相互关系 逻辑结构主要分为线性结构和非线性结构

• 线性结构：一对一

• 非线性结构：不是一对一

  

• 集合 数据元素属于“同一个集合”，并无其他复杂关系
• 线性结构 数据元素之间存在一个对一个的关系
• 树形结构 数据元素之间存在一个对多个的关系
• 图状结构或网状结构 数据元素之间存在多个对多个的关系

  

2、物理结构

指数据的逻辑结构在计算机中的存储形式 数据元素之间的关系在计算机中有两种不同的表示方法：

• 顺序映像：用相对位置来表示数据元素之间的逻辑关系
• 非顺序映像：用指针表示数据元素之间的逻辑关系 分别对应两种不同的存储结构
• 顺序存储结构
• 链式存储结构

物理结构主要有：

• 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的储存单元中，元素之间的关系由储存单元的邻接关系来体现
• 链式存储：把逻辑上相邻的元素存储在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系
• 索引存储：在储存元素信息的同时，还建立附加的索引表。索引表中的每项成为索引项，索引项的一般形式是（关键字，地址）
• 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希存储

不同存储方式的区别：

ps： 要判断是否与数据的存储结构无关，只需要看题中所给的结构是否有具体使用到顺序存储还是链式存储，如果有，那就与存储结构相关。如：栈，并没有说是顺序栈还是链栈，所以无关；线索树，很明显必须要用链式存储来实现，所以相关。

3、数据运算

针对某种逻辑结构，结合实际需求，定义基本运算（增删改查）

• 运算的定义是针对逻辑结构的，指出运算的功能
• 运算的实现是针对存储结构的，指出运算的具体步骤

三、数据类型和抽象数据类型

1、数据类型

是一个值的集合和定义在这个值集上的一组操作的总称。

• 原子类型：其值不可再分的数据类型（bool 型）
• 结构类型：其值可以再分解为若干分量的数据类型（struct 将结构体）

2、抽象数据类型

一个数学模型及该模型上的一组操作

• 原子类型（数位为 100 的整数）
• 固定聚合类型（复数）
• 可变聚合类型（有序整数序列） 抽象数据类型是对数据类型架构的一种全局体现，使我们能够更加清晰地看待某一数据类型

四、算法和算法分析

1、什么是算法

是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

2、算法的特性

• 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。 程序可以是无穷的，但算法不可以无穷
• 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。 如：排序算法有很多种，但不论采用何种排序算法，最终结果是唯一确定的。无歧义！
• 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
• 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
• 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

3、算法设计要求

• 正确性：是指算法至少具有输入、输出和加工处理且无歧义并能正确反映问题的需求，能够得到问题的正确答案。
• 可读性：算法设计的另一个目的就是为了便于阅读、理解和交流
• 健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或其它莫名其妙的结果
• 效率与低存储量需求：花的时间少而且占用内存空间小

4、算法的时间复杂度

时间复杂度：事前预估算法时间开销 T (n) 与问题规模 n 的关系

• 加法规则：T (n) = T{1}(n) + T{2} (n) = O (f (n)) + O (g (n)) = O (max (f (n), g (n))) （多项相加，只保留最高阶的项，且系数变为 1）
• 乘法规则：T (n) = T{1}(n) × T{2} (n) = O (f (n)) × O (g (n)) = O (f (n)×g (n))（多项相乘，都保留）
• 算法好坏：O (1) < O (log{2}n) < O (n) < O (nlog{2}n) < O (n^2) < O (n^3) < O (2^n) < O (n!) < O (n^n)（口诀：常对幂指阶）
• 最坏时间复杂度：最坏情况下算法的时间复杂度
• 平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望运行时间
• 最好时间复杂度：最好情况下算法的时间复杂度（一般只考虑最坏和平均复杂度）

5、算法的空间复杂度

空间复杂度：对算法运行所占空间的度量。 算法原地工作：算法所需内存空间为常量 若数组长不变时，空间复杂度=递归调用的深度

注意：

1. 数据的逻辑结构可以独立于存储结构
2. 数据的存储结构是逻辑结构在计算机上的映射，不可以独立于逻辑结构而存在
3. 链式存储中，各个不同结点的存储空间可以不连续，但是结点内部的存储单元地址必须连续#