Обнаружена ошибка в программировании интервью: связанные списки - PullRequest
Новая
       14

Обнаружена ошибка в программировании интервью: связанные списки

1 голос
/ 14 октября 2010

Я просматривал книгу «Интервью по программированию».Существует код для вставки элемента в начале связанных списков.

bool insertInFront( IntElement **head, int data ){
    IntElement *newElem = new IntElement;
    if( !newElem ) return false;
    newElem->data = data;
    *head = newElem;
    return true;
}

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

Я считаю, что код должен добавить следующую строку в нужном месте. 

newElem->next = *head;

Может кто-нибудь, пожалуйста, просто скажите мне, прав я или нет?

Ответы [ 2 ]

5 голосов
/ 14 октября 2010

Так как это вставка спереди, вы правы.Следующим новым узлом должен быть текущий заголовок, а затем должен быть установлен заголовок, указывающий на новый узел. 

bool insertInFront( IntElement **head, int data ){
    IntElement *newElem = new IntElement;
    if( !newElem ) return false;
    newElem->data = data;
    newElem->next = *head;
    *head = newElem;
    return true;
}

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

4 голосов
/ 14 октября 2010

Я не уверен, какую книгу интервью ты читаешь, но этот пример кода ужасен с ++.

Да, вам нужно указать newElem->next на старое head перед перезаписью head. Кроме того, нет причин проверять, имеет ли newElem значение NULL - если он не может быть выделен, C ++ создает исключение. Кроме того, insertInFront должен быть функцией-членом IntElement, а head должен быть членом данных.

...