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

《j数据机构上joseph环代码.docx》由会员分享，可在线阅读，更多相关《j数据机构上joseph环代码.docx（11页珍藏版）》请在三一办公上搜索。

1、j数据机构上joseph环代码#includestdio.h#includewindows.h#includemalloc.h#includetime.h#include <stdlib.h>#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

2、 *,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

3、);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)pr

4、intf ( *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->next=first;first->pre=first;Initiate(first);m=rand%(N-1);m=m+1;printf(nn 任意数m=%dn,m);Delect(m,first); else i

5、f(u=2)printf ( 请输入人数: );scanf (%d,&n); /总成员数while (n<=0)printf ( 输入错误，请重新输入: n);scanf (%d,&n);if(!CreateList_Circle(&head,n) /创建循环链表，返回头指针headreturn OVERFLOW; printf ( 请输入上限值m: );scanf (%d,&m); /初始mwhile (m<=0)printf ( 输入错误，请重新输入: n);scanf (%d,&m); printf ( 出列顺序为:);p=head;while (n>=2) /寻找出列成员i

6、nt i;m=(m%n=0)?n:m%n; /化简m值for (i=1;i<m;i+) p=p->next; /p指向出列成员printf ( %d,p->No); /输出出列成员序号m=p->password; /修改mDeleteNode(&p); /删除链表中的出列成员n-; /成员数自减printf ( %dn,p->No); /输出最后一个成员序号else if(u=3) exit(0);elseprintf( 输入错误，请输入0、1或2n);status CreateList_Circle(member *p_head,int n)/此算法创建一个无头结点的循环

7、链表，结点数n,*p_head返回链表头指针即首结点地址int i;member *tail,*p;*p_head=(member *)malloc(sizeof(member);if (!(*p_head) return OVERFLOW;(*p_head)->No=1; /储存成员一序号printf ( 请输入第1个人的密码: ); scanf (%d,&(*p_head)->password); /储存成员一密码tail=*p_head;tail->next=NULL;for (i=2;i<n+1;i+)p=(member *)malloc(sizeof(member);

8、if (!p) return OVERFLOW;p->No=i; /储存成员序号printf ( 请输入第%d个人的密码: ,i);scanf(%d,&(p->password); /储存成员密码tail->next=p;tail=p;tail->next=*p_head;return OK;status DeleteNode(member *pp)/此算法删除链表中的结点*pp,操作实质是将*pp下一结点复制到*pp后将其freemember *temp;(*pp)->password=(*pp)->next)->password;(*pp)->No=(*pp

9、)->next)->No;temp=(*pp)->next;(*pp)->next=(*pp)->next->next;free(temp);return OK;void Initiate(body *head)int xxN,yyN;int i;body *p,*q;for(i=0;i<N;i+) yyi=i+1;srand( time(NULL) );for(i=0;i<N;i+)xxi=yyrand%N;head->num=yy0;head->sec=xx0;for(i=1;i<N;i+) p=head;q=(body *)malloc(siz

10、eof(body);q->num=yyi;q->sec=xxi;while(p->next!=head) p=p->next;p->next=q;q->pre=p;q->next=head;head->pre=q;printf(n 序号:);for(i=0;i<N;i+) printf(%2d ,i+1);printf(n 密码:);for(i=0;i<N;i+) printf(%2d ,xxi);void Delect(int x,body *head)body *p;p=head;int i=1,sec;while(i<x & p->next!=p) p=p->next;i+;if(p->next!=p) sec=p->sec;printf( 序号: %2d 密码: %2d n,p->num,p->sec);p=p->pre;p->next=p->next->next;p->next->pre=p;head=p->next;Delect(sec,head);else printf( 序号: %2d 密码: %2d n,p->num,p->sec);