数据结构实验报告题目：约瑟夫环姓名：学号：专业班级：指导教师：课题工作时间：一．需求分析1.约瑟夫环（Joseph）问题的一种描述是：设有编号1,2,3。
n(n>0)的N个人围成一个圈，每个人持有一个密码（正整数）。
开始时从第k（1<=k<=n）个人按顺时针方向自1开始顺序报数，报到m（m为第K个人的密码）的人出圈，再以这个人顺时针方向上的下一个人的密码为m，并开始重新从1报数。
如此下去，直至所有人全部出列为止。
试设计一个程序求出出列顺序。
2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。
3.测试数据(1)m=20, n=7, 结果依次为为3，1，7，2，4，8，4(2)m=20,n=1(3)m=20,n=0前面一组为常规数据，后面两组为边缘数据二、概要设计本程序是多文件程序，构成的函数有int main() 主函数，输出出队序列int initsuiji() 随机数产生初始化int suiji(int x,int y) 随机数产生函数int InitList(SqList &L) 初始化顺序表int ListInsert(SqList &L,int i,ElemType e) 在顺序表中插入元素int ListDelete(SqList &L,int i,ElemType &e) 删除顺序表中的元素int shunxu(int number) 顺序存储算法JosephuNode *Creat_Node(int numbers) 创建单循环链表void Josephu(JosephuNode *head,int Password) 添加元素信息int lianbiao(int number) 链表算法其中，void main()是最主要的函数，分别执行两种算法，并在执行的同时按照出列顺序输出元素信息（编号，密码），并在结尾输出两种算法执行所用的时间长短。
三、详细设计头文件#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <time.h>#include<iostream>typedef struct{int number;int password;}ElemType;typedef struct Node{int Index;int Password;struct Node *next;}JosephuNode;typedef struct{ElemType *elem;int length;int listsize;}SqList;#define LISTINCREMENT 10#define LIST_INIT_SIZE 100#define OK 1;#define ERROR 0;main.c#include"JosephuNode.h"int shunxu(int number);int lianbiao(int number);JosephuNode *head, *tail;ElemType temp;extern int ListInsert(SqList &L,int i,ElemType e); int m;SqList J;int initsuiji(){time_t t;srand((unsigned) time(&t));return 0;}int suiji(int x,int y){int k;k=rand()%(y-x+1)+x;return k;}JosephuNode *Creat_Node(int number){head = tail = (JosephuNode *)malloc(sizeof(JosephuNode)); //申请头结点return 0;}//Creat_Nodeint InitList(SqList &L){//初始化顺序表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem) return ERROR;L.length=0; //空表长度为0L.listsize=LIST_INIT_SIZE; //初始存储容量return OK;}int main(){int number,t_sx,t_lb,i,k;initsuiji();printf("输入人数:\t");scanf("%d",&number);InitList(J);Creat_Node(number);k=suiji(1,5);m=k;ListInsert(J,i,temp); //将节点插入顺序表for(i=0;i<number-1;i++){temp.password=suiji(1,100);temp.number=i+1;ListInsert(J,i,temp); //将节点插入顺序表tail->Index =i+1;tail->Password=temp.password; //产生当前结点所带密码tail->next = (JosephuNode *)malloc(sizeof(JosephuNode)); //申请一个新结点tail = tail->next;}//fortemp.password=suiji(1,100);temp.number=i+1;ListInsert(J,i,temp); //将节点插入顺序表tail->Index = i+1;tail->Password=temp.password;tail->next = head; //将尾结点指针指向表头printf("%d",m);t_sx=shunxu(number);m=k; //将m的值重置为初始值t_lb=lianbiao(number);printf("顺序存储法用时%dms\n",t_sx);printf("链表法用时%dms\n",t_lb);return 0;}shunxu.c#include"JosephuNode.h"using namespace std;extern ElemType temp;extern SqList J;extern int m;int ListInsert(SqList &L,int i,ElemType e){//在顺序表中第i个位置之前插入新的数据元素eElemType *base,*q,*p;if(i<0||i>L.length) return ERROR; // i值不合法if(L.length>=L.listsize){if(!(base=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))))return ERROR; //存储分配失败L.elem=base; //新基地址L.listsize+=LISTINCREMENT; //增加存储容量}q=L.elem+i; //q为插入位置for(p=L.elem+L.length;p>=q;--p) //插入位置及之后的元素右移 *(p+1)=*p;*q=e; //插入e L.length++; //表长加1return OK;}int ListDelete(SqList &L,int i,ElemType &e){//在顺序表中删除第i个元素，并用e返回其值ElemType *p,*q;if(i<0||i>L.length-1) return ERROR; // i值不合法p=L.elem+i; // p为被删除元素的位置e=*p; //被删除元素的值赋给e q=L.elem+L.length-1; // q为表尾元素的位置 for(++p;p<=q;++p) //被删除元素之后的元素左移*(p-1)=*p;L.length--; //表长减1return OK;}int shunxu(int number){int i,p=0,j=1;clock_t start,end;start=clock();while(J.length>0){p--;for(i=0;i<m;i++) //报数m次找到出列的编号p=(p+1)%J.length;ListDelete(J,p,temp);m=temp.password; //获取新的m值printf("第%d个出局的玩家编号是%d\t",j,temp.number);printf("密码是%d\n",temp.password);j++;}//whileend=clock();return(end-start);}lianbiao.c#include"JosephuNode.h"using namespace std;extern int m;extern JosephuNode *head, *tail;///////////////////////////////////////////////// 约瑟夫环void Josephu(JosephuNode *head,int password){int i,j;for (i = 1; tail != head; ++i){for (j = 1; j <password; ++j){tail = head;head = head->next;}tail->next = head->next;printf("\n\t\t第%d个出局的人的编号是：%d\t密码是：%d",i,head->Index,head->Password);password=head->Password; //使用出局的人的密码free(head);head = tail->next;}printf("\n\t\t第%d个出局的人的编号是：%d\t密码是：%d\n",i,head->Index,head->Password);free(head);} //Josephu/////////////////////////////////////int lianbiao(int number){clock_t start,end;int password;start=clock();password=m;printf("%d",password);Josephu(head,password);end=clock();return(end-start);}四.运行与结果五.调试及收获1.在n比较小和N比较大时（N在500以内和10以上）链表法更快，当N的值很大（数千，甚至数万）时，链表法和顺序存储法的时间差距越来越大。