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

华北电力大学实验报告第页共页华北电力大学实验报告实验名称约瑟夫环课程名称算法与数据结构实验专业班级:学生姓名:学号:成绩:指导教师:实验日期:华北电力大学实验报告第页共页一、实验目的及要求?问题描述:约瑟夫问题:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每个人有一个正整数编号。从某个位置上的人开始报数,数到m的人便出列,下一个人(第m+1个)又从1数起,数到m的人便是第2个出列的人,依次重复下去,直到最后一个人出列,于是得到一个新的次序,试设计程序求出出列顺序。请输入测试数据m=4,n=8,每个人的编号1-8。?实验目的:,掌握设计数据结构与算法的主要原理和方法。。。二、所用仪器、设备VC++、。,首先定义链表结点,包含了结点的数据以及指向下一个结点的指针;定义了创建循环单链表的函数node*create(node*head)第i个结点的数据为i,并返回头指针;查找循环初始结点函数node*Find(node*head,intk)其中k为循环位数,最后返回所找到的结点;实现k位循环并输出结点数据,直到链表为空的函数voidoutput(node*p,intm);,voidJosephus(intn,intm,ints)定义了一个元素个数为30(这里数目可以自行设定)的数组,若循环数为一则按顺序输出从初始结点开始的所有结点;若循环数不为一,从k=n开始,k--从而循环n次,每一次循环内从初始结点开始,依次加m减一取余k,找到出列者,然后将其后的元素左移,循环n次后便可得到依次出列者。四、实验源代码#include<>//用循环链表实现structnode//链表结点{intnum;structnode*next;};node*create(node*head)//创建循环单链表,第i个结点的数据为i,返回头指针{node*p=head;cout<<"输入总共的人数:";intn;cin>>n;for(inti=1;i<=n;i++)华北电力大学实验报告第页共页{node*q=newnode;q->num=i;p->next=q;p=q;}p->next=head->next;//使之循环returnhead;}node*Find(node*head,intk)//k为循环位数,最后返回所找到的结点{intj=k;node*p=head;inti=1;while((p->next!=NULL)&&(i!=j)){p=p->next;i++;}if(i==j)returnp;}voidoutput(node*p,intm)//按要求查找并输出数值,直到链表为空{node*q=p->next;while(p!=q)//保证未循环一遍{for(inti=1;i<m;i++){q=q->next;p=p->next;}cout<<q->num;node*r=q;q=q->next;p->next=r->next;delete(r);}cout<<p->num<<endl;p=NULL;deleteq;}//用