Круговая, односвязная, где узлы удаляются один за другим

Question

Добрый вечер, моя программа для следующей задачи на самом деле не выполняет то, что должна, и я не могу найти ошибку.

"Группа из n человек организована по кругу, и эти люди пронумерованы от 1 до n. Кроме того, задано фиксированное натуральное число M. Теперь, начиная с человека 1, m-й человек удаляется из круга, и отсчет начинается снова со следующего человека. Это повторяется до остается только один человек. Задача состоит в том, чтобы найти число L (n, m) ∈ {1, ..., n} этого последнего человека. Для фиксированных n и m эту проблему можно решить с помощью программы, в которой круг лиц представлен круглым, односвязным списком, то есть односвязным списком, где «последняя» запись указывает на «первую» запись

Примеры: L (n = 7, m = 4) = 2 , L (21, 3) = 2, L (100, 10) = 26 "

Когда, например, я сначала ввожу n = 7 & m = 4, затем выдаю список и затем начинаю удаление процесс я получаю этот вывод:

1) input n&m
 2) give out list
 3) start deleting process
 4) END
1
n: 7
m: 4

 1) input n&m
 2) give out list
 3) start deleting process
 4) END
2
1->2->3->4->5->6->7

 1) input n&m
 2) give out list
 3) start deleting process
 4) END
3
The last person is: 7
 1) input n&m
 2) give out list
 3) start deleting process
 4) END
1
n: 6
m: 2

это говорит последний человек остаться это 7, что не соответствует действительности. Я думаю, что это всегда говорит, что n - последний человек, независимо от того, что ввод для m. Это также «работает» только для одного цикла. После того, как я выбрал опцию 3), в первый раз я все еще могу ввести новые числа n & m, однако затем программа, похоже, вообще перестает работать.

Спасибо за ваше время и помощь.

#include <stdio.h>
#include <stdlib.h>
int n,m;

struct s_ring
{
    unsigned int position;
    struct s_ring *next;
};
typedef struct s_ring *t_ring; 
t_ring allocate(void)  
{
    t_ring pointer;
    pointer=(t_ring)malloc(sizeof(*pointer));
    if(pointer==NULL)
    {
        printf("Error malloc");
        exit(1);
    }
    pointer->next=NULL;
    return pointer;
}
void circle(t_ring start, t_ring q, int i, int n)
{
    t_ring p=start;
    while(p->next!=NULL && p->next->position<q->position)
        p=p->next; 
    if(i<n)
    {
        q->next=p->next;
        p->next=q;
    }
    if(i==n)
    {
        q->next=start->next;
        p->next=q;
        start=q;
    }
    return;
}
void print_list(t_ring p)
{
    unsigned int i=p->position;
    while(i!=p->next->position)
    {
        printf("%u->",p->position);
        p=p->next;
    }
    printf("%u\n",p->position);
    return;
}
void delete_m(t_ring pointer,t_ring start,int m)
{
    t_ring p=start,q;
    int i=1;
    while(p->position != p->next->position)
    {
        p=p->next;
        i++;
        if(i==m)
        {
            q=p->next;
            p->next=p->next->next;
            free(q);
            i=1;
        }
    }
    if(p->position==p->next->position)
    {
        pointer=p->position;
    }

    return pointer;
}
int main()
{
    int i;
    unsigned int op;
    t_ring start, 
           pointer;
    pointer=start;
    start=allocate();
    do
    {
        printf("\n 1) input n&m " );
        printf("\n 2) give out list " );
        printf("\n 3) start deleting process " );
        printf("\n 4) END \n" );
        scanf("%u",&op);
        switch(op)
        {
        case 1:
            printf("n: ");
            scanf("%d",&n);
            printf("m: ");
            scanf("%d",&m);
            for(i=1; i<=n; i++)
            {
                pointer=allocate();
                pointer->position=i;
                circle(start,pointer,i,n);
            }
            break;
        case 2:
            print_list(start->next);
            break;
        case 3:
            delete_m(pointer,start,m);
            printf("The last person is: %d",*pointer);
        }
    }
    while(op!=4);
    return 0;
}

Answer 1

Ваш код неверен хотя бы потому, что функция delete_m имеет тип возврата void, но возвращает pointer .:)

void delete_m(t_ring pointer,t_ring start,int m)
{
    //...
    return pointer;
}

. Я могу предложить следующий подход, который показан в демонстрационная программа ниже.

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

struct ring_list
{
    unsigned int n;
    struct ring_list *next;
};

void display( struct ring_list *head )
{
    if ( head )
    {
        struct ring_list *tail = head;

        do
        {
            printf( "%u -> ", head->n );

        } while ( ( head = head->next ) != tail );
    }

    puts( "null" );
}

void clear( struct ring_list **head )
{
    while ( *head )
    {
        struct ring_list *current = *head;

        *head  = current == ( *head )->next ? NULL : ( *head )->next;

        free( current );
    }

}

void init( struct ring_list **head, unsigned int n )
{
    if ( *head ) clear( head );

    struct ring_list *tail = *head;

    for ( unsigned int i = 0; i < n; i++ )
    {
        *head = malloc( sizeof( struct ring_list ) );
        ( *head )->n = i + 1;
        if ( i == 0 ) tail = *head;
        head = &( *head )->next;
    }

    *head = tail;
}

unsigned int remove_each_n( struct ring_list **head, unsigned int n )
{
    struct ring_list **initial_head = head;

    unsigned int result = 0;

    if ( *head != NULL && n != 0 )
    {
        --n;

        while ( *head != ( *head )->next )
        {
            for ( unsigned int i = 0; i < n; i++ )
            {
                head = &( *head )->next;
            }

            struct ring_list *current = *head;
            *head = current->next;
            if ( ( *head )->next == current ) ( *head )->next = *head;
            free( current );
        }

        result = ( *head )->n;
    }

    *initial_head = *head;

    return result;
}   

int main(void) 
{
    struct ring_list *head = NULL;

    unsigned int n = 7;
    unsigned int m = 4;

    init( &head, n );

    display( head );

    unsigned int result = remove_each_n( &head, m );

    printf( "L( %u, %u ) = %u\n\n", n, m, result );

    n = 21;
    m = 3;

    init( &head, n);

    display( head );

    result = remove_each_n( &head, m );

    printf( "L( %u, %u ) = %u\n\n", n, m, result );

    n = 100;
    m = 10;

    init( &head, n);

    result = remove_each_n( &head, m );

    printf( "L( %u, %u ) = %u\n\n", n, m, result );

    return 0;
}

Вывод программы

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
L( 7, 4 ) = 2

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 21 -> null
L( 21, 3 ) = 2

L( 100, 10 ) = 26