约瑟夫环问题实验报告 |
您所在的位置:网站首页 › 约瑟夫循环链表 › 约瑟夫环问题实验报告 |
1.实验目的及要求 目的:能够熟练掌握线性表的基本操作在顺序和链式两种存储结构上的实现,进一步理解线性表的逻辑结构和存储结构,提高使用理论知识指导解决实际问题的能力。 要求:1.建立数据模型,确定存储结构; 2.对任意人数、密码,都能实现约瑟夫环问题; 3.出圈顺序可以依次输出,也可以用一个数组输出。 2.实验步骤 1.实验问题分析 (1)由于当某个人退出圆圈后,报数的工作要从下一个人继续,剩下的人仍要围成一个圆圈,这个问题具有循环性质,考虑使用循环链表; 由于退出圆圈的这个指令对应着结点的删除操作,且这种删除操作使用频繁,考虑选择效率较高的链表结构; 循环链表的结点定义为如下结构类型: 创建一个长度为n的循环链表: (2)由于退出圆圈的这个指令对应着结点的删除操作,于是定义了一个delete函数。在删除结点的时候考虑到几个特殊的情况,头尾结点。在删除第一个结点时,需要将head 指针下移,尾结点的next也需指向第二个结点;删除尾结点时,要将尾结点前的结点与第一个结点相连。当只剩下一个结点时,不需要删除,直接输出data的值。具体实现函数如下: (3)主程序执行。主程序运行时,调用函数。 2.从键盘输入整数m(出圈数)和n(总人数)(1 jd*p,*head,*pe;//创建指针 head=new jd;//创建空地址 head->next=NULL;//置空 pe=head;//将前指针置为头结点 for(int i=0;i jd*pe,*p; int count=1,sum=0; pe=head; p=head->next; while(lo!=0)//无元素时退出 { if(p==head) { pe=pe->next; p=p->next; } if(count==m)//删除等于m的节点 { printf("第%-2d个出圈号数: %d号\n",++sum,p->s); pe->next=p->next; delete(p); p=pe->next;//将p的地址赋为下一个地址 lo--; count=0;//重置 } else { pe=pe->next; p=p->next; } count++; } } int main() { int n,m; int arr[1000]; for(int i=0;i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |