释放我仍然需要的内存，链表

Question

所以我正在做这个作业，作为规则的一部分，在 helpers 中额外定义的任何东西都需要在最后释放。问题是：取一个目标空链表，取 2 个已经排序的链表，并将这两个链表与它们已经存在的地址合并到目标链表中，我不允许定义新节点。这就是我的

void llmrg(struct llist *dest, struct llist *src1, struct llist *src2)
{
    struct llnode *tempdest = dest->front;
    struct llnode *tempsrc;

    while (src1->front != NULL || src2->front != NULL)
    {
        if (src2->front == NULL)
        {
            tempdest->next = src1->front;
            src1->front = NULL;
        }
        else if (src1->front == NULL)
        {
            tempdest->next = src2->front;
            src2->front = NULL;
        }
        else
        {
            if ((src2->front == NULL) || (src1->front->item < src2->front->item))
            {
                tempsrc = src1->front->next;
                if (dest->front != NULL)
                {
                    tempdest->next = src1->front;
                    tempdest = tempdest->next;
                }
                else
                {
                    dest->front = src1->front;
                    tempdest = dest->front;
                }
                src1->front->next = NULL;
                src1->front = tempsrc;
            }
            else
            {
                tempsrc = src2->front->next;
                if (dest->front != NULL)
                {
                    tempdest->next = src2->front;
                    tempdest = tempdest->next;
                }
                else
                {
                    dest->front = src2->front;
                    tempdest = dest->front;
                }
                src2->front->next = NULL;
                src2->front = tempsrc;
            }
        }
    }
    free(tempsrc);
    free(tempdest);
}

所以现在我的问题是，如果我不执行 'free' 语句，一切正常，但不允许我这样做，但如果我释放 'tempdest'（释放'tempsrc' 不会导致问题），然后其中 1 个值消失，因为它仍然使用 tempdest 存储。

因此，如果我的列表是 (1,3,5) 和 (2,4,6)，结果应该是 (1,2,3,4,5,6)，并且无需释放即可运行, 但是随着免费我得到（1,2,3,4,0,6）。

另外数据结构是：

struct llnode { int item; struct llnode *next; };
struct llist { struct llnode *front; };

我所说的释放并不是指链表，那些显然正在被使用。我的意思是我为了解决这个问题而创建的 2 个指针，tempdest 和 tempsrc——它们需要被释放。

有人可以帮助我以某种方式释放 tempdest 并保留值 5 吗？

Answer 1

您将需要更多的临时变量来存储指向您当前所在的每个输入列表的节点节点的指针。

For the lazy

Answer 2

I mean the 2 pointers, tempdest and tempsrc, that I created for the sake of solving this question — those need to be freed.

不，他们没有。您不释放指针，而是释放使用 malloc 分配的内存块。您的函数没有 malloc 任何内存，因此它与 free.

无关

Answer 3

正如我在评论中指出的那样，

Why do you need to free anything? When you merge the two lists, each item in each of the lists should be in the result list, so none of the items should be freed.

因为你有一个 'list head' 结构 (struct llist)，你必须设置传递给 llmrg() 的两个旧列表头结构，这样它们就不再指向任何东西.

You're not 'allowed' to free either tempsrc or tempdest because they are not allocated by your code. They are merely temporary pointers to items in the list. If you free either of them, you will break things. Please get valgrind if at all possible and use it. It will help you see the error of your ways. By the end of the merge function, you need to ensure that src1->front is a null pointer, and that src2->front is a null pointer. But that's all. There's still nothing to free.

这是将您的代码改编成测试工具。请注意，此代码中的任何地方都没有调用 malloc()，因此也不需要在任何地方调用 free()。这主要是为了说明这一点，而不是因为您会在真正的代码中使用非动态内存分配（但您没有显示列表创建代码，并且以这种方式做事也避免了编写它）。

#include <stdio.h>

struct llnode { int item; struct llnode *next; };
struct llist { struct llnode *front; };

static
void llmrg(struct llist *dest, struct llist *src1, struct llist *src2)
{
    struct llnode *tempdest = dest->front;
    struct llnode *tempsrc;

    while (src1->front != NULL || src2->front != NULL)
    {
        if (src2->front == NULL)
        {
            tempdest->next = src1->front;
            src1->front = NULL;
        }
        else if (src1->front == NULL)
        {
            tempdest->next = src2->front;
            src2->front = NULL;
        }
        else
        {
            if ((src2->front == NULL) || (src1->front->item < src2->front->item))
            {
                tempsrc = src1->front->next;
                if (dest->front != NULL)
                {
                    tempdest->next = src1->front;
                    tempdest = tempdest->next;
                }
                else
                {
                    dest->front = src1->front;
                    tempdest = dest->front;
                }
                src1->front->next = NULL;
                src1->front = tempsrc;
            }
            else
            {
                tempsrc = src2->front->next;
                if (dest->front != NULL)
                {
                    tempdest->next = src2->front;
                    tempdest = tempdest->next;
                }
                else
                {
                    dest->front = src2->front;
                    tempdest = dest->front;
                }
                src2->front->next = NULL;
                src2->front = tempsrc;
            }
        }
    }
    src1->front = NULL;
    src2->front = NULL;
}

