北邮数据结构实验一_约瑟夫问题_实验报告

《北邮数据结构实验一_约瑟夫问题_实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验一——线性表学生姓名：班级：班内序号：学号：日期：1．实验要求实验目的熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力实验内容利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。2.程序分析

2、2.1存储结构采用单循环链表实现约瑟夫问题的求解12N……单循环链表存储结构示意图2.2关键算法分析基本思想：首先，应该确定构造链表时所用的插入方法。当数到m的那个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表方式。第13页北京邮电大学信息与通信工程学院其次还要考虑输入值异常的情况。之后，就是关于出列节点的逻辑判断。依次找到待删结点的直接前驱，便于删除结点后修改它的直接后继，如此循环直到最后一个人出列。关键算法：1.最后一个数据指向头指针，形成循环链表head=newNode;//确定头结点p=head;f

3、or(i=1;i<=n-1;i++)//赋初值{p->data=i;p->next=newNode;//为下一个新建内存p=p->next;}p->data=n;//最后一个单独处理p->next=head;//指向头，形成循环链表p=head;2.输入值异常的情况cout<<"请输入环内总人数n:";cin>>n;if(n<1)//考虑n输入错误的情况{cout<<"n值输入错误"<>k;if(k<1

4、

5、k>n)//考虑k输入异常的情况{cout<<"k值输入错误"<

6、值:";cin>>m;if(m<1)//考虑m输入异常的情况{cout<<"m值输入错误"<next){for(i=1;inext;q=p->next;cout<<"第"<data<next=q->next;第13页北京邮电大学信息与通信工程学院p=p->next;deleteq;//释放q的空间s++;}cout<<"最后环内留下的人编号是："<data<

7、l;deletep;算法步骤：①从第一个结点开始，查找第i-1个元素，设为p指向该结点；②设q指向第i个元素：q=p->next;，输出q元素的数据；③摘链，即将q元素从链表中摘除：p->next=q->next;p=p->next;deleteq;3.程序运行结果1、测试主函数流程：流程图如图所示是输入n,k,m，m输入正确请按任意键继续否初始化循环链表是开始移动工作指针p，找到目标结点输出数据，删除结点,n=n-1结束否输出最后一个出列的编号n>1第13页北京邮电大学信息与通信工程学院2、程序运行结果3、输入错误运行结果4.总结在调试程序过程中，虽然没有编译

8、错误，但是运行结果总是和准确值差1，最后发现是把i=1写成i=0，才造成的错误，改过之后就没有问题了。第13页北京邮电大学信息与通信工程学院数据结构为我们提供有效算法，我们需要好好理解其中的每一段算法以便我们运用数据结构的知识解决复杂的问题。数据结构是我们学好编程的好助手。下一步，应该运用模版相关知识，改进程序，使程序更具有可行性与规范性。下面是余秋雨经典励志语录，欢迎阅读。不需要的朋友可以编辑删除！！　　关于年龄　　1.一个横贯终生的品德基本上都是在青年时代形成的，可惜在那个至关重要的时代，青年人受到的正面的鼓动永远是为成功而搏斗，而一般所谓的成功总是带有排他

9、性、自私性的印记。结果，脸颊上还没有皱纹的他们，却在品德上挖下了一个个看不见的黑洞。　　2.我不赞成太多地歌颂青年，而坚持认为那是一个充满陷阱的年代。陷阱一生都会遇到，但青年时代的陷阱最多、最大、最险。　　3.历史上也有一些深刻的哲人，以歌颂青年来弘扬社会的生命力。但这里显然横亘着一种二律背反：越是坚固的对象越需要鼓动青年去对付，但他们恰恰因为年轻，无法与真正的坚持相斡旋。　　4.青年时代的正常状态是什么，我想一切还是从真诚的谦虚开始。青年人应该懂得，在我们出生之前，这个世界已经精精彩彩、复复杂杂地存在过无数年，我们什么也不懂，能够站正脚下的一角建设一点什么，已

10、是万幸。第13页北京邮电