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

Двунаправленный кольцевой список (удаление узлов) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
MarVaL
С++ Beginner
 Аватар для MarVaL
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
13.05.2013, 16:09     Двунаправленный кольцевой список (удаление узлов) #1
Помогите с удалением узлов из списка(~List). Не знаю как правильно удалять

Кликните здесь для просмотра всего текста
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
#include <iostream>
 
typedef int dataList;
 
class List {
public:
    List();
    List(dataList d);
    ~List();
    void addNode(dataList d);
    void showList();
private:
    dataList data;
    List *next;
    List *prev;
} *Head = NULL, *Temp = NULL;
 
List::List() { }
 
List::List(dataList d)
    : data(d), next(NULL), prev(NULL) { }
 
void List::addNode(dataList d) {
    List *node = new List(d);
    if(!Head) {
        Head = node;
        Temp = node;
    } else {
        node->next = Head;
        node->prev = Temp;
        Temp->next = node;
        Temp = node;
    }
    
}
 
void List::showList() {
    List *show = Head;
    while(true) {
        std::cout << show->data << ' ';
        show = show->next;
        if(show == Head)
            break;
    }
}
 
List::~List() {
    while(Head != NULL) {
        List *tmp = Head;
        delete tmp;
        Head = Head->next;
    }
}
 
