约瑟夫循环实验报告

1、精选优质文档-倾情为你奉上实验名称：约瑟夫环问题 实验类型：综合性实验 班级： 学号：姓名：李晓彬实验日期：2012.04.282.问题描述设有编号为1,2,n的n（n0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。3.数据结构设计设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：struct

2、 Node int data; Node *next;4.算法设计一个主函数，两个功能函数。Step1:定义数据结构类型Step2:建立功能函数NODE *createlink(int n)完成建立循环链表的功能。 for(i=2;i<=n;i+) q=(struct node*)malloc(sizeof(struct node); if(q=0) return 0; p->next=q; p=q; p->data=i; Step3: 功能函数void jose(NODE *p,int n,int m)完成报数m出圈的功能。for(i=1;i<=n;i+) for(j

3、=1;j<m;j+)p=p->next; q=p->next; p->next=q->next; if(k%6=0) k+;printf("n"); else k+; printf("%3d:%3dout ",i,q->data-1); free(q); Step4: 主函数完成本实验的主体功能即得到出圈次序，并打印。 NODE *head=NULL; head=createlink(n); jose(head,n,m); 5. 抽象数据类型的设计 NODE *head，*p，*qint m,n,MAX_NODE_NU

4、M,I,k6.界面设计 欢迎使用约瑟夫环问题程序1 请输入人数n（最多1000个）;2 初始密码m:3 结果7.运行、测试与分析（1）运行程序，显示菜单 : (2)输入n：(3)输入m：（4）结果：8.实验收获及思考对单链表的知识掌握的更加透彻，而且自己一步一步编写程序有一点点的成就感。编写程序的过程中界面的友好程度是一个很重要的指标，下次要努力编写一个界面友好的程序。附录源代码：#include<stdio.h>#include<stdlib.h>typedef struct nodeint data;struct node *next;NODE; /*定义

5、节点*/ NODE *createlink(int n)NODE *head=NULL,*p=NULL,*q=NULL;int i=1; head=p=(struct node*)malloc(sizeof(struct node);p->data=i;for(i=2;i<=n;i+) q=(struct node*)malloc(sizeof(struct node); if(q=0) return 0; /分配失败 p->next=q; p=q;/创建新的节点 p->data=i; / 为 每个人分配序号 p->next=head;/循环 return hea

6、d;/返回要用的首地址 /*创建循环链表*/ void jose(NODE *p,int n,int m)int i,j,k=0;NODE *q=NULL;for(i=1;i<=n;i+) for(j=1;j<m;j+)p=p->next; /*访问到每轮的第m-1个*/ q=p->next; /*q是第m个*/ p->next=q->next; /*p直接指向第m+1个*/ if(k%6=0) k+;printf("n"); else k+; /*让出圈的数字一行显示六个*/printf("%3d:%3dout ",

7、i,q->data-1); /*输出出圈的次序和要出圈的值*/ free(q);/*释放节点*/ printf("n");p->next=NULL; /一直到下一个为空即要出圈已经出的了 /*约瑟夫环*/ int main( )int m,n,MAX_NODE_NUM=1000;while (1) printf("欢迎使用约瑟夫环问题程序n") ; printf("1.请输入人数n（最多%d个）: ", MAX_NODE_NUM); scanf("%d", &n); printf("2.初始密码m: "); scanf("%d", &m); printf("3.结果"); if (n > MAX_NODE_NUM) printf("人数太多，请重新输入！n"); continue; else brea