C ++ удалить кратные данного целого числа из связанного списка - PullRequest
Новая
       10

C ++ удалить кратные данного целого числа из связанного списка

1 голос
/ 03 февраля 2020

извините за мое невежество, но я новичок здесь и на C ++. Я изучаю связанный список, и есть упражнение, в котором я должен написать функцию, которая принимает на вход список целых чисел и целых чисел n. Функция должна удалить из списка все узлы, кратные n, и вернуть список. Я думал, что сделал все правильно, но мой код ничего не выводит. Может ли кто-нибудь объяснить мне, почему? Спасибо всем! 

#include <iostream>
using namespace std;

struct list{
    int val;
    list* next;
};
typedef list* ptr_list;

ptr_list new_node(ptr_list old_node, int value);

ptr_list remove_mult(ptr_list head, int n);

void print_list(ptr_list head);

int main() {

    ptr_list head, p1, p2, p3;
    head = new list;
    head->val = 1;
    p1 = new_node(head, 2);
    p2 = new_node(p1, 3);
    p3 = new_node(p2, 4);

    p3->next = NULL;

    remove_mult(head, 2);
    print_list(head);

    return(0);
}

ptr_list new_node(ptr_list old_node, int value)
{
    old_node->next = new list;
    old_node->next->val = value;
    return old_node->next;
}


ptr_list remove_mult(ptr_list head, int n){
    ptr_list prev, curr;
    prev = head;
    curr = head->next;
    while(curr->next != NULL){
        if((head->val % n) == 0){
            head = head->next;
            curr = curr->next;
        }
        else if((curr->val % n) == 0){
            ptr_list tmp;
            tmp = prev->next;
            prev->next = tmp->next;
            delete tmp;
        }
        prev = curr;
        curr = curr->next;
    }
    if((curr->val % n) == 0){
        prev->next = NULL;
        delete curr;
    }
    return(head);
}

void print_list(ptr_list head){
    while ( head != NULL ){
        cout << head->val << " ";
        head = head->next;
    }
}

1 Ответ

0 голосов
/ 03 февраля 2020

Этот подход 

ptr_list head, p1, p2, p3;
head = new list;
head->val = 1;
p1 = new_node(head, 2);
p2 = new_node(p1, 3);
p3 = new_node(p2, 4);

p3->next = NULL;

//...

ptr_list new_node(ptr_list old_node, int value)
{
    old_node->next = new list;
    old_node->next->val = value;
    return old_node->next;
}

плох, потому что он небезопасен. Например, пользователь может передать функции нулевой указатель. Или член данных, следующий за переданным указателем, может указывать на действительный узел. В этом случае он будет перезаписан в функции и произойдет утечка памяти. Или пользователь может забыть установить элемент данных, следующий за последним узлом после выхода из функции, равным nullptr.

Функция remove_mult также недействительна. Например, переданный указатель в целом может быть равен nullptr. В этом случае функция имеет неопределенное поведение. 

ptr_list remove_mult(ptr_list head, int n){
    ptr_list prev, curr;
    prev = head;
    curr = head->next;
    //...

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

    if((head->val % n) == 0){
        head = head->next;
        curr = curr->next;
    }

В этом операторе else 

    else if((curr->val % n) == 0){
        ptr_list tmp;
        tmp = prev->next;
        prev->next = tmp->next;
        delete tmp;
    }

вы забыли установить новое значение переменной curr.

После оператора if-else 

    prev = curr;
    curr = curr->next;

вы устанавливаете prev Еще один раз. Это снова приводит к неопределенному поведению, например, когда текущий узел был удален.

Вот демонстрационная программа, которая показывает, как могут быть реализованы функции для списка. 

#include <iostream>

struct list
{
    int val;
    list* next;
};

typedef list* ptr_list;

ptr_list remove_mult(ptr_list head, int n )
{
    ptr_list curr = head;
    ptr_list prev = nullptr;

    while ( curr != nullptr )
    {
        if ( curr->val % n == 0 )
        {
            ptr_list tmp = curr;

            if ( prev == nullptr )
            {
                head = curr = curr->next;
            }
            else
            {
                curr = prev->next = curr->next;
            }

            delete tmp;
        }
        else
        {
            prev = curr;
            curr = curr->next;
        }
    }

    return head;
}

void print_list( ptr_list head )
{
    for ( ; head != nullptr; head = head->next )
    {
        std::cout << head->val << ' ';
    }
}

ptr_list append_list( ptr_list tail, int val )
{
    if ( tail == nullptr )
    {
        tail = new list { val, nullptr };
    }
    else
    {
        while ( tail->next != nullptr )
        {
            tail = tail->next;
        }

        tail->next = new list { val, nullptr };
        tail = tail->next;
    }

    return tail;
}

int main() 
{
    ptr_list head = nullptr;

    const int N = 10;

    ptr_list tail = nullptr;
    for ( int i = 0; i < N; i++ )
    {
        if ( head == nullptr )
        {
            head = append_list( head, i );
            tail = head;
        }
        else
        {
            tail = append_list( tail, i );
        }
    }

    print_list( head );
    std::cout << '\n';

    head = remove_mult( head, 2 );

    print_list( head );
    std::cout << '\n';

    return 0;
}

Его вывод 

0 1 2 3 4 5 6 7 8 9 
1 3 5 7 9
...