1

我正在编写一个链表，它有一个节点结构和一个列表结构列表错误。

驱动程序.c

#include "target.h"



int main(int argc, char * argv[]){
  struct target_list * target = target_list_alloc("list");
  target_list_print(target);
  target_list_append(target, "G");
  target_list_append(target, "B");
  target_list_print(target);
  target_list_append(target, "S");  
  target_list_print(target);
  target_list_remove(target,"B");
  target_list_print(target);
  target_list_remove(target,"Bl");
  target_list_remove(target,"Br");
  target_list_print(target);
  target_list_append(target,"Ba"); //Here is the problem node
  target_list_print(target);
  return 0;
}

目标.h

#ifndef TARGET_H
#define TARGET_H


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

/*-----------------------------------------*/

extern char * prog;

/*-----------------------------------------*/

struct source_list{
  char * name;
};
struct recipe_list{
  char * name;
};

struct target_node{
  char * name;
  struct target_node * next;
  struct source_list * src_list;
  struct recipe_list * rec_list;
};

struct target_list{
  char * name;
  struct target_node * head;
  struct target_node * tail;
};

/*-----------------------------------------------------*/

void target_list_init(struct target_list * list, const char * targetname);
struct target_list * target_list_alloc(const char * targetname);
void target_list_deallocate(struct target_list * list);
void target_list_print(struct target_list * list);
void target_list_append(struct target_list * list, const char * nodename);
bool is_in_target_list(struct target_list * list, const char * nodename);
void target_list_remove(struct target_list * list, const char * nodename);

/*-----------------------------------------------------*/

#endif

目标.c

#include "target.h"

/*----------------------------------------------------------*/

//This function will initialize a new target_list with name targetname
//This function will assume that target_list is already allocated
void target_list_init(struct target_list * list, const char * targetname){
  verify(list != NULL, "null arg list");
  verify(targetname != NULL, "null arg targetname");
  verify(targetname[0] != '\0',"empty arg targetname");
  list->name = Strdup(targetname);
  list->head = list->tail = NULL;
}

/*----------------------------------------------------------*/

//This function will allocate a new target_list and return a pointer to it
struct target_list * target_list_alloc(const char * targetname){
  verify(targetname != NULL, "null arg targetname");
  verify(targetname[0] != '\0',"empty arg targetname");
  struct target_list * list = malloc(sizeof(struct target_list));
  list->name = Strdup(targetname);
  list->head = list->tail = NULL;
  return list;
}    

/*---------------------------------------------------------*/

//This function will deallocate a target_list
void target_list_deallocate(struct target_list * list){
  verify(list != NULL,"null arg list");
  free(list->name);
  struct target_node * prev = NULL;
  for(struct target_node * p = list->head; p != NULL; p= p->next){
    free(prev);
    free(p->name);
    prev = p;
  }
  free(prev);
  free(list);
}

/*----------------------------------------------------------*/

//This function will print a target_list 
void target_list_print(struct target_list * list){
  verify(list != NULL, "null arg list");
  printf("list of targets: %s\n",safe_string(list->name));
  if(list->head == NULL){
    printf("  <empty>\n");
  }
  else{
    for(struct target_node * p = list->head; p != NULL; p = p->next){
      printf("  %s\n",p->name);
    }
  }
}

/*-----------------------------------------------------------*/

//This function will append a new target_node onto target_list at the end of it
void target_list_append(struct target_list * list, const char * nodename){
  verify(list != NULL, "null arg list");
  verify(nodename != NULL, "null arg nodename");
  verify(nodename[0] != '\0', "empty arg nodename");

  struct target_node * new_node = malloc(sizeof(struct target_node));
  new_node->next = NULL;
  new_node->name = Strdup(nodename);
  new_node->src_list = NULL;
  new_node->rec_list = NULL;
  if(list->head == NULL){
    list->head = list->tail = new_node;
  }
  else{
    list->tail->next = new_node;
    list->tail = new_node;
  }
}

/*--------------------------------------------------------*/

//This function returns 1 if the nodename is already in the target_list and 0 if not
bool is_in_target_list(struct target_list * list, const char * nodename){
  verify(list != NULL, "null arg list");
  verify(nodename != NULL, "null arg nodename");
  verify(nodename[0] != '\0', "empty arg nodename");
  for(struct target_node * p = list->head; p != NULL; p = p->next){
    if(strcmp(nodename,p->name) == 0){
      return 1;
    }
  }
  return 0;
}

