# 第 1 章 绪论（示例讲义）

> 本文件是示例知识库的演示材料，为简化版讲义提纲。

## 1.1 什么是数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
研究内容包括三个层面：

- **逻辑结构**：数据元素之间的逻辑关系 —— 集合、线性结构、
  树形结构、图状结构四大类。
- **存储结构（物理结构）**：逻辑结构在计算机中的表示 ——
  顺序存储、链式存储、索引存储、散列存储。
- **数据的运算**：插入、删除、查找、排序等，定义在逻辑结构上，
  实现依赖存储结构。

## 1.2 抽象数据类型（ADT）

抽象数据类型 = 数据对象 + 数据关系 + 基本操作。
ADT 把「做什么」与「怎么做」分离：使用者只关心操作语义，
实现者决定存储与算法。例如 ADT Stack 只规定 push/pop/top 的行为，
不规定用数组还是链表实现。

## 1.3 算法及其评价

算法的五个特性：有穷性、确定性、可行性、输入、输出。

### 时间复杂度

用渐进上界 O 记号描述基本操作执行次数随问题规模 n 的增长趋势：

- 常见量级：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
- 分析方法：找出最深层循环中的基本操作，数它的执行次数。
- 例：两层嵌套循环遍历 n×n 矩阵为 O(n²)；折半查找每次缩小一半
  规模，为 O(log n)。

### 空间复杂度

算法运行过程中临时占用存储空间的量级。原地工作的算法空间复杂度
为 O(1)；递归算法的空间复杂度要计入递归工作栈的深度。

## 本章要点（考试常考）

1. 逻辑结构与存储结构的区别与举例。
2. ADT 的三要素。
3. 给一段代码，写出其时间复杂度（必考，通常 1-2 题）。
4. 递归程序的空间复杂度分析。