int main() {
    List list;
    list.addNode(3);    
    list.addNode(4);
    list.addNode(5);
    list.showList();
    
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
13.05.2013, 16:16     Двунаправленный кольцевой список (удаление узлов) #2
MarVaL, Да удаляй например с конца указателю предыдущему который указывает на последний элемент присвой 0 и все, ну можешь еще и память высвободить сохранив адрес на последний элемент и вызвав delete указатель на последний элемент.
MarVaL
С++ Beginner
 Аватар для MarVaL
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
13.05.2013, 16:18  [ТС]     Двунаправленный кольцевой список (удаление узлов) #3
Цитата Сообщение от ninja2 Посмотреть сообщение
MarVaL, Да удаляй например с конца указателю предыдущему который указывает на последний элемент присвой 0 и все, ну можешь еще и память высвободить сохранив адрес на последний элемент и вызвав delete указатель на последний элемент.
Можешь написать, или поподробнее плз
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
13.05.2013, 16:29     Двунаправленный кольцевой список (удаление узлов) #4
Цитата Сообщение от MarVaL Посмотреть сообщение
Можешь написать, или поподробнее плз
Поподробнее от допустим у тебя есть указатель
List* next; на следущий элемент указывает
List* prev; указывает на предыдущий
List* tek; указывает на текущий элемент, где мы щас находимся.

Если next=0 то значит мы в конце списка, если prev = 0, то значит мы в начале списка.
Допустим мы находимся в элементе (узле) в котором next=0, а prev не равно 0, то есть список не пустой. Нам нужно удалить этот элемент в котором мы щас находимся делаем tek=prev; tek->next=0 и все мы как бы удалили (в списке его уже не будет), но нам еще нужно память высвободить для системы, поэтому мы предже чем tek=prev; делаем Link* del=tek;, то есть адрес сохраняем чтобы можно было сделать delete del; - высвободить память. Ну примерно так:
C++
1
2
3
4
Link* del=tek;
tek=tek->prev;
tek->next=0;
delete del;//высвобождение памяти.
Примерно так. Конкретно в твоем случае я не смотре, главное это принцип идея
MarVaL
С++ Beginner
 Аватар для MarVaL
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
13.05.2013, 16:42  [ТС]     Двунаправленный кольцевой список (удаление узлов) #5
Ошибка вылетает делаю так:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
while(curr) {
        List *del = curr;
        curr = curr->prev;
        curr->next = 0;
        delete del;
    }

Указатель List *curr добавил в класс. В addNode в конце делаю curr = node;
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
13.05.2013, 16:48     Двунаправленный кольцевой список (удаление узлов) #6
Если у тебя кольцевой список то я не глянул то у тебя next в последнем элементе не будет равно 0, а будет указывать на первый а prev в первом элементе на последний. А чтобы удалить из средины списка тебе нужно просто допустим ты находишься в текущем элементе который ты хочешь удалить , где то в средине списка next - это следующий элемент prev - это предыдущий мы в tek - в текущем элементе, что нам делать? tek у нас должен стать допустим prev. Делаем tek=tek->prev; Элемент который у нас был до этого tek->next->prev должен стать tek->prev; ,Нам нужно еще и сохранить текущий адрес для удаления Link* del=tek; , еще нужно tek->prev->next выставить правильно. Щас попытаюсь правильную последовательность написать, потому что если что то перепутать, то оно работать как надо не будет.
Делаешь так ты в текущем элементе (обязательно есть следущий и предыдущий)
C++
1
2
3
4
5
List* del=tek; //сохраняем адрес для высвобождения памяти
tek->prev->next=tek->next; //меняем ссылки мимо текущего элемента
tek->next->prev=tek->prev;//то же самое
tek=tek->prev;//присваиваем текущим элемент который предыдищий.
delete del; //высвобождение памяти
Тут нужно проверять потому что я без проверки так с головы набрал, возможно ошибся где то. Нужно проверять.
MarVaL
С++ Beginner
 Аватар для MarVaL
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
13.05.2013, 17:07  [ТС]     Двунаправленный кольцевой список (удаление узлов) #7
Ошибка. Как и говорил добавил в класс - List *curr; addNode - curr = node;
Кликните здесь для просмотра всего текста
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
#include <iostream>
 
typedef int dataList;
 
class List {
public:
    List();
    List(dataList d);
    ~List();
    void addNode(dataList d);
    void showList();
private:
    dataList data;
    List *next;
    List *prev;
    List *curr;
} *Head = NULL, *Temp = NULL;
 
List::List() { }
 
List::List(dataList d)
    : data(d), next(NULL), prev(NULL) { }
 
void List::addNode(dataList d) {
    List *node = new List(d);
    if(!Head) {
        Head = node;
        Temp = node;
    } else {
        node->next = Head;
        node->prev = Temp;
        Temp->next = node;
        Temp = node;
    }
    curr = node;
}
 
void List::showList() {
    List *show = Head;
    while(true) {
        std::cout << show->data << ' ';
        show = show->next;
        if(show == Head)
            break;
    }
}
 
List::~List() {
    while(curr) {
        List* del = curr;
        curr->prev->next = curr->next;
        curr->next->prev = curr->prev;
        curr = curr->prev;
        delete del; 
    }
}
 
int main() {
    List list;
    list.addNode(3);    
    list.addNode(4);
    list.addNode(5);
    list.showList();
    
    return 0;
}
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
13.05.2013, 17:29     Двунаправленный кольцевой список (удаление узлов) #8
MarVaL, Не знаю разбирай при создании List list у тебя все указатели должны нулями быть
при добавлении элемента list.addNode просто проверяй если cur=0, то значит список пустой cur=new
Попробуй разделить на класс List и на List_intarface допустим так (либо Node и List)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class List
{
Link* next;
Link* prev;
int data; //данные
public:
List(int d):next(0),prev(0),data(d){};
};
class List_interface
{
List* cur; //Хранит указатель на элемент
public:
//...
//тут пошли методы для работы с классом. add(), del(), print() и. т. д.
};
Так бы было б более правильно

Попробуй такой метод:
C++
1
2
3
4
5
6
7
8
9
10
void List::addNode(dataList d) {
    List *node = new List(d);
    if(curr==0) {//пустой список
        curr=node;
    } else {//есть елементы
        curr->next=node;
        node->prev=curr;
        curr=node;
    }
}
Так должно работать.

Добавлено через 2 минуты
Это для двусвязного списка не кольцевой.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2013, 17:30     Двунаправленный кольцевой список (удаление узлов)
Еще ссылки по теме:

C++ Кольцевой, связанный, двунаправленный список
C++ Двунаправленный список (добавление/удаление/сортировка)

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

Или воспользуйтесь поиском по форуму:
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
13.05.2013, 17:30     Двунаправленный кольцевой список (удаление узлов) #9
MarVaL,
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
#include <iostream>
#include <set>
#include <vector>
#include <limits>
#include <stdio.h>
#include <string>
#include <queue>
#include <time.h>
#include <cmath>
 
using namespace std;
 
template <typename E>
class Tlist{
public:
    struct list{
        E inf;
        list * next;
        list * prev;
    };
    //----
    list * head;
    list * tail;
    list * cur;
    //----
    list * init_list(){ 
        return NULL;
    };
    //----
    E pop_front(){
        list * r = head;
        E k = head->inf;
        if (head->next == NULL)
            head = tail = NULL;
        else {
            head = head->next;
            head->prev = NULL;
        };
        delete r;
        return k;
    };
    //----
    E pop_back(){
        list * r = tail;
        E k = tail->inf;
        if (tail->prev == NULL)
            head = tail = NULL;
        else {
            tail = tail->prev;
            tail->next = NULL;
        };
        delete r;
        return k;
    };
    //----
    void push_back(E key){
        list * r = new list;
        r->next = NULL;
        r->prev = NULL;
        r->inf = key;
        if(!head){
            head = r;
            tail = head;
        } else {
            r->prev = tail; 
            tail->next = r;
            tail = r;
        }
        cur = head;
    };
    //----
    E EraseRight(int x){
        list * r = cur;
        for (int i = 0; i < x; i++){ 
            if (r != tail){
                r = r->next;
            } else {
                r = head;
            };
        };
        int c = r->inf;
        if (r == head) {
            cur = head->next;
            return pop_front();
        };
        if (r == tail) {
            cur = head;
            return pop_back();
        };
        if (r != head && r != tail) {
            cur = r->next;
            r->prev->next = r->next;
            r->next->prev = r->prev;
            delete r;
        };
        return c;
    };
    //----
    E EraseLeft(int x){
        list * r = cur;
        for (int i = 0; i < x; i++){ 
            if (r != head){
                r = r->prev;
            } else {
                r = tail;
            };
        };
        int c = r->inf;
        if (r == head) {
            cur = tail;
            return pop_front();
        };
        if (r == tail) {
            cur = tail->prev;
            return pop_back();
        };
        if (r != head && r != tail) {
            cur = r->prev;
            r->prev->next = r->next;
            r->next->prev = r->prev;
            delete r;
        };
        return c;
    };
    //----
    Tlist(){
        head = tail = init_list();
        cur = head;
    };
};
 
int main() {
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    Tlist <int> l;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        l.push_back(i+1);
    int t;
    for (int i = 0; i < n - 1; i++) {
        scanf("%d", &t);
        if (t > 0) {
            printf("%d\n", l.EraseRight(t));
        } else {
            printf("%d\n", l.EraseLeft(-t));
        }
    }
    printf("%d\n", l.pop_back());
    return 0;
}
Yandex
Объявления
13.05.2013, 17:30     Двунаправленный кольцевой список (удаление узлов)
Ответ Создать тему
Опции темы

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