JesephRing问题上机报告.doc

【实验内容】约瑟夫（Joseph）问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。【实验目的】掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。【实验要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。【测试数据】m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序应为6，1，4，7，2，3，5）。【实验提示】程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n30。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。【程序清单】/单向循环链表操作集合 /*文件SCLinList.h*/typedef struct node /结点结构体定义 DataType data;struct node *next;SCLNode; void SCLLInitiate(SCLNode *head) /初始化if(*head=(SCLNode *)malloc(sizeof(SCLNode)=NULL)exit(1);(*head)-next=*head;int SCLLInsert(SCLNode *head,int i,DataType x) /插入一个结点SCLNode *p,*q;int j;p=head-next; j=1;while(p!=head&jnext; j+;if(j!=i-1&i!=1)printf(插入位置参数有误！); return 0;if(q=(SCLNode *)malloc(sizeof(SCLNode)=NULL)exit(1);q-data=x;q-next=p-next;p-next=q;return 1;int SCLLDelete(SCLNode *head,int i,DataType *x) /删除一个结点SCLNode *p,*q;int j;p=head; j=0;while(p-next!=head&jnext; j+;if(j!=i-1)printf(删除位置参数有误！);return 0;q=p-next;p-next=p-next-next;*x=q-data;free(q);return 1;int SCLLGet(SCLNode *head,int i,DataType *x) /取一个节点数据元素值SCLNode *p;int j;p=head; j=0;while (p-next!=head&jnext; j+;if(j!=i)printf(取元素位置参数有误！);return 0;*x=p-data;return 1;int SCLLNotEmpty(SCLNode *head)if(head-next=head) return 0;else return 1;/*主函数部分，main.c文件*/#include#includetypedef structint number; /序号int cipher; /密码DataType; /定义具体的数据类型 DataType#include SCLList.hvoid SCLLDeleteAfter(SCLNode *p) /删除p指针所指结点的下一个结点SCLNode *q=p-next;p-next=p-next-next;free(q);void JesephRing(SCLNode *head,int m)/带头结点单循环链表head,初始值为m的约瑟夫环问题函数SCLNode *pre,*curr;int i;pre=head;curr=head-next;while(SCLLNotEmpty(head)=1)for(i=1;inext;if(curr=head)pre=curr;curr=curr-next; printf(%dn,curr-data.number); m=curr-data.cipher; curr=curr-next; if(curr=head)curr=curr-next; SCLLDeleteAfter(pre);void main() DataType test7=1,3,2,1,3,7,4,2,5,4,6,8,7,4; int n=7,m=20,i; SCL