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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 73, средняя оценка - 4.90
ТатьянаR
Сообщений: n/a
#1

Удалить элемент из односвязного списка - C++

21.01.2012, 07:58. Просмотров 11310. Ответов 17
Метки нет (Все метки)

У нас есть односвязный список и указатель на один из его элементов, как удалить этот элемент из списка, оставив список целостным ?(сделать это надо за О(1), решение вида пройти с начала списка найти родителя нашего элемента , и поставить у него ссылку на потомка нашего элемента не подходит!)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.01.2012, 07:58     Удалить элемент из односвязного списка
Посмотрите здесь:
Удалить элемент из односвязного списка C++
Удалить первый элемент односвязного списка C++
C++ Удалить из односвязного линейного списка определенный узел
C++ Добавить элемент в конец односвязного списка
Найти максимальный элемент односвязного списка C++
Найти наименьший элемент односвязного линейного списка C++
Создание и вывод односвязного списка (выводится только первый элемент) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4821 / 3241 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
21.01.2012, 08:48     Удалить элемент из односвязного списка #2
пометить его удалённым
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
21.01.2012, 12:19     Удалить элемент из односвязного списка #3
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
int delete_node(list_t *del, list_t **first) {
    list_t *t = (*first)->next;
    list_t *buf;
    if ( *first && *first != del ) { // Если список существует, и удоляемый элемент не является первым
        while ( t && t->next != del ) t = t->next; // Находим элемент, предшествубщий удоляемому
        if ( t ) { // Если он существует, то удаляем
            buf = t->next;
            t->next = t->next->next;
            free(buf);
            return 0; 
        }
        else
            return -1; // Иначе ошибка
    }
    else // Иначе
        if ( *first != del ) { // Если первый
            buf = del;
            *first = del->next;
            free(buf);
            return 0;
        }
        else // Если список пуст
            return -1;
}
ТатьянаR
Сообщений: n/a
21.01.2012, 14:07     Удалить элемент из односвязного списка #4
Спасибо, go. А это разве не решение вида пройти с начала списка найти родителя нашего элемента , и поставить у него ссылку на потомка нашего элемента?
Помоги придумать еще что-нибудь, кроме стандартного варианта!!!
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
21.01.2012, 14:46     Удалить элемент из односвязного списка #5
Цитата Сообщение от ТатьянаR Посмотреть сообщение
А это разве не решение вида
Да, оно и есть. Можно еще через рекурсию, но я понял, что Вам необходимо
Вот (уже не делал этих проверок, принимаем за должное, что указатель валидный)
C++
1
2
3
4
5
6
7
8
9
10
11
12
void del_node(list_t& *node) { // Передаем указатель  предыдущего звена, на это
    list_t *t;
    if ( t = node->next ) {
        node->date = node->next->data; // Или все скопировать с помощью memcpy
        node = node->next->next;
        delete t;
    }
    else { // Если этот узел последний
        node = NULL;
        delete t;
    }
}
accept
4821 / 3241 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
23.01.2012, 03:07     Удалить элемент из односвязного списка #6
ТатьянаR, сделай поле в каждом узле, которое показывает удалён элемент или нет

Добавлено через 3 минуты
Цитата Сообщение от go Посмотреть сообщение
Да, оно и есть. Можно еще через рекурсию, но я понял, что Вам необходимо
Вот (уже не делал этих проверок, принимаем за должное, что указатель валидный)
C++
1
2
3
4
5
6
7
8
9
10
11
12
void del_node(list_t& *node) { // Передаем указатель  предыдущего звена, на это
    list_t *t;
    if ( t = node->next ) {
        node->date = node->next->data; // Или все скопировать с помощью memcpy
        node = node->next->next;
        delete t;
    }
    else { // Если этот узел последний
        node = NULL;
        delete t;
    }
}
в чём смысл 4-ой строки ? узел удаляется
в пятой строке делает лишний переход
какой узел удаляется в 6-ой строке ? следующий за удаляемым ?
утечка памяти при удалении последнего узла
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
23.01.2012, 11:15     Удалить элемент из односвязного списка #7
Цитата Сообщение от accept Посмотреть сообщение
в чём смысл 4-ой строки ? узел удаляется
В удаляемый узел полностью копируем следующий за ним.

Цитата Сообщение от accept Посмотреть сообщение
какой узел удаляется в 6-ой строке ? следующий за удаляемым ?
утечка памяти при удалении последнего узла
да, следующий.
C++
1
2
3
4
else { // Если этот узел последний
                delete node;
                node = NULL;
        }
easybudda
Эксперт CЭксперт С++
9465 / 5478 / 927
Регистрация: 25.07.2009
Сообщений: 10,502
23.01.2012, 12:19     Удалить элемент из односвязного списка #8
ТатьянаR, вот Вам работающий список с добавлением/удалением элементов и незамысловатым интерфейсом:
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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct NODE {
    int val;
    struct NODE * next;
} node_t;
 
typedef struct LIST {
    node_t * first;
    node_t * last;
} list_t;
 
