Nano Hash - криптовалюты, майнинг, программирование

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

Ниже приведен связанный список, написанный на C++, с классом Node и основной функцией. Список перемещается вперед с использованием функции next(), но выдает ошибку времени выполнения при переходе назад с использованием back().

#include <iostream>
using namespace std;

class Node {
    public:
        int object;
        Node *nextNode;
        Node *prevNode;
        
    public:
        
        int get(){
            return object;
        }
        
        void set(int object){
            this->object = object;
        }
        
        Node* getNext(){
            return nextNode;
        }
        
        void setNext(Node *nextNode){
            this->nextNode = nextNode;
        }
        
        Node* getPrev(){
            return prevNode;
        }
        
        void setPrev(Node *prevNode){
            this->prevNode = prevNode;
        }
        
    
};


class List {
    public:
        Node* headNode;
        Node* currentNode;
        int size;
    
    public:
        
        List(){
            headNode = new Node();
            headNode->setNext(NULL);
            headNode->setPrev(NULL);
            currentNode = NULL;
            int size = 0;   
        }
        
        void add(int addObject){
            Node* newNode = new Node();
            newNode->set(addObject);
            
            if(currentNode != NULL){
                newNode->setNext(currentNode->getNext());
                newNode->setPrev(currentNode);
                currentNode->setNext(newNode);
                currentNode = newNode;
                            
            }
            else {
                newNode->setNext(NULL);
                newNode->setPrev(headNode);
                headNode->setNext(newNode);
                currentNode = newNode;
            }
            
            size++;
    
        }
        
        int get(){
            if(currentNode != NULL) {
                return currentNode->get();
            }
        } 
        
        bool next(){
            if(currentNode == NULL) return false;
            
            currentNode = currentNode->getNext();
            
            if(currentNode == NULL) return false;
            else                    return true;
        
        }
        
        bool back(){
            if(currentNode == NULL) return false;
            currentNode = currentNode->getPrev();
            
            if(currentNode == NULL) return false;
            else return true;
        }
        
        void start(){
            currentNode = headNode;
        }
        
        void remove() {
            if (currentNode != NULL && currentNode != headNode){
                delete currentNode;
                size--;
            }
        }
        
        int length() {
            return size;
        }
        
};


int main(){
    
    List list;
    
    list.add(5);
    list.add(13); 
    list.add(4);
    list.add(8);
    list.add(48);
    list.add(12); 
    
    list.start(); 
    
    while(list.next()){
        cout<<endl<<"Element: " << list.get() << endl;
    }
     
    cout<<endl<<"BACK"<<endl;

    while(list.back()){
        cout<<endl<<"Element: " << list.get() << endl;
    } 
}

Функция Back() должна перемещаться по списку в противоположном направлении (от конца к началу).. в обратном порядке. Иногда этот код подвешивает процессор, а иногда запускает только функцию next(), а для функции back() он молчит, ничего не делая.


  • возможно, это связано с тем, что ваша функция get ничего не возвращает, если возникает Null 18.09.2020
  • Вы пытались отладить свой код и проверить, что указатели указывают на ожидаемые местоположения? 18.09.2020
  • Я пытался отлаживать, но смог найти 18.09.2020
  • Когда вы вставляете новые узлы в add, вы обновляете указатель current->next. Но вы не можете обновить current->next->prev, поэтому обратная структура никогда не будет правильно сформирована. 18.09.2020
  • @Asad Razaq Просто выбросьте этот плохой код в мусорное ведро и заново перепишите реализацию списка :) 18.09.2020
  • Не нашел что? Пройдитесь по коду и посмотрите, делает ли он то, что вы ожидаете. 18.09.2020
  • @Asad Razaq Нет особого смысла использовать ток указателя. Список должен иметь два указателя: на головной узел и на хвостовой узел. 18.09.2020
  • @Frodyne Я рассмотрел предыдущую версию, используя эту строку: newNode-›setPrev(currentNode); 18.09.2020
  • @Asad Razaq Этот фрагмент кода в конструкторе headNode = new Node(); //... текущийУзел = NULL; логически непоследовательна и только сбивает с толку читателей кода. 18.09.2020
  • Я не уверен, почему он может зависнуть, но back() всегда будет возвращать false в этом коде, потому что currentNode будет NULL (вместо этого следует использовать nullptr) после последнего вызова next() в первом цикле. Также у вас есть ошибка в функции remove(): вам нужно настроить указатели вокруг удаленного элемента. 18.09.2020

