Метод добавления связанного списка C ++ - PullRequest
Новая
       11

Метод добавления связанного списка C ++

1 голос
/ 25 сентября 2011

Я пишу шаблон класса связанного списка на C ++ для себя, чтобы помочь мне вернуться к программированию на C ++.У меня есть следующее определение класса: 

template <typename T>
class List
{
public:
    List();
    ~List();

    void append(T data);
    void display();
    int  count();

private:
    struct Node
    {
        T data;
        Node *next;
    } *head;
};

У меня есть две версии метода добавления - одна работает, а другая нет.Я не могу понять, в чем разница с точки зрения выполняемых операций и почему вторая не работает.Вот тот, который работает: 

template <typename T>
void List<T>::append(T data)
{
    if (head == NULL)
    {
        head = new Node;
        head->data = data;
        head->next = NULL;
    }
    else
    {
        Node *p = head, *q;
        while (p != NULL)
        {
            q = p;
            p = p->next;
        }

        p = new Node;
        p->data = data;
        p->next = NULL;
        q->next = p;
    }
}

А вот тот, который, кажется, фактически не добавляет никаких элементов в список: 

template <typename T>
void List<T>::append(T data)
{
    Node *p = head, *q = head;

    while (p != NULL)
    {
        q = p;
        p = p->next;
    }

    p = new Node;
    p->data = data;
    p->next = NULL;
    if (q != NULL)
    {
        q->next = p;
    }
}

Любые идеи относительно того, почему вторая версияне добавляет никаких элементов?Я пробовал это с типом T как int.

PS Ни одна из версий не дает никаких ошибок или предупреждений ни во время компиляции, ни во время выполнения.

Ответы [ 2 ]

1 голос
/ 25 сентября 2011

Второй метод обрабатывает только случай, когда список не пуст.

Когда список пуст, строка q->next = p; никогда не достигается, поэтому новый элемент просачивается без указателя, существующего дляпосле того, как p выйдет из области видимости.

Если вы хотите исключить особый случай для пустого списка, вам понадобится Node **, например:

0 голосов
/ 25 сентября 2011

В первой версии вы меняете head, во второй - нет.

Проще было бы: 

template <typename T>
void List<T>::append(T data)
{
    p = new Node;
    p->data = data;
    p->next = head;
    head = p;
}

Это также было бы более логично, потому что при добавлении элемента в связанный список не должно быть O (n), как для вас ...

Если вам абсолютно необходимо добавить в конец,сделать это: 

template <typename T>
void List<T>::append(T data)
{
    p = new Node;
    p->data = data;
    p->next = NULL;
    if (tail)
        tail->next = p;
    else // first time
        tail = head = p;
}
...