澳门太阳娱乐集团官网-太阳集团太阳娱乐登录

澳门太阳娱乐集团官网【数据结构】Joseph难点
分类:操作系统

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

需求表达:略

分析:

澳门太阳娱乐集团官网 2

 

实现:

#include<stdio.h>
#include<stdlib.h>
typedef struct node {
        int payload ;
        struct node* next ;
}node ;

/*Function:在约瑟夫环尾部插入一个结点。add
 * param:node* tail 约瑟夫环的尾巴结点;
 * return: node* tail 返回新的约瑟夫环尾巴结点
 * */
node* add ( node* tail){
        if(tail == NULL){

           tail = (node* ) malloc(sizeof(node)) ;
           tail -> next = tail ;
           return tail ;
        }
        else{
           node* new_tail = (node* ) malloc (sizeof(node));
           new_tail -> next = tail -> next ;
           tail -> next = new_tail ;

           return new_tail;
        }
}

/*Function:遍历约瑟夫环,traverse_joseph_circle
 *param:node* tail
 *return :void
 *
 *
 * */
void traverse_joseph_circle(node* tail){
        node* move = tail  ;//作移动的指针
        //整体思路:有点结点的情况下,进入遍历;把尾结点和头结点的关系给干掉,展成一条链,回到头结点,往下移动,在往下移动前,先游历这个结点,在判断能不能往下
游历。
        while(move != NULL){
            move = move -> next ;//移动回头结点
            printf("%d ;", move -> payload) ;
            if (move == tail) break ;
        }   
        printf("n");
}
/*Function:约瑟夫环问题的实现。eliminate
 *param :node* tail; int step
 *return: void
 *
 * */
void eliminate(node* tail,int step){
        node* move = tail ;
        node* save_previous = tail ;
        int count = 0 ;
        while (NULL != tail && (move != move -> next)){
            save_previous = move ;
            move = move -> next ;if(++ count == step){
                save_previous -> next = move -> next ;
                printf("当前要删结点:%dn",move -> payload);
                if (tail == move ) tail = save_previous ;//更新约瑟夫环 
                free(move);
                printf("当前结点:n");
                traverse_joseph_circle (tail) ;
                move = save_previous ;
                count = 0 ;

             }

        }
}
int main(){
        node* tail;
        //构建十个结点的约瑟夫环
        int i ;
        for ( i = 0 ; i < 20 ; i ++ ){
            tail = add (tail );
            tail -> payload = i ;
        }
        traverse_joseph_circle (tail) ;
        eliminate(tail,3);
}

效果:

[xx@localhost joseph_circle]$ ./joseph_circle.out 
0 ;1 ;2 ;3 ;4 ;5 ;6 ;7 ;8 ;9 ;
当前要删结点:2
当前结点:
0 ;1 ;3 ;4 ;5 ;6 ;7 ;8 ;9 ;
当前要删结点:5
当前结点:
0 ;1 ;3 ;4 ;6 ;7 ;8 ;9 ;
当前要删结点:8
当前结点:
0 ;1 ;3 ;4 ;6 ;7 ;9 ;
当前要删结点:1
当前结点:
0 ;3 ;4 ;6 ;7 ;9 ;
当前要删结点:6
当前结点:
0 ;3 ;4 ;7 ;9 ;
当前要删结点:0
当前结点:
3 ;4 ;7 ;9 ;
当前要删结点:7
当前结点:
3 ;4 ;9 ;
当前要删结点:4
当前结点:
3 ;9 ;
当前要删结点:9
当前结点:
3 ;

 

本文由澳门太阳娱乐集团官网发布于操作系统,转载请注明出处:澳门太阳娱乐集团官网【数据结构】Joseph难点

上一篇:澳门太阳娱乐集团官网手把手教您在U盘里面安装 下一篇:没有了
猜你喜欢
热门排行
精彩图文