Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.60
Spellz
1 / 1 / 0
Регистрация: 29.01.2010
Сообщений: 25
#1

Связанный двусторонний список - C++

29.06.2010, 19:57. Просмотров 1872. Ответов 19
Метки нет (Все метки)

Решил написать свой двусторонний список и совершенно внезапно столкнулся с проблеммой отчистки. Итак вот класс элемента списка и его деструктор:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class T>
class mListNode
{
public:
    mListNode();
    mListNode(const mListNode<T>&);
    ~mListNode();
    void setNext(mListNode* newNext) { next = newNext;};
    void setPrev(mListNode* newPrev) { prev = newPrev;};
    void setInfo(T* inf)             { info = inf;  };
    mListNode* getNext() const       { return next; };
    mListNode* getPrev() const       { return prev; };
    T* getInfo() const               { return info; };
    mListNode<T>& operator= (const mListNode<T>&);
protected:
    T* info;
    mListNode* prev;
    mListNode* next;
};
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class T>
mListNode<T>::~mListNode()
{
    cout << "info\n";
    delete info;
    info = NULL;
    cout << "prev\n";
    delete prev;
    prev = NULL;
    cout << "next\n";
    delete next;
    next = NULL;
}
Объявления класса списка, функции удаления:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class T>
class mList
{
public:
    mList() { size = 0; head = 0;};
    mList(const mList<T>&);
    //~mList();
    void pushBack(T& inf);                      
    void pushTop(T& inf);                       
    mList<T>& operator=(const mList<T>&);
    T& operator[] (unsigned int num) const ;    
    void clear();                              
    void popFront();
    class exOutOfRange { };                     // oor exeption
protected:
    mListNode<T>* head;
    unsigned int size;
};
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <class T>
void mList<T>::clear()
{
    if (size == 0)
        return;
    while (size != 0)
    {
        popFront();
    }
 
}
template <class T>
void mList<T>::popFront()
{
    if (size == 0)
        return;
    mListNode<T>* tmp = head;
    head = head->getNext();
    delete tmp;
    size--;
    head->setPrev(NULL);
 
}
Подабавлял int, нормально выводит. При попытке вытолкнуть элемент или очистить (впринципе одно и тоже) программа крашиться в консоли последняя строчка info (см деструктор элемента списка) и вываливается сообщение:

Debug Assertion Failed!
...dbgdel.cpp
line:52

Expression: _BLOCK_TYPE_IS_VALID (pHead->nBlockUse)

Как понимаю я по многу раз удаляю одно и тоже, но никак не могу понять где утечка >.<
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2010, 19:57     Связанный двусторонний список
Посмотрите здесь:

C++ Однонаправленный связанный список
C++ Связанный список.
C++ Связанный список
Связанный список C++
Связанный список C++
двусторонний список C++
C++ Связанный список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
time2die
51 / 51 / 3
Регистрация: 25.05.2010
Сообщений: 182
29.06.2010, 20:20     Связанный двусторонний список #2
хм.... у тебя есть спсок
x----y----z
потом ты удалил y и получилось
x----мусор---z
как, бы при удалении члена списка, нужно перевязать у соседних элементов указатели на следующий и предыдущий
Spellz
1 / 1 / 0
Регистрация: 29.01.2010
Сообщений: 25
29.06.2010, 20:39  [ТС]     Связанный двусторонний список #3
Так я удаляю не из серидины а выталкиванием первого элемента
C++
1
2
3
4
5
6
7
8
9
10
11
12
template <class T>
void mList<T>::popFront()
{
    if (size == 0)
        return;
    mListNode<T>* tmp = head;
    head = head->getNext();
    delete tmp;
    size--;
    head->setPrev(NULL);
 
}
тут я выбираю начальным элементом второй элемент списка, после этого удаляю первый, а у второго предыдущий элемент ставлю равным нулю.
time2die
51 / 51 / 3
Регистрация: 25.05.2010
Сообщений: 182
29.06.2010, 21:15     Связанный двусторонний список #4
прости, за глупый вопрос, но зачем тебе в связном списке функция pop и push ? не легче, если у тебя уже есть add & delete, реализовать их через них ?
Spellz
1 / 1 / 0
Регистрация: 29.01.2010
Сообщений: 25
29.06.2010, 22:05  [ТС]     Связанный двусторонний список #5
тоесть как зачем функция push? это собственно и есть add, а pop = delete. Но вопрос не об этом, а о том, что собсвенно pop и выдает ошибку.

Кстати если убрать мой деструктор элемента списка программа не крашиться, но и память собственно не освобождается >.<
mih
6 / 6 / 1
Регистрация: 10.05.2010
Сообщений: 56
29.06.2010, 22:16     Связанный двусторонний список #6
попробуй [] после delete...
time2die
51 / 51 / 3
Регистрация: 25.05.2010
Сообщений: 182
29.06.2010, 22:16     Связанный двусторонний список #7
Spellz, чего-то я сегодня не соображаю ничего, как насчёт посмотрет ьв дебаггере на каком именно моменте программа крашится ?
Spellz
1 / 1 / 0
Регистрация: 29.01.2010
Сообщений: 25
29.06.2010, 22:40  [ТС]     Связанный двусторонний список #8
Цитата Сообщение от mih Посмотреть сообщение
попробуй [] после delete...
delete[] удаляет указатель на массив и собственно сам массив в динамической памяти, если я ничего не путаю. В любом случае попробовал, не работает.