int addnode(list_t * list, int val){
    node_t * n;
    
    if ( ! ( n = malloc(sizeof(node_t)) ) )
        return -1;
    
    n->val = val;
    n->next = NULL;
    
    if ( list->first == NULL )
        list->first = n;
    else
        list->last->next = n;
    list->last = n;
    
    return 0;
}
 
void clearlist(list_t * list){
    while ( list->first != NULL ){
        list->last = list->first->next;
        free(list->first);
        list->first = list->last;
    }
}
 
node_t * findbyval(list_t * list, int val){
    node_t * ptr = list->first;
    
    while ( ptr != NULL && ptr->val != val )
        ptr = ptr->next;
    
    return ptr;
}
 
int delnode(list_t * list, node_t * node){
    if ( list->first == node )
        list->first = list->first->next;
    else {
        node_t * ptr;
        for ( ptr = list->first; ptr->next != NULL && ptr->next != node; ptr = ptr->next )
            ;
        if ( ptr->next == NULL )
            return -1;
        else if ( ptr->next == list->last )
            list->last = ptr;
        ptr->next = node->next;
    }
    
    free(node);
    return 0;
}
 
void dump(list_t * list){
    node_t * node;
    
    for ( node = list->first; node != NULL; node = node->next )
        printf("%d ", node->val);
    
    printf("\n");
}
 
void usage(void){
    printf("\n+ value - add to list\n- value - remove from list\np0 - print list\nh0 - this help message\nq0 - quit\n\n");
}
 
int main(void){
    list_t list = { NULL, NULL };
    int val, onoff;
    char act, tail;
    
    onoff = 1;
    usage();
    while ( onoff ){
        printf("> ");
        if ( scanf("%c%d%c", &act, &val, &tail) != 3 || tail != '\n' ){
            fprintf(stderr, "Wrong input!\n");
            break;
        }
        
        switch ( act ) {
            case '+' :
                if ( addnode(&list, val) ){
                    fprintf(stderr, "Memory error!\n");
                    exit(1);
                }
                break;
            case '-' : 
                {
                    node_t * ptr = findbyval(&list, val);
                    if ( ptr == NULL )
                        printf("Value %d not in list\n", val);
                    else if ( delnode(&list, ptr) )
                        fprintf(stderr, "Failed to removing value!\n");
                }
                break;
            case 'p' :
                dump(&list);
                break;
            case 'h' :
                usage();
                break;
            case 'q' :
                printf("See you...\n");
                onoff = 0;
                break;
            default :
                printf("Unknown action.\n");
                break;
        }
    }
    
    clearlist(&list);
    exit(0);
}
Добавлено через 4 минуты
go, есть подозрение, что будет теряться указатель на начало/конец списка. Попробуйте полную версию сделать...
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
23.01.2012, 12:21     Удалить элемент из односвязного списка #9
Цитата Сообщение от easybudda Посмотреть сообщение
Есть проблема: сохранённый указатель на начало списка потеряет смысл, если удаляемый элемент - первый в списке, так же указатель на конец списка потеряет смысл, если удаляемый элемент последний. В первом случае весь лист потеряется, во втором появятся поблемы с добавлением новых элементов.
Ничего такого не будет. Указатель передается по ссылке.

Добавлено через 1 минуту
Цитата Сообщение от easybudda Посмотреть сообщение
go, есть подозрение, что будет теряться указатель на начало/конец списка. Попробуйте полную версию сделать...
Ок. Поближе к выходным сделаю. Я обязательно вернусь к этому вопросу
easybudda
Эксперт CЭксперт С++
9465 / 5478 / 927
Регистрация: 25.07.2009
Сообщений: 10,502
23.01.2012, 12:24     Удалить элемент из односвязного списка #10
Цитата Сообщение от go Посмотреть сообщение
Указатель передается по ссылке.
Коль скоро язык программирования вообще не указан, что с вариантом на С будет? Ну и тем не менее, всё-таки рабочий пример хотелось бы увидеть...

Добавлено через 1 минуту

Не по теме:

Цитата Сообщение от go Посмотреть сообщение
Поближе к выходным сделаю.
На всякий случай: сегодня понедельник...

go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
23.01.2012, 13:58     Удалить элемент из односвязного списка #11
Цитата Сообщение от easybudda Посмотреть сообщение
На всякий случай: сегодня понедельник...
Тогда вот очень грубый вариант, который работает
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
#include <iostream>
 
typedef struct list_ {
    int key;
    struct list_* next;
} list;
 
void push(list* &first, int key) // Длюавление в конец, параметр - ссылка на певый узел, и ключ
{
    list *t = new list;
    t->key = key;
    t->next = NULL;
    
    if ( !first )   // Список еще не создан
        first = t;
    else
    {
        list *buf = first;
        while ( buf->next && (buf = buf->next) );
        buf->next = t;
    }
}
 
list* &search(list* &first, int key) // Поиск, параметр - ссылка на певый узел, и ключ  
{
    static list* &t = first;
    t = first;
    static list *buf = first; 
    buf = first;
    if ( !first )
        exit (1);
    if ( first->key == key)
        return t;   
    while ( buf && (buf->next) && (buf->next->key != key) )
        buf = buf->next;
    if ( buf->next->key == key )
        return buf->next;
    else
        exit(1);
}
 
