图的基本概念

图（Graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。图 $G$ 可以抽象地表示为顶点集合 $V$ 和边集合 $E$ 的组合。通常情况下，图的数据结构会表示为 $G = \{ V, E \}$。

哈夫曼编码概述

哈夫曼编码是一种广泛使用的无损压缩算法，属于熵编码（Entropy Encoding）的一种。它通过使用频率较高的字符分配较短的编码，频率较低的字符分配较长的编码，来实现数据压缩。哈夫曼编码的核心思想是基于字符出现频率的二叉树（哈夫曼树）来构建编码方案。

主要特点

• 最优性：在给定字符及其频率的情况下，哈夫曼编码能够生成最优的前缀码，即没有一个编码是另一个编码的前缀，从而保证了解码的唯一性。
• 动态性：哈夫曼编码可以根据输入数据的不同动态生成不同的编码方案，适应性强。
• 无损压缩：编码后数据可完全还原，无任何信息丢失。

一、表达式的基本概念

在计算机科学中，表达式是用来计算值的语句。表达式可以用不同的表示法进行书写，每种表示法在处理计算和编译时有不同的作用。以下是三种主要的表达式表示法：

1. 中缀表达式 (Infix Expression)

   • 操作符位于操作数之间。
   • 示例：A + B，3 * (4 + 5)。
   • 中缀表达式是我们最常见的数学表达式形式，它在数学和计算中广泛使用。

2. 前缀表达式 (Prefix Expression)

   • 操作符位于操作数之前。
   • 示例：+ A B，* 3 + 4 5。
   • 前缀表达式也被称为波兰表示法，不需要括号来确定操作顺序，这使得它在计算机处理中非常高效。

3. 后缀表达式 (Postfix Expression)

   • 操作符位于操作数之后。
   • 示例：A B +，3 4 5 + *。
   • 后缀表达式也称为逆波兰表示法，它同样不需要括号来确定操作顺序，便于计算机程序进行计算。

堆（Heap）

堆（heap）是一种满足特定条件的完全二叉树，主要分为两种类型：

• 小顶堆（min heap）：任意节点的值 (\leq) 其子节点的值。
• 大顶堆（max heap）：任意节点的值 (\geq) 其子节点的值。

小顶堆与大顶堆

堆作为完全二叉树的一个特例，具有以下特性：

1. 最底层节点靠左填充，其他层的节点都被填满。
2. 我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。
3. 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。

树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。树型结构在现实世界中广泛存在，如社会组织机构的组织关系图就可以用树型结构来表示。树在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构。在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。在许多算法中，常用树型结构描述问题的求解过程、所有解的状态和求解的对策等。这些年的国内、国际信息学奥赛、大学生程序设计比赛等竞赛中，树型结构成为参赛者必备的知识之一，尤其是建立在树型结构基础之上的搜索算法。

在树型结构中，二叉树是最常用的结构，它的分支个数确定，又可以为空，并有良好的递归特性，特别适宜于程序设计，因此也常常将一般树转换成二叉树进行处理。

队列 (Queue) 基本概念

队列（Queue）是一种常见的线性数据结构，遵循先进先出（First-In-First-Out, FIFO）的原则。类似于我们在现实生活中排队等待的场景，先来的人先被服务。

在队列中，元素的插入操作（入队）是在队列尾部进行，而元素的删除操作（出队）是在队列头部进行。这使得队列成为一种适合于顺序处理任务的数据结构。

栈 (Stack) 基本概念

栈（Stack）是一种常见的线性数据结构，遵循后进先出（Last-In-First-Out, LIFO）的原则。类似于我们在现实生活中堆叠书本或盘子的方式，最后放入的元素最先被取出。

在栈中，元素的插入操作（入栈）是在栈顶进行，而元素的删除操作（出栈）也是在栈顶进行。这使得栈成为一种适合于后续操作依赖于最近插入的元素的数据结构。

栈通常具有以下两个基本操作：

• 入栈（Push）： 将元素添加到栈顶。
• 出栈（Pop）： 从栈顶移除一个元素。