第2章：绪论-知识点.pdf

### 第2章：绪论知识点详细解读 #### 知识结构 第2章的绪论部分主要介绍了数据结构的基础概念与术语、逻辑结构与存储结构、数据的运算以及算法定义等方面的知识。 #### 逻辑结构 逻辑结构指数据元素之间的逻辑关系，可分为线性结构和非线性结构。 - **线性结构**：包括线性表、栈（Stack）、队列（Queue），它们的特点是元素间存在一对一的线性关系。 - **非线性结构**：包括树（Tree）、图（Graph）、集合（Set），它们的元素间存在一对多或多对多的关系。 #### 存储结构（物理结构） 物理结构指的是数据在计算机中的存储方式，主要有顺序存储结构和链式存储结构。 - **顺序存储结构**：通过元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如数组，其优点是空间利用率高，可以实现随机存取，缺点是一般要求使用连续的存储空间，可能会产生外部碎片。 - **链式存储结构**：借助指针表示数据元素之间的逻辑关系。其特点是不会产生碎片，但会因为存储指针而占用额外空间。优点是不会产生碎片，缺点是只能顺序存取。 #### 数据结构的存储方法 除了顺序存储结构和链式存储结构，数据结构还有其他两种存储方法。 - **索引存储方法**：存储节点时，额外存储地址，形式如<关键字，地址>。其优点是检索速度快，但缺点是增加了附加的索引表，会占用更多空间，且在增删数据时要修改索引表，会花费更多时间。 - **散列（Hash）存储方法**：根据节点的关键字计算出节点的存储地址。该方法优点是检索、增加、删除节点操作很快，但缺点是如果散列函数选择不好，会出现元素存储单元冲突，解决冲突会增加时间和空间开销。 #### 数据结构三要素 数据结构由数据、关系和操作三个要素组成。 - **数据**：由若干数据项组成，每个数据项称为数据域。例如，链表节点的值域和指针域都是数据域。 - **关系**：数据元素相互之间的逻辑关系。 - **操作**：在逻辑结构上定义的一组操作。 #### 抽象数据类型（ADT） 抽象数据类型是一种数据组织，包括了与之相关的操作。ADT定义只与逻辑特性相关，不涉及物理存储特性。 #### 算法的效率 算法的效率通常通过时间复杂度和空间复杂度来描述。 - **时间复杂度**：算法执行时间随输入规模增长的变化情况。 - **空间复杂度**：执行算法所需的存储空间随输入规模增长的变化情况。 #### 算法的五个特征 算法的五个特征包括：有穷性、确定性、可行性、输入、输出。 - **有穷性**：算法中的每条指令执行的时间有限，算法中每条指令都会执行且只会执行有限次。 - **确定性**：算法中的每条指令都应当清楚无歧义。 - **可行性**：算法中描述的操作都是基本操作，可以通过有限次执行完成。 - **输入**：算法具有零个或多个输入，这些输入来自特定的对象集合。 - **输出**：算法至少有一个或多个输出，这些输出是与输入有特定关系的量。 #### 本章重点 本章的重点在于分析算法的时间、空间复杂度，以及如何通过逻辑结构来设计算法，存储结构来实现算法。 #### 重要概念总结 - **数据元素**：数据的基本单位。 - **数据项**：构成数据元素的不可分割的最小单位。 - **数据对象**：具有相同性质的数据元素的集合。 - **数据类型**：一组值的集合和定义在这些值上的一组操作的总称。 - **原子类型**：值不可再分的数据类型，如整型。 - **结构类型**：值可以再分为若干成分的数据类型，如结构体。 通过学习以上概念和知识点，我们可以更好地理解和掌握数据结构的基础框架和算法效率分析的基本方法。