关于约瑟夫环问题

土沙拉

//n个人围圈报数，报m出列，最后剩下的是几号？
#include <stdio.h>
#include <stdlib.h>

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

node *create(int n)
{
        node *p = NULL, *head;
        head = (node*)malloc(sizeof (node ));
        p = head;
        node *s;
        int i = 1;

        if( 0 != n )
        {
                while( i <= n )
                {
                        s = (node *)malloc(sizeof (node));
                        s->data = i++;    // 为循环链表初始化，第一个结点为1，第二个结点为2。
                        p->next = s;
                        p = s;
                }
                s->next = head->next;
        }

        free(head);

        return s->next ;
}

int main()
{
        int n = 41;
        int m = 3;
        int i;
        node *p = create(n);
        node *temp;

        m %= n;   // m在这里是等于2

        while (p != p->next )
        {
                for (i = 1; i < m-1; i++)
                {
                        p = p->next ;
                }

                printf("%d->", p->next->data );

                temp = p->next ;                                //删除第m个节点
                p->next = temp->next ;
                free(temp);

                p = p->next ;
        }

        printf("%d\n", p->data );

        return 0;
}


p->next = temp->next 这里为什不可以写成p=temp？问题在哪里？望大神解答谢谢

人造人

要问 为什不可以写成p=temp，先得明白 p->next 与 p 有什么区别？

土沙拉

人造人 发表于 2018-2-7 18:51
要问 为什不可以写成p=temp，先得明白 p->next 与 p 有什么区别？

那您说说？我的理解是p->next是p指向的下一个地址

人造人

土沙拉 发表于 2018-2-7 19:21
那您说说？我的理解是p->next是p指向的下一个地址

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

typedef struct Test_tag
{
        int num;
        struct Test_tag *next;
} Test;

int main(void)
{
        Test *head = malloc(sizeof(Test));
        Test *n1 = malloc(sizeof(Test));
        Test *n2 = malloc(sizeof(Test));
        Test *n3 = malloc(sizeof(Test));

        head->num = 0;
        head->next = n1;

        n1->num = 1;
        n1->next = n2;

        n2->num = 2;
        n2->next = n3;

        n3->num = 3;
        n3->next = NULL;

        printf("head:      : 0x%.8X\n", (unsigned int)head);
        printf("head->num  : 0x%.8X\n", (unsigned int)head->num);
        printf("head->next : 0x%.8X\n", (unsigned int)head->next);

        printf("n1         : 0x%.8X\n", (unsigned int)n1);
        printf("n1->num    : 0x%.8X\n", (unsigned int)n1->num);
        printf("n1->next   : 0x%.8X\n", (unsigned int)n1->next);

        printf("n2         : 0x%.8X\n", (unsigned int)n2);
        printf("n2->num    : 0x%.8X\n", (unsigned int)n2->num);
        printf("n2->next   : 0x%.8X\n", (unsigned int)n2->next);

        printf("n3         : 0x%.8X\n", (unsigned int)n3);
        printf("n3->num    : 0x%.8X\n", (unsigned int)n3->num);
        printf("n3->next   : 0x%.8X\n", (unsigned int)n3->next);


        
        Test *p;
        Test *temp;

        p = head;
        while(p != NULL)
        {
                printf("%d ", p->num);
                p = p->next;
        }
        printf("\n");

#if 1
        // 删除 n2
        p = n1;
        temp = p->next;
        p->next = temp->next;
        free(temp);
#else
        // 删除 n2
        p = n1;
        temp = p->next;
        p = temp->next;
        free(temp);
#endif

        printf("head:      : 0x%.8X\n", (unsigned int)head);
        printf("head->num  : 0x%.8X\n", (unsigned int)head->num);
        printf("head->next : 0x%.8X\n", (unsigned int)head->next);

        printf("n1         : 0x%.8X\n", (unsigned int)n1);
        printf("n1->num    : 0x%.8X\n", (unsigned int)n1->num);
        printf("n1->next   : 0x%.8X\n", (unsigned int)n1->next);

        printf("n2         : 0x%.8X\n", (unsigned int)n2);
        printf("n2->num    : 0x%.8X\n", (unsigned int)n2->num);
        printf("n2->next   : 0x%.8X\n", (unsigned int)n2->next);

        printf("n3         : 0x%.8X\n", (unsigned int)n3);
        printf("n3->num    : 0x%.8X\n", (unsigned int)n3->num);
        printf("n3->next   : 0x%.8X\n", (unsigned int)n3->next);


        p = head;
        while(p != NULL)
        {
                printf("%d ", p->num);
                p = p->next;
        }
        printf("\n");

        return 0;
}

#if 1

head:      : 0x004861E0
head->num  : 0x00000000
head->next : 0x00486218
n1         : 0x00486218
n1->num    : 0x00000001
n1->next   : 0x00486080
n2         : 0x00486080
n2->num    : 0x00000002
n2->next   : 0x004860B8
n3         : 0x004860B8
n3->num    : 0x00000003
n3->next   : 0x00000000
0 1 2 3
head:      : 0x004861E0
head->num  : 0x00000000
head->next : 0x00486218
n1         : 0x00486218
n1->num    : 0x00000001
n1->next   : 0x004860B8
n2         : 0x00486080
n2->num    : 0xDDDDDDDD
n2->next   : 0xDDDDDDDD
n3         : 0x004860B8
n3->num    : 0x00000003
n3->next   : 0x00000000
0 1 3
请按任意键继续. . .

#if 0

head:      : 0x010061E0
head->num  : 0x00000000
head->next : 0x01006218
n1         : 0x01006218
n1->num    : 0x00000001
n1->next   : 0x01006080
n2         : 0x01006080
n2->num    : 0x00000002
n2->next   : 0x010060B8
n3         : 0x010060B8
n3->num    : 0x00000003
n3->next   : 0x00000000
0 1 2 3
head:      : 0x010061E0
head->num  : 0x00000000
head->next : 0x01006218
n1         : 0x01006218
n1->num    : 0x00000001
n1->next   : 0x01006080
n2         : 0x01006080
n2->num    : 0xDDDDDDDD
n2->next   : 0xDDDDDDDD
n3         : 0x010060B8
n3->num    : 0x00000003
n3->next   : 0x00000000
0 1 -572662307 请按任意键继续. . .

土沙拉

qq1242009750

                for (i = 1; i < m-1; i++)
                {
                        p = p->next ;
                }                  //  执行完for语句后走了m-1个节点

                printf("%d->", p->next->data );      //把第M个节点的值输出 也就是当前结点的下一个节点的值

                temp = p->next ;                                //把第m个节点给temp
                p->next = temp->next ;                    //把第M个节点的位置改变成第M+1一个节点
                free(temp);                                       //删除第M个节点