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

Удаление значения из односвязного списка - C++

Восстановить пароль Регистрация
 
итернал
4 / 4 / 0
Регистрация: 17.09.2012
Сообщений: 284
06.09.2014, 18:49     Удаление значения из односвязного списка #1
добрый день можете подсказать, пытаюсь удалить элемент односвязного списка, только постояно выдает почему-то ошибку, вообще у меня там записаны значения, но я пытался и по значению и по индексу не получается
вот мой код
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
void CStack::DelVal(int k,int &b)
{
    Elem *pCur=pFirst;
    while(1)
    {
        if(k==pCur->id)
        {
            if(pCur==pFirst && pCur->pNext==NULL)//если элемент первый и последний
            {
                delete pCur;
                pFirst=NULL;
                b=0;
            }
            else if(pCur==pFirst && pCur->pNext!=NULL)//если элемент первый и не последний
            {
                Elem *NewHead=pCur->pNext;
                delete pCur;
                pFirst=NewHead;
            }
            else if(pCur!=pFirst && pCur->pNext==NULL)//если элемент последний
            {
                Elem *pLast=pCur;
                delete pCur;
                pLast=NULL;
            }
            else if(pCur!=pFirst && pCur->pNext!=NULL)//если элемент не первый и не последний
            {
                break;
            }
            else
            {
                cout<<"Wrong name";
                break;
            }
 
        }
        pCur=pCur->pNext;
    }
    
}
ошибка всегда в этой строке
C++
1
if(k==pCur->id)
я писал даже так, пытался по тому значению что там, но дальше этой строчки программа не идет, выбивает ошибку
C++
1
if(name==pCur->name)
ну правда name у меня был тип char,по этому потом постарался сделать по id всеравно не получается, b у меня тут для определения заполнен список вообще или нет и можете подсказать правильно ли я делаю удаления? ну там если первый или если последний, я канешно еще не все написал, просто пока незнаю как удалить если элемент где-то посередине
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Renji
1533 / 981 / 239
Регистрация: 05.06.2014
Сообщений: 2,951
06.09.2014, 20:51     Удаление значения из односвязного списка #2
добрый день можете подсказать, пытаюсь удалить элемент односвязного списка, только постояно выдает почему-то ошибку
1) После delete pCur цикл продолжает крутиться и выполняет pCur=pCur->pNext (использование указателя на удаленную память).
2) После удаления элемента не обновляется pNext в предшествующем ему элементе.
итернал
4 / 4 / 0
Регистрация: 17.09.2012
Сообщений: 284
06.09.2014, 21:53  [ТС]     Удаление значения из односвязного списка #3
Цитата Сообщение от Renji Посмотреть сообщение
1) После delete pCur цикл продолжает крутиться и выполняет pCur=pCur->pNext (использование указателя на удаленную память).
2) После удаления элемента не обновляется pNext в предшествующем ему элементе.
по первому ошибку понял, а по второму не очень)
за второе замечание это где-то тут налажал?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
else if(pCur==pFirst && pCur->pNext!=NULL)//если элемент первый и не последний
            {
                Elem *NewHead=pCur->pNext;
                delete pCur;
                pFirst=NewHead;
                break;
            }
            else if(pCur!=pFirst && pCur->pNext==NULL)//если элемент последний
            {
                Elem *pLast=pCur;
                delete pCur;
                pLast=NULL;
                break;
            }
Добавлено через 4 минуты
просто я еще не совсем во всем этом розабрался, но как думаю я
тут если елемент первый, я запоминаю адрес второго
C++
1
 Elem *NewHead=pCur->pNext;
а тут удаляю первый и тот что был вторым его делаю первым
C++
1
2
delete pCur;
                pFirst=NewHead;
а тут, я запоминаю адрес последнего, если нужный елемент последний, удаляю его и присваеваю значение 0
C++
1
2
3
Elem *pLast=pCur;
                delete pCur;
                pLast=NULL;
вот только незнаю как быть если элемент по середине где-то или же я что-то не так понимаю

Добавлено через 52 минуты
я тут немного исправил с удалением последнего элемента, но незнаю с удалением первого все нормально?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
            else if(pCur==pFirst && pCur->pNext!=NULL)//если элемент первый и не последний
            {
                Elem *NewHead=pCur->pNext;          
                delete pCur;
                pFirst=NewHead;
                break;
            }
            else if(pCur!=pFirst && pCur->pNext==NULL)//если элемент последний
            {
                Elem *pTLast=pFirst;                                
                while(pTLast ->pNext ->pNext != NULL)
                {
                    pTLast = pTLast->pNext;
                }
                Elem *pLast = pTLast; // запомнили адрес предпоследнего (будет последним после удаления)                                
                delete pCur; // удалили последний
                pLast ->pNext = NULL; // предпоследний стал последним
                //n--;
                break;
            }
