学生学号 0121610880426 实验课 成绩 学 生 实 验 报 告 书 实验课程名称 开 课 学 院 计算机科学与技术学院 指导教师姓名 学 生 姓 名 钟忺 母昌祥 学生专业班级 软件工程 1603 2018 -- 2019 学年 第 一 学期 

实验课程名称：_______________ 实验项目名称 约瑟夫环问题 实 验 者 母昌祥 专业班级 软件 1603 实验成绩 组 别 同 组 者 实验日期 2018 年 9 月 28 日 一部分：实验预习报告（包括实验目的、意义，实验基本原理与方法，主要仪器设备 及耗材，实验方案与技术路线等） 1. 问题描述 采用线性表完成 n 个节点的约瑟夫环问题。 2. 实验目的及意义 通过对约瑟夫环问题的解决方法的思考与实现，来达到对课上所学的线性表的只是的巩固 与运用。 3. 实验基本原理与方法 (1)用不带表头结点的循环单链表表示围成圆圈的 n 个人； (2)某人离席相当于删除一个结点要正确设置程序中循环终止的条件和删除结点时指针的 修改变化。 4. 主要仪器设备及耗材 安装了 Dev-C++的 win7PC 机一台 5. 实验方案与技术路线 采用单向循环链表完成本次试验，整个实现过程描述 (1) 读入 m，n (2) 构建单向循环链表：输入 n 之后，调用 initLink 函数构建有 n 个结点的单向循环链表，注意 首尾相连。 node* initLink(int n) { node *head = (node*)malloc(sizeof(node)); head->data = 1; head->next = NULL; node *rear = head; for(int i = 2; i <= n; i++){ 

node *body = (node*)malloc(sizeof(node)); body->data = i; body->next = NULL; rear->next = body; rear = rear->next; } rear->next = head; //首尾相连 return head; } (3) 报 m 的人离席：输入 m 后调用 josephus 函数，输出并删除 m 结点，由 m 的前驱节点指向 m 的后继节点来完成删除操作。 void josephus(node * head,int n,int m){ node *p = head; //找到链表第一个结点的上一个结点，为删除操作做准备 while(p->next != head){ p = p->next; } //报 m 的人退席 for(int i = 1; i <= n; ++i){ for(int j = 1; j <= m - 1; ++j){ p = p->next; } node *q = p->next; printf("%d ", q->data); p->next = q->next; } } 

第二部分：实验过程记录（可加页）（包括实验原始数据记录，实验现象记录，实验过 程发现的问题等） 教师签字__________ 

第三部分 结果与讨论（可加页） 一、实验结果分析（包括数据处理、实验现象分析、影响因素讨论、综合分析和结论等） 二、小结、建议及体会 三、思考题