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

21.01.2012, 07:58. **Показов** 67354. **Ответов** 17

Студворк — интернет-сервис помощи студентам

У нас есть односвязный список и указатель на один из его элементов, как удалить этот элемент из списка, оставив список целостным ?(сделать это надо за О(1), решение вида пройти с начала списка найти родителя нашего элемента , и поставить у него ссылку на потомка нашего элемента не подходит!)

accept · 21.01.2012, 08:48

пометить его удалённым

go · 21.01.2012, 12:19

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;
}

21.01.2012, 14:07

Спасибо, go. А это разве не решение вида пройти с начала списка найти родителя нашего элемента , и поставить у него ссылку на потомка нашего элемента?
Помоги придумать еще что-нибудь, кроме стандартного варианта!!!

go · 21.01.2012, 14:46

Сообщение от Татьяна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 · 23.01.2012, 03:07

Татьяна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 · 23.01.2012, 11:15

Сообщение от accept

в чём смысл 4-ой строки ? узел удаляется

В удаляемый узел полностью копируем следующий за ним.

Сообщение от accept

какой узел удаляется в 6-ой строке ? следующий за удаляемым ?
утечка памяти при удалении последнего узла

да, следующий.

C++
1
2
3
4
else { // Если этот узел последний
                delete node;
                node = NULL;
        }

@easybudda · 23.01.2012, 12:19

Татьяна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 · 23.01.2012, 12:21

Сообщение от easybudda

Есть проблема: сохранённый указатель на начало списка потеряет смысл, если удаляемый элемент - первый в списке, так же указатель на конец списка потеряет смысл, если удаляемый элемент последний. В первом случае весь лист потеряется, во втором появятся поблемы с добавлением новых элементов.

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

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

Сообщение от easybudda

go, есть подозрение, что будет теряться указатель на начало/конец списка. Попробуйте полную версию сделать...

Ок. Поближе к выходным сделаю. Я обязательно вернусь к этому вопросу

@easybudda · 23.01.2012, 12:24

Сообщение от go

Указатель передается по ссылке.

Коль скоро язык программирования вообще не указан, что с вариантом на С будет? Ну и тем не менее, всё-таки рабочий пример хотелось бы увидеть...

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

Не по теме:

Сообщение от go

Поближе к выходным сделаю.

На всякий случай: сегодня понедельник... :)

go · 23.01.2012, 13:58

Сообщение от 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 · 23.01.2012, 19:36

go, на попытке удалить несуществующий элемент валится, а так - вроде да, работает...

go · 23.01.2012, 19:55

Сообщение от 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 · 23.01.2012, 21:10

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 подскажите пожалуйста в чем может быть ошибка?

Заранее огромное спасибо.

go · 23.01.2012, 21:14

isaak, сишный код необходимо компилировать сишным компилятором. Иначе приводите типы.
если эта строка

C
1
if ( ! ( n = (node_t *) malloc(sizeof(node_t)) ) )

accept · 24.01.2012, 02:35

Сообщение от go

В удаляемый узел полностью копируем следующий за ним.

зачем ?

Сообщение от go

C++
1
    node->next = node->next->next;

удаляется какой элемент относительно node ?
где node - это next элемента, стоящего перед удаляемым

никто не заметил вот это условие ?

Сообщение от ТатьянаR

сделать это надо за О(1)

если у вас есть адрес элемента, каким образом вы узнаете адрес предыдущего элемента ?
каждое удаление потребует перебора элементов до удаляемого, будь оно в функции или за её пределами

go · 24.01.2012, 10:35

Сообщение от accept

каждое удаление потребует перебора элементов до удаляемого, будь оно в функции или за её пределами

А как Вы удаляете. Указатель с потолка берете? Ну давайте, покажите мне эту функцию, с прототипом и сложностью О(1)

C
1
void del_node(int val); // ;)

Сообщение от accept

удаляется какой элемент относительно node ?

Полный код я выложил.

Не по теме:

Сообщение от accept

зачем ?

Мне так захотелось :D

...

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
#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 = node;
        
        node = node->next;
        delete t;        
}
        
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, 1));
        print(first); 
 
    return 0;
}

accept · 25.01.2012, 04:54

Сообщение от go

Ну давайте, покажите мне эту функцию, с прототипом и сложностью О(1)

задание подразумевает, что адрес узла уже известен

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int delnode_list(ListNode *np)
{
    if (np && !np->removed) {
        np->removed = 1;
        return 1;
    }
    return 0;
}
 
ListNode *srchnode_list(ListNode *hp, int v)
{
    for ( ; hp; hp = hp->next)
        if (!hp->removed && hp->v == v)
            return hp;
    return NULL;
}
 
...
 
    delnode_list(srchnode_list(value));

получилось что-то типа твоего, но адрес узла участвует напрямую, а реальным удалением может заниматься сборщик мусора
таким же образом можно удалять узлы в дереве и хеш-таблице, а там перестройка элементов - уже затратный процесс
если переделывать твою, чтобы она работала, то нужно передавать ещё и указатель на голову, чтобы иметь возможность её удалить (на неё никакой элемент не указывает)

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

ТатьянаR

	Удалить элемент из односвязного списка 21.01.2012, 07:58. Показов 67354. Ответов 17 Метки нет (Все метки) У нас есть односвязный список и указатель на один из его элементов, как удалить этот элемент из списка, оставив список целостным ?(сделать это надо за О(1), решение вида пройти с начала списка найти родителя нашего элемента , и поставить у него ссылку на потомка нашего элемента не подходит!)

accept 4866 / 3288 / 468 Регистрация: 10.12.2008 Сообщений: 10,570
	21.01.2012, 08:48
	пометить его удалённым 0

ТатьянаR
	21.01.2012, 14:07
	Спасибо, go. А это разве не решение вида пройти с начала списка найти родителя нашего элемента , и поставить у него ссылку на потомка нашего элемента? Помоги придумать еще что-нибудь, кроме стандартного варианта!!!

@easybudda Модератор 12843 / 7592 / 1766 Регистрация: 25.07.2009 Сообщений: 13,973
	23.01.2012, 19:36
	go, на попытке удалить несуществующий элемент валится, а так - вроде да, работает... 0

@isaak 90 / 125 / 28 Регистрация: 17.10.2010 Сообщений: 1,321
	23.01.2012, 21:10
	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 подскажите пожалуйста в чем может быть ошибка? Заранее огромное спасибо. 0