单链表结构插入/删除多个空闲

Question

看了这段代码太久了，我变得沮丧，失去了自己弄清楚它的任何机会:(任何人都可以告诉我我在哪里愚蠢？我只是不明白我在哪里双重释放或可能分配错误地（我必须这样做，但是是的）我不断收到 * glibc detectors * free(): invalid next size

我实际上释放的内容比我需要的多，还是我只是没有分配我需要的内容首先分配。--抱歉，缩进错误，无法让该编辑器正确缩进

我有结构：

typedef int boolean;
typedef char * String;

typedef struct {
    char name[30];
    long ID;
    char address[40];
    char city[20];
    int age;
}Employee;

typedef struct node {
   Employee *anEmployee;
   struct node *next;
}NODE;

typedef struct {
   NODE *head, *tail;
}SLL;

插入函数--SLL（单链表）

void insert(SLL *list, Employee e){
  printf("insert");

   NODE *temp, *current;

   temp = (NODE *)malloc(sizeof(NODE));
   assert(temp != NULL);

   temp -> anEmployee = (Employee *)malloc(sizeof(Employee *));
   assert(temp -> anEmployee != NULL);

   strcpy(temp -> anEmployee -> name, e.name); 

   temp -> anEmployee -> ID = e.ID;

   strcpy(temp -> anEmployee -> address, e.address); 

   strcpy(temp -> anEmployee -> city, e.city);

   temp -> anEmployee -> age = e.age;

 if (list -> head == NULL) {     /* list is empty */
  list -> head = list -> tail = temp;
  return;
   }
   else { // list is not empty
       list -> tail -> next = temp;
       list -> tail = temp;
          }
 }

在删除函数中删除和释放内存。

boolean delete(SLL *list, String str){
  printf("delete");
  NODE *temp, *temp2;
  if (list -> head == NULL) return FALSE;  // list is empty

temp = list -> head;

while ((temp != NULL) && (strcmp(temp -> anEmployee -> name , str) != 0))
   temp = temp -> next;

if (temp == NULL) return FALSE;  // str is not found in the list

// now temp points to the NODE with str in it.  Let us delete it
// from the list

    if ( list -> head == temp) { // temp points to the first NODE
       if (temp -> next == NULL) {  // temp points to the only NODE
           list -> head = list -> tail = NULL;
           free(temp -> anEmployee);
           free(temp);
           return TRUE;
     }
     // temp points to the first NODE but it is not the only NODE
     list -> head = temp -> next;
     free(temp -> anEmployee);
     free(temp);
     return TRUE;
  }

  if (temp -> next == NULL) {  // temp points to the last NODE
      temp = list -> head;
      temp2 = list -> head -> next;
      while(temp2 - > next != NULL){
        temp = temp->next;
        temp2 = temp2 ->next;
    }


       list -> tail = temp ;    
       list -> tail -> next = NULL;
       free(temp2 -> anEmployee);
       free(temp2);
       return TRUE;
  }
       // temp points to some NODE in the middle of the list
      temp2 = temp -> next;
 while(temp2 - > next != NULL){

    temp ->anEmployee = temp2 - > anEmployee // 
    temp = temp->next;
    temp2 = temp2 ->next;
}
    temp ->anEmployee = temp2 - > anEmployee

   list -> tail = temp ;    
   list -> tail -> next = NULL;
   free(temp2 -> anEmployee);
   free(temp2);
   return TRUE;
 }

Answer 1

首先，在 insert 中，您分配的内存

temp -> anEmployee = (Employee *)malloc(sizeof(Employee *));

仅分配足够的内存来容纳 Employee 指针，而不是整个 Employee代码>结构。您应该为 temp->anEmployee 分配一个大小为 sizeof(Employee) 的块。

您对 free 的调用就有意义。想要释放 someNode->anEmployee 和 someNode 以彻底清理单个节点占用的内存。

您可以按如下方式简化 delete 实现：

boolean delete(SLL* list, String str)
{
    NODE* temp = list->head, *prev = NULL;
    while(temp != NULL && strcmp(temp->name, str) != 0) {
        prev = temp;
        temp = temp->next;
    }
    if(temp == NULL)
        return FALSE;

    if(prev != NULL)
        prev->next = temp->next;

    if(list->head == temp)
        list->head = temp->next;

    if(list->tail == temp)
        list->tail = temp->next;

    free(temp->anEmployee);
    free(temp);
    return TRUE;
}

通过跟踪查找之前的节点（如果有），您可以避免所有令人讨厌的特殊情况，并将核心列表更新减少为三个简单的条件分配。

Answer 2

没有读完所有内容，delete 的第一行应该做什么？

  NODE *temp, *temp2; // temp is uninitialized

    if ( list -> head == temp) { // temp points to the first NODE

我不知道 delete 应该删除什么。看来 str 参数未使用。您是否想根据 str 搜索特定记录，将 temp 设置为指向它，然后继续执行所示的代码？

Answer 3

在 insert() 中，当您分配 temp->anEmployee 时，您只是为指针分配了足够的空间，而不是为整个 Employee 分配了足够的空间。

这一行：

   temp -> anEmployee = (Employee *)malloc(sizeof(Employee *));

应该是：

   temp -> anEmployee = (Employee *)malloc(sizeof(Employee));