约瑟夫环实验报告(附源码)

《约瑟夫环实验报告(附源码)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、约瑟夫环一、需求分析1.本程序要求输入正整数m,和n（n

2、e对象的指针基本操作：intList();//构造函数，对循环链表进行初始化boolappend(constint);//利用添加结点，链表中保存了递增的数字序列boolshanchu();//删除被选中的结点算法的基本思想利用循环链表和链表的fence指针，用for循环计数，选中符合要求的结点，进行输出，然后删除该结点。一直循环到最后一个结点被删除。程序的流程1、用户输入该序列的长度和步长（即每隔几个数被选中一个对象）2、根据用户输入的序列长度，生成符合要求的链表3、用循环和fence指针，根据步长，选中符合要求的对象结点，输出对应的编号，再删掉该结点，直到最后一个结

3、点被删除，推出循环三、详细设计物理数据类型要求输入的数要大于0,。因为序列的长度与用户的数据相关，长度变化大，故采用循环单链表来实现其物理数据结构。链表的每个结点只存储一个整数值和一个指向结点的指针。classintNode//定义结点{public:intn;intNode*next;};classintList//链表定义－4－{private:intNode*head;//指向头结点intNode*tail;//指向尾结点public:intNode*fence;//指向当前结点intlength;//记录链表长度intList();//构造函数，对循环链表进行初

4、始化boolappend(constint);//在尾结点后添加结点boolshanchu();//删除当前结点};intList::intList()//构造函数，对循环链表进行初始化（函数体）{head=tail=fence=newintNode;head->n=1;head->next=tail;length=1;}boolintList::append(constintt)//在尾结点后添加结点{//tail指针后移，tail->next指向头tail=tail->next=newintNode;tail->n=t;tail->next=head;length+

5、+;returntrue;}boolintList::shanchu()//删除当前结点{inti;for(i=0;inext;intNode*temp;temp=fence->next;fence->next=fence->next->next;deletetemp;length--;returntrue;}说明：不能再用析构函数了，因为在主程序中的一个while循环的跳出条件为所有的结点被删除。算法的时空分析－4－算法的执行主要是增添n个结点，以及删除结点，显示。增添结点时间复杂度为O(1)，由于删除结点时，删除

6、fence的当前结点，不是fence->next所指的结点，所以时间复杂度与链表长度有关。所以上述时间复杂度为O(n2)输入和输出的格式输入：num=//提示等待输入step=//提示等待输入输出：36927185104四、调试分析主要是一些细节部分，因为没注意到删除结点时，已将结点删除完了，造成重复删除结点，从而报错。五、测试结果六、实验心得由于没仔细思考，没充分利用循环链表的删除结点功能，造成了程序浪费空间，效率低下。编程，写代码不是主要的，关键是思考。六、附录（可选）－4－#includeusingnamespacestd;classintNo

7、de//定义结点{public:intn;intNode*next;};classintList{private:intNode*head;intNode*tail;public:intNode*fence;intlength;intList();//构造函数boolappend(constint);//增添结点boolshanchu();//删除结点};intList::intList()//实现环链{head=tail=fence=newintNode;head->n=1;head->next=tail;length=1;}booli