资源描述：
《约瑟夫环C实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、author：AndySueeChan一、需求分析1、本程序演示约瑟夫问题：编号为1，2，...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）开始任选一个正整数作为报数值,自第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他持有的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。编写完整的程序求出出列顺序。2、利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号3、测试数据：初始密码：20，人数：7.7个人的密码以次是3、1、7、2、4、8
2、、4二、概要设计1、循环链表抽象数据类型定义ADTOrderedList{数据对象：D={ai
3、ai属于Elemtype，i=1，2，3......，n>=0}数据关系：R1={
4、ai-1,ai属于D，ai-1《ai，i=2，3.....n}基本操作：createNode(n,m)操作结果：生成一个结点，n：编号、m：密码createList(&L，n)操作结果：根据n的值，构造一个空的循环链表，n为链表中结点的个数jose(&L,n)操作结果：实现出队操作}ADTOrderedList2、本程序包含三个模块（1）构造结点模
5、块（2）生成链表模块（3）出队处理（4）主函数模块各模块调用关系：（4）-》（2）-》（1），（4）-》（3）三、详细设计1、结点类型typedefstructLNode{intnum;//编号intpwd;//密码structLNode*next;}LNode;2、构造结点LNode*createNode(intm_num,intm_pwd){LNode*p;p=(LNode*)malloc(sizeof(LNode));//生成一个结点p->num=m_num;//把实参赋给结点相应的数据域p->pwd=m_pwd;p->next=NUL
6、L;//指针域指向空returnp;}3、生成链表voidcreateList(LNode**ppHead,intn){inti,m_pwd;LNode*p,*cur;//cur：浮标指针for(i=1;i<=n;i++){printf("输入第%d个人的密码:",i);scanf("%d",&m_pwd);p=createNode(i,m_pwd);//调用构造结点函数if(*ppHead==NULL)//如果头结点为空{*ppHead=cur=p;//生成头结点，让cur指向它cur->next=*ppHead;//cur的指针域指向自身
7、}else//如果不为空，则插入结点{p->next=cur->next;cur->next=p;cur=p;//cur指向新插入结点}}printf("完成创建!");//提示链表创建完成}4、出队处理voidjose(LNode**ppHead,intm_pwd){intcount,tag;//count：记数、tag：标记tag=1;//1：出队0：结束LNode*p,*cur,*p_del;p=cur=*ppHead;//指向头结点while(p->next!=*ppHead)//如果不是尾结点，就移动一次{p=p->next;}
8、while(tag)//标记为出队{for(count=1;countnext=cur->next;//出队操作cur=cur->next;m_pwd=p_del->pwd;//获取最后一个出队结点的密码p=cur;//浮动指针指向移动一次后的结点cur=cur->next;//再移动到下一个结点，为出队准备}if(p==cur)//出队结束{tag=0;}else{p_del=cur;//把要出队的结点赋
9、给p_del指针p->next=cur->next;//出队操作cur=cur->next;m_pwd=p_del->pwd;//获取出队结点的密码printf("第%d个人出列,密码:%d",p_del->num,p_del->pwd);free(p_del);//释放结点}}*ppHead=NULL;//全部出列后，头指针指向空}（5）主函数模块intmain(void){intn,m;LNode*pHead=NULL;printf("请输入人数n:");scanf("%d",&n);printf("初始密码m:");scanf("%
10、d",&m);createList(&pHead,n);printf("");jose(&pHead,m);return0;}四、程序演示
