数据结构上机实验：约瑟夫环与多项式加减法

本资源是一份关于数据结构上机实验的报告，主要涉及了两个经典问题的实现：约瑟夫环和多项式加减法。实验者为陈德创，指导教师为王凯东，实验时间为2020年10月6日。 **约瑟夫环** 约瑟夫环问题是一个著名的理论问题，其基本描述是：n个人按照顺时针方向围坐一圈，每个人持有正整数密码，从编号为1的人开始按顺序报数，报到m的人退出圈子，其密码成为新的m值，然后从下一个人继续报数，直到所有人都退出圈子。报告中针对此问题进行了以下分析： 1. **需求分析** - **题目描述**：描述了问题的基本设置，包括n个人，顺时针报数，报到m的人出局，密码成为新的m值。 - **题目分析**：提出了使用循环链表作为数据结构来模拟问题，并概述了算法的主要步骤，即遍历m个结点，删除末尾元素，更新m值，重复该过程直到链表为空。还提到了一个小优化，即每次前移只需要进行m mod n次，以提高效率。 2. **程序设计** - **整体概览**：给出了链表节点的定义，包括数据成员（密码和编号）以及指针成员（指向下一个节点）。 **多项式加减法** 报告中还涵盖了多项式加减法的实现： 1. **需求分析** - **题目描述**：未提供具体描述，但通常涉及到表示多项式，如系数和指数的处理。 - **题目分析**：同样没有具体分析，但可以推断需要设计数据结构来存储多项式的项，并实现加减运算。 2. **程序设计** - **整体概览**：未给出具体细节，但可能涉及创建表示多项式的类或结构，以及实现加法和减法的方法。 - **具体分析**：未提供，但可能包括如何合并相同指数的项，以及如何处理不同指数的情况。 3. **程序复杂度**：这部分未给出详细信息，但通常多项式加减法的时间复杂度与多项式的项数有关，可能是线性的。 **总结** 实验报告可能对这两个问题的实现进行了总结，包括遇到的挑战、解决方案以及程序运行效果的评估。 **附录** 附录部分包含了约瑟夫环和多项式加减法的源代码，供读者参考和学习。 这份报告提供了一个实践数据结构问题解决的实例，通过约瑟夫环和多项式加减法展示了链表在解决问题中的应用，以及如何通过编程实现这些算法。