и если можно подскажите как правильно будет удалить если элемент не первый и не последний, а по середине где-то, вообще не могу сообразить что-то
Renji
1533 / 981 / 239
Регистрация: 05.06.2014
Сообщений: 2,951
06.09.2014, 22:32     Удаление значения из односвязного списка #4
за второе замечание это где-то тут налажал?
Да, в удалении последнего элемента.
и если можно подскажите как правильно будет удалить если элемент не первый и не последний, а по середине где-то, вообще не могу сообразить что-то
Как-то так.
C++
1
2
3
4
5
6
7
8
9
10
11
for(Elem**next=&pFirst;*next;next=&(*next)->pNext)
{
    if((*next)->id==k)
    {
        Elem*to_delete=*next;
        *next=to_delete->pNext;
        delete to_delete;
        return;
    }
}
//вставить сюда ругань "нет такого элемента"
итернал
4 / 4 / 0
Регистрация: 17.09.2012
Сообщений: 284
06.09.2014, 22:38  [ТС]     Удаление значения из односвязного списка #5
Цитата Сообщение от Renji Посмотреть сообщение
Да, в удалении последнего элемента.
я вроде исправил, можете посмотреть если он первый, но не последний, так сойдет или надо тоже что-то поменять с указанием на следующий?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
else if(pCur==pFirst && pCur->pNext!=NULL)//если элемент первый и не последний
            {
                Elem *NewHead=pCur->pNext;          
                delete pCur;
                pFirst=NewHead;
                break;
            }
            else if(pCur!=pFirst && pCur->pNext==NULL)//если элемент последний
            {
                Elem *pTLast=pFirst;                                
                while(pTLast ->pNext ->pNext != NULL)
                {
                    pTLast = pTLast->pNext;
                }
                Elem *pLast = pTLast; // запомнили адрес предпоследнего (будет последним после удаления)                                
                delete pCur; // удалили последний
                pLast ->pNext = NULL; // предпоследний стал последним
                //n--;
                break;
            }
Renji
1533 / 981 / 239
Регистрация: 05.06.2014
Сообщений: 2,951
06.09.2014, 22:57     Удаление значения из односвязного списка #6
я вроде исправил, можете посмотреть если он первый, но не последний, так сойдет или надо тоже что-то поменять с указанием на следующий?
Вероятно, работать будет. Но при этом пробег по списку осуществляется дважды, что не айс. DelVal должно искать не элемент у которого id равен k, а элемент за которым следует элемент с id равный k. Тогда у вас будет сразу и указатель на искомый элемент, и на предшествующий.

И во избежание всего этого геморроя с проверками на "первый, не первый" лучше сделайте CStack потомком Elem и первым элементом списка. Так вы будете точно знать что 1) в списке есть хоть один элемент (заголовочный, он же CStack). 2) Удаляемый вами элемент - точно не является первым (первый элемент - CStack, а он сам себя не удаляет). 3) pNext в CStack равно pFirst, а значит сам pFirst можно выкинуть.
итернал
4 / 4 / 0
Регистрация: 17.09.2012
Сообщений: 284
06.09.2014, 23:27  [ТС]     Удаление значения из односвязного списка #7
простите а можно немного коментариев или обьяснений) а то несовсем понятно, просто хочется имено разобратся а не просто вставить и что бы работало
Цитата Сообщение от Renji Посмотреть сообщение
for(Elem**next=&pFirst;*next;next=&(*next)->pNext)
{
* * if((*next)->id==k)
* * {
* * * * Elem*to_delete=*next;
* * * * *next=to_delete->pNext;
* * * * delete to_delete;
* * * * return;
* * }
}
//вставить сюда ругань "нет такого элемента"
это вы делаете как бы отдельным цыклом? или все таки уже в этом условие?
C++
1
2
3
4
 else if(pCur!=pFirst && pCur->pNext!=NULL)//если элемент не первый и не последний
            {
                break;
            }
ну вместо break в будущем там будет какой-то код)
Renji
1533 / 981 / 239
Регистрация: 05.06.2014
Сообщений: 2,951
06.09.2014, 23:42     Удаление значения из односвязного списка #8
простите а можно немного коментариев или обьяснений)
1) DelVal должно найти и удалить элемент.
2) После удаления элемента, должен быть исправлен указатель на этот элемент (pNext или pFirst).
3) *next - псевдоним указателя из пункта 2.
4) Elem**next - указатель на указатель из пункта 2.
5) & перед переменной - взятие указателя на эту переменную.
это вы делаете как бы отдельным цыклом? или все таки уже в этом условие?
Это как бы DelVal целиком.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2014, 00:49     Удаление значения из односвязного списка
Еще ссылки по теме:

Удаление элементов из односвязного списка списка C++
Удаление элемента из односвязного списка, представленного классом C++
Удаление положительных значений из односвязного списка C++

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

Или воспользуйтесь поиском по форуму:
итернал
4 / 4 / 0
Регистрация: 17.09.2012
Сообщений: 284
07.09.2014, 00:49  [ТС]     Удаление значения из односвязного списка #9
Цитата Сообщение от Renji Посмотреть сообщение
Это как бы DelVal целиком.
воу) так просто, ладно щас с обьяснениями попытаюсь вникнуть еще раз, спасибо большое
Yandex
Объявления
07.09.2014, 00:49     Удаление значения из односвязного списка
Ответ Создать тему
Опции темы

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