Цитата Сообщение от time2die Посмотреть сообщение
Spellz, чего-то я сегодня не соображаю ничего, как насчёт посмотрет ьв дебаггере на каком именно моменте программа крашится ?
Программа крашиться при попытке приминения функций pop или clear. Если быть точнее, тогда когда программа "попадает" в деструктор mListNode
mih
6 / 6 / 1
Регистрация: 10.05.2010
Сообщений: 56
29.06.2010, 23:24     Связанный двусторонний список #9
а как насчет конструктора mListNode ?
в студию плиз...

Добавлено через 14 минут
оо новая теория ))
в ~mListNode не надо delete Next и Prev
о как )))
Spellz
1 / 1 / 0
Регистрация: 29.01.2010
Сообщений: 25
29.06.2010, 23:24  [ТС]     Связанный двусторонний список #10
Копий
C++
1
2
3
4
5
6
7
template <class T>
mListNode<T>::mListNode(const mListNode<T> & rhs)
{   
    info = rhs.info;
    prev = rhs.prev;
    next = rhs.next;
}
Обычный
C++
1
2
3
4
5
template <class T>
mListNode<T>::mListNode():
info(0) , prev(0), next(0)
{
}
mih
6 / 6 / 1
Регистрация: 10.05.2010
Сообщений: 56
29.06.2010, 23:29     Связанный двусторонний список #11
ну не удаляй next и prev и да прибудет стобой сила
Spellz
1 / 1 / 0
Регистрация: 29.01.2010
Сообщений: 25
29.06.2010, 23:38  [ТС]     Связанный двусторонний список #12
Прога подвисает на удаление info, до next и prev еще не доползли
mih
6 / 6 / 1
Регистрация: 10.05.2010
Сообщений: 56
29.06.2010, 23:46     Связанный двусторонний список #13
в таком случае +main
Spellz
1 / 1 / 0
Регистрация: 29.01.2010
Сообщений: 25
29.06.2010, 23:57  [ТС]     Связанный двусторонний список #14
всмысле?
mih
6 / 6 / 1
Регистрация: 10.05.2010
Сообщений: 56
30.06.2010, 00:30     Связанный двусторонний список #15
выкладывай всю прогу
Spellz
1 / 1 / 0
Регистрация: 29.01.2010
Сообщений: 25
30.06.2010, 02:44  [ТС]     Связанный двусторонний список #16
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <iostream>
using namespace std;
 
#ifndef MLIST_H
#define MLIST_H
//                      Class mListNode - node of my List Container class
template <class T>
class mListNode
{
public:
    mListNode();
    mListNode(const mListNode<T>&);
    ~mListNode();
    void setNext(mListNode* newNext) { next = newNext;};
    void setPrev(mListNode* newPrev) { prev = newPrev;};
    void setInfo(T* inf)             { info = inf;  };
    mListNode* getNext() const       { return next; };
    mListNode* getPrev() const       { return prev; };
    T* getInfo() const               { return info; };
    mListNode<T>& operator= (const mListNode<T>&);
protected:
    T* info;
    mListNode* prev;
    mListNode* next;
};
 
template <class T>
mListNode<T>::mListNode(const mListNode<T> & rhs)
{
    cout << "in COPY ctor of node\n";   
    info = rhs.info;
    prev = rhs.prev;
    next = rhs.next;
    cout << "exit COPY ctor of node\n";
}
template <class T>
mListNode<T>& mListNode<T>::operator =(const mListNode<T> &rhs)
{
    if (this == &rhs)
        return *this;
    delete info;
    delete prev;
    delete next;
    info = rhs.info;
    prev = rhs.prev;
    next = rhs.next;
    return *this;
}
template <class T>
mListNode<T>::mListNode():
info(0) , prev(0), next(0)
{
    //cout << "in ctor of node\n";
    //cout << "exit ctor of node\n";
}
 
template <class T>
mListNode<T>::~mListNode()
{
    cout << "info\n";
    delete info;
    info = NULL;
    cout << "prev\n";
    delete prev;
    prev = NULL;
    cout << "next\n";
    delete next;
    next = NULL;
}
 
 
//                      Class mList - my List Container
 
template <class T>
class mList
{
public:
    mList() { size = 0; head = 0;};
    mList(const mList<T>&);
    //~mList();
    void pushBack(T& inf);                      //добавляет информацию в конец списка
    void pushTop(T& inf);                       //добавляет информацию в начало списка
    mList<T>& operator=(const mList<T>&);
    T& operator[] (unsigned int num) const ;    //получение информации основываясь на номере в списке
    void clear();                               //отчистка списка
    void popFront();
    class exOutOfRange { };                     // oor exeption
protected:
    mListNode<T>* head;
    unsigned int size;
};
 
