Разность односвязных списков

Question

Разность односвязных списков

Рейтинг: 0Ответов: 1Опубликовано: 01.05.2015

#include "stdafx.h"
using namespace std;


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

void print(list *a)
{
    list *p = a;
    cout << "Spisok: ";
    while (p != NULL)
    {
        cout << p->val;
        p = p->next;
    }
}

list *init(int a)
{
    list *head = new list;
    head->val = a;
    head->next = NULL;
    return (head);
}

list *add(list *head, int data)
{
    list *temp, *p;
    p = head->next;
    temp = new list;
    head->next = temp;
    temp->val = data;
    temp->next = p;
    return (temp);
}

void del(list *&p, int v)
{
    if (p == NULL)
        return;
    list *t = p;
    if (t->val == v)
    {
        p = t->next;
        delete t;
        return;
    }

    list *t1 = t->next;
    while (t1)
    {
        if (t1->val == v)
        {
            t->next = t1->next;
            delete t1;
            return;
        }
        t = t1;
        t1 = t1->next;
    }
}

void sub(list *&a, list *&b)
{
    list *p1, *p2;
    p1 = a;
    p2 = b;
    while (p1)
    {
        while (p2)
        {
            if (p1->val == p2->val)
                del(p1, p1->val);
            p2 = p2->next;
        }
        p1 = p1->next;
    }
}


int main()
{
    setlocale(LC_ALL, "Russian");

    list *p1 = new list;
    list *p2 = new list;
    p1 = init(5);
    add(p1, 6);
    add(p1, 9);
    p2 = init(6);
    add(p2, 7);

    sub(p1, p2);
    print(p1);
    cout << endl;
    print(p2);

    delete p1;
    delete p2;
    _getch();
    return 0;
}

Не работает функция разности списков sub. Не могу понять в чем ошибка.

c# односвязный-список списки

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Метод sub полностью неверен.

Смотрите, что вы делаете. На первой итерации внешнего цикла вы сравниваете все элементы второго списка с головным элементом первого. Затем вы не реинициализируете p2, и в дальнейших итерациях он остаётся равным NULL. Таким образом, дальнейшие итерации вовсе ничего не делают.

Смотрите, что надо сделать. Обратите внимание на то, что метод del удаляет значение во всём списке. Поэтому вам должно быть достаточно пробежаться по второму списку, и вызвать del для каждого элемента второго списка:

for (list *p2 = b; p2; p2 = p2->next)
    del(a, p2->val);

или оставаясь в стиле вашего кода

list *p2;
p2 = b;
while (p2)
{
    del(a, p2->val);
    p2 = p2->next;
}

Обратите внимание, что вам нужно удалять по a, а не его копии p1, потому что процедура del может модифицировать переданный указатель.

В коде ещё наверняка есть погрешности. Например, у вас потеря памяти в начале main (list *p1 = new list; — это значение тут же теряется). (И в конце: для освообждения памяти списка простого delete недостаточно.)

Разность односвязных списков

Ответы