主要内容

程序 = 数据结构 + 算法
数据结构 = 数据集 + 关系 + 操作
即数据结构是数据集合及其之间的关系和**操作（运算）**的集合。

概括地说，数据结构是一门研究“程序设计问题中计算机操作对象以及它们之间的关系和操作”的学科。

具体地说，数据结构主要研究数据之间有哪些结构关系，如何表示，如何存储，如何处理。

基本术语

数据

数据是信息在计算机程序中的表现形式或编码形式，是描述客观事物的数、字符及所有能输入到计算机中并被计算机程序处理的符号的集合。

是对计算机处理的对象的一个统称，被看作为信息的载体

大致可分为两类：

• 数值型数据：整数、实数、复数等
• 非数值型数据：字符、字符串、图像、声音等

数据元素

数据的基本单位是数据元素，它是计算机处理或访问的基本单位。

数据项

数据不可分割的最小标识单位，一个数据元素可由若干数据项组成。

其中一个人的信息就是一个数据元素，而他的学号、姓名、性别、年龄、专业就是数据项。

即

是一个数据元素，而 1001，张三，男，20，计算机 是这个数据元素的数据项。

数据结构

数据结构是由与特定问题相关的某一数据元素的集合和该集合中数据元素之间的关系组成的。

数据对象

从狭义的观点把数据对象定义为具有一定关系的相同性质的数据元素的集合。

例如，学生的集合、教师的集合、图书的集合等。

从广义的观点把数据对象定义为一个由数据抽象和处理抽象构成的封装体，即数据对象的声明中不但要包含属性，还要包含可用的操作。

例如一个学生对象，除了包含学号、姓名、性别、年龄等属性外，还包含了增加、删除、修改、查询等操作。

数据类型

数据类型是对一类数据的描述，它定义了数据的值域（数据的取值范围）、数据的操作（可对数据执行的操作），以及数据如何存储在计算机中的方式。数据类型确定了数据的基本属性和操作规则。

抽象数据类型（ADT）

抽象数据类型（Abstract Data Type）是数据类型的一种扩展，它不仅仅关注数据本身，还定义了对数据的操作，但是不关心数据的具体实现方式。抽象数据类型强调的是“如何操作数据”，而不是“数据是如何存储的”。

数据结构的分类

分解和抽象

数据结构的核心技术是分解和抽象。
通过分解划分出数据的层次；再通过抽象舍弃数据的具体内容得到数据的逻辑结构。

逻辑结构与存储结构

逻辑结构是根据问题需要建立的数据元素和它们之间的关系，完全不考虑具体如何实现。
存储结构是逻辑结构在计算机中的存储表示，是逻辑结构在计算机中的映像。

从用户角度能看到的只能是逻辑结构，所以所称的数据结构一般指的是逻辑结构。

逻辑结构的分类

• 线性结构
• 非线性结构

存储结构的分类

1. 存取方式的不同

• 直接存取结构
• 顺序存储结构
• 索引结构

2. 存储方式的不同

• 顺序存储方式
• 链接存储方式
• 索引存储方式
• 散列存储方式

3. 选取存储结构的依据

• 访问频率
• 修改频率
• 安全保密

定义在数据结构上的操作

• 创建
• 销毁
• 查找
• 插入
• 删除
• 排序
• …

算法和算法设计

算法的基本定义和特性

• 有输入：0个或多个输入
• 有输出：1个或多个输出
• 确定性：算法的每一步都有确定的含义
• 有穷性：算法在执行有限步之后终止
• 可行性：算法的每一步都是可行的，能够通过已经实现的基本运算执行有限次完成

算法的设计步骤

1. 理解需求
2. 设计思路
3. 算法框架
4. 程序实现

算法设计的基本方法

• 穷举法
• 迭代法
• 递推法
• 递归法

算法的评价标准

• 正确性：算法是否能解决问题
• 健壮性：在不正确的输入下，算法是否能自我保护
• 可读性：算法和程序是否容易理解
• 高效性：算法是否能在合理的时间和空间内解决问题
• 简单性：采用的数据结构和算法是否简单，越简单出错的可能性越小
  • 环路复杂度：程序中判断语句和子程序调用的总数 + 1
  • 软件工程要求：环路复杂度不超过10

算法的计算复杂度

• 时间复杂度
• 空间复杂度

渐近分析，大O表示法