北工大数据结构上机实验报告1

实验一报告姓名：学号：完成日期：2015年4月7日题目：设有n个人坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此反复直到所有的人全部出列为止。Josephus问题是：对于任意给定的n、s、m，求出按出列次序得到的n个人员的序列。试在计算机上模拟Josephus问题的求解工程。需求分析输入形式、输入值的范围：输入的值必须为正整数输出形式：输出为一组正整数程序功能：对于任意给定的n、s、m，求出按出列次序得到的n个人员的序列。测试数据：正确的输入：632正确的输出：462531错误的输入：632错误的输出：123456概要设计主程序流程：开始开始输入数据信息输入数据信息创建数组或链表，并将编号存入创建数组或链表，并将编号存入是否全部出列否是否全部出列是结束结束调试分析调试中并遇到的问题：运行结果少一个数解决方案：在while循环的限制条件中，是循环次数加1算法时空分析：O(n)用户使用说明运行程序后，用户按照提示顺序输入3个正整数，然后按回车可得到结果测试结果输入：632输出：462531源程序以顺序表实现：#include<iostream>usingnamespacestd;voidJJ(intn,ints,intm){int*a=newint[10000];inti;intcount=0;intt=0;for(i=0;i<n;i++){a[i]=i+1; }i=s-1; cout<<"出列次序为：";while(count<n-1){ if(a[i]!=0)t++;if(t==m){t=0;//记数归0cout<<a[i]<<"";//依次输出删除的编号a[i]=0;//给删除的数组赋0count++;//退出人数加1 } i++;if(i==n)i=0;//报数到末尾后i恢复为0} cout<<endl;}voidmain(){intn,s,m;cout<<"请输入总人数:"<<endl; cin>>n;cout<<"请输入开始报数的人员序号:"<<endl; cin>>s;cout<<"请输入出列人员的序号:"<<endl;cin>>m;JJ(n,s,m);}以链表实现：#include<iostream>usingnamespacestd;typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;voidJJ(intn,ints,intm){LinkListp,r,list=NULL;inti;//建立一个循环链表for(i=0;i<n;i++){p=(LinkList)malloc(sizeof(LNode));p->data=i+1;//存放第i个结点的编号if(list==NULL)list=p;elser->next=p;r=p;}p->next=list;p=list;for(i=1;i<s;i++){r=p;//当m!=1,但s=1时如果没有这条语句，此时删除动作无法完成p=p->next;}//此时p指向第1个出发结点 cout<<"出列次序为：";while(p->next!=p){for(i=1;i<m;i++){r=p;p=p->next;}//p指向第m个结点,r指向第m-1个结点r->next=p->next;//删除第m个结点cout<<p->data<<"";deletep;p=r->next;}cout<<p->data; cout<<endl;}voidmain(){intn,s,m;cout<<"请输入总人数:"<<endl;scanf("%d",&n)