Почему переупорядочение связанного списка не удается? - PullRequest
Новая
       6

Почему переупорядочение связанного списка не удается?

0 голосов
/ 13 января 2020

В этом коде я пытаюсь изменить список так, чтобы четные числа появлялись первыми в списке, а нечетные числа появлялись последними в списке, используя функцию evenOdd ().
Но ожидаемый результат не получен , помогите мне.

Ожидаемый результат:

Перед заказом:
1 -> 2 -> 3 -> 4 -> 5 - -> 6 -> 7 -> NULL
после заказа:
2 -> 4 -> 6 -> 1 -> 3 -> 5 -> 7 -> NULL

Фактический вывод:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL 

#include<iostream>
using namespace std;

class Node
{
public:
    int data;
    Node* next;
};

void addEnd(Node **head, int val)
{
    Node *temp=*head;
    Node *newnode=new Node();
    newnode->data=val;
    newnode->next=NULL;
    if(*head == NULL) {*head = newnode; return;}
    while(temp->next!=NULL) {temp=temp->next;}
    temp->next=newnode;
}

void deleteKey(Node **head,int val)
{
    Node *temp=*head;
    Node* prev;
    if(temp!=NULL and temp->data == val)
    {
        *head = temp->next;
        delete temp;
        return;
    }
    while(temp->next!=NULL)
    {
        if(temp->data == val) {prev = temp; break;}
        prev=temp;
        temp=temp->next;
    }
    if(temp->data != val) {cout<<"NO SUCH VAlUES"; return;}
    prev->next=temp->next;
}

void evenOdd(Node **head)
{
    Node *temp = *head;
    while(temp != NULL)
    {
        if(temp->data%2 == 1)
        {addEnd(*(&head),temp->data); deleteKey(*(&head),temp->data);}
        temp = temp->next;
    }
}

void printList(Node *node)
{
    while(node!=NULL)
    {
        cout<<"  "<<node->data<<" --> ";
        node=node->next;
    }
    cout<<"NULL";
}

int main()
{
    Node *head = NULL;
    addEnd(&head,1);
    addEnd(&head,2);
    addEnd(&head,3);
    addEnd(&head,4);
    addEnd(&head,5);
    addEnd(&head,6);
    addEnd(&head,7);
    cout<<"Before Ordering :\n";
    printList(head);
    evenOdd(&head);
    cout<<"After Ordering :\n";
    printList(head);
    return 0;
}

Ответы [ 2 ]

2 голосов
/ 13 января 2020

С помощью этой комбинации 

if(temp->data%2 == 1)

и 

deleteKey(*(&head),temp->data);

вы удаляете узел, который просматриваете в данный момент. Включая фактическую 

delete temp;

внутри deleteKey.

Но затем вы получаете доступ к только что удаленной памяти, здесь 

temp = temp->next;

внутри evenOdd.

После этого все ставки отключены.

Но наблюдаемая проблема возникает здесь, внутри deleteKey: 

prev->next=temp->next;

, где используется prev со значением, идентичным temp.
Т.е. он не меняет темп и, в особенности, не указывает на указатель, который указывает на темп.
Для этого вам необходимо отслеживать указатель, указывающий на узел, который вы хотите удалить, и изменять ТА.
Именование ваших переменных означает, что вы знаете концепцию и пытаетесь сделать это здесь 

{prev = temp; break;}

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

{prev->next = temp->next; break;} /* prev->next currently points to temp, but prev!= temp */
/* update the "next" pointing to current node so that it points to the next one */

Вы можете найти другие мои ответы полезными для анализа таких проблем с пуитнером:
Трюки для анализа указателя и структуры указатель-указатель в C?

0 голосов
/ 13 января 2020

в функции evenOdd temp указывает на узел, вставленный сзади, тогда как он должен указывать на 2,3,4-й узел согласно итерации. поэтому, когда вы делаете temp = temp-> next, оно переполняется.

...