数据结构约瑟夫环实验报告.doc

工商学院数据结构实验报告年级2012学号54姓名刘怡然成绩专业电气实验地点B3-401指导教师许文强实验项目约瑟夫环问题实验日期一、实验目的本实验的目的是进一步理解线性表的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力。二、实验问题描述设编号为1、2、……n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。三、实验步骤1、实验问题分析由于当某个人退出圆圈后,报数的工作要从下一个人开始继续,剩下的人仍然是围成一个圆圈的,可以使用循环表,由于退出圆圈的工作对应着表中结点的删除操作,对于这种删除操作频繁的情况,选用效率较高的链表结构,为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断,链表不带头结点。所以,对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为L,浮标指针p,并根据具体情况移动。功能(函数)设计由于函数功能比较简单,对子模块可以不再细分,而使用主函数main()做数组的初始化和输出工作,使用函数Josephus()做删除结点和输出顺序的工作,使用函数Move()做移动链表指针的工作,使用Creat_Linklist()做初始化链表的工作。实验结果(程序){ intnumber; structNode*next;}LNode,*Linklist;#include""#include""#include""LinklistCreat_Linklist(intx);voidJosephus(LinklistL,inty,intz,int[]);LinklistMove(LinklistL,intx);intmain(){ LinklistL;intn,k,m; intASA[100]; cout<<"人数上限为100,请输入人数n:"; cin>>n; L=Creat_Linklist(n); printf("请输入起点k,循环基数m,逗号隔开:"); scanf("%d,%d",&k,&m); if(k<=0||k>n) {cout<<"你输入的K值不符合题目要求!";return0;} Josephus(L,k,m,ASA); cout<<"出列顺序为:"<<endl; for(inti=0;i<n;i++) cout<<ASA[i]<<endl; return1;}LinklistCreat_Linklist(intx){ LinklistL; LNode*s,*r; L=r=NULL; inti; for(i=1;i<=x;i++) { s=newLNode; s