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

у меня такая структура

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

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

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

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


c doubly-linked-list
person Lena Bru    schedule 11.01.2015    source источник
comment
Если loc == 1, на что указывает указатель старых первых узлов prev? А если список пуст, то почему вы вообще не добавляете узел?   -  person Some programmer dude    schedule 11.01.2015
comment
Что касается вашей ошибки сегментации, что, если вы хотите добавить новый узел последним? т.е. когда curPtr это NULL?   -  person Some programmer dude    schedule 11.01.2015
comment
И, наконец, что произойдет, если вы укажете loc больше, чем узлов в списке?   -  person Some programmer dude    schedule 11.01.2015
comment
первый вопрос - должен указать на хвост, 2-й вопрос добавить его в хвост, 3-й вопрос обвести список несколько раз, пока не употребите местоположение   -  person Lena Bru    schedule 11.01.2015

Ответы (2)


arrow_upward
1
arrow_downward

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

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

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

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

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

person Some programmer dude    schedule 11.01.2015

arrow_upward
0
arrow_downward

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

См. это: C : Почему неназначенные указатели указывают на непредсказуемую память, а НЕ указывают на NULL?

и это: Почему я получаю ошибку сегментации?

person sleeping_dragon    schedule 11.01.2015