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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
MarVaL
С++ Beginner
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
#1

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

13.05.2013, 16:09. Просмотров 2012. Ответов 8
Метки нет (Все метки)

Помогите с удалением узлов из списка(~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;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2013, 16:09
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Двунаправленный кольцевой список (удаление узлов) (C++):

Кольцевой двунаправленный список - C++
Дали задачу на практике. Пусть L обозначает кольцевой двунаправленный список с заглавным звеном.Описать функцию или процедуру, которая в...

Двунаправленный кольцевой список - C++
Ребята, спасайте. Очень много дают информации, всё не успеваю освоить. Потихоньку стараюсь наверстать, но срочно необходимо решить 2...

Кольцевой, связанный, двунаправленный список - C++
Добрый вечер. Помогите, пожалуйста, написать код: Составить кольцевой, связанный, двунаправленный список для элементов: стол, шкаф. ...

Двунаправленный список (добавление/удаление/сортировка) - C++
Задание: Необходимо создать двунаправленный список содержащий в себе информацию в виде &quot;Имя и номер телефона&quot; Операции которые должны...

Реализовать удаление элемента из пользовательского класса "Двунаправленный список" - C++
Программа для работы с двунаправленным списком. Пользователь вводит список с клавиатуры, программа должна выводить его в обоих...

Двунаправленный список (добавление/удаление элементов в голову, просмотр списка, реализовать дублирование элементов с заданным значением) - C++
Здравствуйте! Помогите написать программу, обеспечивающую работу с двунаправленным нециклическим списком: добавление/удаление элементов в...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
13.05.2013, 16:16 #2
MarVaL, Да удаляй например с конца указателю предыдущему который указывает на последний элемент присвой 0 и все, ну можешь еще и память высвободить сохранив адрес на последний элемент и вызвав delete указатель на последний элемент.
0
MarVaL
С++ Beginner
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
13.05.2013, 16:18  [ТС] #3
Цитата Сообщение от ninja2 Посмотреть сообщение
MarVaL, Да удаляй например с конца указателю предыдущему который указывает на последний элемент присвой 0 и все, ну можешь еще и память высвободить сохранив адрес на последний элемент и вызвав delete указатель на последний элемент.
Можешь написать, или поподробнее плз
0
ninja2
231 / 187 / 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;//высвобождение памяти.
Примерно так. Конкретно в твоем случае я не смотре, главное это принцип идея
0
MarVaL
С++ Beginner
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;
0
ninja2
231 / 187 / 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; //высвобождение памяти
Тут нужно проверять потому что я без проверки так с головы набрал, возможно ошибся где то. Нужно проверять.
0
MarVaL
С++ Beginner
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;
}
0
ninja2
231 / 187 / 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 минуты
Это для двусвязного списка не кольцевой.
0
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;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2013, 17:30
Привет! Вот еще темы с ответами:

Реализовать пользовательский класс "Двунаправленный список"; реализовать добавление и удаление элементов - C++
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить К элементов с...

Реализовать кольцевой список. Как закольцевать список обычный? - C++
Помогите пожалуйста реализовать кольцевой список. Я так понимаю, он может быть двусвязным и односвязным? Меня интересует односвязный....

кольцевой список - C++
Граждане - товарищи, нужна помощь! Задание- Описать процедуру, которая формирует очередь Queue, включив в нее по одному разу элементы,...

Кольцевой список - C++
Что нужно поменять,чтобы новые елементы добавлялись не в конец списка, а в начало? void List::Insert_end_list_2(int &amp;x) { ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.05.2013, 17:30
Ответ Создать тему
Опции темы

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