第一章 数据与数据的组织

1.1 数据

数据的定义

  • 数据是对客观事物的符号表示，是信息的载体。
  • 在计算机科学中，数据是指所有能输入到计算机并被计算机程序处理的符号总称。

数据的分类

  • 数值型数据：整数、浮点数等。
  • 非数值型数据：字符、字符串、图像、音频、视频等。

数据的基本单位

  • 位（bit）：计算机中数据的最小单位，表示一个二进制0或1。
  • 字节（Byte）：1 Byte = 8 bit，是计算机中存储容量的基本单位。

数据类型

  • 整型（int）、浮点型（float）、字符型（char）、布尔型（bool）等。

1.2 数据的组织

数据结构的概念

  • 数据结构是指数据元素之间存在一种或多种特定关系的集合。
  • 数据结构包括逻辑结构和存储结构两个层次。

逻辑结构

  • 集合结构：数据元素间仅存在“同属一个集合”的关系。
  • 线性结构：数据元素之间存在一对一的关系（如数组、链表、队列、栈）。
  • 树形结构：数据元素之间存在一对多的关系（如二叉树）。
  • 图形结构：数据元素之间存在多对多的关系（如图、网络）。

存储结构

  • 顺序存储：用一组连续的存储单元依次存储数据元素。
  • 链式存储：用一组任意的存储单元存储数据元素，通过指针建立联系。

第二章 数组与链表

2.1 数组

数组的定义

  • 数组是一种线性数据结构，由相同类型的元素组成，并占用连续的内存空间。

数组的特点

  • 元素类型相同，内存连续。
  • 支持随机访问，通过下标可在O(1)时间内访问任意元素。
  • 插入和删除操作效率较低，平均需要O(n)时间移动元素。

多维数组

  • 二维数组可看作“数组的数组”，常用于表示矩阵、表格等。
  • 存储方式：行优先（C/C++、Python）或列优先（Fortran）。

数组的基本操作

  • 创建、访问、修改、遍历、插入、删除。

2.2 链表

链表的定义

  • 链表是一种线性数据结构，由一系列节点组成，节点之间通过指针链接。

节点的结构

  • 数据域：存储数据元素。
  • 指针域：存储指向下一个节点的指针。

链表的分类

  • 单向链表：每个节点只有一个指向后继的指针。
  • 双向链表：每个节点有指向前驱和后继的两个指针。
  • 循环链表：最后一个节点的指针指向头节点，形成环状。

链表的特点

  • 内存不连续，通过指针连接。
  • 插入和删除操作效率高，只需修改指针，O(1)时间。
  • 不支持随机访问，查找元素需要遍历，O(n)时间。

链表的基本操作

  • 创建、插入（头插、尾插、中间插入）、删除、查找、遍历。

数组与链表的比较

  • 访问速度：数组快（O(1)），链表慢（O(n)）。
  • 插入/删除效率：数组慢（需移动元素），链表快（改指针）。
  • 内存使用：数组连续分配，链表有额外指针开销。

第三章 字符串、队列和栈

3.1 字符串

字符串的定义

  • 字符串是由零个或多个字符组成的有限序列。
  • 字符串通常用双引号表示，如"hello world"。

字符串的基本操作

  • 求长度（len）、拼接（+）、比较、截取子串、查找子串、替换等。

字符串的存储

  • 顺序存储：用连续内存存储字符数组，末尾常加结束符（如C语言的'\0'）。
  • 链式存储：每个节点存储一个或多个字符（块链结构）。

字符串匹配算法

  • 朴素匹配：逐个位置比较，时间复杂度O(mn)。
  • KMP算法：利用部分匹配信息，时间复杂度O(m+n)。

3.2 队列

队列的定义

  • 队列是一种先进先出（FIFO，First In First Out）的线性数据结构。

队列的基本操作

  • 入队（enqueue）：在队尾添加元素。
  • 出队（dequeue）：移除队首元素并返回。
  • 判空（isEmpty）：判断队列是否为空。
  • 取队首（peek/front）：返回队首元素但不删除。

队列的存储实现

  • 顺序队列：用数组实现，需处理“假溢出”问题，常采用循环队列。
  • 链式队列：用链表实现，有队首和队尾指针。

队列的应用

  • 任务调度、消息队列、缓冲区、广度优先搜索（BFS）等。

3.3 栈

栈的定义

  • 栈是一种后进先出（LIFO，Last In First Out）的线性数据结构。

栈的基本操作

  • 入栈（push）：在栈顶添加元素。
  • 出栈（pop）：移除栈顶元素并返回。
  • 判空（isEmpty）：判断栈是否为空。
  • 取栈顶（peek/top）：返回栈顶元素但不删除。

栈的存储实现

  • 顺序栈：用数组实现，栈顶指针指向最新元素。
  • 链式栈：用链表实现，栈顶为链表头节点。

栈的应用

  • 函数调用栈、表达式求值、括号匹配、深度优先搜索（DFS）、撤销操作等。

第四章 树

4.1 树与二叉树

树的定义

  • 树是由n（n≥0）个节点组成的有限集合。n=0时为空树。
  • 非空树有且仅有一个根节点，其余节点可分为互不相交的若干子树。