template <class T>
mList<T>::mList(const mList& rhs)
{
    head = rhs.head;
    size = rhs.size;
}
template <class T>
mList<T>& mList<T>::operator =(const mList<T> &rhs)
{
    if (this == &rhs)
        return *this;
    delete head;
    head = rhs.head;
    size = rhs.size;
}
 
template <class T>
T& mList<T>::operator[] (unsigned int num) const
{
    if (num > size - 1)
        throw exOutOfRange();
    mListNode<T>* tmp = head;
    for (unsigned int i = 0; i < num; i++)
    {
        tmp = tmp->getNext();
    }   
    T& info = *(tmp->getInfo());    
    return info;
}
 
template <class T>
void mList<T>::pushBack(T& inf)
{
    
    if (size == 0)
    {
        head = new mListNode<T>;
        head->setInfo(&inf);
        size++;
        return;
    }
    else
    {
        mListNode<T>* newNode = new mListNode<T>;
        mListNode<T>* current = head;
        mListNode<T>* next = 0;
        newNode->setInfo(&inf);
 
#define ever ;;
        for(ever)
        {
            next = current->getNext();
            if (next == NULL) //следущего нету - сюда и ставим
            {
                newNode->setPrev(current);
                newNode->setNext(NULL);
                current->setNext(newNode);
                break;
            }
            else //идем дальше
                current = next;
        }
 
    }
}
 
template <class T>
void mList<T>::pushTop(T& inf)
{
    if (head == NULL)
    {
        head = new mListNode<T>;
        head->setInfo(&inf);
        head->setPrev(NULL);
        head->setNext(NULL);
        size++;
        return;
    }
    else
    {
        mListNode<T>* newNode = new mListNode<T>;
        newNode->setInfo(&inf);
        newNode->setNext(head);
        newNode->setPrev(NULL);
        head->setPrev(newNode);
 
        head = newNode;
        size++;
    }
}
 
template <class T>
void mList<T>::clear()
{
    if (size == 0)
        return;
    while (size != 0)
    {
        popFront();
    }
 
}
template <class T>
void mList<T>::popFront()
{
    if (size == 0)
        return;
    mListNode<T>* tmp = head;
    head = head->getNext();
    delete tmp;
    size--;
    head->setPrev(NULL);
 
}
#endif
собственно почти все уже было выложенно

Добавлено через 1 час 55 минут
Убрав деструктор mListNode все прекрасно удаляется с одним но: память не освобождается. Тоесть я динамически создаю элементы, которые стандартный деструктор удалить не может. В свою же очередь мой деструктор вылетает с критической ошибкой. Застрелиться можно >.<
mih
6 / 6 / 1
Регистрация: 10.05.2010
Сообщений: 56
30.06.2010, 06:51     Связанный двусторонний список #17
да, но все таки main....

Добавлено через 8 минут
кста, конструктор копирования и перегруженый оператор присваивания не совсем верно работают...
они у тя ссылки копируют, а должны выделять дин.память у туда копировать обьекты...
Spellz
1 / 1 / 0
Регистрация: 29.01.2010
Сообщений: 25
30.06.2010, 09:11  [ТС]     Связанный двусторонний список #18
ммм так я не один не сплю ) ладно щаз посмотрим

Добавлено через 1 час 8 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "mList.h"
using namespace std;
 
int main()
{
 
    mList<int> thelist;
    for (int i =0; i <2; i++)
        thelist.pushBack(i);
    char res;
    cin >> res;
    thelist.clear();
    cin >> res;
    for (int i =0; i <10000; i++)
        thelist.pushBack(i);
    cin >> res;
    thelist.clear();
    for (int i =0; i <10000; i++)
        thelist.pushBack(i);
    cin >> res;
    return 0;
}
вот мейн, собственно не вижу в нем ничего такого, что бы могло привести к сбою. Кстати конструктор копий и оператор присваивания нигде не используются, проверил путем вывода сообщения об их использовании. Собственно сообщений получил ноль.
mih
6 / 6 / 1
Регистрация: 10.05.2010
Сообщений: 56
30.06.2010, 11:14     Связанный двусторонний список #19
фуух, мой мозк...

функция setInfo устанавливает T*info на обычную переменную из main, а потом пытается ее удалить ))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.06.2010, 19:35     Связанный двусторонний список
Еще ссылки по теме:

Связанный список. Создать, записать в связный список последовательность слов,обозначающих месяцы года,заданных пользователем C++
Создать связанный список C++
И снова связанный список C++
C++ Связанный список (ООП)
Циклический связанный список C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Spellz
1 / 1 / 0
Регистрация: 29.01.2010
Сообщений: 25
30.06.2010, 19:35  [ТС]     Связанный двусторонний список #20
эм собственно это была одна из проблем, но не главная. суть была в том, что я сначало удалял объект, а потом пытался отвязать его от списка, ес-сно этого не происходило. вместо этого деструкторы врубались по цепочке удаляя сами себя бесконечное количество раз и вводя программу в полный хаос. но всеравно спасибо за помощ )
Yandex
Объявления
30.06.2010, 19:35     Связанный двусторонний список
Ответ Создать тему
Опции темы

Текущее время: 01:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru