VPF::Непредсказуемое поведение списка списков

AmXSe

Дата 21.4.2013, 23:57 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 18.3.2013

Репутация: нет
Всего: нет

Доброе время суток!
Есть список списков. При удалении и последующей вставке элементов в дочерние списки происходят непонятные вещи: указатель на конец дочернего списка неведомым образом становится "сам по себе" и теряется, посему вставка просто-напросто не происходит.

Добавление элемента в список:

Код


template <class T>
int List<T>::Add(T& rtData)
{
    Node *pnNode = new Node;

    if (!pnNode)    // Не можем выделить память
        return -1;

    pnNode->data = rtData;

    if (tail_ptr)
        tail_ptr->next_node_ptr = pnNode;
    else
        head_ptr = pnNode;

    tail_ptr = pnNode;

    size += 1;

    return size;
}

Удаление:

Код


template <class T>
bool List<T>::Delete(int nPos)
{
    if (nPos >= size || nPos < 0)
        return NULL;

    if (nPos == 0)        // Удаление первого элемента списка
    {
        Node *pnTemp = head_ptr->next_node_ptr;

        if (head_ptr)
            delete head_ptr;
        head_ptr = pnTemp;

        size--;

        if (!size)
            tail_ptr = NULL;

        return true;
    }

    Node *pnNode = head_ptr;

    for (int i = 0; i < nPos+1; i++)
    {
        if (i+1 == nPos)
        {
            if (!pnNode->next_node_ptr)
                return false;

            Node *pnTemp = pnNode->next_node_ptr->next_node_ptr;

            if (pnNode->next_node_ptr)
                delete pnNode->next_node_ptr;
            pnNode->next_node_ptr = pnTemp;

            size--;

            if (i+2 == size)    // Последний узел списка
                tail_ptr = pnNode;

            return true;
        }

        pnNode = pnNode ? pnNode->next_node_ptr : NULL;

        if (!pnNode)
            return false;
    }

    return false;
}

Проблема вылазит здесь:

Код


void tradeFatBunnies(ofstream &out, List<int> * island, List<int> &boat, int &free_capacity) {
    // Выторговать несколько худых кроликов на одного толстого островитянина
    if ( !island->Empty() && !boat.Empty() && island->Elem(0) != NULL ) {
        // ..

       ///////////////////////////////////////////////////////////////////
       ////                Проблема возникает ниже                     ////

        if (bunnies_to_trade_num > 0) {
            //int i = 0;
          for (int i = 0; i < bunnies_to_trade_num; i++) {
              island->Add( boat[0] );
              free_capacity += boat[0];
              boat.Delete(0);
          }

          boat.Add( weight_to_reach );
          free_capacity -= weight_to_reach;
        }
      ///////////////////////////////////////////////////////////////////
    }
}

При выполнении вывод примерно следующий:

Код


World state: 
----
21 19 18 5
28 27 26 26 25 24 16 15 8 4 1
27 24 19 19 12 12 5
22 21 20 16 12 8 3
29 24 22 12 11 8 8
26 23 15 12 5
15 15 15 11 10 5 5 5 1
24 22 21 15 11 10 1
29 25 20 11 4 3
25 18 12 10 10 3
----
Boat state: 
----
5 21
----
Boat state: 
----
28
----
Boat state: 
----
28
----
Boat state: 
----
28
----
Boat state: 
----
28
----
Boat state: 
----
28
----
Boat state: 
----
1 28
----
Boat state: 
----
1 28
----
Boat state: 
----
1 28
----
World state: 
----
19 18
28 27 26 26 25 24 16 15 8 4 
27 24 19 19 12 12 5
22 21 20 16 12 8 3
29 24 22 12 11 8 8
26 23 15 12 5
15 15 15 11 10 5 5 5
24 22 21 15 11 10 1
29 25 20 11 4 3
25 18 12 10 10 3
----

Тогда как для взятого случая ожидается вот что:

Код


World state: 
----
21 19 18 5
28 27 26 26 25 24 16 15 8 4 1
27 24 19 19 12 12 5
22 21 20 16 12 8 3
29 24 22 12 11 8 8
26 23 15 12 5
15 15 15 11 10 5 5 5 1
24 22 21 15 11 10 1
29 25 20 11 4 3
25 18 12 10 10 3
----
Boat state: 
----
5 21
----
Boat state: 
----
28
----
Boat state: 
----
28
----
Boat state: 
----
28
----
Boat state: 
----
28
----
Boat state: 
----
28
----
Boat state: 
----
1 28
----
Boat state: 
----
1 28
----
Boat state: 
----
1 28
----
World state: 
----
19 18
27 26 26 25 24 16 15 8 4 5 21
27 24 19 19 12 12 5
22 21 20 16 12 8 3
29 24 22 12 11 8 8
26 23 15 12 5
15 15 15 11 10 5 5 5
24 22 21 15 11 10 1
29 25 20 11 4 3
25 18 12 10 10 3
----

Как быть?
Помогите, пожалуйста, разрешить ситуацию.

P.S.: В аттаче полный код

Присоединённый файл ( Кол-во скачиваний: 4 )

krs_proj.7z 949,59 Kb

mes

Дата 22.4.2013, 00:26 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(AmXSe @ 21.4.2013, 22:57

)

if (tail_ptr)
        tail_ptr->next_node_ptr = pnNode;
    else
        head_ptr = pnNode;
    tail_ptr = pnNode;

сомнительно..

--------------------

http://opendots.net

kolesnle

Дата 22.4.2013, 00:30 (ссылка)

(нет голосов)

Загрузка ...

Упертый сишник

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 22.3.2013

Репутация: нет
Всего: нет

+ Кажется по теме, у каждого контейнера должны быть итераторы begin(), end()
Если надумаешь, вот реализация итератора:

Код


template <typename iteratorValueType>
    struct vector_iterator
    {
        typedef iteratorValueType value_type;
        typedef iteratorValueType& reference;
        typedef iteratorValueType* pointer;
        typedef std::random_access_iterator_tag iterator_category;
        typedef std::ptrdiff_t difference_type;
        typedef std::ptrdiff_t distance_type;
 
        explicit vector_iterator(const pointer value = pointer()) :
        _value(const_cast<pointer>(value))
        {
        }
 
        vector_iterator& operator ++ ()
        {
            ++_value;
            return *this;
        }
 
        vector_iterator operator ++ (int)
        {
            return vector_iterator(_value++);
        }
 
        vector_iterator& operator -- ()
        {
            --_value;
            return *this;
        }
 
        vector_iterator operator -- (int)
        {
            return vector_iterator(_value--);
        }
 
        bool operator < (const vector_iterator& value) const
        {
            return _value < value._value;
        }
 
        bool operator != (const vector_iterator& value) const 
        {
            return _value != value._value;
        }
 
        bool operator == (const vector_iterator& value) const 
        {
            return _value == value._value;
        }
 
        difference_type operator - (const vector_iterator& value) const 
        {
            return _value - value._value;
        }
 
        vector_iterator operator - (distance_type value) const
        {
            return vector_iterator(_value - value);
        }
 
        vector_iterator operator + (distance_type value) const 
        {
            return vector_iterator(_value + value);
        }
 
        reference operator * ()
        {
            return *_value;
        }
 
        pointer operator -> ()
        {
            return _value;
        }
 
    private:
        pointer _value;
    };

А также функция size(). Я думаю это упростит работу, и указатели теряться не будут.

Это сообщение отредактировал(а) kolesnle - 22.4.2013, 00:44

AmXSe

Дата 22.4.2013, 01:51 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 18.3.2013

Репутация: нет
Всего: нет

mes, а как иначе здесь? Вроде всё просто: обновляем указатель на соседа у последнего элемента, затем обновляем ссылку на последний элемент в самом списке. Если конец списка не установлен, то полагаем что список пуст и так же обновляем указатель на голову.

kolesnle, в данном конкретном случае вроде не понадобится - указанный баг это единственное что отделяет меня от победы над задачей. Но на будущее учту, спасибо!

Это сообщение отредактировал(а) AmXSe - 22.4.2013, 01:53

mes

Дата 22.4.2013, 02:23 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(AmXSe @ 22.4.2013, 00:51

)

. Если конец списка не установлен, то полагаем что список пуст и так же обновляем указатель на голову.

ну а про следущую строчку зачем умолчали? smile

Цитата(AmXSe @ 21.4.2013, 22:57

)

tail_ptr = pnNode;

Добавлено через 6 минут и 38 секунд

Цитата(AmXSe @ 22.4.2013, 00:51

)

указанный баг это единственное что отделяет меня от победы над задачей

Цитата(AmXSe @ 21.4.2013, 22:57

)

Node *pnTemp = pnNode->next_node_ptr->next_node_ptr;

тут тоже сомнительно..

может стотит вначале самому уделить внимание и написать логику в более читаемом виде ?

--------------------

http://opendots.net

kolesnle

Дата 22.4.2013, 09:24 (ссылка)

(нет голосов)

Загрузка ...

Упертый сишник

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 22.3.2013

Репутация: нет
Всего: нет

+ Зачем #pragma once, если ты уже написал #ifdef...#define..#endif?

Добавлено через 14 минут и 47 секунд
+ Не используй NULL, он определен, как

Код


#define NULL (void*)0

Используй nullptr.

kolesnle

Дата 22.4.2013, 09:40 (ссылка)

(нет голосов)

Загрузка ...

Упертый сишник

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 22.3.2013

Репутация: нет
Всего: нет

+ Используй быструю сортировку

Добавлено @ 09:43
Определи begin, end, size хотя бы так

Код


    Node* begin(){ return head_ptr; }
    Node* end() { return tail_ptr+1; }
    size_t size() {return size;}

А лучше используй итераторы.

Добавлено @ 09:50

[/code]

Это сообщение отредактировал(а) kolesnle - 22.4.2013, 21:13

kolesnle

Дата 22.4.2013, 09:59 (ссылка)

(голосов:1)

Загрузка ...

Упертый сишник

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 22.3.2013

Репутация: нет
Всего: нет

+ секцию private: обычно располагают в конце, public: в начале, а protected: в середине

AmXSe

Дата 22.4.2013, 13:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 18.3.2013

Репутация: нет
Всего: нет

mes,
kolesnle, спасибо за ответы.
Рефакторинг проделаю.

Как оказалось, проблема возникала при удалении последнего элемента списка - криво обновлялся указатель на хвост. Переписал полностью.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »