CHC5223数据结构和算法2023-2024第2学期课业1价值40%的课程
个人工作学习成果学生将能够理解：
1.1数据结构
1.2数据结构的应用
1.3面向对象编程概念
1.4程序测试方法学生将掌握以下方面的技能：
2.1数据抽象
2.2数据结构的使用
2.3使用高级面向对象语言进行更高级的编程
2.4程序测试和文件编制学生将掌握以下方面的技能：
3.1自我管理
3.2学习
3.3沟通
3.4问题解决
3.5信息技术
投稿要求提交的课业应压缩为.zip文件，以下文件应为包含在压缩文件中：
•作为Microsoft Word文档的报告，包含您所有类的代码。文件名格式：学生ID+CCH5223_CW1_Report.docx
•包含项目的.zip文件：可运行的jar文件（如果可用）和所有程序的源代码（.java）。文件名格式：学生ID+CHC5223_CW1_Files.zip
一般要求所有编程都必须符合“Java惯例和编程指南”—请参阅模块Moodle站点。您必须将实现的关键源代码以文本或形式粘贴到报告中屏幕截图。介绍这个赋值的主题是数组、链表和哈希表。这样做的目的任务是利用一个双链表作为潜在机制。
要求基本规则完成所有任务后，必须创建一个可执行项目。一个Java类应该分别定义在一个.Java文件中。CHC5223数据结构和算法2023-2024第2学期第2页，共4页在报告中，每个任务的源代码以及相应的解释应该单独呈现。不遵守这些规则将导致零分。
任务1
必须在不使用任何现有实现的情况下设计和实现双链接列表在Java中。
➢ 双链接列表应该是可以存储字符串元素的通用数据结构数据类型。
➢ 必须创建一个Node类，该类表示双链接列表中的每个元素。
➢ 您必须创建一个LinkedList类，该类表示应包含的双链接列表用于插入、删除、访问特定元素、检查为空、返回大小的方法，以及您想要实现的其他操作。
➢ 插入操作应该在列表的前面完成。
➢ 实现应该包括错误处理，以处理诸如删除之类的错误空列表中的元素代 写CHC5223数据结构和算法，并且访问越界。
5个标记您必须在中对您的设计和实现给出明确的理由和详细的解释报告。5个标记
任务2您必须基于Java数组（而不是任何数组列表或现有的从Java库实现），并通过使用线性探索的方式。
➢ 必须使用用于冲突解决的线性探测方式。阵列的初始容量不应超过20。
➢ 您必须设计一个能够很好地处理字符串类型数据的哈希函数。散列函数设计应尽量减少碰撞的发生。您不能使用Java内置ashCode方法，不过您可以试用它。
➢ 该实现可以处理诸如空键或具有意外格式的键之类的错误。
➢ 实现应包括插入、搜索、删除和
访问键值对。
➢ 插入操作的实现可以根据如果哈希表太满，您设计的策略。
➢ 删除操作的实现可以处理密钥不在时的情况建立
➢ 该实现可以跟踪哈希表的负载因子，并在每次插入或删除。
➢ 搜索操作的实现可以搜索关键字并返回如果找到密钥，则为相应的值。
5个标记您必须在中对您的设计和实现给出明确的理由和详细的解释报告。HC5223数据结构和算法2023-2024第2学期第3页，共4页5个标记
任务3您必须基于链表设计和实现哈希表，并实现冲突通过使用单独的链接方式解决方案。
➢ 必须使用创建一个表示哈希表的ChainingHashTable类用于冲突解决的单独链接方式。
➢ 您必须使用任务1中设计的双链接列表来实现单独的链接方法单独链接的链表的容量不应超过8。
➢ 您必须设计一个能够很好地处理字符串类型数据的哈希函数。散列散列函数的策略应该与任务2的策略设计不同，并且应该地减少碰撞的发生。您不能使用Java内置的hashCode方法，尽管你可以尝试一下。
➢ 该实现可以处理诸如空键或具有意外格式的键之类的错误。
➢ 实现应包括插入、搜索、删除和访问键值对以及确定负载因子。
➢ 插入操作的实现可以有效地调整表的大小，如果散列
桌子太满了。
➢ 删除操作的实现可以处理密钥不在时的情况建立
➢ 该实现可以跟踪哈希表的负载因子，并在每次插入或删除。
➢ 搜索操作的实现可以搜索关键字并返回如果找到密钥，则为相应的值。
➢ 哈希表的实现可以根据您设计的战略。
5个标记您必须在中对您的设计和实现给出明确的理由和详细的解释报告。
5个标记
任务4您必须实现一个主程序，该程序同时使用LinearProbeingHashTable的对象
类和ChainingHashTable类。
➢ 您必须设计一组测试用例来评估两个的功能和正确性不同的哈希表。
•将哈希表的容量设置为一个小值，以便容易发生冲突。
•验证每个哈希函数是否正常工作。
•验证每个实施的方法是否正确工作。
•验证线性探测方式和独立链式方式的实施因为碰撞解决方案正在有效工作。
➢ 生成的哈希表的内部结构应清楚地显示为程序的执行结果。
4个标记CHC5223数据结构和算法2023-2024第2学期第4页，共4页您必须在中对您的设计和实现给出明确的理由和详细的解释报告。
➢ 演示程序的执行结果，包括生成的哈希表和
相应的测试数据。
➢ 对比分析基于同一组测试用例生成的两个哈希表鉴于
➢ 对比并分析您基于设计的两个哈希函数之间的差异给出了相同的测试用例集。
➢ 对两种不同的碰撞策略的影响进行理论基础和详细分析解决方案个标记
共40分相关报价“构建软件设计有两种方法：一种方法是使其简单到显然没有不足之处，另一种方法是使其变得如此复杂，以至于存在
没有明显的缺陷。第一种方法要困难得多。”Tony Hoare爵士教授1980年图灵奖讲座；ACM通讯24（2），（1981年2月）：第75-83页请试着用第一种方法。我们鼓励要求进一步澄清这项任务的要求。请尽量在正常联系时间内这样做，避免在前一周寻求此类帮助你可以与其他人讨论课业中的要求和材料，但你创造的东西必须全部是你自己的作品。小心避免串通。在报告中声明除模块教学之外您收到的任何帮助团队反馈除了我们旨在在正常时间间隔内提供的书面反馈外，您将能够获得快速、简短、口头的形成性反馈，并帮助纠正你在
课程。