时间戳

首页 > 解决方案 > C lang“过滤器映射”实现免费

c - C lang“过滤器映射”实现免费

问题描述

我正在尝试编写非常简单的函数来更新链表的元素，同时过滤掉（和释放）一些元素。我已经能够推导出这个实现，尽管根据 valgrind 它包含无效的免费以及内存泄漏。我想知道实施有什么问题。

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

typedef struct List {
  int head;
  struct List *tail;
} List;

List *cons(int h, List *tail)
{
  List *list = malloc(sizeof(List));
  list->head = h;
  list->tail = (struct List*) tail;

  return list;
}

bool is_odd(int val)
{
  return val % 2 != 0;
}

int square(int val)
{
  return val * val;
}

void print_list(List *l)
{
  while (l) {
    printf("item: %d, ", l->head);
    l = (List*) l->tail;
  }

  printf("\n");
}

List *square_odd(List *list)
{
  List *new_head = NULL;
  List *prev_head = NULL;

  while (list != NULL) {
    List *next = (List *) list->tail;
    if (is_odd(list->head)) {
      if (new_head == NULL) new_head = list;
      if (prev_head != NULL) prev_head->tail = (struct List*) list;
      list->head = square(list->head);
      prev_head = list;
    } else {
      if (next == NULL) {
        prev_head->tail = NULL;
      }
      free(list);
    }

    list = next;
  }

  return new_head;
}

int main()
{
  List *t = NULL;
  List init = {100, NULL};
  t = &init;
  t = cons(1, t);
  t = cons(2, t);
  t = cons(3, t);
  t = cons(4, t);
  t = cons(5, t);
  t = cons(6, t);
  t = cons(7, t);
  t = cons(8, t);

  t = square_odd(t);

  List *tmp = NULL;
  print_list(t);

  while(t->tail != NULL) {
    tmp = t;
    t = (List*) t->tail;
    if (tmp != NULL) free(tmp);
  }

  return 0;
}

valgrind 输出为：

==17692== Memcheck, a memory error detector
==17692== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==17692== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==17692== Command: ./main
==17692== 
==17692== Invalid free() / delete / delete[] / realloc()
==17692==    at 0x4835948: free (in /nix/store/wrj8cjkfqzi0qlwnigx8vxwyyfl01lqq-valgrind-3.15.0/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==17692==    by 0x40127D: square_odd (in /tmp/linked/main)
==17692==    by 0x401371: main (in /tmp/linked/main)
==17692==  Address 0x1ffeffeac0 is on thread 1's stack
==17692==  in frame #2, created by main (???:)
==17692== 
item: 49, item: 25, item: 9, item: 1, 
==17692== 
==17692== HEAP SUMMARY:
==17692==     in use at exit: 16 bytes in 1 blocks
==17692==   total heap usage: 9 allocs, 9 frees, 1,152 bytes allocated
==17692== 
==17692== LEAK SUMMARY:
==17692==    definitely lost: 16 bytes in 1 blocks
==17692==    indirectly lost: 0 bytes in 0 blocks
==17692==      possibly lost: 0 bytes in 0 blocks
==17692==    still reachable: 0 bytes in 0 blocks
==17692==         suppressed: 0 bytes in 0 blocks
==17692== Rerun with --leak-check=full to see details of leaked memory
==17692== 
==17692== For lists of detected and suppressed errors, rerun with: -s
==17692== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

标签： calgorithmdata-structuresmemory-managementlinked-list

解决方案

实施有什么问题。

您正在传递initto的地址free。init是一个没有分配自动存储持续时间的变量malloc，所以你不能free。

因为最初t = &init，那么里面第一次打电话给cons你做new_t->tail = t你有效的事new_t->tail = &init。因此，在所有cons调用之后，链中的最后一个元素指向&init.

 t->tail-> ... ->tail->tail == &init

在你的循环中，然后你将地址传递&init给free函数。

我会说实现实际上是可以的，第一个元素的分配是错误的。

我建议，只需删除init并创建第一个链malloc：

int main() {
   List *t = cons(100, NULL);
   t = cons(1, t);
   // the rest unchanged

free(NULL)什么也没做。您可以替换if (tmp != NULL) free(tmp);为free(tmp).

推荐阅读