> ## Documentation Index
> Fetch the complete documentation index at: https://docs.0907world.cn/llms.txt
> Use this file to discover all available pages before exploring further.

# 第 1 章 绪论

本章是数据结构课程的开篇，主要复习数据结构的基本概念、术语，以及算法的特性与分析方法建议重点掌握逻辑结构与物理结构的区别，以及算法复杂度的基本分析思路

## 基本概念和术语

<AccordionGroup>
  <Accordion title="核心概念：数据、元素、对象与结构">
    * **数据**：对客观事物的符号表示，在计算机科学中指所有能输入到计算机中并被程序处理的符号的总称
    * **数据元素**：数据的基本单位，在程序中通常作为一个整体进行考虑和处理
      <Info>一个数据元素可由若干个**数据项**组成</Info>
    * **数据对象**：性质相同的数据元素的集合，是数据的一个子集
    * **数据结构**：相互之间存在一种或多种特定关系的数据元素的集合包含三个方面的内容：**逻辑结构**、**存储结构**和**数据的运算**
  </Accordion>

  <Accordion title="逻辑结构与存储结构">
    * **逻辑结构**：
      * 线性结构
      * 非线性结构（集合、树形结构、图状结构或网状结构）

    * **存储结构（物理结构）**：数据结构在计算机中的表示（又称映像）
      <Info>数据元素在计算机中的映像称为**元素或结点**当数据元素由若干数据项组成时，对应于各数据项的子位串称为**数据域**</Info>
      主要包含四种：
      1. 顺序存储结构（顺序映像）
      2. 链式存储结构（非顺序映像）
      3. 索引存储
      4. 散列存储（哈希存储）

    <Tip>**结论**：算法的设计取决于选定的**数据逻辑结构**，而算法的实现依赖于采用的**存储结构**</Tip>
  </Accordion>

  <Accordion title="数据类型与抽象数据类型 (ADT)">
    * **数据类型**：与数据结构密切相关，最早出现在高级程序语言中，用以刻画（程序）操作对象的特性
      * 原子类型
      * 结构类型
    * **抽象数据类型 (ADT)**：指一个数学模型以及定义在该模型上的一组操作
      * 原子类型
      * 固定聚合类型
      * 可变聚合类型
        <Info>固定聚合类型与可变聚合类型可统称为结构类型</Info>
    * **多形数据类型**：指其值的成分不确定的数据类型
  </Accordion>
</AccordionGroup>

## 算法和算法分析

<AccordionGroup>
  <Accordion title="算法的 5 个重要特性">
    <Tip>记忆口诀：**有穷、确定、可行、输入、输出**</Tip>

    * **有穷性**：算法必须在执行有限步之后结束
    * **确定性**：算法的每条指令必须有确切的含义
    * **可行性**：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现
    * **输入**：一个算法有零个或多个输入
    * **输出**：一个算法有一个或多个输出
  </Accordion>

  <Accordion title="算法的设计要求">
    好的算法通常需要满足以下四个要求：

    * **正确性**：满足具体问题的需求
    * **可读性**：便于人们阅读、理解和交流
    * **健壮性**：当输入数据非法时，算法也能适当地做出反应或进行处理
    * **效率与低存储量需求**：执行时间短（时间复杂度低），且不占用过多内存（空间复杂度低）
  </Accordion>

  <Accordion title="算法效率的度量与空间需求">
    * **算法效率的度量方法**：
      * 事后统计的方法
      * 事前分析估算的方法
    * **算法的存储空间需求**：
      <Warning>**易错点**：如果一个问题所占的输入数据空间是固定的、和算法无关的，那么我们在分析空间复杂度时，**只需要关注算法额外使用的空间（也叫辅助空间）**</Warning>
  </Accordion>
</AccordionGroup>