Проблема со связными списками

332
21 января 2018, 04:36

Код компилируется, но выводится только один список, в порядке, в котором он был создан. А функция reverse, которая ставит в обратном порядке элементы, почему-то совершенно бесполезна - я ее вызываю, но ничего не происходит. На выходе список остается неизменным.

Может, проблема в том, что я эту функцию пишу, до того, как создается сам список?

struct Data
{
    int a;
};
struct List
{
    Data d;
    List * next;
};
// Рекурсия, инверсия списка
List * reverse(List *u)
{
        if (u == 0) return 0;
        if (u->next == 0) return u;
        List * tmp = reverse(u->next);
        u->next->next = u;
        u->next = 0;
        return tmp;
}
// Находим значения списка
bool Find_Item_Single_List(List * u, int DataItem)
{
    List *ptr; 
    ptr = u;
    while (ptr != NULL)
    {
        if (DataItem == ptr->d.a) return true;
        else ptr = ptr->next;
    }
    return false;
}
int main(int argc, char** argv)
{
    List *u = NULL;
    // 1-й узел
    u = new List; // Объявление
    u->d.a = 3;  
    u->next = NULL; // Указатель на следующий элемент
    // Для удобства создаем переменную-указатель, которая хранит адрес последнего элемента
    List *x;
    // 2-й узел
    x = u;
    x->next = new List;
    x = x->next;
    x->d.a = 5;
    x->next = NULL;
    // 
    List *c;
    // 3-й узел
    c = x;
    c->next = new List;
    c = c->next;
    c->d.a = 1;
    c->next = NULL;
    //
    List *b;
    // 4-й узел
    b = c;
    b->next = new List;
    b = b->next;
    b->d.a = 9;
    b->next = NULL;
    // Вывод (просто идем по списку)
    while(u)
    {
        cout << u->d.a << endl; 
        u = u->next;         
    }
    reverse(u);
    return 0;
}
Answer 1

Работать это никак не может потому, что вы своих циклом вывода

while(u)
{
    cout << u->d.a << endl; 
    u = u->next;         
}

"испортили" значение u. После этого цикла u содержит нулевой указатель. Доступ к началу вашего списка вы потеряли. Вызов

reverse(u);

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

Во-первых, не портьте значение u вашим циклом вывода. u - это указатель на начало вашего списка. Его вам надо беречь, как зеницу ока. Не пользуйтесь переменной u для посторонних целей.

Если вы хотите вывести список - заведите для прохода по списку отдельную переменную

for (const List *p = u; p != NULL; p = p->next)
    cout << p->d.a << endl; 

Во-вторых, функция reverse переворачивает ваш список и возвращает вам новый указатель на его новое начало. Не забывайте сохранять это значение. Вот тут-то как раз разумно его сохранить в u

u = reverse(u);

В-третьих, если вы хотите напечатать перевернутый список - то печатайте его. У вас в коде нет ни малейших попыток напечатать перевернутый список. Неудивительно, что ничего не печатается. Опять

for (const List *p = u; p != NULL; p = p->next)
    cout << p->d.a << endl; 

Разумеется, для печати вашего списка имеет смысл завести отдельную функцию, а не ляпать в текст программы один и тот же цикл снова и снова.

READ ALSO
дана прямокутна матриця цілих чисел [требует правки]

дана прямокутна матриця цілих чисел [требует правки]

дана прямокутна матриця цілих чиселВизначити номер першого зі стовпців, що містять хоча б один нульовий елемент та номери всіх рядків, які...

321
Обход busy waiting. - C++

Обход busy waiting. - C++

ЗдравствуйтеКак обойти busy-waiting на C++? Вот код:

215