C++约瑟夫环实验报告

数据结构集中上机试验报告学院：计算机科学与技术专业：计算机科学与技术学号：111111111111班级：（6）姓名：莫莫莫200joseph环上机实验报告实验名称：joseph环题目要求的约瑟夫环操作：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。实验要求：1~）利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。2~）建立输入处理输入数据，输入每个人的密码，建立单循环链表。3~）测试数据：m的初值为6，n=7,7个人的密码依次为3，1，7，2，4，8，4，首先m=6,则正确的输出是什么？实验过程：1.基本算法以及分析：本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下structJoseph{ longnumber; Joseph*next; floatscore;};程序有主函数开始，首先，提示输入每个环上所带的密码。然后，开始调用Joseph*Create()函数，利用单循环链表建立起约瑟夫环， pEnd->next=head;就是将最后一个结点的后继指向头结点，函数结尾return(head);将约瑟夫环的头指针返回，并将它赋值head，依次录入各节点的密码值，然后主函数继续调用 Delete函数，实现如下功能：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。2.程序源代码：约瑟夫环#include<iostream>usingnamespacestd;structJoseph{ longnumber; Joseph*next; floatscore;};Joseph*head;Joseph*Create(){ intk=1; Joseph*ps;//当前要插入的结点 Joseph*pEnd;//链尾指针 ps=newJoseph;//为当前要插入的结点分配空间 cin>>ps->score; ps->number=k++; head=NULL;//初始化链表，开始时链表为空 pEnd=ps; while(ps->score!=0)//以输入的学生号为0作为结束条件 { if(head==NULL)//当前插入的结点为链表的第一个结点 head=ps; else pEnd->next=ps; pEnd=ps; ps=newJoseph; cin>>ps->score; ps->number=k++; } pEnd->next=head; deleteps;//释放结点成员number为0的结点所占的内存 return(head);}voidDelete(Joseph*q,intm){ Joseph*p;Joseph*pGuard; pGuard=q; p=newJoseph; p->next=pGuard; while(pGuard->next!=pGuard)//循环判断，若只剩下最后一个节点，则循环结束 { for(inti=1;i<m;i++)//开始顺序报数 { p=pGuard; pGuard=pGuard->next; } p->next=pGuard->next; cout<<pGuard->number<<"havebeendeleted\n"<<endl;//输出循环删除的结点m=pGuard->score;//将节点密码作为新的m值 delete(pGuard); pGuard=p->next; }cout<<pGuard->number<<"havebeendeleted\n"<<endl;//输出最后删除的结点 }voidmain(){ cout<<"请依次输入每个人的密码："; head=Create(); Delete(head,6); }3.运行结果初始密码6，输入七个人的密码，以0作为结束条件输入密码：3172484输出结果：6147235

4此程序目前的缺点在于，结点密码数据类型定义的存储类型是int型，不能超过-2147483648～21