# COMP2521 24T3 – Assignment 1
## 1. 作业概述
– **课程信息**：COMP2521 24T3，数据结构与算法课程，新南威尔士大学计算机科学与工程学院
– **作业贡献**：占期末成绩的15%
– **提交要求**
– **截止时间**：第7周周一晚上8点
– **提交文件**：Mset.c、MsetStructs.h和analysis.txt
– **提交方式**：命令行（`$ give cs2521 ass1 Mset.c MsetStructs.h analysis.txt`）或give的网页界面
– **注意事项**：可多次提交，以最后一次为准；提交后需检查是否成功
– **评分标准**
– **正确性（75%）**
– 包括基本操作（如插入、删除、获取大小、获取总数、获取元素计数、打印等）和高级操作（如并集、交集、包含判断、相等判断、获取最常见元素等）的实现正确性，以及平衡二叉搜索树更新后的相关操作正确性和游标操作的正确性
– 每个操作有相应的分数占比，若出现内存错误/泄漏会有相应扣分
– **复杂度分析（15%）**：分析.txt中复杂度分析的正确性和解释质量
– **代码风格（10%）**：包括缩进、空格使用、函数使用、代码分解、注释等方面的评估
## 2. 作业内容
### 2.1 Multiset抽象数据类型（ADT）
– 是一种允许重复元素的集合，每个元素有一个计数，表示在集合中出现的次数。
– 是抽象数据类型，关注其操作集合，实现细节不重要，只要对用户呈现出期望的行为。
– **操作要求**
– **基本操作（Part 1）**
– **MsetNew**：创建一个新的空Multiset，时间复杂度要求为$O(1)$。
– **MsetFree**：释放Multiset分配的所有内存，时间复杂度为$O(n)$。
– **MsetInsert**：向Multiset中插入一个元素，若元素等于UNDEFINED则不做任何操作，时间复杂度为$O(h)$。
– **MsetInsertMany**：插入给定数量的元素，若元素等于UNDEFINED或数量为0或更少则不做任何操作，时间复杂度为$O(h)$。
– **MsetDelete**：从Multiset中删除一个元素，时间复杂度为$O(h)$。
– **MsetDeleteMany**：删除给定数量的元素，时间复杂度为$O(h)$。
– **MsetSize**：返回Multiset中不同元素的数量，时间复杂度为$O(1)$。
– **MsetTotalCount**：返回Multiset中所有元素计数的总和，时间复杂度为$O(1)$。
– **MsetGetCount**：返回Multiset中一个元素的计数，若元素不在Multiset中则返回0，时间复杂度为$O(h)$。
– **MsetPrint**：将Multiset打印到文件，元素按升序排列，格式为`{(元素, 计数),…}`，时间复杂度为$O(n)$。
– **高级操作（Part 2）**
– **MsetUnion**：给定两个Multiset，返回它们的并集，新Multiset中的元素计数为两个原始Multiset中该元素计数的最大值。需要分析时间复杂度并写在analysis.txt中，不能使用将树转换为数组或链表再处理的方法。
– **MsetIntersection**：给定两个Multiset，返回它们的交集，新Multiset中的元素计数为两个原始Multiset中该元素计数的最小值。同样需要分析时间复杂度并写在analysis.txt中，禁止特定的处理方法。
– **MsetIncluded**：给定两个Multiset，判断一个是否包含在另一个中，根据元素计数判断包含关系，需要分析时间复杂度并写在analysis.txt中，禁止特定的处理方法。
– **MsetEquals**：给定两个Multiset，判断它们是否相等，根据元素和计数是否完全相同判断，需要分析时间复杂度并写在analysis.txt中，禁止特定的处理方法。
– **MsetMostCommon**：给定一个Multiset、一个整数和一个数组，将Multiset中最常见的元素按计数降序存储到数组中并返回存储的元素数量，需要分析时间复杂度并写在analysis.txt中。
– **平衡二叉搜索树（Part 3）**
– 更新实现，使用高度平衡的二叉搜索树，使MsetInsert、MsetInsertMany、MsetDelete和MsetDeleteMany的最坏情况时间复杂度为$O(log n)$，并保证任何Multiset的底层二叉搜索树始终是高度平衡的。
– **游标操作（Part 4）**
– **MsetCursorNew**：为给定的Multiset创建一个新游标，初始位置在Multiset的开头。
– **MsetCursorFree**：释放给定游标分配的所有内存。
– **MsetCursorGet**：返回游标位置的元素及其计数，如果游标在Multiset的开头或结尾则返回{UNDEFINED, 0}。
– **MsetCursorNext**：将游标移动到下一个最大的元素，如果没有下一个最大元素则移动到Multiset的结尾，如果游标已经在结尾则不移动，操作后如果游标在结尾则返回false，否则返回true。
– **MsetCursorPrev**：将游标移动到下一个最小的元素，如果没有下一个最小元素则移动到Multiset的开头，如果游标已经在开头则不移动，操作后如果游标在开头则返回false，否则返回true。
– 所有游标操作的最坏情况时间复杂度应为$O(1)$或$O(log n)$，需要在analysis.txt中解释设计和实现以及如何满足时间复杂度要求。
### 2.2 作业文件说明
– **初始文件**
– **Makefile**：用于控制编译的依赖关系集合。
– **Mset.h**：Multiset ADT的接口，不可修改。
– **Mset.c**：Multiset ADT的实现（初始不完整）。
– **MsetStructs.h**：Multiset ADT中使用的结构体定义（初始不完整）。
– **testMset.c**：包含一些对Multiset ADT的基本测试的主程序。
– **analysis.txt**：用于输入所选函数的时间复杂度分析的模板。
– **结构体使用要求**
– 必须使用`struct node`作为二叉搜索树节点。
– 多集中的元素必须存储在`struct node`的`elem`字段中，其计数必须存储在`count`字段中。
– `left`和`right`指针用于连接树节点与其左右子树，不能用于其他目的。
– `tree`字段必须指向存储多集所有元素的二叉搜索树。
### 2.3 测试与调试
– 提供了`testMset.c`作为基本测试程序，可以通过`make`编译并运行`./testMset`进行测试。
– 测试是基于断言的，测试失败会导致程序退出。可以通过注释掉相应的测试函数来暂时忽略某个测试。
– 建议添加自己的测试函数。
– 期望学生了解基本调试方法，如使用打印语句、基本的GDB命令和运行Valgrind。
– 可以通过相关的实验课程学习GDB和Valgrind的使用。
## 3. 背景知识
– **前置知识要求**：递归、算法分析、抽象数据类型、二叉搜索树、平衡二叉搜索树（包括AVL树）
– **Multiset相关概念**
– 与集合概念类似，但允许重复元素，每个元素有计数。
– 可以用大括号括起来的元素及其计数的形式表示，如`{(1, 3), (4, 2)}`表示元素1出现3次，元素4出现2次。
– 定义了相关的符号表示，如`cA(x)`表示元素`x`在多集`A`中的计数，如果`x`不在`A`中则`cA(x)=0`，空多集用`∅`表示。