@[TOC](Luo Valley P1996 Joseph problem (C language)) data structure a little tired, learn a simple algorithm to alleviate the following, today do Joseph, although the first year has done, but now have the knowledge of data structure, do these must have a further experience and perception of it.

The title

1. Single linked list simulation

We used arrays a long time ago, but now let’s take a different approach and see how it works with linked lists:

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
} Node;

void CreatFromTail(Node *head,int length)
{
    Node *p;                  / / stern interpolation
    int flag=1;
    p=head;
    int i;
    for(i=1; i<=length; i++) { p->next=(Node*)malloc(sizeof(Node));
        p->next->data=i;
        p=p->next;
    }
    p->next=head->next;// Notice here, as usual the first node head is not used
}

void Josephus(Node *head,int m)
{
    Node *p,*q,*s;
    p=head->next;
    int i,j=1;
    while(p->next! =p) {while(j<m)
        {
            q=p;
            p=p->next;
            j++;
        }
        // Delete the node
        s=p;
        p=p->next;
        q->next=p;
        printf("%d ",s->data);
        free(s);
        j=1;
    }
    printf("%d ",p->data);
}
int main(a)
{
    Node *head=(Node*)malloc(sizeof(Node));// Space must be allocated
    int length,m;
    scanf("%d %d",&length,&m);
    CreatFromTail(head,length);
    Josephus(head,m);
    return 0;

}

Copy the code

The result is correct as shown below:In fact, the idea is on the surface, with the linked list simulation, to the MTH delete and output can be.

2. Queue simulation

It feels like a storm in a teacup to solve this problem with queues. Queue functions are written more than bodies. The idea is that the first element of the team, see not to m, not put at the end of the team, arrived on the team. The code is as follows:

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 100

typedef struct queue{
    int Qnum[MAXSIZE];// Note here is the key. We use the same queue type as our ADT!!
    int front;
    int rear;
}Queue;// In this case I chose to operate with arrays

void initilize(Queue *Q) { // Initialize the queue
    Q->front = 0;
    Q->rear = 0;
}

int Pop(Queue *Q)/ / out of the team
{
    Q->front++;
    return Q->Qnum[Q->front];
}

void Push(Queue *Q,int i)/ / team
{
    Q->rear++;
    Q->Qnum[Q->rear]=i;
}

int Isempty(Queue *Q)/ / found empty
{
    return Q->front==Q->rear;
}

void Setup(Queue *Q,int length)// Create a task queue
{
    initilize(Q);
    for(int i=1; i<=length; i++) { Push(Q,i); }}void Josephus(Queue *Q,int m)
{
    int i,j=1,move,remove;
    while(! Isempty(Q)) {while(j<m)
        {
            move=Pop(Q);
            Push(Q,move);
            j++;
        }

        remove=Pop(Q);
        printf("%d ",remove);
        j=1; }}int main(a)
{
    Queue Q;
    int length,m;
    scanf("%d %d",&length,&m);
    Setup(&Q,length);
    Josephus(&Q,m);

    return 0;
}

Copy the code

Array emulation

#include<stdio.h>
int ML=105;
int n,m;
int a[105];
int main(a)
{
    scanf("%d%d",&n,&m);
    int num=n,last=1;
    while(num)
    {
        int cnt=0;
        for(inti=last; cnt! =m; i++) {if(i>n) i%=n;
            if(a[i]==- 1) continue;
            cnt++;
            if(cnt==m)
            {
                a[i]=- 1;
                num--;
               	last=i+1;
               	printf("%d ",i);
               	break; }}}return 0;
    }
Copy the code

This train of thought is consistent with the above mentioned, and will not be repeated.