数据结构习题1.pdf

数据结构与算法实验题 2.3 大家一起来报数 实验任务 编号为 1 - n 的 n 个人按顺时针方向围坐一圈，从第一个人开始按顺时针方向自 1 开 始报数，报到 m 时停止，在报到 m 的那个人的左右的两个人出列，从他在顺时针方向下 一 个人开始重新从 1 报数，如此下去。如果还在游戏的人数少于 3 个，则游戏终止。在一行 内输出最后留下来的人编号 数据输入 输入第一行为 T ，代表接下去有 T 组测试， 0 < T < =10 接下去 T 行，每行两个数代表 n 和 m，0 < n，m < =1000 数据输出 对于每个输入，在一行内输出最后留下来的人编号，如果有两个人留下来，则用空格隔 开，并按从小到大排序。 输入示例 输出示例 3 1 2 3 1 4 2 1 1 2 4 #include<stdio.h> #include<malloc.h> typedef struct LinkedList* List; struct LinkedList { List right; List left; int n; }; List creatList(int peopleNum) { Li 数据结构与算法是计算机科学中的核心领域，它们在软件开发中扮演着至关重要的角色。这里有两个实验题目，分别涉及到了链表操作和动态规划的概念。 第一个实验题是“大家一起来报数”，它实际上是一个简化版的约瑟夫环问题。在这个问题中，n个人围成一个圈，按照顺时针方向从1开始报数，每报到m的人和他的左右两边的人都退出游戏，直到剩下少于3人为止。这个问题可以通过模拟循环链表来解决。创建一个双向链表，每个节点代表一个人，节点包含一个编号n。然后，从链表头开始报数，每报到m就删除对应的节点及其左右邻居，直到链表长度小于3。为了实现这个过程，可以定义一个`searchList`函数，它接受链表、人数n和报数m作为参数，通过循环和链表操作完成报数过程，并输出最后留下的编号。 第二个实验题是“价值问题”，它涉及到动态规划的概念。问题要求找出连续一段时间内，心情值最差那天的心情等级与这段时间心情等级总和的乘积的最大值。为了求解这个问题，可以维护一个数组`sum`，其中`sum[i]`表示前i天的心情等级之和。然后，遍历每一天，对于每一天i，计算从第i天到第n天的最坏心情等级，即在这段时间内的最小心情等级，与`sum[n] - sum[i-1]`相乘，记录最大值。这个过程可以通过一个简单的双重循环完成。 在实现这两个问题时，需要注意的是，对于链表操作，要确保正确处理边界条件和指针的更新，以避免内存泄漏或错误的链表结构。而对于动态规划问题，关键在于找到状态转移方程，有效地存储中间结果，避免重复计算。 这两个实验题目的解决方案都需要扎实的数据结构基础和算法思维，通过它们，我们可以深入理解链表操作和动态规划在实际问题中的应用。在编写代码时，要注重代码的清晰性和效率，遵循良好的编程实践。