第一章 绪论

第一章 绪论

  大家好，我叫亓官劼（qí guān jié ）

数据结构核心原理与算法应用

1.1 数据结构的基本概念

1.1.1 基本概念和术语

1. 数据：数据是信息的载体。是所有能输入到计算机中并被计算机程序识别和处理的符号的集合。操作对象的总称。
2. 数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理，是数据集合中的一个个体，是数据结构中讨论的基本单位。
3. 数据项：一个数据元素可以由若干个数据项组成。数据项是数据结构中讨论的最小单位。
4. 数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
5. 数据类型：数据类型是一个值的集合和定义在此集合上的一组操作的总称。

1. 原子类型。值不可再分的数据类型。例如int、char、float等。值的集合+操作。
2. 结构类型。值可以再分解为若干成分的数据类型。例如list、map、stack等。结构的集合+操作。
3. 抽象数据类型。抽象数据组织及与之相关的操作。ADT。数据对象+数据关系+操作。

6. 抽象数据类型（ADT）：一个数学模型及定义在该模型上的一组操作。
7. 数据结构：是相互之间存在一种或多种关系的数据元素的集合，可以表示为一个二元组（D,R），其中D为数据元素的集合，R为元素间的关系。

1.1.2 数据结构的三要素

1. 数据的逻辑结构：元素之间的逻辑关系。
   按逻辑结构可分为：

1. 线性结构。（一对一的关系）
2. 集合。（同属一个集合）
3. 树形结构。（一对多的关系）
4. 图状结构。（多对多关系）

2. 数据的存储结构：数据结构在计算机中的表示(映像)，也称作物理结构。
   数据的存储主要的顺序存储、链式存储、索引存储和散列存储。
   1）顺序存储：将逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来提现。
   优点：可以实现随机存取，每个元素占用最少的存储空间。
   缺点：只能使用相邻的一整块存储单元，会产生较多外部碎片。增加、删除一个元素的效率不高。
   2）链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储位置的指针来表示元素直接的逻辑关系。
   优点：不会出现碎片现象，能够充分利用存储单元。增加、删除一个元素的效率较高。
   缺点：每个元素因存储指针会额外占用存储空间，只能实现顺序存储，访问效率较低。
   3）索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项为索引项，索引项一般形式为：（关键字，地址）。
   优点：检索速度快。
   缺点：增加附加的索引表后会占用较多的存储空间，在增加和删除数据是要修改索引表，因此要花费较多时间。
   4）散列存储：根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。
   优点：检索、增加、删除节点的操作都很快。
   缺点：若散列函数不好，则会出现元素存储单元的冲突，而解决冲突会增加时间和空间的开销。效率较大的依赖于散列函数的选择。
3. 数据的运算：施加在数据上的运算，包括运算的定义和实现。

1.2 算法和算法评价

1.2.1 算法的基础概念

算法是对特定问题求解步骤的一种描述，他是指令的有限序列，其中的每条指令表示一个或多个操作。此外，一个算法还具有以下五个重要特性：有穷性、确定性、可行性、输入、输出。

通常，设计一个优质的算法，我们需要注意一下几个问题：

1. 正确性。算法应能正确的解决问题。
2. 可读性。算法应具有良好的可读性，以帮助人们理解。
3. 健壮性。输入非法数据时（或边界情况），应该能做出适当的反应。
4. 效率与存储。算法的时间效率和空间复杂度应该尽可能的小。

算法和程序的区别：

• 算法是解决问题的一种方法或者一种过程，设计如何将一个解决一个问题的方法、途径。
• 程序是某种程序设计语言对算法的具体实现。

1.2.2 算法效率的度量

算法效率的度量是通过时间复杂度和空间复杂度来描述的。我们描述一个算法，通常使用最坏情况下的算法的时间复杂度。

1. 时间复杂度
   通常我们使用程序中使用频次最高的语句的数量级来表示时间复杂度。

1. 加法规则。
   T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))
2. 乘法规则。
   T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n)*g(n))

2. 空间复杂度
   算法的空间复杂度S(n)定义为该算法所耗费的存储空间，他是问题规模n的函数，渐进空间复杂度也常简称为空间复杂度。

---

  大家好，我叫亓官劼（qí guān jié ）