Блог

Главная - Вопросы по программированию - связанный список не удаляет / не добавляет первые заголовки

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

#c #linked-list #stack #doubly-linked-list #function-definition

#c #связанный список #стек #дважды связанный список #функция-определение

Вопрос:

Я создаю программу, которая добавляет / удаляет заголовок, когда он совпадает, однако он не работает. Что-то не так с этими двумя функциями? У меня есть больше кода связанного списка, но это те два, которые я использую в своей программе.

Предполагается, что они работают аналогично функции push / pop стека

 linkedList* createLinkedList()
{
    linkedList* list;
    list = malloc(sizeof(linkedList));
    list->size = 0;
    list->head = NULL;
    list->tail = NULL;
    return list;
}
void insertStart(linkedList* list, void* inData)
{
    listNode* node;
    node = (listNode*)malloc(sizeof(listNode));
    node->data = inData;
    list->size  ;
    if (list->head == NULL)
    { 
        list->head = node;
        list->tail = node;
        node->next = NULL;
        node->prev = NULL;
    }
    else
    { 
    
        list->head->prev = node;
        node->next = list->head;
        node->prev = NULL;
        list->head = node;
    }
}

void* removeStart(linkedList* list)
{
    listNode* removed = NULL;
   /* void* outData = NULL;*/
 
        removed = list->head;
        list->head = list->head->next;
        list->head->prev = NULL;
        list->size -= 1;
       /* outData = removed->data;
        free(removed);*/
   
    return removed;
}

Комментарии:

1. Просто примечание, если у вас нет особой потребности в size члене, поскольку вы добавляете больше функциональности в свой список, size член может быть громоздким в обслуживании и иметь ограниченную полезность. (кроме ответа «Сколько узлов у меня есть?» или если вы ограничиваете количество узлов) Просто что-то, что нужно иметь в виду.

Ответ №1:

Хотя insertStart он будет работать правильно, его можно значительно упростить:

 void insertStart(linkedList* list, void* inData)
{
    listNode* node = malloc(sizeof *node);
    node->data = inData;
    node->next = list->head;
    node->prev = NULL;
    if (list->head)
        list->head->prev = node;
    else
        list->tail = node;
    list->head = node;
    list->size  ;
}

Однако реальная проблема заключается removeStart в следующем. У него есть несколько серьезных недостатков:

  1. Он вообще не управляет tail указателем.
  2. Предполагается, что список не является пустым.
  3. Возвращен неверный результат. (вы хотите вернуть элемент данных, а не указатель на узел)

Первый из них полностью разрушит все, что требует правильно управляемого хвостового указателя; второй вызовет неопределенное поведение, если пустой список. Последний элемент — это просто надзор. Все они могут быть решены менее чем за двадцать строк кода:

 void* removeStart(linkedList* list)
{
    void *data = NULL;

    if (list->head)
    {
        listNode* removed = list->head;
        list->head = removed->next;
        if (list->head)
            list->head->prev = NULL;
        else
            list->tail = NULL;
        data = removed->data;
        free(removed);
        --list->size;
    }
    return data;
}

Ответ №2:

Функция insertStart содержит дублированный код. Также для предотвращения неопределенного поведения следует проверить, была ли успешно выделена память для нового узла.

Функция может быть объявлена и определена следующим образом.

 int insertStart(linkedL ist *list, void* inData )
{
    listNode *node = malloc( sizeof( listNode ) );
    int success = node != NULL;

    if ( success )
    {
        node->data = inData;
        node->next = list->head;
        node->prev = NULL;

        if ( list->head == NULL )
        {
            list->tail = node;
        }
        else
        {
            list->head->prev = node;
        }

        list->head = node;
          list->size;
    }

    return success;
}

Основная проблема с функцией emoveStart заключается в том, что она не проверяет, является ли список пустым. Также он не обновляет узел, на который указывает указатель tail , когда список содержит один узел.

Функция может быть определена следующим образом

 void *  removeStart( linkedList *list )
{
    void *data = NULL;

    if ( list->head != NULL )
    {
        listNode *removed = list->head;
        data = removed->data;

        list->head = list->head->next;

        if ( list->head == NULL )
        {
            list->tail = NULL;
        }
        else
        {
            list->prev = NULL;
        }

        free( removed );
        --list->size;
    }

    return data;
}