精华内容
下载资源
问答
  • 约瑟夫环循环链表

    2017-11-20 23:14:37
    约瑟夫环问题的一种描述是:编号为1,2,3,n的n个人按顺时针围坐一圈,每人持有一个密码(正整数),一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将...

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

    //测试数据:m的初值为20,n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为6,正确的顺序应是6,1,4,7,2,3,5.

     #include<stdio.h>

     

    #include<malloc.h>

     

    typedef struct node

    {

     

         int number;

         int key;

         struct node* next;

     

    }listnode, * circularlist;//定义了结点类型listnode和指针类型circularlist

     

    int main()

    {

     

           int amount,t,code,m,k;// amount表示总人数,code表示相应的学生密码

           circularlist w=(listnode*)malloc(sizeof(listnode));

           w->next=w;//循环链表仅一个元素时依然满足

           listnode *v;

           printf("请输入总人数:");

           scanf("%d",&amount);

           v=w;

     

           for(k=1;k<=amount;k++)

          {

     

                  printf("请输入第 %d学生的密码: ",k);

                  scanf("%d",&code);

                  w->key=code;

                  w->number=k;

                  if(k!=amount)

                  {

                        w->next=(listnode*)malloc(sizeof(listnode));

                        w=w->next;

                  }

     

                 w->next=v;

     

            }//循环结束后自动生成链表头

     

           printf("约瑟夫环已建成,可以开始!\n");

     

           printf("请输入初值: ");

     

           scanf("%d",&m);

     

           if(m<=0)

          {

                 printf("输入错误,请重新输入\n");

                 return(1);

          }

     

           m=m-1;//使w提前停下

     

           printf("出列顺序是: ");

     

           //w为起始点

     

           do

          {

                  t=0;//加入m1后为零的情况

                  while(t!=m)

                 {

                       w=w->next;

                          t++;

                 }

     

                   v=w->next;

                    w->next=v->next;

                    printf(" %d",v->number);

                      m=v->key;

                    m=m-1;

                      free(v);//释放v的存储空间

          }while(w->next!=w);

     

           printf(" %d\n",w->number);

           free(w); //释放w的存储空间

           getchar();

           getchar();

           return(0);

     

    }

    展开全文
  • 2012-03-19 10:28 | 527055685@qq.com约瑟夫环的变体-37个奴隶问题,我也用了循环链表去做#include #include #define MAX 111 //总的奴隶数#define DIE 3 //数K个,第K个要被杀typedef struct link{int value;...

    2012-03-19 10:28 | 527055685@qq.com

    约瑟夫环的变体-37个奴隶问题,我也用了循环链表去做

    #include

    #include

    #define MAX 111 //总的奴隶数

    #define DIE 3 //数K个,第K个要被杀

    typedef struct link{

    int value; //用了保存奴隶的编号

    struct link *next;

    }* loop_link;

    void fun(struct link *slave);

    int main(void)

    {

    loop_link slave=NULL,current,head;

    int i;

    for(i=1;i<=MAX;i++)

    {

    current=malloc(sizeof(struct link));

    current->value=i;

    current->next=NULL;

    if(slave==NULL)

    {

    slave=current;

    head=slave;

    }

    else

    {

    slave->next=current;

    slave->next=slave->next;

    slave=slave->next;

    }

    }

    slave->next=head; /*将最后一个奴隶指向第一个奴隶,最终在这里形成一个循环链表 */

    slave=head;

    fun(slave);

    return 0;

    }

    void fun(struct link *slave)

    {

    int j;

    struct link* current;

    if(slave->value==slave->next->value)

    printf("这个编号为%d的奴隶不用被杀\n",slave->value);

    else

    {

    for(j=1;j

    {

    current=slave;

    slave=slave->next;

    }

    current->next=slave->next;

    current=slave;

    slave=current->next;

    free(current);

    fun(slave);

    }

    }  回复  更多评论

    展开全文
  • 编写测试案例public class Cicle {@Testpublic void test() {LinkedList linkedList = new LinkedList();linkedList.addNode(0);linkedList.addNode(1);linkedList.addNode(2);linkedList.addNode(3);...

    编写测试案例

    public class Cicle {

    @Test

    public void test() {

    LinkedList linkedList = new LinkedList();

    linkedList.addNode(0);

    linkedList.addNode(1);

    linkedList.addNode(2);

    linkedList.addNode(3);

    linkedList.addNode(4);

    //linkedList.print();

    Scanner scanner = new Scanner(System.in);

    int m = scanner.nextInt();

    Node tempNode = linkedList.tail;

    while(tempNode!=tempNode.next){//这是表示只剩下一个节点的情况

    for(int i = 0;i

    tempNode = tempNode.next;

    }

    System.out.print(tempNode.next.data+"  ");

    tempNode.next = tempNode.next.next;

    linkedList.size--;

    }

    System.out.println("最后剩下的数字"+tempNode.data);

    }

    }

    展开全文
  • 链表的使用,还可以把链表的两头连接,形成了一...实际应用:约瑟夫环问题约瑟夫环问题,是一个经典的循环链表问题,题意是:已知 n 个人(以编号1,2,3,…,n分别表示)围坐在一张圆桌周围,从编号为 k 的人开始顺...

    链表的使用,还可以把链表的两头连接,形成了一个环状链表,称为循环链表。

    和它名字的表意一样,只需要将表中最后一个结点的指针指向头结点,就形成了一个环。

    a268696e396c3dbc6398541e16eba82a.png

    图1 循环链表

    循环链表和动态链表相比,唯一的不同就是循环链表首尾相连,其他都完全一样。

    实际应用:约瑟夫环问题

    约瑟夫环问题,是一个经典的循环链表问题,题意是:已知 n 个人(以编号1,2,3,…,n分别表示)围坐在一张圆桌周围,从编号为 k 的人开始顺时针报数,数到 m 的那个人出列;他的下一个人又从 1 还是顺时针开始报数,数到 m 的那个人又出列;依次重复下去,要求找到最后出列的那个人。

    例如有 5 个人,要求从编号为 3 的人开始,数到 2 的那个人出列:

    df8dc3eb1834a6c4a6d245f5d056b526.png

    出列顺序依次为:

    编号为 3 的人开始数 1,然后 4 数 2,所以 4 先出列;

    4 出列后,从 5 开始数 1,1 数 2,所以 1 出列;

    1 出列后,从 2 开始数 1,3 数 2,所以 3 出列;

    3 出列后,从 5 开始数 1,2 数 2,所以 2 出列;

    最后只剩下 5 自己,所以 5 出列。

    完整代码

    #include

    #include

    typedefstructnode

    {intnumber;struct node *next;

    }person;

    person*initLink(intn)

    {

    person* head = (person*)malloc(sizeof(person));

    head->number = 1;

    head->next = NULL;

    person*cyclic = head;for (int i=2; i<=n; i++)

    {

    person*body = (person*)malloc(sizeof(person));

    body->number = i;

    body->next = NULL;

    cyclic->next = body;

    cyclic= cyclic->next;

    }

    cyclic->next = head;  //首尾相连

    returnhead;

    }void findAndKillK(person *head, int k, intm)

    {

    person*tail = head;//找到链表第一个结点的上一个结点,为删除操作做准备

    while (tail->next != head)

    {

    tail= tail->next;

    }

    person*p = head;//找到编号为k的人

    while (p->number!=k)

    {

    tail=p;

    p=p->next;

    }//从编号为k的人开始,只有符合p->next==p时,说明链表中除了p结点,所有编号都出列了,

    while (p->next!=p)

    {//找到从p报数1开始,报m的人,并且还要知道数m-1de人的位置tail,方便做删除操作。

    for (int i=1; i

    {

    tail= p;

    p= p->next;

    }

    tail->next = p->next;  //从链表上将p结点摘下来

    printf("出列人的编号为:%d\n", p->number);free(p);

    p= tail->next;//继续使用p指针指向出列编号的下一个编号,游戏继续

    }

    printf("出列人的编号为:%d\n", p->number);free(p);

    }intmain()

    {

    printf("输入圆桌上的人数n:");intn;

    scanf("%d", &n);

    person*head = initLink(n);

    printf("从第k人开始报数(k>1且k

    scanf("%d", &k);

    printf("数到m的人出列:");intm;

    scanf("%d", &m);

    findAndKillK(head, k, m);return 0;

    }

    输出结果:

    输入圆桌上的人数n:5从第k人开始报数(k>1且k<5):3数到m的人出列:2出列人的编号为:4出列人的编号为:1出列人的编号为:3出列人的编号为:2出列人的编号为:5

    总结

    循环链表和动态链表唯一不同在于它的首尾连接,这也注定了在使用循环链表时,附带的最多的操作就是遍历链表。

    在遍历的过程中,尤其要注意循环链表虽然首尾相连,但并不表示该链表没有第一个节点和最后一个结点。所以,不要随意改变头指针的指向。

    展开全文
  • 什么是约瑟夫环问题?约瑟夫,是一个古犹太人,曾经在一次罗马叛乱中担任将军,后来战败,他和朋友及另外39个人躲在一口井里,但还是被发现了。罗马人表示只要投降就不死,约瑟夫想投降,可是其他人坚决不同意。...
  • 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律...
  • 简单的循环链表,c语言编写,希望多多支持
  • 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求...
  •  3 //约瑟夫环的实现:一群人围成一圈,这群人共有 n个人,每个人身上都一个key,依次给这圈人编号:  4 //1,2,n 一开始报数的上限值为m从第一个人(编号:1)自一开始报数报到m时停止报数,报到m的人出列...
  • 约瑟夫(Joseph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按...此程序运用了循环链表和递归的方法来...
  • #include <stdio.h> #include <stdlib.h> typedef struct Node{ int data; struct Node *next; }Node, *LinkedList;...LinkedList insert(LinkedList head, Node *node, int index) { ...
  • 是最简单的约瑟夫环代码 结构简单易懂 保证你会满意的呀
  • "约瑟夫环长度为 : ";;   cin >> n;    int m=0;   cout   "每此数到m个时,此人出列";    int k;   cin >> k;   cout   "从第k 个开始数"  endl;   cin >>m;   ...
  • 代码如下, #include <STDIO.H> #include <MALLOC.H> #include <iostream> using namespace std; typedef struct Node { int data; struct Node *next; }node; ...
  • 首先,约瑟夫环的数学优化方法为:为了讨论方便,先把问题稍微改变一下,并不影响原意:问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。我们知道第一个人...
  • 请输入你的循环链表的结点数:";cin>>n;CreateList(newlist,n);DisplayList(newlist);cout<do{cout<cin>>from;}while(0>=from || from>n);cout<cin>>interval;Josephus(newlist,n,...
  • ************************************************************************/ /*约瑟夫环说明:N(N>1) 个人组成一圈,从第 num 个人开始报数(从 1 开始报数) *当谁报到数字 count 时将执行枪决,然后继续从后面一位...
  • 每个人有一个num,跳出时将当前的m改为num继续约瑟夫环 #include using namespace std; typedef struct node { int data,num; struct node *next; }LNode; int main() { LNode *First,*P,*tmp; First=new ...
  • 约瑟夫环循环链表

    2011-11-19 20:00:00
    约瑟夫环循环链表 附一组测试数据:3172684 20 6147235
  • }//创建单向循环链表 ElemSN*Fun(ElemSN*t,int s){ int i; ElemSN*h1=NULL,*t1,*h; //t1是行链表的尾结点指针,h是建立新链表的结点(出约瑟夫环的结点),h1新链表的头结点 while(t-t->next){//截止条件是环中只剩下...
  • 一开始任选一个正整数作为报数上限值 m ,从第一个人开始按顺时针方向自 1 开始顺序报数,报到 m 时停止报数。报 m 的人出列,将他的密码作为新的 m 的值...基本要求利用单向循环链表存储结构模拟此过程,按照出列的...
  • 循环链表约瑟夫环 循环链表的实现 单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表。当它是空表,向后结点就只想了自己,这也是它与单链表的...
  • #include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std;...//创建约瑟夫环循环链表 person* initLink(int n) { person * head=(person*)malloc(sizeof(perso...
  • 问题描述:约瑟夫环(Joseph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始人选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,...
  • 这是作者在数据结构课程学习过程中,在链表学习部分的一个小小作品
  • 约瑟夫环双向链表

    2018-04-15 21:21:26
    /*该约瑟夫环使用的是循环链表*/ /*构建结构体*/ typedef struct Node{ int Num; struct Node *next; struct Node *pre; }JoseNode, *PNode, *HNode;//这个结构代表一个数据域和指针域的结点...
  • 约瑟夫环循环链表

    2020-05-21 10:30:48
    约瑟夫环的定义 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;...
  • 循环链表和约瑟夫环循环链表的实现单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表。当它是空表,向后结点就只想了自己,这也是它与单链表的主要...
  • 约瑟夫环,用循环链表实现,语言为Java。假设数到三的数出列。程序输出1到10的出列顺序。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,642
精华内容 656
关键字:

约瑟夫环循环链表