Ответы:


1

Сначала исправим код:

 bool next(){
        if(currentNode == nullptr)  return false; 
        // if next is null we are at the end, don't go futher
        if (  currentNode->getNext() == nullptr ) return false;
        currentNode = currentNode->getNext();
        return true;
    }
    
    bool back(){
        if(currentNode == nullptr) return false;
        
        // if prev is head, we are at the start, stop here 
        if ( currentNode->getPrev() == headNode) return false;
        currentNode = currentNode->getPrev();
       
        return true;
    }

Логика:

// we are at the last element, so we have to print BEFORE going back
do{
    cout<<endl<<"Element: " << list.get() << endl;
} while (list.back());

Прямая демонстрация


Предупреждения:

предупреждение: неиспользуемая переменная 'size'

В этом случае с этим предупреждением все в порядке, вы можете использовать метод length(), если хотите избавиться от него.

В функции-члене 'int List::get()': предупреждение: управление достигает конца непустой функции [-Wreturn-type]

В вашем методе get if(currentNode == nullptr ) вы ничего не возвращаете, и это вызовет ошибку. Один из способов исправить это — throw создать исключение.

int get(){
    if(currentNode == nullptr ) {
       throw std::logic_error("CurrentNode is null");
    }
    return currentNode->get();
} 

Лично я думаю, что лучшим решением будет: кодировать все функции-члены List так, чтобы currentNode не могло быть нулевым.


Управление памятью

Вы создаете свой узел с помощью new, но никогда не используете delete, поэтому у вас есть утечка памяти. Проверьте valgrind (веб-сайт или этот хороший пост), он очень полезен.

valgrind ./leaky --leak-check=full
....
==3225== HEAP SUMMARY:
==3225==     in use at exit: 168 bytes in 7 blocks
==3225==   total heap usage: 9 allocs, 2 frees, 73,896 bytes allocated
==3225== 
==3225== LEAK SUMMARY:
==3225==    definitely lost: 24 bytes in 1 blocks 
==3225==    indirectly lost: 144 bytes in 6 blocks
==3225==      possibly lost: 0 bytes in 0 blocks
==3225==    still reachable: 0 bytes in 0 blocks
==3225==         suppressed: 0 bytes in 0 blocks

Так что да, valgrind нашел утечку.

Вам нужно добавить деструктор.

~List(){
       // first be sure that we are at one end
       while (next()) {}
        
       while (back())
       {
           std::cout << "delete the node we just left : " << currentNode->getNext()->get() << std::endl;
           delete currentNode->getNext();
       }
       // don't forget this one (without valgrind I will have miss it!)
       delete currentNode;

       std::cout << "finaly we clear the head" << std::endl;
       delete headNode;
}

Но теперь, если мы напишем:

List list2 = list;

У нас есть :

double free or corruption (fasttop)

Потому что у нас есть 2 объекта, пытающихся удалить одну и ту же память.

Мы можем просто запретить копирование:

 List(const List&) = delete;
 List& operator=(const List&) = delete;

Обычно большая часть управления памятью осуществляется с помощью умного указателя< /а>.


Видимость:

Используйте private для своих атрибутов:

private :
    int object;
    Node *nextNode;
    Node *prevNode;

а также

private:
    Node* headNode;
    Node* currentNode;
    size_t size = 0;
 

Окончательная версия: Демо

Проверьте с помощью valgrind:

==3532== HEAP SUMMARY:
==3532==     in use at exit: 0 bytes in 0 blocks
==3532==   total heap usage: 9 allocs, 9 frees, 73,896 bytes allocated
==3532== 
==3532== All heap blocks were freed -- no leaks are possible

Течи нет, все хорошо ;)

Надеюсь, поможет !

19.09.2020
Новые материалы

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

Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..

Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..

Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..

Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..

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

Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..