数据结构-数据结构的一般概念

大纲：

1. 掌握数据结构的基本概念和术语。
2. 了解抽象数据类型的概念。
3. 掌握算法的特性，算法的描述和算法的分析。

---

数据结构的基本概念

基本概念和术语

1. 数据：所有能被输入到计算机中并被处理的符号的集合
2. 数据元素：数据的基本单位，通常做一个整体考虑
3. 数据项：构成数据元素的不可分割的最小单位，一个数据元素由若干数据项组成
4. 数据对象：相同性质的数据元素的集合，是数据的一个子集
5. 数据类型：一个值的集合和定义在这个集合上的一组操作的总称
   5.1 原子类型：值不可以再分的数据类型
   5.2 结构类型：值可以再分解成若干的数据类型
   5.3 抽象数据类型：抽象数据组织和与之相关的操作
6. 抽象数据类型（ADT）：一个数学模型以及定义在该模型上的一组操作，其定义只与逻辑特性有关，通常采用（数据对象，数据关系，基本操作集）这样的三元组来表示抽象数据类型
7. 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。包括：逻辑结构、存储结构和数据的运算

数据结构的三要素

1. 数据的逻辑结构

逻辑结构指数据元素之间的逻辑关系

数据的逻辑结构分类图

• 集合：结构中的数据元素之间除了“同属一个集合”的关系之外，没有任何关系
• 线性结构：结构中的数据元素之间只存在一对一的关系
• 树型结构：结构中的数据元素之间存在一对多的关系
• 图状结构或网状结构：结构中的数据元素之间存在多对多的关系

2. 数据的存储结构

存储结构指数据结构在计算机中的表示，也称物理结构

• 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，通过存储单元的邻接关系来表示元素之间的逻辑关系
  • 优点：实现随机存储，每个元素占用空间小
  • 缺点：只能使用相邻的一整块存储单元，会产生较多外部碎片
• 链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，通过指针表示元素之间的逻辑关系
  • 优点：不会出现碎片现象，充分利用所有的存储单元
  • 缺点：每个元素要存储指针，需要多占用部分存储空间，而且只能顺序存取
• 索引存储：存储信息的同时，建立附加的索引表，索引表中每一项称为索引项，索引项一般形式是：（关键字，地址）
  • 优点：检索速度快
  • 缺点：增加了索引表，占用较多存储空间，增删数据时也要修改索引表，花费较多时间
• 散列存储：根据元素的关键字直接计算出该元素的存储地址，也称Hash存储
  • 优点：检索，增删结点操作都很快
  • 缺点：散列函数不好可能会出现元素存储单元的冲突，解决冲突会增加时间、空间的开销

---

算法和算法评价

算法的基本概念

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

1. 算法的5个重要特性
   1.1 有穷性
   1.2 确定性
   1.3 可行性
   1.4 输入
   1.5 输出
2. 算法设计的要求
   2.1 正确性
   2.2 可读性
   2.3 健壮性
   2.4 效率与低存储量需求

算法效率的度量

算法效率的度量通过时间复杂度和空间复杂度来描述

1. 时间复杂度：算法中所有语句的频度（指该语句在算法中被重复执行的次数）之和记作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ⁿ)

2. 空间复杂度：算法耗费的存储空间，记作S(n)=O(g(n))

   • 算法原地工作指算法所需辅助空间是常量，即O(1)