数据结构案例教程（C语言版）

数据结构案例教程（C语言版）内容总结

• 这本书系统地介绍了C语言常用的数据结构，包括线性表、栈、队列、串、数组、树、图以及查找和排序。
• 你能获得：通过学习本书，你将掌握各种数据结构的特点、存储实现及基本操作，为高效编写软件打下坚实基础。

核心内容

1. 数据结构基础

• 计算机科学是研究数据表示和数据处理的科学，要设计一个结构好而且效率高的程序，必须研究数据的特性、数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。

• 计算机处理的对象之间通常存在着一种简单的线性关系，这类数学模型可称为线性的数据结构，如表、树、图的数据结构。

• 数据结构的形式定义为一个二元组：D_S=(D,R))，D是数据元素的有限集，R是D上关系的有限集，数据结构包括数据逻辑结构和数据存储结构。

• 抽象数据类型（ADT）是指一个数学模型及定义在该模型上的一组操作，抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。

• 算法（Algorithm）是为解决特定问题而规定的一系列操作，一个算法应该具有有穷性、确定性、可行性、输入、输出五个重要特性。

• 算法的优劣应从正确性、可读性、健壮性、高效性几个方面来评价，算法性能分析的标准主要从算法执行时间与占用存储空间两方面考虑，即用算法执行所需的时间和存储空间来判断一个算法的优劣。

• 详细解释：

  • 数据是信息的载体，可以是数值或非数值数据。
  • 数据元素是数据的基本单位，可由多个数据项组成。
  • 数据对象是相同性质的数据元素的集合。
  • 数据逻辑结构分为集合、线性结构、树结构和图结构。
  • 数据存储结构包括顺序存储、链式存储、索引存储和散列存储。

2. 线性表

• 线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其特点包括有序性、有穷性和同一性。

• 线性表的存储方式包括顺序存储（顺序表）和链式存储（链表）。

• 顺序表：一组地址连续的存储单元顺序存放线性表的各个数据元素。特点是逻辑上相邻的数据元素，其物理存储次序也相邻，是一种随机存取的存储结构。

• 链表：通过一组任意的存储单元来存储线性表中数据元素，不需要用地址连续的存储单元来实现，而是通过“链”建立起数据元素之间的逻辑关系，插入、删除不需要移动数据元素。

• 详细解释：

  • 顺序表的优点是存取速度快，缺点是插入和删除元素需要移动大量元素，且存储空间是静态分配的。
  • 链表的优点是插入和删除元素不需要移动元素，且存储空间是动态分配的，缺点是存取速度慢。

3. 栈和队列

• 栈是限制在表的一端（表尾）进行插入和删除操作的线性表，遵循“后进先出”（LIFO）原则。

• 队列是一种“先进先出”（FIFO）的数据结构，插入操作在表的一端进行，而删除操作在表的另一端进行。

• 栈常用于子程序的嵌套调用、操作系统的中断处理、括号匹配、表达式求值和函数的递归调用等。

• 队列常用于资源等待队列、就绪队列以及排队等候等。

• 详细解释：

  • 栈的存储方式包括顺序栈和链栈。
  • 队列的存储方式包括链队列和循环队列。
  • 递归过程与栈：递归函数的调用类似于多层函数的嵌套调用，在每次调用时，系统将属于各个递归层次的信息保存在系统的“递归工作栈”中。

4. 串

• 串（即字符串）是由零个或任意多个字符组成的有限序列，是一种特殊的线性表。

• 串主要用于信息检索、文本编辑等领域。

• 串的抽象数据类型定义包括StrAsign, StrCopy, StrLength, StrCat, SubString, StrIndex, StrInsert, StrDelete, StrReplace, StrEmpty, StrCompare等。

• 模式匹配

  是串中最主要的操作之一，

  BF

  算法和

  KMP

  算法是两种常用的字符串匹配算法。

• 详细解释：

  • 串的存储方式包括
    • 定长顺序存储：长度固定的字符数组，容易产生溢出。
    • 堆存储：动态分配存储空间，操作灵活，但需要手动管理内存。
    • 块链存储：以链表形式存储，每个节点可以存储多个字符。
  • BF算法（Brute Force）：简单直观，时间复杂度高。
  • KMP算法：通过预处理模式串，减少不必要的比较，提高匹配效率。

5. 数组和广义表

• 数组可看作线性表的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。

• 数组类型包含一维数组、二维数组等，每一个数据元素用唯一的一组下标来标识。

• 广义表是线性表的推广，其中的数据元素可以是原子也可以是子表。

• 数组主要有取值和设值操作，广义表主要有求长度以及取表头、表尾操作。

