Структура односвязного списка вставка / удаление нескольких бесплатных - PullRequest
Новая
       40

Структура односвязного списка вставка / удаление нескольких бесплатных

0 голосов
/ 23 апреля 2011

Я слишком долго смотрел на этот код, и я становлюсь мрачным, и все шансы его выяснить самостоятельно упущены :( Кто-нибудь может сказать мне, где я тупой? Я просто не понимаю, где я дважды освобождаюсь или возможно неправильное распределение (что я должен делать, но да). Я продолжаю получать * обнаруженный glibc * free (): неверный следующий размер

Я на самом деле освобождаю больше, чем мне нужно, или я просто не распределяю то, что мне нужно выделять в первую очередь. - извините за плохой отступ, но этот редактор не может правильно сделать отступ

У меня есть структуры: 

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;
 }

Ответы [ 3 ]

1 голос
/ 23 апреля 2011

Во-первых, в insert вы выделяете 

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

, который выделяет только достаточно памяти для хранения указателя Employee , а не всей структуры Employee.Вы должны выделить блок размером sizeof(Employee) для temp->anEmployee.

Ваши звонки на 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;
}

Отслеживая узел, который предшествует вашей находке, если таковые имеются, вы можете избежать всех неприятныхособые случаи и сокращают обновление основного списка до трех простых условных присвоений.

0 голосов
/ 23 апреля 2011

В insert (), когда вы выделяете temp->anEmployee, вы выделяете достаточно места только для указателя, а не для полного сотрудника.

Эта строка: 

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

должнабыть: 

   temp -> anEmployee = (Employee *)malloc(sizeof(Employee));
0 голосов
/ 23 апреля 2011

Не прочитав все это, что должны делать первые строки delete 

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

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

Я не могу сказать, что delete предполагается удалить. Похоже, что аргумент str не используется. Вы хотите найти определенную запись на основе str, установить temp, чтобы указать на нее, а затем продолжить с кодом, как показано?

...