数据结构 | 绪论

数据结构在学什么

• 如何用程序代码把现实世界的问题信息化
• 如何用计算机高效地处理这些信息从而创造价值

408各科之间的联系

什么是数据

• 数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合【二进制 0/1】
• 数据是计算机程序加工的原料
  

计算机处理的数据

• 早期的计算机——只用于处理纯数值型问题
  
• 现代计算机——经常处理非数值型问题
• 对于非数值型的问题
  1. 每个个体的具体信息
  2. 个体之间的关系

数据元素——描述一个个体

• 数据元素：【数据元素是数据的基本单位】，通常作为一个整体进行考虑和处理
• 数据项：一个数据元素可由若干数据项组成，【数据项是构成数据元素的不可分割的最小单位】

什么是数据对象

• 数据对象是具有【相同性质】的数据元素的集合，是数据的一个子集
• 数据结构是【相互之间存在一种或多种特定关系】的数据元素的集合

什么是数据结构

• 数据结构是相互之间存在一种或多种特定关系的数据元素的集合
• 同一个数据对象里面的数据元素，可以组成不同的数据结构
  
  

数据结构的三要素

逻辑结构

• 表示的是数据元素之间的逻辑关系

集合

线性结构

树形结构

网状（图）结构

数据的运算

• 针对于某种逻辑结构，结合实际需求，定义基本运算

物理结构（存储结构）

• 如何用计算机表示数据元素的逻辑关系
  

顺序存储

链式存储

索引存储

散列存储

1. 若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的
2. 数据的存储结构会影响存储空间分配的方便程度
3. 数据的存储结构会影响对数据运算的速度（Eg：在b和d之间插入新元素c）
   

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

数据类型vs抽象数据类型

数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称

1. 原子类型：其值不可再分的数据类型
   

2. 结构类型：其值可以再分解为若干成分（分量）的数据类型
   

抽象数据类型

• Abstract Data Type，ADT
• 是抽象数据组织及与之相关的操作
• 定义一个ADT，其实就是定义了一个完整的数据结构，其实就是对一个数据结构的逻辑特性（逻辑结构+数据运算）的一个描述，而数据结构的实现者才需要去关注逻辑结构在计算机内部如何表示以及各种运算在计算机内部应该如何实现

什么是算法？

• 算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作

算法的特性

有穷性

• 一个算法必须总在执行有穷步之后结束并且每一步都可以在有穷时间内完成
• 算法必须是有穷的（用有限步骤解决某个特定的问题），而程序可以是无穷的（微信是程序，不是算法）

确定性

• 算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出

可行性

• 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现

输入

• 一个算法有0个或多个输入，这些输入取自于某个特定的对象的集合

输出

• 一个算法有1个或多个输出，这些输出是与输入有着某种特定关系的量

“好”算法的特质

• 设计算法时要尽量追求的目标

正确性

• 算法应该能够正确地解决求解问题

可读性

• 算法应具有良好的可读性，以帮助人们理解

健壮性

• 输入非法数据时，算法能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果

高效率与低存储量需求

• 高效要求花的时间少，即时间复杂度低
• 低存储量要求不费内存，即空间复杂度低

算法效率的度量

如何评估算法时间开销？

算法的时间复杂度

时间复杂度小练习

程序运行时的内存需求

空间复杂度

函数递归调用带来的内存开销