Как найти ошибку в этой функции подкачки (односвязный список)? - PullRequest
Новая
       4

Как найти ошибку в этой функции подкачки (односвязный список)?

0 голосов
/ 10 февраля 2019

Я не могу поменять значения в связанном списке, если одно из них является заголовком.Я вставляю три значения (4, 5, 7) в a и удаляю 2 и меняю местами 5, 4, но код не поменяется местами, когда одно из значений является головкой, и он просто не поменяется местами и не отобразит вывод, когда одиниз них голова, тот же код работает хорошо для не головных узлов 

struct node
{
int x;

node* next;
};

void swapper(node **headref, int a, int b)
{
    node *temp1 = *headref, *temp2 = *headref, *prev2 = NULL, *prev1 = NULL;

    while(temp1 != NULL && temp1->x != a)
    {
        prev1 = temp1;
        temp1 = temp1->next;
    }

    while(temp2 != NULL && temp2->x != b)
    {
        prev2 = temp2;
        temp2 = temp2->next;
    }

    if(temp1 == *headref)
    {
        swap(temp1->next, temp2->next);
        prev2->next = *headref;
        *headref = temp2;
    }

    if(temp2 == *headref)
    {
        swap(temp1->next, temp2->next);
        prev1->next = *headref;
        *headref = temp1;
    }

    if(temp1 != NULL && temp2 != NULL)
    {
        swap(prev1->next, prev2->next);
        swap(temp1->next, temp2->next);
    }
}

Output:

4 1 2 3
4 1 2 5 3 
4 1 2 5 3 7 
4 1 5 3 7

Предполагается, что нужно поменять местами 5 и 4 и отобразить 5 1 4 3 7, но этого не происходит.Я не могу найти ошибку в коде.

1 Ответ

0 голосов
/ 10 февраля 2019

Проблема в том, что вы не продумали разные случаи должным образом.Если вам нужно поменяться местами, то вам нужно сделать только один раз, поэтому у вас должен быть оператор if ... else if ... else для обработки различных случаев.

Что конкретно идет не так в вашем примере:что temp1 == *headref тогда происходит своп, но после свопа temp2 == *headref программа пытается выполнить второй своп.

У вас также есть ошибка, если вы пытаетесь поменять голову с чем-то, чего нет в списке,в этом случае у вас будут (например) temp1 == *headref и temp2 == NULL, что будет проблемой.

Последний баг - своп с головой.Это также дает сбой, потому что prev2 == NULL в этом случае.

Вот версия, которая работает.Как вы видите, он очень похож на ваш, я только что подумал о различных способах поменять местами более осторожно. 

void swapper(node **headref, int a, int b)
{
    node *temp1 = *headref, *temp2 = *headref, *prev2 = NULL, *prev1 = NULL;

    while (temp1 != NULL && temp1->x != a)
    {
        prev1 = temp1;
        temp1 = temp1->next;
    }

    while (temp2 != NULL && temp2->x != b)
    {
        prev2 = temp2;
        temp2 = temp2->next;
    }

    if (temp1 == NULL || temp2 == NULL || temp1 == temp2)
    {
        // nothing to do
    }
    else if (temp1 == *headref)
    {
        swap(temp1->next, temp2->next);
        prev2->next = *headref;
        *headref = temp2;
    }
    else if (temp2 == *headref)
    {
        swap(temp1->next, temp2->next);
        prev1->next = *headref;
        *headref = temp1;
    }
    else
    {
        swap(prev1->next, prev2->next);
        swap(temp1->next, temp2->next);
    }
}

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

...