Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/18: Рейтинг темы: голосов - 18, средняя оценка - 4.89
300 / 265 / 113
Регистрация: 05.06.2013
Сообщений: 845
1

Удаление последнего элемента из однонаправленного линейного списка

31.10.2018, 12:51. Показов 3409. Ответов 13
Метки нет (Все метки)

Здравствуйте, удаляю значится элемент:
(x - порядковый номер удаляемого элемента, начиная с 1. records_cnt - количество элементов в списке, например 5)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    if (x > 0 && x <= records_cnt)
    {
        ListNode<Data>* node = _head;
        ListNode<Data>* temp = _head;
        
        for (int i = 1; i < x; i++)
        {
            node = temp; // предыдущее значение temp
            temp = temp->next;
        }
 
        if (temp == _head) // если элемент который надо удалить - первый
        {
            _head = temp->next;
        }
        else
        {
            node->next = temp->next;
        }
        
        free(temp);
        records_cnt--;
    }
Если удаляю первый элемент - всё ок, элемент удалён, в список спокойно добавляются новые элементы.
Если удаляю элементы с 2го по 4й - всё ок, элемент удалён, в список спокойно добавляются новые элементы.
Если удаляю последний элемент - элемент удаляется, но в список добавить новые элементы больше невозможно.

Как правильно удалить последний элемент списка, что бы не сломать список?
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.10.2018, 12:51
Ответы с готовыми решениями:

Написать программу линейного списка однонаправленного типа данных float добавление и удаление в любом месте элемента
Написать программу линейного списка однонаправленного типа данных float добавление и удаление в...

Удаление элемента из однонаправленного списка
Есть функция удаления элемента из списка. Она проходит по списку два раза. Как сделать так, чтобы...

Удаление элемента из однонаправленного списка
Не могу разобраться с выводом на экран и удалением все делаю по аналогии с различной литературой но...

Удаление элемента из однонаправленного списка
помогите написать функцию удаление ОПРЕДЕЛЕННОГО элемента одн. списка. необходима удалить элемент...

13
6992 / 6030 / 2738
Регистрация: 14.04.2014
Сообщений: 25,792
31.10.2018, 13:37 2
Отладчиком смотри.
0
300 / 265 / 113
Регистрация: 05.06.2013
Сообщений: 845
31.10.2018, 14:55  [ТС] 3
nmcf, посмотрел, но ничего не увидел
0
6992 / 6030 / 2738
Регистрация: 14.04.2014
Сообщений: 25,792
31.10.2018, 15:26 4
Ты же говоришь, что элементы после не добавить. Ну вот и смотри отладчиком, почему не добавляется.
0
471 / 423 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
31.10.2018, 16:08 5
Работа с односвязными кольцевыми списками
Вытащи то, что нужно тебе.

Не понятно, куда ты добавляешь элементы, и почему они не добавляются вдруг, если удалился последний элемент а присутствует только голова - значит добавляются в начало...
0
300 / 265 / 113
Регистрация: 05.06.2013
Сообщений: 845
31.10.2018, 16:32  [ТС] 6
Цитата Сообщение от SuperKir Посмотреть сообщение
Не понятно, куда ты добавляешь элементы, и почему они не добавляются вдруг, если удалился последний элемент а присутствует только голова - значит добавляются в начало...
Добавляю так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void List::Add()                                // Добавление нового элемента
{
    Data node;
    
    node.val1 = 1;
        node.val2 = 2;
    node.val3 = 3;
        ...
    
    ListNode<Data>* newNode = new ListNode<Data>;
    newNode->data = node;
    newNode->next = NULL;
    if (_tail)
        _tail->next = newNode;
    if (!_head)
        _head = newNode;
    _tail = newNode;
}
Сейчас покуру ваш код да пройдусь дебагером.
Но кажется мне, что удалив последний элемент я должен задать хвост.
0
471 / 423 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
31.10.2018, 17:19 7
Jefe, ужасно, всё ужасно.
А что, когда 1 узел, он не хвостовой теперь уже, только головной? И хвост и голова должны быть по одному адресу тогда.
Ты добавляешь в конец, но при этом, когда элемент крайний удаляешь, хвосту адрес предпоследнего не передаешь, поэтому он станет мусорным и будет бЯда...
0
300 / 265 / 113
Регистрация: 05.06.2013
Сообщений: 845
31.10.2018, 17:28  [ТС] 8
SuperKir, знаю, что ужасно.
Пробовал так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (temp == _head)
        {
            _head = temp->next;
        }
        else if (x < records_cnt)
        {
            node->next = temp->next;
        }
        else
        {
            _tail = node;
        }
        
        free(temp);
Но при попытке отобразить то, что после этого получается ловлю исключение bad_alloc.
Пока не понимаю как правильно это исправить.
0
44 / 20 / 14
Регистрация: 23.10.2018
Сообщений: 103
31.10.2018, 19:03 9
Цитата Сообщение от Jefe Посмотреть сообщение
Но при попытке отобразить то, что после этого получается ловлю исключение bad_alloc.
Пока не понимаю как правильно это исправить.
При удалении указатель _tail не пробовали обновлять?
0
300 / 265 / 113
Регистрация: 05.06.2013
Сообщений: 845
31.10.2018, 19:07  [ТС] 10
Цитата Сообщение от sty4ent Посмотреть сообщение
При удалении указатель _tail не пробовали обновлять?
В приведенном выше примере строка 11 это моя оппытка обновить _tail и присвоить ему значение node.
node в этот момент является указателем на предпоследний элемент, тоесть элемент перед удаляемым.

