当前位置:文档之家› 约瑟夫环问题 实验报告

约瑟夫环问题 实验报告


return count==0; } template <class T> bool SqList<T>::Full() const { return count==maxsize; } template <class T> int SqList<T>::Length() const { return count; } template <class T> void SqList<T>::Clear() { count=0; //这里并不是将所有元素删除,而是将元素个数置 0,实际上元素还在,但可以重新输入元素替换原来的元素 } template <class T> bool SqList<T>::SetElem(int position,const T &e) { if(position<1||position>Length()) //范围出错 { cout<<"范围出错,无法赋值!"<<endl; return false; } else { elems[position-1]=e; return true; } }
for(;i<=m;i++) { j++; if(j>len) j=1; while(S.GetElem(j)==0) { j++; if(j>len) j=1; } } if(j==0) j=1; cout<<S.GetElem(j)<<" "; S.SetElem(j,0); flag++; i=1; } cout<<endl; } return 0; } 测试用例:
数据结构课程实验报告实验一
实验题目:顺序表的应用 实验内容:约瑟夫环问题:设编号为1,2,3,……,n的n(n>0)个人按 顺时针方向围坐一圈,m为任意一个正整数。从第一个人开始顺时针方 向自1起顺序报数,报到m时停止并且报m的人出列,再从他的下一个人 开始重新从1报数,报到m时停止并且报m的人出列。如此下去,直到所 有人全部出列为止。要求设计一个程序模拟此过程,对任意给定的m和 n,求出出列编号序列。 一 设计分析: 1、定义一个List类,类中public:申明list(构造线性表);申明 add(向线性表尾加入元素b);申明delete(删除表中下标尾 index);申明display(输出线性表);getend(返回线性表的位置) 2、分别定义1中申明的函数 3、定义baoshu函数,用于执行从1开始计数,到m是输出并删除m,并从 下一个元素开始 从新记数。到表尾时,再从头计数,依次循环输出, 直到表空。 4、定义主函数,输入n、m。并执行相应的函数,并输出结果。 二 程序代码:#include <iostream> #include <cassert> using namespace std; template <class T> class SqList { protected: T *elems; //存放数据的数组 int count; //元素个数 size_t maxsize; //最大元素个数 void Init(size_t ); //初始化顺序表 public: SqList(size_t ); //构造 virtual ~SqList();//析构 bool Empty() const;//判断顺序表是否为空 bool Full() const;//判断顺序表是否已满 void Clear(); //清空顺序表 int Length() const;//求顺序表长度
//表已满
cout<<"表已满,无法增加元素!"<<endl; return false; } else { elems[count]=e; count++; return true; } } template <class T> void SqList<T>::Traverse(void(*Visit)(T &)) { for(int i=1;i<=Length();i++) { (*Visit)(elems[i-1]); } } int main() { while(1) { size_t n; cout<<"环中人数:"; cin>>n; SqList<int> S(n); for(int x=1;x<=n;x++) S.Add(x); int len=S.Length(); int m; cout<<"出列间隔:"; cin>>m; int i=1,j=0,flag=0; cout<<"出列序列:"; while(flag<len) { //加入元素e //表长加1
} SetElem(position,e); return true; } }
//将元素插
template <class T> bool SqList<T>::Delete(int position) { if(position<1||position>Length()) //范围出错 { cout<<"范围出错,无法删除元素!"<<endl; return false; } else if(Empty()) //表为空 { cout<<"表为空,无法删除元素!"<<endl; return false; } else { for(int i=position+1;i<=Length();i++) //从要删除的元素 开始,其后的每一个元素向前移动一位 { T e=GetElem(i); SetElem(i-1,e); } count--; //表长减1 return true; } } template <class T> bool SqList<T>::Add(const T &e) { if(Full()) {
//出列的元素置0以作标识
实验总结: 通过这次实验,对线性表有了更深刻的认识,对相关内容有了更熟练 的掌握。由于对编程还不是很熟悉,实验过程中出现了很多错误,但调 试过后大部分解决了。查阅资料,请教同学,分析问题,解决问题,提 高了自己的动手能力。

template <class T> T SqList<T>::GetElem(int position) { T e; if(position<1||position>Length()) { cout<<"范围出错,无法读取元素!"<<endl; exit(1); } else { e=elems[position-1]; } return e; } template <class T> bool SqList<T>::Insert(int position,const T &e) { if(position<1||position>Length()) //范围出错 { cout<<"范围出错,无法插入!"<<endl; return false; } else if(Full()) //表已满 { cout<<"表已满,无法插入!"<<endl; return false; } else { count++; //表长加1 for(int i=count;i>=position;i--) //从要插入的位置开 始,后面的每一个元素向后移一位 { T temp=GetElem(i-1); //用temp取出要移动的元素 SetElem(i,temp); //移到下一位
bool SetElem(int position,const T &e);//将第position个元素 设为e T GetElem(int position); //读取第position个元素 bool Insert(int position,const T &e);//在第position个位置插 入e bool Delete(int position); //删除第position个位置的元素 bool Add(const T &e); //将e加到表尾 void Traverse(void(*Visit) (T& )); //依次对表中每个元素调用 Visit元素 }; template <class T> void SqList<T>::Init(size_t size) { maxsize=size; if(elems!=NULL) delete []elems; elems=new T[maxsize]; assert(elems!=NULL); count=0; } template <class T> SqList<T>::SqList(size_t size) { elems=NULL; Init(size); } template <class T> SqList<T>::~SqList() { delete [] elems; } template <class T> bool SqList<T>::Empty() const {
相关主题