(数据结构)清华大学出版社

数据结构C语言版·第2版清华大学计算机系列教材·严蔚敏吴伟民编著Contents目录数据结构（清华大学出版社）课程知识体系总览，涵盖从基础理论到算法应用的完整学习路径。01基础理论篇：绪论与线性结构02进阶结构篇：树、图与非线性结构03算法应用篇：排序与查找技术CHAPTER01基础理论篇从问题抽象到程序实现的思维跃迁Chapter01·基础理论数据结构核心概念数据结构是计算机存储、组织数据的方式，包含逻辑结构、存储结构和运算三个要素。良好的数据结构设计能显著提升算法效率，是程序性能优化的基石。基本概念体系集合·线性·树形·图形四类逻辑结构01数据元素是数据的基本单位，可由多个数据项组成，如学生记录包含学号、姓名等字段02逻辑结构分为集合、线性、树形和图形四类，决定了数据元素间的内在关系03存储结构包括顺序、链式、索引和散列四种实现方式，影响算法的时间与空间效率算法分析方法不同复杂度函数的增长曲线对比01时间复杂度用大O表示法描述执行时间随输入规模增长的趋势，如O(n²)表示平方级增长02空间复杂度衡量算法运行所需的额外存储空间，递归算法需特别关注栈空间消耗03最坏情况分析保证算法在任何输入下的性能下限，是工程实践中常用的评估标准DataStructures·LinearList线性表实现对比线性表的顺序存储与链式存储各有优劣，顺序表适合频繁查询场景，链表适合动态增删场景。实际应用中需根据操作频率选择合适结构。连续内存空间的数组存储方式顺序表连续内存空间实现，支持O(1)随机访问，但插入删除需O(n)时间移动元素需预先分配固定容量，动态扩容导致数据拷贝，空间利用率存在波动约瑟夫环问题中，数组下标运算可直观模拟环形计数过程节点与指针链接的链式存储结构单链表节点通过指针链接，插入删除仅需O(1)修改指针，但查询需O(n)遍历动态分配内存，无容量限制，但指针域增加额外空间开销约瑟夫环实现时，链表节点的物理删除更符合问题描述包含前驱与后继指针的链式结构双向链表增加前驱指针实现双向遍历，删除操作无需前驱节点查询，效率提升每个节点需存储两个指针，空间开销比单链表增加50%适用于频繁前后移动的场景，如浏览器历史记录管理Chapter02进阶结构篇从线性到非线性的结构跃迁DataStructures堆栈与队列对比堆栈与队列是操作受限的线性表，分别遵循LIFO和FIFO原则，是理解递归、广度优先搜索等概念的基础。堆栈（LIFO）迷宫路径搜索·回溯过程可视化仅允许在栈顶进行插入删除，函数调用栈、括号匹配等场景天然适配顺序栈需预判容量防止溢出，链栈动态分配但增加指针开销迷宫求解通过栈记录路径，回溯时可逐层弹出错误分支队列（FIFO）银行排队叫号系统·公平调度示例队头删除、队尾插入，适用于任务调度、层次遍历等场景循环队列通过取模运算解决假溢出问题，空间利用率显著提升银行排队系统通过队列实现公平调度，VIP队列可扩展优先级机制Chapter04·树与二叉树二叉树核心知识二叉树是递归定义的非线性结构，其遍历算法与存储方式直接影响程序效率。哈夫曼树等应用展示了数据结构在信息压缩领域的核心价值。逻辑结构每个节点最多两棵子树，左右子树有序不可交换。满二叉树与完全二叉树是特殊形态，具有严格的数学性质。二叉搜索树通过左小右大规则实现高效查找，平衡二叉树（AVL、红黑树）保证操作对数时间复杂度。Structure存储实现顺序存储用数组表示，完全二叉树可节省空间，普通树需补空节点。链式存储用leftChild/rightChild指针，灵活但增加内存开销。线索二叉树利用空指针域存储遍历前驱后继，避免递归栈空间，提升遍历效率。Storage遍历与应用前序遍历（根-左-右）适合表达式树求值，中序遍历输出有序序列，后序遍历用于计算子树高度。层次遍历借助队列实现广度优先搜索。哈夫曼树通过带权路径最小化实现数据压缩，广泛应用于文件编码。TraversalCHAPTER03算法应用篇从理论到实践的算法工程化SortingAlgorithms经典排序算法对比排序算法的选择需综合考虑时间复杂度、空间开销、稳定性等因素。从O(n²)的基础算法到O(nlogn)的高效算法，体现了算法设计的渐进优化思想。INSERTION插入排序直接插入排序逐步插入元素构建有序序列，适合小规模基本有序数据希尔排序按增量分组插入，最终增量为1时完成全局排序，平均O(n1.3)稳定性：直接插入稳定，希尔排序不稳定（跨组交换破坏顺序）O(n1.3)SELECTION选择排序直接选择排序每次选最小元素放到已排序末尾，复杂度恒为O(n²)堆排序利用堆顶元素最大/最小特性，通过堆调整实现O(nlogn)稳定性：直接选择不稳定（交换破坏顺序），堆排序不稳定O(nlogn)EXCHANGE交换排序冒泡排序通过相邻元素交换将最大元素"浮"到末尾，最优O(n)快速排序选