Но видимо что-то не так.
0
44 / 20 / 14
Регистрация: 23.10.2018
Сообщений: 103
31.10.2018, 19:18 11
Лучший ответ Сообщение было отмечено Jefe как решение

Решение

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
#include <iostream>
 
template<typename T>
class List {
private:
    struct Node {
        Node(const T& value) {
            next = nullptr;
            data = value;
        }
 
        T data;
        Node* next{nullptr};
    };
 
public:
    class Iterator {
    public:
        Iterator(Node* node) : _node(node) {
        }
        
        bool operator!=(const Iterator& it) {
            return _node != it._node;
        }
        
        Iterator operator++(int) {
           Iterator result = *this;
           _node = _node->next;
           return result;
        }    
        
        T& operator*() {
            return _node->data;
        }
        
    private:
        Node* _node;
    };
 
public:
    void remove_by_index(int index) {
        if ((index <= 0) || (index > _size)) {
            return;
        }
        
        Node* prev = nullptr;
        Node* temp = _head;
        
        for (int x = 1; x != index; x++) {
            prev = temp;
            temp = temp->next;
        }
        
        if (temp == _tail) {
            _tail = prev;
        }
        
        if (temp == _head) {
            _head = _head->next;
        } else {
            prev->next = temp->next;
        }
 
        delete temp;
        _size--;
    }
 
    void push_back(const T& value) {
        Node* new_node = new Node(value);
        if (_tail) {
            _tail->next = new_node;
        } else {
            _head = new_node;
        }
        _tail = new_node;
        _size++;
    }
    
    Iterator begin() {
        return Iterator(_head);
    }
    
    Iterator end() {
        return Iterator(nullptr);
    }
 
private:
    int _size{0};
    Node* _head{nullptr};
    Node* _tail{nullptr};
};
 
int main() {
    struct MyData {
        int id;
    } data;
    List<MyData> list;
    
    for (int x = 1; x <= 5; x++) {
        data.id = x;
        list.push_back(data);
    }
    
    MyData new_value{100};
    list.remove_by_index(5);
    list.push_back(new_value);
 
    for (auto i = list.begin(); i != list.end(); i++) {
        const MyData& d = *i;
        std::cout << d.id << " ";
    }
    std::cout << "\n";
    
    return 0;
}
Добавлено через 10 минут
Цитата Сообщение от Jefe Посмотреть сообщение
if (temp == _head)
* * * * {
* * * * * * _head = temp->next;
* * * * }
* * * * else if (x < records_cnt)
* * * * {
* * * * * * node->next = temp->next;
* * * * }
* * * * else
* * * * {
* * * * * * _tail = node;
* * * * }
free(temp);
Но при попытке отобразить то, что после этого получается ловлю исключение bad_alloc.
Пока не понимаю как правильно это исправить.
Здесь как минимум надо обновить ещё указатель на следующий элемент (_tail->next = nullptr).
1
300 / 265 / 113
Регистрация: 05.06.2013
Сообщений: 845
01.11.2018, 14:42  [ТС] 12
sty4ent, спасибо.
Окончательный рабочий вариант:
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
if (x > 0 && x <= records_cnt)
    {
        ListNode<Data>* node = _head;
        ListNode<Data>* temp = _head;
        
        for (int i = 1; i < x; i++)
        {
            node = temp;
            temp = temp->next;
        }
 
        if (temp == _head)
        {
            _head = temp->next;
        }
        else if (x < records_cnt)
        {
            node->next = temp->next;
        }
        else
        {
            _tail = node;
            _tail->next = nullptr;
        }
        
        free(temp);
        records_cnt--;
    }
0
44 / 20 / 14
Регистрация: 23.10.2018
Сообщений: 103
02.11.2018, 15:43 13
Цитата Сообщение от Jefe Посмотреть сообщение
Окончательный рабочий вариант:
Не уверен я в этом. Создайте список из 1 элемента. Потом удалите этот элемент. Затем попробуйте добавить ещё что-то. Предполагается, что для добавления элементов используется та функция, которая представлена выше.
0
300 / 265 / 113
Регистрация: 05.06.2013
Сообщений: 845
02.11.2018, 17:09  [ТС] 14
Цитата Сообщение от sty4ent Посмотреть сообщение
Не уверен я в этом.
Нет, и с одним элементом работает.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.11.2018, 17:09

Удаление элемента из линейного однонапраленного списка.
Говорят, что существует множество способов удаления из списка. Вот один из них: void los::del_el()...

Удаление каждого второго элемента линейного списка
нужно написать функцию удаления каждого 2 элемента списка, вот код по сути требуется только...

Сортировка однонаправленного линейного списка
Нужно отсортировать однонаправленный линейный список сортировкой слиянием и бинарной сортировкой....

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


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

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