• 详细解释：

  • 数组可采用顺序存储结构，分为以行为主序和以列为主序两种方式。
  • 特殊矩阵（如对称矩阵、三角矩阵）为了节省存储空间，可以采用压缩存储方式。
  • 对于稀疏矩阵（矩阵中非零元素远少于零元素）， 采用三元组顺序表或十字链表等方式表示。
  • 广义表的应用：符号计算系统、人工智能。

6. 树和二叉树

• 树是n（n≥0）个节点的有限集合，具有分支关系的层次结构。

• 二叉树是每个节点最多只有两个子节点的树，具有五种基本形态。

• 树和二叉树存储：

  • 树的存储结构有三种：双亲表示法、孩子表示法和孩子兄弟表示法。
  • 二叉树的存储结构可采用顺序存储和链式存储两种方式。

• 树可以通过孩子兄弟表示法转换为二叉树，森林可以通过将每棵树的根节点相连转换为二叉树。

• 线索二叉树为了保留节点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。

• 哈夫曼树也称最优二叉树，是指具有最小带权路径长度的二叉树，哈夫曼编码是将字符集合编码形成不等长编码，用于数据压缩等方面，常用于信息传输。

• 详细解释：

  • 二叉树的遍历分为先序遍历、中序遍历和后序遍历。
  • 可以通过先序序列和中序序列重构二叉树。
  • 哈夫曼编码的主要思想是使出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码。

7. 图

• 图是由顶点集合和边集合组成的数据结构，用于描述顶点之间的关系，关系可以是任意的，非常灵活。

• 与树不同，图无根节点，且图中任一顶点都可能和其他顶点相关，顶点之间的联系也可以称为网络。

• 图可以分为有向图和无向图。

• 图的存储方式包括邻接矩阵、邻接表、十字链表、邻接多重表等。

• 图的遍历分为深度优先搜索和广度优先搜索。

• 图的一个典型应用是

  最小生成树

  ，最小生成树的两个算法分别为

  Prim

  算法和

  Kruskal算法

  • Prim 算法通过逐步增加结点来构建最小生成树。
  • Kruskal 算法通过逐步增加边来构建最小生成树。

• 图还有一种重要算法

  最短路径问题

  • Dijkstra 算法是一种解决从单个源节点到所有其他节点的最短路径问题的经典算法。

• 详细解释：

  • 邻接矩阵适合稠密图，邻接表适合稀疏图。
  • 深度优先搜索类似于树的先根遍历，广度优先搜索类似于树的层次遍历。

8. 查找

9. 排序

• 排序是将一个数据元素集合或序列重新排列成按关键字非递减或非递增顺序排列的过程。

• 排序分为内部排序和外部排序。

• 内部排序算法可以分为以下几类：插入排序、交换排序、选择排序、归并排序和基数排序。

• 内部排序算法的评价主要考虑时间复杂度和空间复杂度。

• 详细解释：

  • 插入排序：直接插入排序、折半插入排序、希尔排序。
  • 交换排序：冒泡排序、快速排序。
  • 选择排序：简单选择排序、堆排序。
  • 归并排序。
  • 基数排序。

问答

Q: 数据结构和抽象数据类型有什么区别？

A: 数据结构是一种抽象概念，侧重于数据元素之间的关系；抽象数据类型是指一个数学模型及定义在该模型上的一组操作，关注的是"做什么"，而不是"怎么做"，将一切用户不必了解的细节封装起来，从而简化了问题。

Q: 如何选择顺序表和链表？

A: 顺序表的访问速度快，但插入和删除操作效率低，且存储空间是静态分配的；链表的插入和删除操作效率高，且存储空间是动态分配的，但访问速度慢，频繁做插入、删除等“动态性”较强的线性表宜选择链式存储。

Q: 什么是KMP算法？它有什么优点？

A: KMP算法是一种字符串匹配算法，通过利用已经“部分匹配”的结果，调整模式串指针，避免不必要的回溯，提高了匹配效率，相比BF算法，时间复杂度更低。

Q: 什么是最小生成树？有哪些算法可以构造最小生成树？

A: 最小生成树是指一个连通图中，包含所有顶点，且边的权值之和最小的树。Prim算法和Kruskal算法是两种常用的构造最小生成树的算法，分别采用加点法和加边法。

Q: 稳定排序和非稳定排序的区别是什么？哪些排序算法是稳定的？

A: 稳定排序是指，在具有相同主关键字的记录序列，经过排序后这些具有相同关键字的记录之间的相对次序不变。这样的排序方法是稳定的。反之，是一种不稳定的排序方法。

• 稳定的排序算法：
  • 直接插入排序、冒泡排序、归并排序、基数排序
• 不稳定的排序算法：
  • 希尔排序、快速排序、选择排序、堆排序