static void print_llist(const char *tag, struct llist *list)
{
    printf("%s:", tag);
    struct llnode *node = list->front;
    while (node != 0)
    {
        printf(" %d", node->item);
        node = node->next;
    }
    putchar('\n');
}

int main(void)
{
    struct llnode data[] =
    {
        { 1, &data[1] }, { 3, &data[2] }, { 5, 0 },
        { 2, &data[4] }, { 4, &data[5] }, { 6, 0 }
    };
    struct llist ll1 = { &data[0] };
    struct llist ll2 = { &data[3] };
    struct llist ll3 = { 0 };
    printf("Before:\n");
    print_llist("ll1", &ll1);
    print_llist("ll2", &ll2);
    print_llist("ll3", &ll3);

    llmrg(&ll3, &ll1, &ll2);

    printf("After:\n");
    print_llist("ll1", &ll1);
    print_llist("ll2", &ll2);
    print_llist("ll3", &ll3);

    return 0;
}

我在 llmrg() 函数的末尾添加了两个赋值来代替您的两个 free() 调用。我不确定它们是否有必要，但它们确实可以完成这项工作。显然，如果列表结构或节点结构是动态分配的，则需要释放它们，但不需要在 llmrg() 代码中释放。

示例输出：

Before:
ll1: 1 3 5
ll2: 2 4 6
ll3:
After:
ll1:
ll2:
ll3: 1 2 3 4 5 6

请注意，您可以大大简化合并功能 — 减少 25 行代码。（通常更容易使小函数正确并保持正确。但是，使用 struct llnode **dest 无疑是微妙的，尽管它很有效。）当代码包含 &(*dest)->next 时，这等同于 &((*dest)->next) — *dest指向的next指针的地址。

#include <assert.h>
#include <stdio.h>

struct llnode { int item; struct llnode *next; };
struct llist { struct llnode *front; };

static
void llmrg(struct llist *dst0, struct llist *src1, struct llist *src2)
{
    struct llnode *node1 =  src1->front;
    struct llnode *node2 =  src2->front;
    struct llnode **dest = &dst0->front;

    src1->front = NULL;
    src2->front = NULL;

    while (node1 != NULL && node2 != NULL)
    {
        if (node1->item < node2->item)
        {
            *dest = node1;
            node1 = node1->next;
        }
        else
        {
            *dest = node2;
            node2 = node2->next;
        }
        dest = &(*dest)->next;
    }

    if (node1 != NULL)
        *dest = node1;
    if (node2 != NULL)
        *dest = node2;
}

static void print_llist(const char *tag, struct llist *list)
{
    printf("%s:", tag);
    struct llnode *node = list->front;
    while (node != 0)
    {
        printf(" %d", node->item);
        node = node->next;
    }
    putchar('\n');
}

int main(void)
{
    struct llnode data[] =
    {
        { 2, &data[1] }, { 3, &data[2] }, { 5, 0 },
        { 1, &data[4] }, { 4, &data[5] }, { 6, &data[6] }, { 8, 0 },
    };
    struct llist ll1 = { &data[0] };
    struct llist ll2 = { &data[3] };
    struct llist ll3 = { 0 };

    printf("Before:\n");
    print_llist("ll1", &ll1);
    print_llist("ll2", &ll2);
    print_llist("ll3", &ll3);

    llmrg(&ll3, &ll1, &ll2);

    printf("After:\n");
    print_llist("ll1", &ll1);
    print_llist("ll2", &ll2);
    print_llist("ll3", &ll3);

    return 0;
}

测试数据略有不同；它会像处理此数据一样愉快地处理原始数据。

示例输出：

Before:
ll1: 2 3 5
ll2: 1 4 6 8
ll3:
After:
ll1:
ll2:
ll3: 1 2 3 4 5 6 8

Answer 4

无需释放 tempsrc 或 tempdst。这些指针尚未分配任何内存，而只是指向您已经拥有和需要的内存（列表中的 llnodes）。你实际上不需要释放任何东西。您的情况与此类似：

int* someInts = malloc(sizeof(int) * 10); // allocates memory for 10 ints

int* tempInt = &someInt[5]; // points to the 5th int someInts, no new memory allocated 

//free(tempInt);
//There is no need to free this as it is just a pointer
//to some memory already "owned" by someInts

free(someInts);
//Freeing this pointer frees all the memory allocated in the first line.

释放我仍然需要的内存，链表

Issue freeing memory that I still need, linked list

c

free

memory-management

linked-list

data-structures