余弦の博客

稀疏表（Sparse Table）是一种用于解决区间最值查询的算法，预处理时间为O(n log n)，查询时间为O(1)，但不支持在线修改。通过预处理出每个区间长度为2^j的最值，利用对数函数确定查询区间的划分，实现快速查询。

本文介绍了树结构的基本概念、术语、二叉树的定义与特性、遍历方法以及存储结构。重点讲解了树的定义、节点属性、二叉树的五种基本形态、重要性质（如节点关系与完全二叉树的深度），以及二叉树的顺序存储和链式存储方式，并详细说明了前序、中序、后序和层序遍历的递归与非递归实现方法。

本文介绍了队列这一抽象数据类型，包括其基本操作和两种存储实现方式：顺序存储（循环队列）和链式存储。循环队列通过数组的循环利用实现高效插入和删除，使用n-1个空间区分空和满状态；链式存储则使用单链表，通过头尾指针实现队列的入队和出队操作。

本文介绍了栈（Stack）这一抽象数据类型，包括其数据对象集和基本操作，详细说明了栈的顺序存储和链式存储实现方法，并通过实例讲解了栈在表达式求值中的应用，如将中缀表达式转换为后缀表达式，同时还提到了栈在函数调用、递归、深度优先搜索和回溯算法等场景中的应用。

本文介绍了广义表和多链表两种数据结构。广义表允许元素本身也是广义表，而多链表通过多个指针字段实现节点间的多向连接，适用于复杂数据结构如树和图的存储。以稀疏矩阵为例，使用“正交链表”结构只存储非零元素，通过行指针和列指针实现行和列的连接，并用标签字段区分头节点和非零元素节点。

本文介绍了线性表的抽象数据类型及其两种存储结构——顺序存储和链式存储。顺序存储通过数组实现，支持高效随机访问，操作包括初始化、查找、插入、删除和求长度；链式存储通过链表节点连接元素，无需移动数据，插入和删除仅修改指针，效率较高且灵活。文章通过代码演示了两种存储方式的基本操作及运行结果。