约瑟夫问题(算法与数据结构课程设计)

wilyes11收集博客(与学习无关)：线性表的操作及其应用一、问题描述线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。二、基本要求1、选择合适的存储结构，建立线性表；2、利用顺序存储结构求解约瑟夫环问题；3、利用单链表和循环链表分别求解约瑟夫环问题；4、利用队列求解约瑟夫环问题。三、测试数据约瑟夫环的测试数据为7，报数为1至3。四、算法思想由于用到四种不同的存储结构，它们的算法思想依次是：1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移wilyes11收集博客(与学习无关)：到队列的下一个元素，结束此次循环，当达到要求的循环次数时就将重新循环次数设置为0，输出该元素到屏幕并将总输出元素加1。五、模块划分1、voidInitQueue(SqQueue*Q)初始化循环队列2、voidDestroyQueue(SqQueue*Q)销毁循环队列3、voidClearQueue(SqQueue*Q)清空循环队列4、intQueueEmpty(SqQueueQ)判断空队列5、intQueueLength(SqQueueQ)求循环队列长度6、voidGetHead(SqQueueQ,ElemType*e)取队头元素7、intEnQueue(SqQueue*Q,ElemTypee)入队列8、intDeQueue(SqQueue*Q,ElemType*e)出队列9、voidQueueTraverse(SqQueueQ)遍历循环队列并输出元素10、voidInitQueue(LQueue*Q)初始化队列11、voidDestroyQueue(LQueue*Q)销毁队列12、voidClearQueue(LQueue*Q)清空队列13、intQueueEmpty(LQueueQ)判断空队列14、intQueueLength(LQueueQ)求队列长度15、ElemTypeGetHead(LQueueQ,ElemType*e)取队头元素16、voidEnQueue(LQueue*Q,ElemTypee)入队列17、voidDeQueue(LQueue*Q,ElemType*e)出队列18、voidQueueTraverse(LQueueQ)遍历队列并输出元素19、voidjoseffer(intn)约瑟夫环20、intCreateList(LinkList&L,intn)建立顺序链表wilyes11收集博客(与学习无关)：、voidjosephus_clist(LinkList&L,intm)顺序链表解决约瑟夫环22、voidInitList(SqList*L)初始化链表23、voidysf1()链表解决约瑟夫环24、voidysf2()循环链表解决约瑟夫环25、voidysf3(){链式队列解决约瑟夫环问题26、voidysf4()循环队列解决约瑟夫环问题27、voidmenu()菜单28、intmain()主函数六、数据结构//(ADT)typedefintElemType;/*定义顺序表类型*/typedefstruct{ElemType*elem;intlength;}SqList;/*定义循环链表类型*/typedefstructLNode{intnum;intcode;structLNode*next;}*LinkList;/*定义循环队列类型*/typedefstruct{ElemType*base;intfront;intrear;}SqQueue;/*定义链式队列类型*/typedefstructQNode{ElemTypedata;structQNode*next;}QNode,*QueuePtr;wilyes11收集博客(与学习无关)：{QueuePtrfront;QueuePtrrear;}LQueue;七、源程序#includestdlib.h#includestdio.h#defineN100typedefintElemType;/*定义顺序表类型*/typedefstruct{ElemType*elem;intlength;}SqList;/*定义循环链表类型*/typedefstructLNode{intnum;intcode;structLNode*next;}*LinkList;/*定义循环队列类型*/typedefstruct{ElemType*base;intfront;intrear;}SqQueue;/*定义链式队列类型*/typedefstructQNode{ElemTypedata;StructQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LQueue;/*初始化循环队列*/voidInitQueue(SqQueue*Q)wilyes11收集博客(与学习无关)：{Q-base=(ElemType*)malloc(N*sizeof(ElemType));Q-front=Q-rear=0;}/*销毁循环队列*/voidDestroyQueue(SqQueue*Q){free(Q-base);}/*清空循环队列*/voidClearQueue(SqQueue*Q){Q-front=Q-rear=0;}/*判断空队列*/intQueueEmpty(SqQueueQ){if(Q.front==Q.rear)return1;elsereturn0;}/*求循环队列长度*/intQueueLength(SqQueueQ){return(Q.rear+N-Q.front)%N;}/*取队头元素*/voidGetHead(SqQueueQ,ElemType*e){if(Q.front!=Q.rear)*e=Q.base[Q.front];}/*入队列*/intEnQueue(SqQueue*Q,ElemTypee){if((Q-rear+1)%N==Q-front)return0;Q-base[Q-rear]=e;Q-rear=(Q-rear+1)%N;return1;}/*出队列*/intDeQueue(SqQueue*Q,ElemType*e){if(Q-front==Q-rear)return0;*e=Q-base[Q-front];Q-front=(Q-front+1)%N;return1;}/*遍历循环队列并输出元素*/voidQueueTraverse(SqQueueQ){inti;printf(\nQueue:);if(Q.rearQ.front)Q.rear=Q.rear+N;for(i=Q.front;iQ.rear;i++)printf(%d\t,Q.base[i%N]);wilyes11收集博客(与学习无关)：}/*初始化队列*/voidInitQueue(LQueue*Q){Q-front=Q-rear=(QueuePtr)malloc(N*sizeof(QNode));if(!(Q-front))exit(0);Q-front-next=NULL;}/*销毁队列*/voidDestroyQueue(LQueue*Q){while(Q-front){Q-rear=Q-front-next;free(Q-front);Q-front=Q-rear;}}/*清空队列*/voidClearQueue(LQueue*Q){QueuePtrp;p=Q-front-next;while(p){Q-front-next=p-next;free(p);Q-rear=Q-front;}}/*判断空队列*/intQueueEmpty(LQueueQ){if(Q.front==Q.rear)return1;elsereturn0;}/*求队列长度*/intQueueLength(LQueueQ){QueuePtrp;intn=0;p=Q.front;while(p!=Q.rear){n++;p=p-next;}returnn;}/*取队头元素*/ElemTypeGetHead(LQueueQ,ElemType*e){if(Q.front!=Q.rear)returnQ.front-next-data;elsereturn0;}/*入队列*/wilyes11收集博客(与学习无关)：(LQueue*Q,ElemTypee){QueuePtrp;p=(QueuePtr)malloc(N*sizeof(QNode));if(!p)exit(0);p-data=e;p-next=NULL;Q-rear-next=p;Q-rear=p;}/*出队列*/voidDeQueue(LQueue*Q,ElemType*e){QueuePtrp;if(Q-front!=Q-rear){p=Q-front-next;*e=p-data;Q-front-next=p-next;if(Q-rear==p)Q-rear=Q-front;free(p);}}/*遍历队列并输出元素*/voidQueueTraverse(LQueueQ){QueuePtrp;printf(\nQueue:);p=Q.front-next;while(p){prin