C语言 约瑟夫环单向循环链表报数游戏 用循环链表方解决 出了问题 求教 代码图片如下

本科系列课程参见:《》

约瑟夫(Joeph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数报m的人出列,将他的密码作为新的m值从他在顺时针方向上的下一个囚开始重新从1报数,如此下去直至所有人全部出列为止。试设计一个程序求出出列顺序

利用单向循环链表存储结构模拟此过程,按照絀列的顺序印出各人的编号

游戏实现的关键是游戏信息的储存包括玩家座位信息,玩家所报数信息以及密码信息我们通过自定义单向循环链表Joeph_list存储结构来实现游戏过程的模拟。链表以结点连接结点Node存储的信息包括每个人手中的密码、每个人的位置以及下一个结点在计算机中的存储位置,及指向下一个结点的指针值得注意的是,信息“每个人的位置”是必不可少的因为他不等同于结点在链表中的位置——但一个玩家被移除之后,链表后的元素位置会“前进”而我们需要的玩家的位置始终是不变的。
玩家的报数我们通过循环中计數器的递增实现,当顺序递增到链表中最后一个结点而循环仍没有结束时,我们继续从第一个元素开始递增——及相当于最后一个玩家仍没有报数到m我们就从第一个玩家重头开始报数直到计数器累加到m,则发现我们要移除的结点记录并输出移出结点的信息,继续游戏直到链表中元素被清空,程序结束
算法的关键是将实际游戏场景抽象到链表中的元素的查找和移除上,要掌握清楚哪些数据代表哪些信息并熟悉程序运行中各种判断的流程。


在这个游戏中假定每个人都是一个节点,这样有利于程序的理解


Joeph_list类:储存游戏中玩家座位、密码等信息的数据结构

List类:以链表的方式存储图片等数据结构

1、游戏开始,初始m为6从第一个玩家开始自动报数,报到数的人出列

2、以絀列人手中的密码为密码(不大于6)继续游戏

3、直到所有人出列游戏结束



(*点击图片可跳转到Youku视频)

编号为12…n的n个人按顺时针方向圍坐一圈,每人持有一个密码一开始人选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数报到m时停止报数,报m嘚人出列将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数直到所有人出列。设计程序求出列顺序

    将编号num,密碼data下个人的指针next封装成一个结构体,代表一个“人”围成一圈可以用循环链表实现,但是尾插法构造链表时尾元结点指向首元结点会避免绕圈时遇到头结点的情况
  1. 删除操作与判空操作一同写在main函数中。
    若p->next=p则该结点p已经是最后一个人所以在循环结束后不要忘记最后一個剩下的人。删除操作一定要先找到要删元素的前驱结点前驱结点指向p->next->next.

我要回帖

更多关于 约瑟夫环单向循环链表 的文章

 

随机推荐