大纲：
- 掌握数据结构的基本概念和术语。
- 了解抽象数据类型的概念。
- 掌握算法的特性，算法的描述和算法的分析。
数据结构的基本概念
基本概念和术语
- 数据：所有能被输入到计算机中并被处理的符号的集合
- 数据元素：数据的基本单位，通常做一个整体考虑
- 数据项：构成数据元素的不可分割的最小单位，一个数据元素由若干数据项组成
- 数据对象：相同性质的数据元素的集合，是数据的一个子集
- 数据类型：一个值的集合和定义在这个集合上的一组操作的总称
5.1 原子类型：值不可以再分的数据类型
5.2 结构类型：值可以再分解成若干的数据类型
5.3 抽象数据类型：抽象数据组织和与之相关的操作 - 抽象数据类型（ADT）：一个数学模型以及定义在该模型上的一组操作，其定义只与逻辑特性有关，通常采用（数据对象，数据关系，基本操作集）这样的三元组来表示抽象数据类型
- 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。包括：逻辑结构、存储结构和数据的运算
数据结构的三要素
- 数据的逻辑结构
逻辑结构指数据元素之间的逻辑关系
数据的逻辑结构分类图
- 集合：结构中的数据元素之间除了“同属一个集合”的关系之外，没有任何关系
- 线性结构：结构中的数据元素之间只存在一对一的关系
- 树型结构：结构中的数据元素之间存在一对多的关系
- 图状结构或网状结构：结构中的数据元素之间存在多对多的关系
- 数据的存储结构
存储结构指数据结构在计算机中的表示，也称物理结构
- 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，通过存储单元的邻接关系来表示元素之间的逻辑关系
- 优点：实现随机存储，每个元素占用空间小
- 缺点：只能使用相邻的一整块存储单元，会产生较多外部碎片
- 链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，通过指针表示元素之间的逻辑关系
- 优点：不会出现碎片现象，充分利用所有的存储单元
- 缺点：每个元素要存储指针，需要多占用部分存储空间，而且只能顺序存取
- 索引存储：存储信息的同时，建立附加的索引表，索引表中每一项称为索引项，索引项一般形式是：（关键字，地址）
- 优点：检索速度快
- 缺点：增加了索引表，占用较多存储空间，增删数据时也要修改索引表，花费较多时间
- 散列存储：根据元素的关键字直接计算出该元素的存储地址，也称Hash存储
- 优点：检索，增删结点操作都很快
- 缺点：散列函数不好可能会出现元素存储单元的冲突，解决冲突会增加时间、空间的开销
算法和算法评价
算法的基本概念
算法对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令都表示一个或多个操作
- 算法的5个重要特性
1.1 有穷性
1.2 确定性
1.3 可行性
1.4 输入
1.5 输出 - 算法设计的要求
2.1 正确性
2.2 可读性
2.3 健壮性
2.4 效率与低存储量需求
算法效率的度量
算法效率的度量通过时间复杂度和空间复杂度来描述
-
时间复杂度：算法中所有语句的频度（指该语句在算法中被重复执行的次数）之和记作T(n)，时间复杂度主要分析T(n)的数量级。算法中基本运算（最深层循环内的语句）的频度与T(n)同数量级，所以一般采用算法中基本运算的频度f(n)来分析算法时间复杂度。即T(n)=O(f(n))
- 常见的渐进时间复杂度：
O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
- 常见的渐进时间复杂度：
-
空间复杂度：算法耗费的存储空间，记作S(n)=O(g(n))
- 算法原地工作指算法所需辅助空间是常量，即O(1)
网友评论