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

问：

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

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;
    }
  }

现在我正在努力寻找约瑟夫斯排列后要重新定义的最后一个元素。我有这个：

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;
    }
}

c 指针链接循环列表约瑟夫斯

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->next;
        pn->next = del->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
}

你可以用空话和没有计划地让自己陷入困境。

注意：减少计数可能会减少 1。更改为适合您对围绕收缩的节点环行进多远的解释。M--ii--

编辑
经过仔细检查，我相信以下是一个更好的版本。（上面没有显示的更改。create()

int killOff( int M, node *pn ) {
    // the previous "victim" is #0 at the start of each iteration
    // So, the first iteration begins with 1; subsequent iterations with 0
    for( int i = 1; pn->next != pn; i = 0 ) {
        while( ++i < M ) pn = pn->next;
        node *del = pn->next;
        pn->next = pn->next->next;
        free( del );
    }
    int survivorID = pn->no;
    free( pn ); // Last "survivor" is free'd here, remembered only by "name."
    return survivorID;
}

int main( void ) {
    printf( "Survivor: %d\n", killOff( 3, create( 17 ) ) );

    return 0;
}

建议您在两个版本中添加尽可能多的“print debugging”语句...尝试使用“受限”打印语句，在两个版本的“循环”周围使用 M+4 节点。你会看到你的版本不是一个循环的LL...学习可能很艰难，但值得攀登所有可以攀登的山峰！干杯！:-)

1赞 Azizbek Sattorov 10/28/2023

谢谢伙计，它真的奏效了。我没有完全复制您的解决方案，而是比较了它们并找出了错误。再次感谢你

上一个：为什么访问我的哈希表的单元格会返回问号？

下一个：如何在 C 语言中释放 linkedlist 中动态分配的内存

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

Why circular list doesn't solve Josephus problem?

评论

评论