《数据结构》上机实验报告-约瑟夫环问题.doc

福州大学数计学院数据结构上机实验报告专业和班级：信息计算科学与应用数学6班学号姓名成绩实验名称线性表结构及其应用实验内容约瑟夫环问题实验目的和要求【实验目的】利用单向循环链表解决约瑟夫环问题，提高综合设计能力。【基本要求】 利用单向循环链表存储结构模拟此过程，按归口炪列的顺序印出各人的编号。问题描述和主要步骤【问题描述】 约瑟夫问题：编号为1，2，.n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。【主要程序】#include #include typedef struct node int number; int pwd; struct node * next;Node, *Link; Link Init(void) Link L; L = (Link)malloc(sizeof(Node); L-next = L; return L;void Insert(Link L, int e_pwd, int e_number) Link p,q; p = (Link)malloc(sizeof(Node); p-pwd = e_pwd; p-number = e_number; q = L; while(q-next != L)q = q-next; p-next = q-next; q-next = p;void Delete(Link L, int i) Link p,q; q = L; while(q-next != q & q-next-number != i) q = q-next; if(q-next-number = i) p = q-next; q-next = p-next; free(p); void main() Link p,q,L; int i,m,n,pwd; printf(请输入参与人数与初始值：); scanf(%d%d,&n,&m); if(n=0 | m=0) return; L = Init(); i=1; while(i=n) printf(请输入第%d个人的密码：,i); scanf(%d,&pwd); if(pwd next; while(L-next != L) q = p; p = p-next; if(p =L) q = p; p = p-next; i+; if(i = m) printf(t%d,p-number); m = p-pwd; Delete(L, p-number); p = q; i = 0; 【测试数据】M的初值为20;n=7,7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序应为6，1，4，7，2，3，5）【结果截图】研究与探讨解决约瑟夫环问题有三个算法：一个是在顺序表上实现，另一个是在单向循环链表上实现，第三个则是利用循环队列的方式来实现。说明：实验名称为教学大纲中各章的实验项目名称，实验内容为具体章节的实验内容名称