c - 链表 : Pointer being freed was not allocated

Question

我正在使用 C 语言研究 Segdwick 的算法，并尝试动态链表数组。我在 main 的 return 0 处遇到段错误。我的重点是正确加载和打印链接列表，完成后我没有释放列表数组。

所以我添加了 freeList 函数，现在得到 pointer being freed was not allocated。显然，我缺少指针/取消引用的细微差别。有什么建议吗？

lldb 运行:

a.out(3057,0x7fffb470c380) malloc: *** error for object 0x100300470: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
44Process 3057 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGABRT
    frame #0: 0x00007fff7c22cb6e libsystem_kernel.dylib`__pthread_kill + 10
libsystem_kernel.dylib`__pthread_kill:
->  0x7fff7c22cb6e <+10>: jae    0x7fff7c22cb78            ; <+20>
    0x7fff7c22cb70 <+12>: movq   %rax, %rdi
    0x7fff7c22cb73 <+15>: jmp    0x7fff7c223b00            ; cerror_nocancel
    0x7fff7c22cb78 <+20>: retq
Target 0: (a.out) stopped.

运行a.out:

a.out(3061,0x7fffb470c380) malloc: *** error for object 0x7fbac1c02970: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
44Abort trap: 6

代码:

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

#define maxV 13

struct node {
    int v; // vertex number
    struct node *next;
};

// load array of linked lists

static void load_adjlist_array(struct node ***adj){
    // load adjacency array
    int j,x,y,V,E;
    struct node *t;
    int idx[maxV]; // vertex location on adjacency matrix

    // ALL edges, single way (combinations)
    char v1[maxV] = {'A','A','A','L','J','J','J','E','F','H','F','A','G'};
    char v2[maxV] = {'G','B','C','M','M','L','K','D','D','I','E','F','E'};

    V = maxV; // number of vertices
    E = maxV; // number of edges

    // setup vertex positions in linked list
    for (j=0;j<V;j++) idx[j] = j;
    // setup head for each vertex (vertex connected to NULL by default)
    for (j=0;j<V;j++){
      t = (struct node *) malloc(sizeof *t); // pointer to allocated node memory
      if(t!= NULL){
        t->v    = j;
        t->next = NULL;
        adj[j] = &t;
      } else return;
    }

    // for each edge ('AB'), update the relevant linked list: add node to head of that vertex's list
    for (j=0;j<E;j++) {
        // edge xy: vertex numbers (also positions in idx)
        x = idx[v1[j]-'A'];
        y = idx[v2[j]-'A'];
        // load x data into t, then add t to y's adj list
        //printf("handling %c\n",v1[j]);
        t = (struct node *) malloc(sizeof *t);
        if(t!=NULL){
          t->v = x;
          t->next = *adj[y];
          *adj[y] = t;
        } else return;
        // add y to x's adj list
        //printf("handling %c\n",v2[j]);
        t = (struct node *) malloc(sizeof *t);
        if(t!=NULL){
          t->v = y;
          t->next = *adj[x];
          *adj[x] = t;
        } else return;
    }

    printf("load_adjlist_array completed\n");
}


static void freeList(struct node* head)
{
   struct node* tmp;
   printf("\n");
   while (head != NULL)
    {
       tmp = head;
       head = head->next;
       printf("%d",head->v);
       free(tmp);
    }

}

int main(){

  int j;
  struct node **adj; // pointers to adjacency list
  adj = malloc(maxV * sizeof(struct node *));  // allocates pointers to linked lists
  if (adj==NULL) return -1;

  load_adjlist_array(&adj); // allocates memory to linked lists in adj

  for (j=0;j<maxV;j++){
    freeList(adj[j]);
  }
  free(adj);

  return 0 ;
}

Answer 1

切勿使用三重星指针(例如 struct node ***adj)。它们几乎总是会产生不好的/不可读的结果。有更清洁的替代方法。在这里，双星可能就是您想要的。

如 MFisherKDX 所述，执行 adj[j] = &t; 是将基于堆栈的指针变量 t 的地址保存到数组中，而不是 t 指向。要解决此问题，函数参数必须使用struct node **adj

---

这是您的代码的一个版本。您的原始代码 [that needs to be changed] 包装如下:

#if 0
// original code
#else
// fixed code
#endif

这是您的代码已修复(旁注:不要强制转换 malloc 的返回值)。另外，请注意原始 freeList 中的 printf 会取消引用空指针，因此我修复了 [没有 #if 0 配对]:

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

#define maxV 13

struct node {
    int v;                              // vertex number
    struct node *next;
};

// load array of linked lists

static void
#if 0
load_adjlist_array(struct node ***adj)
#else
load_adjlist_array(struct node **adj)
#endif
{
    // load adjacency array
    int j,
     x,
     y,
     V,
     E;
    struct node *t;
    int idx[maxV];                      // vertex location on adjacency matrix

    // ALL edges, single way (combinations)
    char v1[maxV] = { 'A', 'A', 'A', 'L', 'J', 'J', 'J', 'E', 'F', 'H', 'F', 'A', 'G' };
    char v2[maxV] = { 'G', 'B', 'C', 'M', 'M', 'L', 'K', 'D', 'D', 'I', 'E', 'F', 'E' };

    V = maxV;                           // number of vertices
    E = maxV;                           // number of edges

    // setup vertex positions in linked list
    for (j = 0; j < V; j++)
        idx[j] = j;
    // setup head for each vertex (vertex connected to NULL by default)
    for (j = 0; j < V; j++) {
        t = (struct node *) malloc(sizeof *t);  // pointer to allocated node memory
        if (t != NULL) {
            t->v = j;
            t->next = NULL;
#if 0
            adj[j] = &t;
#else
            adj[j] = t;
#endif
        }
        else
            return;
    }

    // for each edge ('AB'), update the relevant linked list: add node to head of that vertex's list
    for (j = 0; j < E; j++) {
        // edge xy: vertex numbers (also positions in idx)
        x = idx[v1[j] - 'A'];
        y = idx[v2[j] - 'A'];
        // load x data into t, then add t to y's adj list
        // printf("handling %c\n",v1[j]);
        t = (struct node *) malloc(sizeof *t);
        if (t != NULL) {
            t->v = x;
#if 0
            t->next = *adj[y];
#else
            t->next = adj[y];
#endif
#if 0
            *adj[y] = t;
#else
            adj[y] = t;
#endif
        }
        else
            return;
        // add y to x's adj list
        // printf("handling %c\n",v2[j]);
        t = (struct node *) malloc(sizeof *t);
        if (t != NULL) {
            t->v = y;
#if 0
            t->next = *adj[x];
#else
            t->next = adj[x];
#endif
#if 0
            *adj[x] = t;
#else
            adj[x] = t;
#endif
        }
        else
            return;
    }

    printf("load_adjlist_array completed\n");
}

static void
freeList(struct node *head)
{
    struct node *tmp;

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

}

int
main()
{

    int j;
#if 0
    struct node **adj;                  // pointers to adjacency list
#else
    struct node **adj;                  // pointers to adjacency list
#endif

    adj = malloc(maxV * sizeof(struct node *)); // allocates pointers to linked lists
    if (adj == NULL)
        return -1;

#if 0
    load_adjlist_array(&adj);           // allocates memory to linked lists in adj
#else
    load_adjlist_array(adj);            // allocates memory to linked lists in adj
#endif

    for (j = 0; j < maxV; j++) {
        freeList(adj[j]);
    }
    free(adj);

    return 0;
}

---

这是一个清理后的版本:

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

#define maxV 13

struct node {
    int v;                              // vertex number
    struct node *next;
};

// load array of linked lists

static void
load_adjlist_array(struct node **adj)
{
    // load adjacency array
    int j,
     x,
     y,
     V,
     E;
    struct node *t;
    int idx[maxV];                      // vertex location on adjacency matrix

    // ALL edges, single way (combinations)
    char v1[maxV] = { 'A', 'A', 'A', 'L', 'J', 'J', 'J', 'E', 'F', 'H', 'F', 'A', 'G' };
    char v2[maxV] = { 'G', 'B', 'C', 'M', 'M', 'L', 'K', 'D', 'D', 'I', 'E', 'F', 'E' };

    V = maxV;                           // number of vertices
    E = maxV;                           // number of edges

    // setup vertex positions in linked list
    for (j = 0; j < V; j++)
        idx[j] = j;
    // setup head for each vertex (vertex connected to NULL by default)
    for (j = 0; j < V; j++) {
        t = malloc(sizeof *t);  // pointer to allocated node memory
        if (t != NULL) {
            t->v = j;
            t->next = NULL;
            adj[j] = t;
        }
        else
            return;
    }

    // for each edge ('AB'), update the relevant linked list: add node to head of that vertex's list
    for (j = 0; j < E; j++) {
        // edge xy: vertex numbers (also positions in idx)
        x = idx[v1[j] - 'A'];
        y = idx[v2[j] - 'A'];
        // load x data into t, then add t to y's adj list
        // printf("handling %c\n",v1[j]);
        t = malloc(sizeof *t);
        if (t != NULL) {
            t->v = x;
            t->next = adj[y];
            adj[y] = t;
        }
        else
            return;
        // add y to x's adj list
        // printf("handling %c\n",v2[j]);
        t = malloc(sizeof *t);
        if (t != NULL) {
            t->v = y;
            t->next = adj[x];
            adj[x] = t;
        }
        else
            return;
    }

    printf("load_adjlist_array completed\n");
}

static void
freeList(struct node *head)
{
    struct node *tmp;

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

}

int
main()
{

    int j;
    struct node **adj;                  // pointers to adjacency list

    // allocates pointers to linked lists
    adj = malloc(maxV * sizeof(struct node *));
    if (adj == NULL)
        return -1;

    load_adjlist_array(adj);            // allocates memory to linked lists in adj

    for (j = 0; j < maxV; j++) {
        freeList(adj[j]);
    }
    free(adj);

    return 0;
}

---

这里是固定程序的输出:

load_adjlist_array completed

52160
01
02
543
6534
0435
406
87
78
1011129
910
91211
91112