实验 一 约瑟夫环问题实验报告

《实验 一 约瑟夫环问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、题目二约瑟夫环问题设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。structnode//结点结构{intnumber;/*人的序号*/intcipher;/*密码*/structnode*next;/*指向下一个节点的指针*/};一、循环链表的结点类型定义/*单链表的结点类型*/type

2、defstructnode{intnumber;intcipher;structnode*next;}list,*linklist;二、循环链表的初始化/*函数功能:初始化n个元素的循环链表参数;链表(linklistL)，元素个数（intn）通过后插法对无头结点的链表初始化。*/voidinit(linklist&L,intn){intkey,i;cout<<"输入第1个人的密码为：";//输入第一个节点的密码。cin>>key;L=newlist;L->number=1;L->cipher=key;L->next=L;for(i=2;i<=n;i++)//输入2—n的节点密码。{link

3、listp=newlist;cout<<"输入第"<>key;p->cipher=key;p->number=i;p->next=L->next;//使用后插法插入。L->next=p;L=L->next;}cout<next;//循环链表的头结点为第一个节点}三、循环链表的长度/*函数功能:求循环链表的长度参数;链表(linklistL)通过各个扫描求循环链表长度*/intsize(linklistL){if(L==NULL)//头结点为空返回循环链表长度为0return0;inti=1;linklistp=L->next;whil

4、e(p!=L)//判断是否到尾。{i++;p=p->next;}returni;//返回循环链表的长度}四、显示循环链表/*函数功能:循环链表的显示参数;链表(linklistL)通过各个扫描各个节点输出各个节点的密码*/voidshow(linklistL){inti=1;linklistp=L;cout<<"第1个人的密码为："<cipher<next;while(p!=L)//判断是否到尾部{i++;cout<<"第"<cipher<next;}cout<

5、实现所有人的出列次序参数;链表(linklistL)，密码（intm）每次要找到出列者的前驱，把出列者删除*/voidJoseph(linklist&L,intm){linklistp=L;//p指向头结点。for(intn=size(L);n>0;n--){cout<<"密码为"<next;cout<next->number<next->cipher;linklistq=p->next;//删除出列者p->next=q->next;free(q);//释

6、放内存}}总结：main函数先调用初始化循环链表的的函数voidinit(linklist&L,intn)，然后将循环链表输出voidshow(linklistL)，最后调用可以使人出列的函数voidJoseph(linklist&L,intm)。本程序可以很好地运行，具有一定的除错能力，输入数据时可以对其进行判断，减少程序出现bug的可能性。通过对本实验的操作，我熟悉了循环链表的基本操作，而且对循环链表的基本操作有了很好的掌握。程序清单#include"iostream"#include"stdlib.h"usingnamespacestd;typedefstructnode{intnum

7、ber;intcipher;structnode*next;}list,*linklist;voidinit(linklist&L,intn){intkey,i;cout<<"输入第1个人的密码为：";cin>>key;L=newlist;L->number=1;L->cipher=key;L->next=L;for(i=2;i<=n;i++){linklistp=newlist;cout<<"输入第"<