第6次上机课实验题kkkkkkkkkkkkkkk

在本次的实验课中，我们将关注三个主要任务：二叉树的统计、堆的基本操作实现以及并查集的实现。这些任务都是数据结构与算法领域中的核心概念，对于理解和掌握计算机科学的基础至关重要。 Task 1是关于二叉树的统计。我们需要编写一个名为`count.cpp`的程序，它能够接收一个表示扩展二叉树前序序列的字符串输入，其中空节点由字符'#'表示。程序的目标是计算这个二叉树中只有一个孩子（即叶子节点或单分支节点）的节点数量。例如，输入"AB#D##C##"将返回1，因为在这个树形结构中，只有一个节点B只有一个孩子。要注意，实现这个功能时不能使用C++/STL库，但可以使用stdlib、stdio、iostream、memory和malloc的头文件。 接下来，Task 2涉及堆的操作实现。你需要编写`heap.cpp`，实现一个堆的数据结构。堆是一种特殊的树形数据结构，通常用于优先队列。程序需要支持以下四种操作： 1. 插入元素（Insert）：接收一个整数值并将其插入堆中。 2. 删除最小元素（Delete_Min）：移除并返回堆顶（最小值）元素。 3. 删除指定索引元素（Delete）：根据索引移除堆中的元素。 4. 减少指定索引元素的值（Decrease_Value）：接收一个索引和新的值，减少相应元素的值并保持堆的性质。 例如，给定的样例输入和输出展示了如何对堆进行一系列操作并输出最终状态。 Task 3是关于并查集（Disjoint Set）的实现，这是处理无向图连通性的关键工具。你需要编写`disjointset.cpp`，该程序接收节点数和边数，然后是边的起始和结束节点。并查集的主要操作包括查找根节点（Find）以确定元素所属的集合，以及路径压缩（Union）来合并两个集合。在样例输入中，有3个节点和1条边，所以输出是2，表示有两个连通分量。 实验课的评分规则是严格的，课上提交的版本将被视为最终版本，课后提交的作业会受到不同程度的分数折扣。此外，作弊是绝对禁止的，一旦发现将给予零分处罚。 为了成功完成这三个任务，你需要对二叉树的遍历、堆的性质和操作、以及并查集的实现有深入的理解。记得在编程时遵循指定的输入输出格式，避免使用限制的库，并确保程序能够正确处理各种边界条件和测试用例。这些实践将对你的编程技能和算法理解大有裨益。