Обмен последнего узла связанного списка идет в infinte - C ++ - PullRequest
Новая
       95

Обмен последнего узла связанного списка идет в infinte - C ++

1 голос
/ 21 марта 2020

Ниже приведен код, 

#include<bits/stdc++.h>
using namespace std;

class node{
public:
    int data;
    node * next;

    node(){
        this->next = NULL;
    }

    node(int data){
        this->data = data;
        this->next = NULL;
    }
};

class linkedList{
public:
    node * head;
    node * tail;

    linkedList(){
        this->head = NULL;
    }

    void getTail(node *& t){
        t = head;
        while(t->next != NULL){
            t = t->next;
        }
    }

    void insertAtEnd(int data){
        node * newNode = new node(data);

        if(head == NULL){
            head = newNode;
            return;
        }

        node * temp = head;
        while(temp->next != NULL){
            temp = temp->next;
        }
        temp->next = newNode;
    }

    void print(){
        node * temp = head;
        while(temp != NULL){
            printf("%d->", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }

    void swap(node *& a, node *& b){ 
        node * temp = a;
        a = b;
        b = temp; 
    } 

    void swapNode(node ** start, node ** end){
        swap(*start, *end);
        swap(((*start)->next), (*end)->next);
    }
};

int main(){
    ///////////////////////////////////////
    linkedList * ll1 = new linkedList(); //
    ll1->insertAtEnd(6);                 //
    ll1->insertAtEnd(2);                 //
    ll1->insertAtEnd(1);                 //
    ll1->insertAtEnd(3);                 //
    ll1->print();                        /////////////////////
    ll1->swapNode(&ll1->head, &ll1->head->next->next->next);// ----> This is working
    //////////////////////////////////////////////////////////

    linkedList * ll2 = new linkedList();
    ll2->insertAtEnd(6);
    ll2->insertAtEnd(2);
    ll2->insertAtEnd(1);
    ll2->insertAtEnd(3);
    ll2->print();
    node * tail;
    ll2->getTail(tail);
    ll2->swapNode(&ll2->head, &tail); // This is not working // Going into a infinte loop
    ll2->print();

}

Когда хвостовой узел хранится в какой-то другой переменной, кажется, что навсегда l oop. Пока код работает, когда хвостовой узел задается путем обхода до последнего с использованием следующего указателя.

Итак, ниже приведен вывод для первого примера связанного списка, то есть 6-> 2-> 1 -> 3-> NULL 1-> 2-> 6-> 3-> NULL

Для связанного списка # 2 вывод выглядит так: 6-> 2-> 1-> 3-> NULL 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2- > 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3 -> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3- > 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1 -> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1- > 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2 -> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2- > 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3 -> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3-> 2-> 1-> 3- > 2-> 1-> 3-> 2-> нет окончания

Ответы [ 2 ]

3 голосов
/ 21 марта 2020

Когда вы меняете два узла a и b, вы также должны зафиксировать указатели, достигшие a и достигающие b. Например, 

     x1 -> x2 -> a -> x3 -> x4 -> b -> x5 -> x6 -> NULL

для замены узлов a и b, чтобы не нужно было исправлять только a.next и b.next, а также x2.next и x4.next.

Эта часть кода отсутствует в вашей реализации.

0 голосов
/ 22 марта 2020

Изображения часто помогают при работе со связанными списками. Вот начальный список. 

head
 |
 V
 ------------    ------------    ------------    ------------    
 | 6 | next | -> | 2 | next | -> | 1 | next | -> | 3 | NULL |
 ------------    ------------    ------------    ------------

Теперь мы будем вызывать ll1->swapNode(&ll1->head, &ll1->head->next->next->next), что добавляет к изображению две переменные. 

start
  |
  V
  head                                  end
   |                                     |
   V                                     V
   ------------    ------------    ------------    ------------    
   | 6 | next | -> | 2 | next | -> | 1 | next | -> | 3 | NULL |
   ------------    ------------    ------------    ------------

Далее идет вызов swap(*start, *end), который меняет указатель головы и указатель next в узле с данными 1. Таким образом, указатель головы будет указывать на узел 3, а узел 1 будет указывать на узел 6. 

                                              start
                                                |
                                                V
                                      end       head
                                       |         |
                                       V         V
 ------------    ------------    ------------    ------------    
 | 6 | next | -> | 2 | next | -> | 1 | next |    | 3 | NULL |
 ------------    ------------    ------------    ------------    
 ^                                      |
 |                                      |
 L---------------------------------------

Наконец, вызов swap(((*start)->next), (*end)->next), который меняет next указатели в узлах, чьи данные 3 и 6. Поэтому узел 3 будет указывать на узел 2, а указатель узла 6 станет нулевым. 

       start
         |
         V
         head
          |
          V
          ------------
          | 3 | next |
          ------------                end
                 |                     |
                 V                     V
 ------------    ------------    ------------
 | 6 | NULL |    | 2 | next | -> | 1 | next |
 ------------    ------------    ------------
 ^                                      |
 |                                      |
 L---------------------------------------

Ура! Узлы поменялись местами.

Теперь посмотрите на вызов ll2->swapNode(&ll2->head, &tail);, который добавляет три переменные к исходному изображению. 

start                                            end
  |                                               |
  V                                               V
  head                                            tail
   |                                               |
   V                                               V
   ------------    ------------    ------------    ------------    
   | 6 | next | -> | 2 | next | -> | 1 | next | -> | 3 | NULL |
   ------------    ------------    ------------    ------------

Далее идет вызов swap(*start, *end), который меняет указатель головы и tail (не указатель хвоста списка, а локальную переменную main()). 

 end                                            start
  |                                               |
  V                                               V
  tail                                            head
   |                                               |
   V                                               V
   ------------    ------------    ------------    ------------    
   | 6 | next | -> | 2 | next | -> | 1 | next | -> | 3 | NULL |
   ------------    ------------    ------------    ------------

Уже есть заметное отличие от первого случая в том, что узлы из списка без изменений. Хм ... ну, давайте продолжим и назовем swap(((*start)->next), (*end)->next), который поменяет указатели next в узлах, данные которых 3 и 6. Таким образом, узел 3 будет указывать на узел 2, а указатель 6 станет нулевым. Это то, что произошло в первом случае, так сработает? 

 end                                            start
  |                                               |
  V                                               V
  tail                                            head
   |                                               |
   V                                               V
   ------------    ------------    ------------    ------------    
   | 6 | NULL |    | 2 | next | -> | 1 | next | -> | 3 | next |
   ------------    ------------    ------------    ------------    
                   ^                                      |
                   |                                      |
                   L---------------------------------------

ПРОБЛЕМА! Мы остались с циклом! Что случилось с шагом, когда узел 1 был изменен, чтобы указывать на узел 6? Правильно, вместо этого мы изменили tail, и в результате получилась катастрофа.

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

  1. Избавьтесь от #include<bits/stdc++.h>; вместо этого включите заголовки, которые вам нужны. Для этого примера вам нужно просто #include <cstdio>.
  2. Сделать node private подробность реализации linkedList. Надежность имеет тенденцию увеличиваться вместе с герметизацией. Если никто не знает структуры данных, используемые linkedList, вы ограничиваете то, что может делать другой код. Имея меньше возможностей для учета, легче убедиться, что вы учли все из них.
  3. Не объявляйте поле (linkedList::tail), которое никогда не используется. Кто-то захочет использовать это поле в какой-то момент, не осознавая, что оно содержит мусор.

(Существуют и другие улучшения, которые, на мой взгляд, являются наиболее важными.)

...