/*------------------------------------------------------*/

//This function removes a node with name nodename from target_list */
void target_list_remove(struct target_list * list, const char * nodename){
  verify(list != NULL, "null arg list");
  verify(nodename != NULL, "null arg nodename");
  verify(nodename[0] != '\0', "empty arg nodename");
  if(is_in_target_list(list,nodename)){
    struct target_node * prev = NULL;
    struct target_node * cur = list->head;
    while(cur != NULL){
      if(strcmp(cur->name,nodename) == 0){
    break;
      }
      prev = cur;
      cur = cur->next;
    }
    //case 1: removing head pointer
    if(cur == list->head){
      free(cur->name);
      free(cur->src_list);
      free(cur->rec_list);
      free(cur);
      list->head = NULL;
      list->tail = NULL;
      free(prev);
      cur = NULL;
      prev = NULL;
    }
    //case 2: removing tail pointer
    else if(cur == list->tail){
      free(cur->name);
      free(cur->src_list);
      free(cur->rec_list);
      free(cur);
      list->tail = prev;
      free(prev);
      prev = NULL;
      cur = NULL;
    }
    //case 3: removing a middle node
    else{
      prev->next = cur->next;
      free(cur->name);
      free(cur->src_list);
      free(cur->rec_list);
      free(cur);
      cur = NULL;
      free(prev);
      prev = NULL;
    }
  }
  else{
    fprintf(stderr,"%s: Error %s is not in %s, cannot remove it from %s\n",prog,nodename,list->name,list->name);
  }
} 

/*----------------------------------------------------*/

在 else where (verify,..) 定义了几个辅助函数，但它们不影响 malloc

编译：

gcc -Wall -Wextra -std=c99 -g -o test driver.c target.c cmpsc311.c
driver.c:5: warning: unused parameter ‘argc’
driver.c:5: warning: unused parameter ‘argv’

输出：

list of targets: list
  <empty>
list of targets: list
  G
  B
list of targets: list
  G
  B
  S
list of targets: list
  G
  S
[no name]: Error Bl is not in list, cannot remove it from list
[no name]: Error Br is not in list, cannot remove it from list
list of targets: list
  G
  S
list of targets: list
  Ba

运行gdb后查看列表，list->head,list->tail和new_node(ba)不知道为什么new_node在malloc ed时获取到list->head的地址

数据库：

78    struct target_node * new_node = malloc(sizeof(struct target_node));
4: new_node = (struct target_node *) 0x3a00000000
3: list->tail = (struct target_node *) 0x100100940
2: list->head = (struct target_node *) 0x1001008e0
1: list = (struct target_list *) 0x1001008b0
(gdb) n
79    new_node->next = NULL;
4: new_node = (struct target_node *) 0x1001008e0
3: list->tail = (struct target_node *) 0x100100940
2: list->head = (struct target_node *) 0x1001008e0
1: list = (struct target_list *) 0x1001008b0
(gdb) n

谁能告诉我这是为什么以及如何解决？谢谢

4

3 回答 3

1

你的target_list_remove()功能看起来很假。遍历列表后，prev指向要删除的元素（prev = cur;）并cur指向下一个，而prev应该指向要删除的元素之前的元素。

free()另外，您正在调用curand prev，但我的猜测是您只想删除一个元素。

修复您的指针并free()仅调用一次。

于 2012-04-19T05:16:36.943 回答
0

问题出在您的删除功能中。您正在调用free(prev)，因此在调用target_list_remove(target,"B");中列表的头部也被释放。然后分配器将重新使用存储以供您下次调用malloc. 您可以使用诸如valgrind之类的工具来调试此类内存问题。

于 2012-04-19T05:16:44.067 回答
0

当您在 target_list_remove 中删除“B”时，它会落入“ case 3: removing a middle node”，因为您的列表此时看起来像这样：

G -> B -> S

在该部分代码中，您从列表 ( prev->next = cur->next) 中删除 cur 节点并继续为当前节点释放资源。此时您的列表如下所示：

G -> S

...但是在释放 cur 节点之后，您继续释放 prev 节点（即列表头）并将其设置为 null。

当满足条件时附加“Ba”节点时，list->head == NULL它为真，因此将列表的头部和尾部设置为新的“Ba”节点。

于 2012-04-19T05:19:17.373 回答