数据结构实验报告_实验三1

数据结构实验报告主要探讨了两个问题：约瑟夫问题（Josephus Problem）和多项式乘法，使用链表作为核心数据结构来实现解决方案。 约瑟夫问题是经典的理论问题，本实验采用两种方法来解决：一是基于游标的循环链表方法，二是基于数学推导的递归/迭代方法。在循环链表实现中，首先需要理解如何用链表模拟数组，通过`malloc`和`free`管理内存。报数从1开始，人编号从0开始，以保持不同算法的输出一致性。对于数学推导的解决方案，涉及到递归方程`f(k, m)=(f(k-1, m)+m)%k`和边界条件`f(1, m)=0`，这个方法是从最基础的情况逐步构建到整个问题的解决方案。 多项式乘法的实现利用链表的优势，避免了非稀疏多项式可能导致的内存浪费。实验中对比了两种情况：未排序指数和已排序指数。对于未排序的指数，需要遍历两个多项式的每一项进行逐项乘法，并检查新指数是否已存在于结果链表中，若存在则累加系数，否则创建新节点。对于已排序的指数，首先确定结果的最高次项，然后将第二个多项式反向，这样可以更有效地找到相乘项，减少不必要的遍历。 算法实现部分展示了具体代码，例如`Josephus_1`函数用于链表模拟约瑟夫问题，`j2_rec`函数是一个递归的约瑟夫问题求解器。这些函数演示了如何在实际编程环境中应用上述理论分析。 这个实验报告深入探讨了数据结构在解决实际问题中的应用，包括链表的操作（如插入、删除、遍历）以及递归和迭代算法的设计。通过约瑟夫问题和多项式乘法的解决，学生可以更好地理解和掌握数据结构的基本概念，以及如何在实际问题中运用这些概念。