第一章 绪论
1.1 计算机研究的问题
数值计算： 解决数学问题
-
非数值计算：管理系统（数据结构）
DS（Data structure）:是一门非数值计算程序的操作对象，以及这些对象之间关系和操作的学科（增删改查）。
1.2 数据、数据元素、数据项和数据对象
- 数据：客观事物的符号表示 ，能输入到计算里面的，并能被计算机识别处理的总称。（一整张学生表都是数据）
- 数据元素：数据的基本单位。（如一条记录）完整的描述。
- 数据项：组成数据元素、独立、不可分割的最小单位。
- 数据对象：性质相同的数据元素的集合，数据的子集。
数据结构（DR）(DS)：
- 数据元素的集合
- 数据元素之间存在一种或者多种关系的集合
数据元素+结构
结构（逻辑结构和存储结构）
-
逻辑结构（给人看） 从逻辑上描述数据，与数据存储无关，是独立于计算机的。
线性结构 O---O----O----O O元素 ----关系 （1对1）
树结构（一对多）
图结构或者网状结构（多对多）
集合结构 （0对0）
逻辑 分成两大类
线性结构 栈、队列，线性表，串数组，广义表
非线性结构：树，二叉树，图，有向图，无向图，集合
<img src="https://i.loli.net/2020/05/22/2IwURqcBiFulQma.jpg" />
-
存储结构（物理结构）（给机器看） 数据对象在计算机的存储表示
- 顺序存储
- 链式存储
数据类型
- 基本类型
- 自定义（结构体）
抽象数据类型
1数据对象：集合D
2数据关系：S
3基本操作：P
举例 ADT（abstract data type）=(DSP) studentList
D数据对象{a,b,c,d}
S数据关系{<a,b><b,c><a,d>}
P基本操作
- 实例化操作
- 添加学生
- 删除学生
- 修改学生
- 查找学生
算法
- 解决问题的有限操作序列（操作步骤）
算法的重要特征：
- 有穷性：每一步都在有穷时间内完成
- 确定性：确切的规定，不产生二义性
- 可行性：要由可实现的基本操作执行运算有限次来实现
- 输入：0或者多个输入
- 输出：1个或者多个输出
评价算法的基本标准
- 正确性
- 可读性
- 健壮性
- 高效性：时间快------- 空间内存少
评价算法的时间复杂度
- 算法的执行时间大致等于所有语句执行时间的总和
- 事前统计法
- 事后统计
语句频度：一条语句重复的次数
-
常量阶：语句频度是固定的.
a=1; b=2;c=3; //或者 for(int i=0;i<100;i++) { x++; a++; } //时间复杂度 = O(1);
2.线性阶：
for(int i=0;i<n;i++)
{
x++;
}
//时间复杂度 = O(n); 线性阶
- 平方阶
for(int i=0;i<n;i++)
{
for(int j=0;j<n;i++)
{
x++;
}
}
//时间复杂度 = O(n^2);
- 立方阶
for(int i=0;i<n;i++)
{
for(int j=0;j<n;i++)
{
for(int j=0;j<n;i++)
{
x++;
}
}
}
//时间复杂度 = O(n^3);
- 对数阶
for(int i=0;i<n;i=i*2)
{
x++;
}
对数阶的时间复杂度为
空间复杂度
- 用到多少辅助空间
例如将数组a 进行倒序
算法1 a 给b 再给a 用到了辅助空间b -------- 空间复杂度 O(n)
算法2 a中 首尾交换 只用了一个辅助空间temp ------- 空间复杂度O(1)
