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

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

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

2、2N……单循环链表存储结构示意图2.2关键算法分析基本思想：首先，应该确定构造链表时所用的插入方法。当数到m的那个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表方式。其次还要考虑输入值异常的情况。之后，就是关于出列节点的逻辑判断。依次找到待删结点的直接前驱，便于删除结点后修改它的直接后继，如此循环直到最后一个人出列。关键算法：1.最后一个数据指向头指针，形成循环链表head=newNode;//确定头结点p=head;for(i=1;i<=n-1;i++)//赋初值{p->data=i;p->next=newNode;//为下

3、一个新建内存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值输入错误"<>m;if(m<1)//考虑m输入异常的情况{cout<<"m值输入错误"<

6、个出环并找出最后一个出环的序号while(p!=p->next){for(i=1;inext;q=p->next;cout<<"第"<data<next=q->next;p=p->next;deleteq;//释放q的空间s++;}cout<<"最后环内留下的人编号是："<data<next;，输出q元素的数据；③摘链，即将q元素从链表中摘除：p-

7、>next=q->next;p=p->next;deleteq;3.程序运行结果1、测试主函数流程：流程图如图所示是输入n,k,m，m输入正确请按任意键继续否初始化循环链表是开始移动工作指针p，找到目标结点输出数据，删除结点,n=n-1结束否输出最后一个出列的编号n>12、程序运行结果3、输入错误运行结果4.总结在调试程序过程中，虽然没有编译错误，但是运行结果总是和准确值差1，最后发现是把i=1写成i=0，才造成的错误，改过之后就没有问题了。数据结构为我们提供有效算法，我们需要好好理解其中的每一段算法以便我们运用数据结构的知识解决复杂的问题。数据结构是我们学好编程的好助手。下一步，

8、应该运用模版相关知识，改进程序，使程序更具有可行性与规范性。