为什么循环列表不能解决约瑟夫问题？

Question

我正在开发解决 C 上的 Josephus 问题 的程序。我必须在这里使用循环链表。目前我有这个代码来创建列表：

void create_list(int N, struct node* head){
    int i, j, k;
    for(i = 2; i <= N; i++){
        struct node* tmp_node = (struct node*)malloc(sizeof(struct node));
        tmp_node -> number = i;
        tmp_node -> next = NULL;
        tmp_node -> next = head -> next;
        head -> next = tmp_node;
        head = tmp_node;
    }
  }

现在我正在努力寻找 Josephus 排列后要提醒的最后一个元素。我有这个：

int find_last(int M, struct node* head){
    int i, j = 1;

    if(head -> next == NULL){
        return head -> number;
    }
    else {
        struct node* current = head;
        while(current -> next != NULL){
            while(current -> next -> number != j){
                current = current -> next;
                j++;
            }
            if (j % M == 0){
                struct node* delete_node;
                delete_node = current -> next;
                current -> next = delete_node -> next;
                free(delete_node);
                j = 1;
            }
        }
        return current -> number;
    }
}

这是我的主要内容：

int main(){
    int M, N, i, j, res;
    struct node* head = (struct node*)malloc(sizeof(struct node));
    head -> number = 1;
    head -> next = NULL;
    read_numbers(&N, &M);
    create_list(N, head);
    res = find_last(M, head);
    printf("%d\n", res);
    
    return 0;
}

问题出现在 int find_last 函数中。请告诉我错误以及我可以采取哪些措施来解决问题，感谢您的宝贵时间。

编辑。

我已经绘制了算法并更新了我的函数，但它仍然不起作用。这是：

int find_last(int M, int N, struct node* head){
    int i = 0, j = 1;

    if(head -> next == NULL){
        return head -> number;
    }
    else {
        struct node* current = head;
        while(i != N){
            while(j % M != 0){
                current = current -> next;
                j++;
            }
            struct node* delete;
            delete = current -> next;
            delete -> next = current -> next;
            free(delete);
            i++;
        }
        return current -> number;
    }
}

Answer 1

create_list()

不会创建圆形 LL。您必须检查代码才能发现自己的错误。最短的解释将比仅仅修复代码需要更长的时间。

要学习的更短（工作！）代码：

typedef struct n { // typedef reduces verbiage
    int no; // simple, short and sweet name for variables
    struct n *next;
} node;

node *create( int N ) { // simple function name
    node *pHead = NULL, *pTail = NULL; // track head & tail of LL

    for( int i = 1; i <= N; i++ ) { // make N nodes
        node *pn = malloc( sizeof *pn ); // no casting, and sizeof tied to variable, not type
        // Omitting verification for brevity
        pn->no = i; // assign the value

        if( !pTail )
            pHead = pTail = pn; // first node
        else
            pTail = pTail->next = pn; // linking onto end
    }
    return pTail->next = pHead; // May the circle be unbroken!!
}

int killOff( int M, node *pn ) { // NB: function name tells all

    while( pn->next != pn ) { // until only "self" remains
        for( int i = M; --i; ) pn = pn->next; // skip M nodes around circle
        node *del = pn;
        pn->next = pn->next->next; // dead man walking in exile now
        free( del ); // bye bye
    }
    return pn->no; // survivors ID
}

int main( void ) {
    int M = 3, N = 17; // constants

    node *head = create( N ); // simple, right?

    printf( "Survivor: %d\n", killOff( M, head ) ); // simpler, too!

    free( head ); // kill off the last of them

    return 0; // and good night
}

你可能会因冗长的废话而毫无计划地让自己陷入困境。

警告：

M

向下计数可能会减少一。将

--i

更改为

i--

以适合您对围绕不断收缩的节点环行进多远的解释。