Вставить функцию в двусвязный список

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

  void insert(int index, ItemType& item) 
  {

    int pos = 0;
    Node* current = new Node;
    Node* n = new Node;
    n->info = item;
    if (index >= 0 && index <= size)
    {
        if (size == 0)
        {
            head = n;
            tail = n;
            n->next = NULL;
            n->prev = NULL;
            size++;
            return;
        }
        else if (index == 0)
        {
            n->prev = NULL;
            n->next = head;
            head->prev = n;
            head = n;
            size++;
            return;
        }
        else if (index == size)
        {
            n->next = NULL;
            n->prev = tail;
            tail->next = n;
            tail = n;
            size++;
            return;
        }
        else if (index < size/2)
        {
            current = head;
            while(pos != index)
            {
            current = current->next;
            pos++;
            }

        }
        else if (index > size/2)
        {
            int endpos = size - 1;
            current = tail;
            while(endpos != index)
            {
            current = current->prev;
            endpos--;

            }
        }


    n->next = current;
    current->prev->next = n; // HERE is where the code breaks, don't know why.
    n->prev = current->prev;
    current->prev = n;
    size++;


  }
}

Таким образом, код прерывается на операторе current->prev->next = n, в котором говорится, что существует место записи нарушения прав доступа. Поэтому я не уверен, правильно ли это закодировано или я напутал в назначении указателей в более раннем коде. Если кто-нибудь знает, почему это происходит, и может указать мне правильное направление, это было бы здорово. Спасибо.


c++ pointers doubly-linked-list
person DrackBlagon    schedule 18.03.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Из моего наблюдения,

  1. Ваш код не работает, когда index = size/2.

Когда есть два элемента (размер == 2) и когда вы пытаетесь вставить в позицию 1, тогда current->prev->next = n; бессмысленно

Внесите одно из этих изменений else if (index <= size/2) или else if (index >= size/2)

person Krishna M    schedule 18.03.2014
comment
Отлично, это было прекрасно, исправили. Большое спасибо. - person DrackBlagon; 18.03.2014

arrow_upward
0
arrow_downward

Если current является первым узлом в списке, то current->prev будет NULL, поэтому current->prev->next вызовет проблемы. Вы должны проверить, является ли current первым элементом в списке перед этой строкой.

Кроме того, в вашем коде происходит утечка памяти, потому что вы выделяете new Node для current и не удаляете его. Поскольку вы используете current для перемещения по списку, а не для создания нового узла, вы должны объявить его как просто

Node* current;

скорее, чем

Node* current = new Node;
person trm    schedule 18.03.2014