树的基本术语

  • 节点：树的基本单元。
  • 度：节点拥有的子树数。
  • 叶子：度为0的节点。
  • 分支节点：度大于0的节点。
  • 孩子、双亲、兄弟：节点之间的层次关系。
  • 层次：根为第1层，依次递增。
  • 深度：树中节点的最大层次数。

二叉树

  • 每个节点最多有两棵子树（左子树和右子树），有左右之分。
  • 满二叉树：所有叶子节点都在同一层，且所有非叶子节点都有左右孩子。
  • 完全二叉树：除了最后一层，其他层节点数达到最大，且最后一层节点靠左排列。

二叉树的性质

  • 第i层最多有2^(i-1)个节点。
  • 深度为k的二叉树最多有2^k - 1个节点。
  • 叶子节点数 = 度为2的节点数 + 1。

二叉树的遍历

  • 前序遍历：根 → 左 → 右。
  • 中序遍历：左 → 根 → 右。
  • 后序遍历：左 → 右 → 根。
  • 层次遍历：从上到下、从左到右逐层访问。

4.2 二叉树的基本操作

二叉树的存储

  • 顺序存储：用数组存放，适合完全二叉树。
  • 链式存储：每个节点包含数据域、左指针、右指针。

二叉树的基本操作

  • 创建二叉树、插入节点、删除节点、查找节点。
  • 遍历（递归与非递归实现）、求深度、求叶子节点数等。

二叉搜索树（BST）

  • 左子树上所有节点的值均小于根节点的值。
  • 右子树上所有节点的值均大于根节点的值。
  • 中序遍历BST得到有序序列。
  • 查找、插入、删除操作平均时间复杂度O(log n)。

4.3 抽象数据类型

抽象数据类型的概念

  • 抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。
  • ADT强调“做什么”而非“怎么做”，实现了数据抽象和信息隐藏。

ADT的表示

  • ADT通常用三元组表示：（数据对象、数据关系、基本操作）。

常见ADT举例

  • 栈ADT：数据对象为元素序列，操作有push、pop、isEmpty等。
  • 队列ADT：操作有enqueue、dequeue、isEmpty等。
  • 二叉树ADT：操作有遍历、插入、删除、查找等。

第五章 数据结构与算法

5.1 数据结构与算法的关系

  • 程序 = 数据结构 + 算法。
  • 数据结构是算法的基础，为算法提供组织数据的方式。
  • 算法是对数据的具体操作步骤，不同的数据结构适合不同的算法。

5.2 迭代与递归

迭代

  • 迭代是通过循环结构重复执行一段代码，每次迭代更新变量的值。
  • 示例：for循环、while循环实现累加、遍历等。

递归

  • 递归是指函数直接或间接调用自身。
  • 递归需要满足两个条件：①存在递归终止条件（基线条件）；②每次递归调用都向终止条件靠近。

递归与迭代的比较

  • 递归代码简洁易懂，但可能栈溢出、效率较低（有函数调用开销）。
  • 迭代效率高，但某些问题（如树的遍历）用递归更自然。

常见递归算法

  • 斐波那契数列、汉诺塔、二叉树遍历、快速排序等。

5.3 数据排序

排序算法的稳定性

  • 稳定排序：相等元素的相对顺序在排序后保持不变。

常见排序算法

  • 冒泡排序：相邻元素比较交换，O(n²)，稳定。
  • 选择排序：每轮选择最小（大）元素放到已排序末尾，O(n²)，不稳定。
  • 插入排序：将元素插入已排序序列的合适位置，O(n²)，稳定。
  • 快速排序：分治思想，选基准划分，O(n log n)平均，不稳定。
  • 归并排序：分治法，合并有序序列，O(n log n)，稳定。
  • 希尔排序：改进的插入排序，O(n^1.3)平均，不稳定。

5.4 数据查找

顺序查找

  • 从第一个元素开始逐个比较，时间复杂度O(n)。

二分查找（折半查找）

  • 要求数据有序（通常是升序），每次与中间元素比较，缩小查找范围。
  • 时间复杂度O(log n)。

哈希查找

  • 利用哈希函数直接计算存储位置，理想情况O(1)。
  • 需处理哈希冲突（开放地址法、链地址法）。

二叉搜索树查找

  • 利用BST性质查找，平均O(log n)。

第六章 大数据时代数据的组织

6.1 实时查询系统中数据的组织

  • 实时查询系统要求低延迟、高并发，如搜索引擎、推荐系统等。
  • 常用技术：倒排索引、缓存、分布式存储（如Redis、Memcached）。

倒排索引

  • 以关键词为主键，记录包含该关键词的文档列表。
  • 常用于全文搜索引擎，可快速定位包含查询词的文档。

6.2 POI数据的组织与应用

POI数据的概念

  • POI（Point of Interest，兴趣点）是指地理信息中的点状要素，如餐馆、商场、学校等。
  • 每个POI通常包含名称、类别、经纬度、地址等信息。

POI数据的组织

  • 常用空间索引结构：网格索引、四叉树、R树等，用于快速空间查询。
  • 可存储于关系型数据库或NoSQL数据库（如MongoDB）。

POI数据的应用

  • 地图应用（如百度地图、高德地图）的附近搜索功能。
  • 位置推荐、路径规划、地理围栏等。