j数据机构上joseph环代码.docx

j数据机构上joseph环代码#include"stdio.h"#include"windows.h"#include"malloc.h"#include"time.h"#include &ltstdlib.h&gt#define OVERFLOW -2 #define OK 1 #define ERROR 0#define N 10typedef struct LNodeint password; /密码int No; /序号 struct LNode *next; /下一成员指针member; /成员结构体typedef int status;status CreateList_Circle(member *,int);status DeleteNode(member *);typedef struct nodeint num ;int sec ;struct node *pre;struct node *next;body;void Initiate(body *x);void Delect(int x,body *head); status mainint n,m,u;member *head=NULL,*p=NULL; /头指针即首成员地址，遍历指针pprintf (" *n");printf (" JOSEPH环 n");printf (" 编号是1，2，,n的n个人按照顺时针方向围坐一圈，每n");printf (" 个人只有一个密码。一开始任选一个正整数作n");printf (" 为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报n");printf (" 数，报到m时停止报数。报m的人出列，将他的密码作为新n");printf (" 的m值，从他在顺时针方向的下一个人开始重新从1报数，如n");printf (" 此下去，直到所有人全部出列为止。设计一个程序来求出出n");printf (" 列顺序。n");printf (" *n");printf (" 要求：n");printf (" 利用单向循环链表存储结构模拟此过程，按照出列的顺序输n");printf (" 出各个人的编号。n");while(1)printf (" *n");printf (" 1 由计算机随机产生约瑟夫环 n");printf (" 2 输入指定约瑟夫环 n");printf (" 3 离开 n");printf (" *n");printf (" 请选择序号： ");scanf("%d",&u);if(u=1)int m;body *first;first=(body *)malloc(sizeof(body);first-&gtnext=first;first-&gtpre=first;Initiate(first);m=rand%(N-1);m=m+1;printf("nn 任意数m=%dn",m);Delect(m,first); else if(u=2)printf (" 请输入人数: ");scanf ("%d",&n); /总成员数while (n&lt=0)printf (" 输入错误，请重新输入: n");scanf ("%d",&n);if(!CreateList_Circle(&head,n) /创建循环链表，返回头指针headreturn OVERFLOW; printf (" 请输入上限值m: ");scanf ("%d",&m); /初始mwhile (m&lt=0)printf (" 输入错误，请重新输入: n");scanf ("%d",&m); printf (" 出列顺序为:");p=head;while (n&gt=2) /寻找出列成员int i;m=(m%n=0)?n:m%n; /化简m值for (i=1;i&ltm;i+) p=p-&gtnext; /p指向出列成员printf (" %d",p-&gtNo); /输出出列成员序号m=p-&gtpassword; /修改mDeleteNode(&p); /删除链表中的出列成员n-; /成员数自减printf (" %dn",p-&gtNo); /输出最后一个成员序号else if(u=3) exit(0);elseprintf(" 输入错误，请输入0、1或2n");status CreateList_Circle(member *p_head,int n)/此算法创建一个无头结点的循环链表，结点数n,*p_head返回链表头指针即首结点地址int i;member *tail,*p;*p_head=(member *)malloc(sizeof(member);if (!(*p_head) return OVERFLOW;(*p_head)-&gtNo=1; /储存成员一序号printf (" 请输入第1个人的密码: "); scanf ("%d",&(*p_head)-&gtpassword); /储存成员一密码tail=*p_head;tail-&gtnext=NULL;for (i=2;i&ltn+1;i+)p=(member *)malloc(sizeof(member);if (!p) return OVERFLOW;p-&gtNo=i; /储存成员序号printf (" 请输入第%d个人的密码: ",i);scanf("%d",&(p-&gtpassword); /储存成员密码tail-&gtnext=p;tail=p;tail-&gtnext=*p_head;return OK;status DeleteNode(member *pp)/此算法删除链表中的结点*pp,操作实质是将*pp下一结点复制到*pp后将其freemember *temp;(*pp)-&gtpassword=(*pp)-&gtnext)-&gtpassword;(*pp)-&gtNo=(*pp)-&gtnext)-&gtNo;temp=(*pp)-&gtnext;(*pp)-&gtnext=(*pp)-&gtnext-&gtnext;free(temp);return OK;void Initiate(body *head)int xxN,yyN;int i;body *p,*q;for(i=0;i&ltN;i+) yyi=i+1;srand( time(NULL) );for(i=0;i&ltN;i+)xxi=yyrand%N;head-&gtnum=yy0;head-&gtsec=xx0;for(i=1;i&ltN;i+) p=head;q=(body *)malloc(sizeof(body);q-&gtnum=yyi;q-&gtsec=xxi;while(p-&gtnext!=head) p=p-&gtnext;p-&gtnext=q;q-&gtpre=p;q-&gtnext=head;head-&gtpre=q;printf("n 序号:");for(i=0;i&ltN;i+) printf("%2d ",i+1);printf("n 密码:");for(i=0;i&ltN;i+) printf("%2d ",xxi);void Delect(int x,body *head)body *p;p=head;int i=1,sec;while(i&ltx && p-&gtnext!=p) p=p-&gtnext;i+;if(p-&gtnext!=p) sec=p-&gtsec;printf(" 序号: %2d 密码: %2d n",p-&gtnum,p-&gtsec);p=p-&gtpre;p-&gtnext=p-&gtnext-&gtnext;p-&gtnext-&gtpre=p;head=p-&gtnext;Delect(sec,head);else printf(" 序号: %2d 密码: %2d n",p-&gtnum,p-&gtsec);