约瑟夫环问题-数据结构实现代码

以下是约瑟夫环问题的实现代码：由两部分组成jeseph.h文件和jesephMain.c文件jeseph.h文件如下：/*自定义DataType数据类型*/ typedef structint number;/每个人所对应的序号 int cipher;/每个人手中的密码 DataType;/*构造循环单链表结点数据类型,包括个人信息及结点间的相互关系*/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; /*表示结点(头结点)下标从1开始，即要插入结点的序号i就表示第几个结点 若j=-1,则表示下标从0开始，要插入结点序号i表示第i-1个结点 */ while(p!=head&jnext; j+; if(j!=i-1&i!=1) /*此时头结点的序号为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; /为空返回0 else return 1; /非空返回1 jesephMain.c文件如下：#include#include#includejeseph.h /*包含jeseph抽象数据类型 */void SCLLDeleteAfter(SCLNode *p)/删除 p指针所指结点的下一个结点 SCLNode *q=p-next; p-next=p-next-next; free(q); /将链表中断开后的节点，即要删除的节点从内存中释放 void JesephRing(SCLNode *head,int m,int n) /*带头结点循环单链表 head，初始报数值为 m的约瑟夫环问题函数*/ SCLNode *pre,*curr; int i,j=0; int an,bn;/n表示约瑟夫环数的个数 pre=head; curr=head-next; while(SCLLNotEmpty(head)=1) for(i=1;inext; if(curr=head) pre=curr; curr=curr-next; /*将出列约瑟夫环数的序号及其所对应的密码放在b,a中*/ bj=curr-data.number; aj=curr-data.cipher; j+; m=curr-data.cipher; curr=curr-next; if(curr=head) curr=curr-next; SCLLDeleteAfter(pre); /*分别输出ai和bi*/ printf(约瑟夫环的先后出列顺序为：); for(i=0;ij;i+) printf( %d号 ,bi); printf(nn各出列序号所对应的密码： ); for(i=0;ij;i+) printf( %d ,ai); void main() DataType test7=1,1,2,10,3,7,4,2,5,9,6,8,7,6; int n=7,m=20,i; SCLNode *head; SCLLInitiate(&head); for(i=1;i=n;i+) SCLLInsert(head,i,testi-1); JesephRing(head,m,n); printf(nn);