Добавление и удаление из двойного связанного списка

Question

Я имею такую ​​структуру

typedef struct node 
{ 
    struct node *prev; 
    void  *data; 
    struct node *next; 
}NODE; 

typedef struct head 
{ 
    unsigned int length; 
    struct node *first; 
    struct node *last; 
}HEAD; 


STATUS addNode(HEAD *head, NODE *newNode, int loc) 
{ 
int i; 
STATUS ret = SUCCESS; 

NODE *curPtr; 

if(head && newNode && loc && (loc <= (head->length)+1)) 
{ 
    if(loc == 1) 
    { 
     newNode->prev = NULL; 
     newNode->next = head->first; 

     if(head->first) 
      head->first = newNode; 
    } 
    else 
    { 
     curPtr = head->first; 

     for(i=1; i<(loc-1); i++){ 
      curPtr = curPtr->next; 
     } 

     newNode->prev = curPtr; 
     newNode->next = curPtr->next; 

     if(curPtr->next){ 
      curPtr->next->prev = newNode; 
     } 
     curPtr->next = newNode; 

    } 

    head->length++; 
} 
else 
    ret = FAILURE; 

return ret; 
} 



STATUS removeNode(HEAD *head,NODE *nodeToRemove) 
{ 
    STATUS ret = SUCCESS; 

    NODE *curPtr; 

    if(head && head->first) 
    { 
     curPtr = nodeToRemove->prev; 
     curPtr->next = nodeToRemove->next; 
     if(!(curPtr->next)){ 
      curPtr->next = head->first; 
     } 
     head->length--; 
    } 
    else 
     ret = FAILURE; 

    return ret; 
} 

Я знаю, что я не называю бесплатно (узел) в удалить из списка, этот вызов сделан где-то еще

моя проблема, что иногда на линии newNode->next = curPtr->next; в дополнительном узле он падает на ошибку сегментации

Не могли бы вы рассказать мне, почему это может случиться?

Answer 1

Возможно, что curptr->next не назначен ни на что, что не обязательно укажет на NULL, и, следовательно, вы можете столкнуться с ошибками сегментации во время выполнения. Убедитесь, что при создании списка все ваши указатели в NODE инициализируются до NULL перед любым назначением/операцией на них.

Смотреть это: C: Why do unassigned pointers point to unpredictable memory and NOT point to NULL?

и это: Why am I getting a segmentation fault?

Answer 2

Хорошо, давайте начнем с первой из моих комментариев: Что происходит, когда вы вызываете функцию addNode с loc == 1: Вы инициализировать новый узел, так что next указатель указывает на старую главу списка, а указатель prev указывает на NULL. Это все хорошо и хорошо, но тогда ваша проблема начинается. Вы только добавляете новый узел в список , если список не пустой. Вы также не меняете предыдущие головные узлы prev указатель.

Это означает, что если список пуст (то есть когда head->first - NULL), то вы не добавите узел, и список будет по-прежнему пустым. Если список не пуст, у вас есть список с двойной связью, в котором вы можете идти только в одну сторону (от (нового) первого узла до (нового) второго узла, вы не можете идти в противоположном направлении, так как вы не есть ссылка настроить таким образом

---

Теперь для второго и третьего из моих комментариев:.. Петля при loc != 1 Прежде всего, это не будет работать вообще, если loc == 0, то есть он добавит к голове (который является то, что вы пытаетесь сделать, когда loc == 1). Это не будет работать, если список пуст, так как curPtr тогда будет NULL и вы будете иметь undefined behavior когда вы разыменование этого указателя.

Во-вторых, давайте предположим, что вам удалось добавить некоторые узлы в список, и вы передаете значение, большее, чем число узлов плюс один в списке, как loc (т. если у вас есть один узел, и вы передаете значение, превышающее 2, или у вас есть пять узлов и передайте значение больше 6), тогда цикл будет повторяться один раз для многих, оставив вас с curPtr равным NULL. Вы не проверяете это где угодно, а это значит, что вы рано или поздно (в цикле или после) попытаетесь разыменовать указатель NULL, который ведет к undefined behavior.

---

Undefined behavior является наиболее частой причиной аварий, таких, как тот, который вы имеете. И в следующий раз, когда у вас случится сбой, первое, что вам нужно сделать, это использовать отладчик и запустить свою программу в нем. Отладчик остановится в месте сбоя, позволяя вам изучить стек вызовов функций, а также подойти к стеку вызовов.Вы также сможете изучить значения переменных на каждом уровне стека вызовов (если отладчик имеет информацию для этого уровня). Вы также должны попытаться пройти через код, по очереди, в отладчике для разных сценариев, чтобы увидеть, что то, что вы намереваетесь произойти, на самом деле происходит. Если вы все еще в тупике, , то вы можете прийти к SO и задать вопрос о Это. Рядом с компилятором отладчик - лучший инструмент для программиста. О, говоря о компиляторах, всегда создавайте с максимально возможным количеством предупреждений, поскольку компиляторы довольно хорошо разбираются в подозрительных вещах, и это может привести к UB (неопределенное поведение).