快捷搜索:

您的位置:澳门新葡4473网站 > 热门贴子 > 【数据结构】约瑟夫问题 C语言链表实现

【数据结构】约瑟夫问题 C语言链表实现

发布时间:2019-10-11 01:30编辑:热门贴子浏览(163)

    1.首先,我们先来了解一下什么是约瑟夫环问题:

    讲一个比较有意思的故事:约瑟夫是犹太军队的一个将军,在反抗罗马的起义中,他所率领的军队被击溃,只剩下残余的部队40余人,他们都是宁死不屈的人,所以不愿投降做叛徒。一群人表决说要死,所以用一种策略来先后杀死所有人。 
    于是约瑟夫建议:每次由其他两人一起杀死一个人,而被杀的人的先后顺序是由抽签决定的,约瑟夫有预谋地抽到了最后一签,在杀了除了他和剩余那个人之外的最后一人,他劝服了另外一个没死的人投降了罗马。

     

    通俗来说就是:

    按照如下规则去杀人:

    • 所有人围成一圈
    • 顺时针报数,每次报到3的人将被杀掉
    • 被杀掉的人将从房间内被移走
    • 然后从被杀掉的下一个人重新报数,继续报3,再清除,直到剩余一人

    那么程序实现为:

      链表的定义: 定义为编号即可 所以data项为int

      

    typedef struct NODE{
        struct NODE *next;
        int data;
    }Node,*Linklist;
    

     

    由于是循环,直到最后一个人, 所有可以使用特殊的链表: 循环链表。 当链表中只剩下一个元素后,便认为完事了。 即 L->next = L;

    #include <stdio.h>
    #include <stdlib.h>
    #include "Linklist.h"
    
    void Print_Linklist(Linklist L)
    {
        Linklist head = L;
        printf("List: ");
        while(L->next != head)
        {
            printf("%d ",L->data);
            L = L->next;
        }
        printf("%d ",L->data);
        printf("n");
    }
    
    int main()
    {
        int i;
        Linklist L;
        Linklist head;
        Linklist Out;
        L = (Node*)malloc(sizeof(Node));
        head = L;
        L->data = 1;
        L->next = head;
        for(i=2;i<=41;i++)
        {
            L->next=(Node*)malloc(sizeof(Node));
            L->next->data = i;
            L->next->next = head;
            L = L->next;
        }
        Print_Linklist(head);
        L = head;
        while(L != L->next)
        {
             for(i=1;i<2;i++)
             {
                 L = L->next;
             }
             Out = L->next;
             printf("%2d号 ----> 自杀!n",Out->data);
             L ->next = Out->next;
             L = L->next;
             free(Out);
        }
        printf("幸存者是:%d",L->data);
        return 0;
    }
    

    图片 1

    本文由澳门新葡4473网站发布于热门贴子,转载请注明出处:【数据结构】约瑟夫问题 C语言链表实现

    关键词:

上一篇:没有了

下一篇:没有了