Как я могу создать функцию, которая меняет два смежных элемента в односвязном списке, только изменяя ссылки?

Question

Я пытаюсь сделать функцию в моем связанном списке, когда передаю ей два целых числа. Он будет менять свои узлы, изменяя то, что указывает каждый из их узлов. Я теряю один из узлов после завершения функции. Как я могу заставить его работать?

Это само

void linkedList::swapTwoAdjacent(int num1, int num2) { 

    if (head == NULL) { 
     cout << "List is empty" << endl; 
     return; 
    } 

    node *temp1, *temp2, *temp3; 

    for (temp1 = head, temp2 = temp1->next; temp1->next != NULL; temp1 = temp1->next, temp2 = temp2->next) { 
     cout << endl << "IN FOR" << endl; 
     if (temp1->data == num1 && temp2->data == num2) { 
      cout << "IN IF BEFORE NODES SWAP" << endl; 
      // swap nodes 
      cout << "Temp1 : " << temp1 << " -- Temp2 : " << temp2 << " -- Temp3 : " << temp3 << endl; 
      temp3 = temp2->next; 
      temp2->next = temp1; 
      temp1->next = temp3; 
      cout << "IN IF AFTER NODES SWAP" << endl; 

     } 
     else { 
      continue; 
     } 
    } 

} 

функция Это полная реализация

#include <iostream> 

using namespace std; 

struct node 
{ 
    int data; 
    node* next; 
}; 

class linkedList { 
    private: 
     node* head; 

    public: 
     linkedList(); 
     node* createNode(int num); 
     void append(int num); 
     // void add_as_first(int num); 
     // void addAfter(int c, int num); 
     void del(int num); 
     void display(); 
     int count(); 
     void swapTwoAdjacent(int num1, int num2); 
     // ~linkedList(); 
}; 
int main(){ 
    linkedList List; 

    List.display(); 

    int numNodes = 0; 
    cout << "Enter number of nodes that you want to add: "; 
    cin >> numNodes; 
    cout << endl; 
    for (int i = 0; i < numNodes; i++) { 
     int current_element; 
     cin >> current_element; 
     List.append(current_element); 
     cout << endl << current_element <<" has been appended to the list "<< endl; 
     cout << "-------------------------------------------------------------------" << endl; 
    } 

    List.display(); 
    // List.del(5); 
    List.swapTwoAdjacent(4,6); 
    List.display(); 
    // List.count(); 
    return 0; 
} 

// constructor initializes head to null 
linkedList::linkedList() 
{ 
    head = NULL; 
} 

// create node 
node* linkedList::createNode(int num) 
{ 
    node* new_node; 
    new_node = new node; 
    new_node -> data = num; 
    new_node -> next = NULL; 

    return new_node; 
} 

void linkedList::append(int num) 
{ 
    node *temp, *nNode; 
    nNode = createNode(num); 
    if (head == NULL) { 
     head = nNode; 
    } 

    else { 
     temp = head; 
     while(temp -> next != NULL) 
     { 
      temp = temp -> next; 
     } 
     temp -> next = nNode; 

    } 
} 

void linkedList::display() 
{ 
    // if the list is empty 
    if (head == NULL) { 
     cout << "No nodes added yet!" << endl; 
    } 

    else { 
     // create a temp variable to hold the heads 
     node* temp = head; 
     // as long as we haven't reached the end of the list 
     while (temp != NULL) { 
      // print current element 
      cout << temp->data << " "; 
      // go to the next node 
      temp = temp->next; 
     } 
    } 
} 

int linkedList::count() 
{ 
    int counter = 0; 
    if (head == NULL) { 
     cout << endl << "The list has " << counter << " elements." << endl; 
    } 

    else { 


      for (node* temp = head; temp != NULL; temp = temp->next) { 
       counter++; 
      } 
     } 

    cout << endl << "The list has " << counter << " elements." << endl; 
} 

void linkedList::del(int n) { 
    if (head == NULL) { 
     cout << "No elements are in the list " << endl; 
    } 
    node *temp1, *temp2; 
     if (head-> next == NULL) { 
       head = NULL; 

       cout << endl << n << " was deleted" << endl; 
       cout << endl << "Current elements in the list :" << endl << "-----------------------------------------" << endl; 
       this->display(); 
       return; 
     } 

     for (temp1 = head, temp2 = temp1->next; temp2 != NULL; temp1 = temp1->next, temp2 = temp1->next) { 
      if (temp1->data == n) { 

       head = temp2; 
       cout << endl << n << " was deleted" << endl; 
       cout << endl << "Current elements in the list :" << endl << "-----------------------------------------" << endl; 
       this->display(); 
       break; 
      } 
      else if (temp2->data == n) { 
       temp1->next = temp2->next; 
       cout << endl << n << " was deleted" << endl; 
       cout << endl << "Current elements in the list :" << endl << "-----------------------------------------" << endl; 
       this->display(); 
       break; 
      } 


      else { 
       continue; 
      } 
     } 
} 

