2021春季数据结构作业2：顺序表合并与复杂度分析

在2021春季的SEU数据结构课程中，作业2报告关注于使用顺序列表合并两个已排序数组La和Lb，同时消除其中的重复元素。本报告由学生<Name>（在GitHub和CSDN上以TeddyvanJerry的身份活动）完成，日期为2021年3月11日。 问题部分要求设计一个算法，将La和Lb中的元素合并到一个新的有序列表Lc中，同时注意避免添加重复项。这个任务涉及的时间和空间复杂度分析是核心内容。由于La和Lb已经是升序排列，合并过程中可以直接选择当前未合并部分中较小的元素。为了实现这一功能，学生利用了自定义的HeapVector类（继承自标准库的Vector），这个类提供了有限的功能，包括迭代器支持。 核心代码分为两部分： 1. TVJSort.h: 学生参考了自己的GitHub项目TVJ_Sort（链接：https://github.com/Teddy-van-Jerry/TVJ_Sort），该库包含了快速排序的优化版本（在2021年3月10日更新至v2.2）。这部分代码用于对合并前的两个Vector（La和Lb）进行排序。 2. Main.cpp: - 文件名：Main.cpp - 代码开始注释： - 该文件包含主函数，首先对La和Lb进行合并操作。 - 合并过程通过`merge`函数实现，该函数首先对输入的两个Vector进行快速排序，然后逐个比较并添加元素到Lc中，同时检查是否存在重复，确保无重复元素被添加。 整个解决方案的关键在于合并算法的设计和性能优化，尤其是在处理已排序数组时，可以利用已排序特性减少比较次数。此外，使用自定义的HeapVector简化了代码，提高了效率。时间复杂度主要取决于快速排序的平均情况，为O(n log n)，而空间复杂度取决于额外存储临时数据的需要，可能是O(n)。这份报告不仅展示了数据结构的基础知识，还锻炼了学生的编程实践能力和算法理解。