void del_node(list* &node) { // Передаем указатель  предыдущего звена, на это
        list* t;
        if ( t = node->next ) {
                node->key = node->next->key; // Или все скопировать с помощью memcpy
        node->next = node->next->next;
                delete t;
        }
        else { // Если этот узел последний
                delete node;
                node = NULL;
    }
}
    
void print(list *first)
{
    while ( first )
    {
        std::cout << first->key << " ";
        first = first->next;
    }
    std::cout << std::endl;
}
    
int main()
{
    list *first = NULL;
    
    //----------------------------------------------
    push(first, 1);
    push(first, 2);
    push(first, 3);
    push(first, 4);
    push(first, 5);
    push(first, 6);
    //-----------------------------------------------
    print(first);
    del_node(search(first, 6));
    print(first); 
 
    return 0;
}
easybudda
Эксперт CЭксперт С++
9465 / 5478 / 927
Регистрация: 25.07.2009
Сообщений: 10,502
23.01.2012, 19:36     Удалить элемент из односвязного списка #12
go, на попытке удалить несуществующий элемент валится, а так - вроде да, работает...
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
23.01.2012, 19:55     Удалить элемент из односвязного списка #13
Цитата Сообщение от easybudda Посмотреть сообщение
на попытке удалить несуществующий элемент валится,
Торопился. И не пробовал. Перед 36 строчкой вставить это
C++
1
2
        if ( !buf->next )
            exit(1);


Хотя если честно, то здесь (в моем коде) необходимо хранить ссылку на удаляемый элемент в виде
C++
1
2
3
4
list *node; // Звено перед удаляемым
list* &del = node->next // для первого list* &del = first;
// т.е.
list* &del = search(first, 1); // как-то так
что тоже является ухитрением, но del указатель на удаляемый элемент, а как мы его нашли не имеет значение (указатели ведь искать надо, а не с потолка брать)
Полный, исправленный, код.
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
#include <iostream>
 
typedef struct list_ {
        int key;
        struct list_* next;
} list;
 
void push(list* &first, int key) // Длюавление в конец, параметр - ссылка на певый узел, и ключ
{
        list *t = new list;
        t->key = key;
        t->next = NULL;
        
        if ( !first )   // Список еще не создан
                first = t;
        else
        {
                list *buf = first;
                while ( buf->next && (buf = buf->next) );
                buf->next = t;
        }
}
 
list* &search(list* &first, int key) // Поиск, параметр - ссылка на певый узел, и ключ  
{
        static list* &t = first;
        t = first;
        static list *buf = first; 
        buf = first;
        if ( !first )
                exit (1);
        if ( first->key == key)
                return t;       
        while ( buf && (buf->next) && (buf->next->key != key) )
                buf = buf->next;
    if ( !buf->next )
        exit(1);
        if ( buf->next->key == key )
                return buf->next;
        else
                exit(1);
}
 
void del_node(list* &node) { // Передаем указатель  предыдущего звена, на это
        list* t;
        if ( t = node->next ) {
                node->key = node->next->key; // Или все скопировать с помощью memcpy
                node->next = node->next->next;
                delete t;
        }
        else { // Если этот узел последний
                delete node;
                node = NULL;
        }
}
        
void print(list *first)
{
        while ( first )
        {
                std::cout << first->key << " ";
                first = first->next;
        }
        std::cout << std::endl;
}
        
int main()
{
        list *first = NULL;
        
        //----------------------------------------------
        push(first, 1);
        push(first, 2);
        push(first, 3);
        push(first, 4);
        push(first, 5);
        push(first, 6);
        //-----------------------------------------------
        print(first);
        del_node(search(first, 6));
        print(first); 
 
    return 0;
}
isaak
102 / 39 / 9
Регистрация: 17.10.2010
Сообщений: 658
23.01.2012, 21:10     Удалить элемент из односвязного списка #14
easybudda почему то при компиляции вашего кода выскакивает ошибка:

1 IntelliSense: a value of type "void *" cannot be assigned to an entity of type "node_t *" c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1500\one-way list\one-way list\one-way list.cpp 17 20 One-way list

среда разработки visual studio 2010 подскажите пожалуйста в чем может быть ошибка? Заранее огромное спасибо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.01.2012, 21:14     Удалить элемент из односвязного списка
Еще ссылки по теме:
C++ Как удалить нужный элемент из списка или заменить этот элемент на другой?
C++ Задача Иосифа Флавия. Удалить каждый второй элемент из списка и в конце вывести на экран последний оставшийся элемент
Удалить элемент из списка C++
Удалить элемент из списка C++
Удаление элементов из односвязного списка списка C++

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

Или воспользуйтесь поиском по форуму:
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
23.01.2012, 21:14     Удалить элемент из односвязного списка #15
isaak, сишный код необходимо компилировать сишным компилятором. Иначе приводите типы.
если эта строка
C
1
if ( ! ( n = (node_t *) malloc(sizeof(node_t)) ) )
Yandex
Объявления
23.01.2012, 21:14     Удалить элемент из односвязного списка
Ответ Создать тему
Опции темы

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