void linkedList::swapTwoAdjacent(int num1, int num2) { 

    if (head == NULL) { 
     cout << "List is empty" << endl; 
     return; 
    } 

    node *temp1, *temp2, *temp3; 

    for (temp1 = head, temp2 = temp1->next; temp1->next != NULL; temp1 = temp1->next, temp2 = temp2->next) { 
     cout << endl << "IN FOR" << endl; 
     if (temp1->data == num1 && temp2->data == num2) { 
      cout << "IN IF BEFORE NODES SWAP" << endl; 
      // swap nodes 
      cout << "Temp1 : " << temp1 << " -- Temp2 : " << temp2 << " -- Temp3 : " << temp3 << endl; 
      temp3 = temp2->next; 
      temp2->next = temp1; 
      temp1->next = temp3; 
      cout << "IN IF AFTER NODES SWAP" << endl; 

     } 
     else { 
      continue; 
     } 
    } 

} 

Выборочная проверка с выходом пробежал Valgrind показывает много ошибок

==14392== Memcheck, a memory error detector 
==14392== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. 
==14392== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info 
==14392== Command: ./singleLinkedList 
==14392== 
No nodes added yet! 
Enter number of nodes that you want to add: 5 

9 

9 has been appended to the list 
------------------------------------------------------------------- 
2 

2 has been appended to the list 
------------------------------------------------------------------- 
4 

4 has been appended to the list 
------------------------------------------------------------------- 
6 

6 has been appended to the list 
------------------------------------------------------------------- 
8 

8 has been appended to the list 
------------------------------------------------------------------- 
9 2 4 6 8 
IN FOR 

IN FOR 

IN FOR 
IN IF BEFORE NODES SWAP 
==14392== Use of uninitialised value of size 8 
==14392== at 0x4F36E01: int std::__int_to_char<char, unsigned long>(char*, unsigned long, char const*, std::_Ios_Fmtflags, bool) (locale_facets.tcc:826) 
==14392== by 0x4F3845B: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<unsigned long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, unsigned long) const (locale_facets.tcc:876) 
==14392== by 0x4F3864E: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, void const*) const (locale_facets.tcc:1191) 
==14392== by 0x4F45729: put (locale_facets.h:2460) 
==14392== by 0x4F45729: std::ostream& std::ostream::_M_insert<void const*>(void const*) (ostream.tcc:73) 
==14392== by 0x4010AE: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList) 
==14392== by 0x400AEA: main (in /home/captainmoha/uni/data_structure/singleLinkedList) 
==14392== Uninitialised value was created by a stack allocation 
==14392== at 0x400F86: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList) 
==14392== 
==14392== Conditional jump or move depends on uninitialised value(s) 
==14392== at 0x4F36E08: int std::__int_to_char<char, unsigned long>(char*, unsigned long, char const*, std::_Ios_Fmtflags, bool) (locale_facets.tcc:824) 
==14392== by 0x4F3845B: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<unsigned long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, unsigned long) const (locale_facets.tcc:876) 
==14392== by 0x4F3864E: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, void const*) const (locale_facets.tcc:1191) 
==14392== by 0x4F45729: put (locale_facets.h:2460) 
==14392== by 0x4F45729: std::ostream& std::ostream::_M_insert<void const*>(void const*) (ostream.tcc:73) 
==14392== by 0x4010AE: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList) 
==14392== by 0x400AEA: main (in /home/captainmoha/uni/data_structure/singleLinkedList) 
==14392== Uninitialised value was created by a stack allocation 
==14392== at 0x400F86: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList) 
==14392== 
==14392== Conditional jump or move depends on uninitialised value(s) 
==14392== at 0x4F38564: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<unsigned long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, unsigned long) const (locale_facets.tcc:905) 
==14392== by 0x4F3864E: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, void const*) const (locale_facets.tcc:1191) 
==14392== by 0x4F45729: put (locale_facets.h:2460) 
==14392== by 0x4F45729: std::ostream& std::ostream::_M_insert<void const*>(void const*) (ostream.tcc:73) 
==14392== by 0x4010AE: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList) 
==14392== by 0x400AEA: main (in /home/captainmoha/uni/data_structure/singleLinkedList) 
==14392== Uninitialised value was created by a stack allocation 
==14392== at 0x400F86: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList) 
==14392== 
Temp1 : 0x5aa7d20 -- Temp2 : 0x5aa7d70 -- Temp3 : 0xffefffca0 
IN IF AFTER NODES SWAP 
9 2 4 8 ==14392== 
==14392== HEAP SUMMARY: 
==14392==  in use at exit: 72,784 bytes in 6 blocks 
==14392== total heap usage: 6 allocs, 0 frees, 72,784 bytes allocated 
==14392== 
==14392== LEAK SUMMARY: 
==14392== definitely lost: 32 bytes in 2 blocks 
==14392== indirectly lost: 48 bytes in 3 blocks 
==14392==  possibly lost: 0 bytes in 0 blocks 
==14392== still reachable: 72,704 bytes in 1 blocks 
==14392==   suppressed: 0 bytes in 0 blocks 
==14392== Rerun with --leak-check=full to see details of leaked memory 
==14392== 
==14392== For counts of detected and suppressed errors, rerun with: -v 
==14392== ERROR SUMMARY: 19 errors from 3 contexts (suppressed: 0 from 0) 

