[已解决]小甲鱼数据结构第18讲约瑟夫环问题

扶苏Gisele

为什么 第58行的 free释放 有跟没有对代码没有影响
还有为什么第57行p->next=temp->next和第60行的p=p->next不能整合优化成p=temp->next

源码如下
#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 = 6;
        int m = 3;
        int i;
        node *p = create(n);
        node *temp;

        m %= n;   // m在这里是等于3
        printf("%d\n",n);

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

最佳答案

月排行榜 / 总排行榜

FayeHao

2020-5-12 22:11:01

扶苏Gisele 发表于 2020-5-12 20:39
额最近在肝数据结构的栈没看贴不好意思。
1：比如建立上面那个约瑟夫环1、2、3、4、5、6，每3个输出，输 ...

1. free和链表的删除无关，链表中的删除结点操作使得该结点脱离链表但其内存空间中依然保留有原数据，会作为碎片一直占据内存。而free的作用就是将该内存空间内容进行清零，并告诉内存我现在是自由身了，可以让我干其他活了。

2. 56和57行的程序就是链表的删除操作，结点2的指向从结点3更改为了结点4，同时暗含了链表的长度减少了1。这个减少不是由free导致的，而就是56和57两行语句决定的

3. 60行的语句含义与56和57行的含义不同，你所谓的优化其实是可以的，但容易出现概念上的混乱。我运行了并没有出错。

跳转到最佳答案楼层

扶苏Gisele

FayeHao

回答1：free释放的是一个内存空间而已，和程序执行结果无关。就比如儿童时期留下的旧衣服虽然不再拿出来穿了(删除的结点)，但还可以存放在储衣柜中(依然占据内存空间)，对你最后选择穿哪件衣服出门(程序执行结果)无关。free的作用就是把不穿的旧衣服给扔掉，给储衣柜留出新的空间来存放新衣服。

回答2：个人认为你这样的想法没有问题，或者p=p->next->next也可以(还省略了temp呢)。不过小甲鱼这样写的好处在于可以释放掉一个链表结点，也就是将一个链表不再使用的内存空间还给内存。虽然说如今的内存空间都特别的大，但是大家编程都不节省内存的话，那么多少G的内存也是不够用的。(如果一个游戏不节省空间，整体大小达到1个T，那将会劝退多少玩家)

扶苏Gisele

FayeHao 发表于 2020-5-10 09:21
回答1：free释放的是一个内存空间而已，和程序执行结果无关。就比如儿童时期留下的旧衣服虽然不再拿出来穿 ...

额最近在肝数据结构的栈没看贴不好意思。
1：比如建立上面那个约瑟夫环1、2、3、4、5、6，每3个输出，输出应该是3、6、4、2、5、1，其实我原本的理解是free掉3、6之后循环遍历一次就是正常输出4，根据你的回答之后我又有点不清楚了，为什么它循环之后会自动跳过3而读取4呢？
2：不知道你那边优化之后是什么样子，你的想法跟我一样的话，优化之后的代码在我这边运行会出错，所以emmmmm
感谢

扶苏Gisele

搞不懂，有没有大神解答一下

扶苏Gisele

原本我以为free释放3和6之后遍历才能读取4，没有free释放环节的话应该会进入3、6、3、6...这样的读取循环的

FayeHao

扶苏Gisele 发表于 2020-5-12 20:39
额最近在肝数据结构的栈没看贴不好意思。
1：比如建立上面那个约瑟夫环1、2、3、4、5、6，每3个输出，输 ...

1. free和链表的删除无关，链表中的删除结点操作使得该结点脱离链表但其内存空间中依然保留有原数据，会作为碎片一直占据内存。而free的作用就是将该内存空间内容进行清零，并告诉内存我现在是自由身了，可以让我干其他活了。

2. 56和57行的程序就是链表的删除操作，结点2的指向从结点3更改为了结点4，同时暗含了链表的长度减少了1。这个减少不是由free导致的，而就是56和57两行语句决定的

3. 60行的语句含义与56和57行的含义不同，你所谓的优化其实是可以的，但容易出现概念上的混乱。我运行了并没有出错。

FayeHao

FayeHao 发表于 2020-5-10 09:21
回答1：free释放的是一个内存空间而已，和程序执行结果无关。就比如儿童时期留下的旧衣服虽然不再拿出来穿 ...

我写错了，不是p=p->next->next，而是p->next=p->next->next

扶苏Gisele

FayeHao 发表于 2020-5-12 22:11
1. free和链表的删除无关，链表中的删除结点操作使得该结点脱离链表但其内存空间中依然保留有原数据，会 ...

oooooooook懂了

QAQ学习鸭

扶苏Gisele 发表于 2020-5-9 01:03

太感谢了，我说的代码咋不对，看了你的我才发现问题