本章是数据结构课程的开篇，主要复习数据结构的基本概念、术语，以及算法的特性与分析方法建议重点掌握逻辑结构与物理结构的区别，以及算法复杂度的基本分析思路Documentation Index
Fetch the complete documentation index at: https://0907.mintlify.app/llms.txt
Use this file to discover all available pages before exploring further.
基本概念和术语
核心概念：数据、元素、对象与结构
核心概念：数据、元素、对象与结构
- 数据：对客观事物的符号表示，在计算机科学中指所有能输入到计算机中并被程序处理的符号的总称
- 数据元素：数据的基本单位，在程序中通常作为一个整体进行考虑和处理
一个数据元素可由若干个数据项组成
- 数据对象：性质相同的数据元素的集合，是数据的一个子集
- 数据结构：相互之间存在一种或多种特定关系的数据元素的集合包含三个方面的内容：逻辑结构、存储结构和数据的运算
逻辑结构与存储结构
逻辑结构与存储结构
-
逻辑结构：
- 线性结构
- 非线性结构（集合、树形结构、图状结构或网状结构）
-
存储结构（物理结构）：数据结构在计算机中的表示（又称映像）
主要包含四种：数据元素在计算机中的映像称为元素或结点当数据元素由若干数据项组成时，对应于各数据项的子位串称为数据域
- 顺序存储结构（顺序映像）
- 链式存储结构（非顺序映像）
- 索引存储
- 散列存储（哈希存储）
数据类型与抽象数据类型 (ADT)
数据类型与抽象数据类型 (ADT)
- 数据类型：与数据结构密切相关，最早出现在高级程序语言中，用以刻画（程序）操作对象的特性
- 原子类型
- 结构类型
- 抽象数据类型 (ADT)：指一个数学模型以及定义在该模型上的一组操作
- 原子类型
- 固定聚合类型
- 可变聚合类型
固定聚合类型与可变聚合类型可统称为结构类型
- 多形数据类型：指其值的成分不确定的数据类型
算法和算法分析
算法的 5 个重要特性
算法的 5 个重要特性
- 有穷性：算法必须在执行有限步之后结束
- 确定性：算法的每条指令必须有确切的含义
- 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现
- 输入：一个算法有零个或多个输入
- 输出：一个算法有一个或多个输出
算法的设计要求
算法的设计要求
好的算法通常需要满足以下四个要求：
- 正确性：满足具体问题的需求
- 可读性：便于人们阅读、理解和交流
- 健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理
- 效率与低存储量需求：执行时间短（时间复杂度低），且不占用过多内存（空间复杂度低）
算法效率的度量与空间需求
算法效率的度量与空间需求
- 算法效率的度量方法：
- 事后统计的方法
- 事前分析估算的方法
- 算法的存储空间需求：