Answer 1

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

if (temp1->data == num1 && temp2->data == num2) 
{ 
    temp3 = temp2->next; //temp# == node# at this moment 
    temp2->next = temp1; //node2 now links back to node1 
    temp1->next = temp3; //node1 now skips node2 and goes to node3 
} 

После выполнения этого кода, теперь вы удалили узел я называю node2 из списка. И из-за того, как вы пишете цикл, вы заканчиваете в конце своего списка раньше, чем ожидалось, и пытаетесь разыменовать нулевой указатель. В вашем для цикла:

temp1 = temp1->next, /*temp1->next now points to last node*/ 
temp2 = temp1->next /*temp2 is now a null pointer*/ 

Таким образом, условие цикла temp2->next != NULL терпит неудачу, потому что temp2 самого NULL.

В комментариях было обнаружено, что изменение temp2 = temp1->next на temp2 = temp2->next делает остановку segfault. Это связано с тем, что temp2->next указал на node, и поэтому потребовалось больше итераций, чтобы добраться до конца, где цикл не удался. Если вы только return от функции после «swap», у вас не будет этой ошибки.

EDIT: Я добавил код для обмена двумя узлами.

void linkedList::swapTwoAdjacent(int num1, int num2) 
{ 
    if (head == NULL) { 
     cout << "List is empty" << endl; 
     return; 
    } 
    node** np = &head; //two star programmer club 
    node* temp; 
    while ((*np)->next != NULL) //As long as next node exists 
    { 
     if ((*np)->data == num1 && (*np)->next->data == num2) 
     { 
      temp = *np; //temp = &node1 
      *np = (*np)->next; //node0->next = &node2 
      temp->next = (*np)->next; //node1->next = node2->next 
      (*np)->next = temp; //node2->next = node1 
      //node0->node2->node1->node3 
      //If you want to only swap the first pair of values you find, uncomment the next line, otherwise it swaps every matching pair 
      //return; 
     } 
     np = &((*np)->next); //Point to pointer to next node 
    } 
} 

Используя указатель на указатель на узел, мы можем изменить указатель, который указывал на текущий узел мы Перебор. Комментарии, надеюсь, объясняют, что делают все задания.

Answer 2

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

Это метод работы с комментариями, которые мы надеемся объяснить, что я сделал:

void linkedList::swapTwoAdjacent(int num1, int num2) { 
    node *temp1, *temp2, *temp3; 


    temp1 = head; 
    temp2 = temp1->next; 

    if (head == NULL) { 
     cout << "List is empty" << endl; 
     return; 
    } 
    else if (head->next == NULL) { 
     cout << "Swap not possible! List has only one node." << endl; 
    } 

    else if (temp1->data == num1 && temp2->data == num2) {  // if the nodes to swap are the first two nodes 
       head->next = temp2->next; // make the next of head point to the third node 
       temp2->next = head;   // make the next of the second node point to head 
       head = temp2;    // now make the second node the head 
      } 


    else { 
     node *tempHolder1, *tempHolder2, *tempHolder3; // holders for nodes in temps to make swapping easier 

     // go through nodes in the list with three pointers 
     // temp1->temp2->temp3 
     // I'm using three pointers so that I always know the node before the two nodes I'm looking for 

     for (temp1 = head, temp2 = temp1->next, temp3 = temp2->next; temp3 != NULL; temp1 = temp1->next, temp2 = temp1->next, temp3 = temp2->next) { 
      // cout << "IN FOR" << endl; 

      if (temp2->data == num1 && temp3->data == num2) { // if the two nodes are found 

       // these are just placeholders to make swapping easier 

       tempHolder1 = temp1; // now temp1 is the node before the two nodes I want to swap 
       tempHolder2 = temp2; // temp2 is the first node 
       tempHolder3 = temp3; // temp3 is the second node 

       temp1->next = tempHolder2->next;  // make the first node point to the third node 
       temp2->next = tempHolder3->next;  // make the second node point to what's after the third node 
       temp3->next = tempHolder2;    // make the third node point to the second node 

       break; 

      } 

      else { 
       continue; 
      } 
     } 

    } 

}