第一章 绪论

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基本操作

• 实例化操作
• 添加学生
• 删除学生
• 修改学生
• 查找学生

算法

• 解决问题的有限操作序列（操作步骤）

算法的重要特征：

1. 有穷性：每一步都在有穷时间内完成
2. 确定性：确切的规定，不产生二义性
3. 可行性：要由可实现的基本操作执行运算有限次来实现
4. 输入：0或者多个输入
5. 输出：1个或者多个输出

评价算法的基本标准

1. 正确性
2. 可读性
3. 健壮性
4. 高效性：时间快------- 空间内存少

评价算法的时间复杂度

1. 算法的执行时间大致等于所有语句执行时间的总和
   • 事前统计法
   • 事后统计

语句频度：一条语句重复的次数

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); 线性阶

3. 平方阶

for(int i=0;i<n;i++)
{
for(int j=0;j<n;i++)
  {
    x++;
  }
}
//时间复杂度  = O(n^2);

4. 立方阶

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);

5. 对数阶

for(int i=0;i<n;i=i*2)
{
    x++;
}

对数阶的时间复杂度为

空间复杂度

• 用到多少辅助空间

例如将数组a 进行倒序

算法1 a 给b 再给a 用到了辅助空间b -------- 空间复杂度 O(n)

算法2 a中 首尾交换 只用了一个辅助空间temp ------- 空间复杂度O(1)