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

Удаление структуры из двусвязного списка - C++

Восстановить пароль Регистрация
 
Gad
 Аватар для Gad
12 / 0 / 0
Регистрация: 27.01.2014
Сообщений: 31
27.01.2014, 15:41     Удаление структуры из двусвязного списка #1
Доброго времени суток!
Пытаюсь создать функцию удаления из списка структуры, не выполняется цикл while в функции 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
struct spis
 {
   char name[20];
   char author[20];
   int year;
   struct spis *prev;
   struct spis *next;
  };
 void create(void);
 void list(spis *);
 void add(void);
 void del();
 struct spis *head, *tail;
 
void del()
 { 
   spis *p,*temp;
   int year2;
   clrscr();
   printf("\n Enter the year of publication ");scanf("%d",&year2);
   p=head;
   while (p!=NULL)
    {  
     if(p->year==year2) 
      { if(p==head)
          { printf("\n udalena first zapis: %20s%20s%d \n",p->name,p->author,p->year);
        head=p->next;
        head->prev=NULL;
        free(p);
        p=head;
       }
    else 
     if(p==tail)
     {printf("\n udalena poslednyy zapis  %20s%20s%d \n",p->name,p->author,p->year);
      tail=p->prev;
      tail->next=NULL;
      free(p);
      p=tail;
      }
     else
     { printf("\n Udalena zapis  %20s%20s%d \n",p->name,p->author,p->year);
       p->next->prev=p->prev;
       p->prev->next=p->next;
       temp=p;
       p=p->next;
       free(temp);
       }     
    }
       else
   p=p->next;
 }
 }
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
27.01.2014, 15:58     Удаление структуры из двусвязного списка #2
Цитата Сообщение от Gad Посмотреть сообщение
C++
1
while (p!=NULL)
а Вы уверены что это условие верно? а еще Вы уверены что дойдя до конца списка p занулится?
Gad
 Аватар для Gad
12 / 0 / 0
Регистрация: 27.01.2014
Сообщений: 31
27.01.2014, 16:26  [ТС]     Удаление структуры из двусвязного списка #3
Цитата Сообщение от aLarman Посмотреть сообщение
а Вы уверены что это условие верно?
Поставил для самопроверки перед while
C++
1
2
3
4
5
6
      p=head;
   printf("%20s%20s%d \n",p->name,p->author,p->year);
   getch();
   p=tail;
   printf("%20s%20s%d \n",p->name,p->author,p->year);
   getch();
Выводится правильно, ну уж точно не пусто.
Цитата Сообщение от aLarman Посмотреть сообщение
а еще Вы уверены что дойдя до конца списка p занулится?
Прошу прощения, здесь видимо надо было добавить функцию создания списка для ясности.
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
void create(void)
  {
    clrscr();
    spis *p,*pred;
    pred=NULL;
 
    do
      {
        p=(spis *)malloc(sizeof(spis));
        printf("\n Enter the name of publication:   ");
        scanf("%s",&p->name);
        printf("Enter author of publication:   ");
        scanf("%s",&p->author);
        printf("Enter the year of publication:  ");
        scanf("%d",&p->year);
 
        p->prev=pred;
        if(pred!=NULL)
         pred->next=p;
        else
         head=p;
 
         pred=p;
        printf("\n Press <esc> for the exit or any key to continue");
      }
  while(getch()!=27);
    tail=p;
  tail->next=NULL;
 }
Я только начинающий, вот думаю что где-то на пустом месте застопорился, может где-то что-то упустил
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
27.01.2014, 17:02     Удаление структуры из двусвязного списка #4
C++
1
2
3
4
5
6
7
8
if(p==head)
{
    printf("\n udalena first zapis: %20s%20s%d \n",p->name,p->author,p->year);
    head=p->next;//а если 1 элемент? head == tail тогда p->next будет 0, тогда следущая строчка undef behavior
    head->prev=NULL;// тут head ==0
    free(p);
    p=head;
}
вот что в глаза бросилось
Gad
 Аватар для Gad
12 / 0 / 0
Регистрация: 27.01.2014
Сообщений: 31
28.01.2014, 11:21  [ТС]     Удаление структуры из двусвязного списка #5
Цитата Сообщение от aLarman Посмотреть сообщение
вот что в глаза бросилось
так-то оно может и так, но это тот случай когда одна запись в списке, а у меня должно быть как минимум три структуры, иначе не выполняются условия задачи.
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
28.01.2014, 11:40     Удаление структуры из двусвязного списка #6
Прошу прощения, здесь видимо надо было добавить функцию создания списка для ясности.
Создайте конструктор для структуры:
C++
1
2
spis():prev(NULL), next(NULL)
{}
Тогда указатели будут по умолчанию указывать туда куда надо.
Gad
 Аватар для Gad
12 / 0 / 0
Регистрация: 27.01.2014
Сообщений: 31
28.01.2014, 12:37  [ТС]     Удаление структуры из двусвязного списка #7
Цитата Сообщение от Ilot Посмотреть сообщение
Создайте конструктор для структуры:
C++
1
2
spis():prev(NULL), next(NULL)
{}
Тогда указатели будут по умолчанию указывать туда куда надо.
Так вроде не было с этим проблем или я не понял что-то. Мы этой темы еще не проходили, сомневаюсь, что нам давали бы задания с таким элементом, но я уже читал про классы и конструкторы в них, добавил в структуру такой конструктор. Проблема в не выполняющемся условии в функции del()
C++
1
if(p->year==year2)
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
28.01.2014, 13:06     Удаление структуры из двусвязного списка #8
Посмотрел внимательно код. Уважаемый так делать не надо. Создайте два класса один представляет собой список, второй элементы списка. Указатели на голову и хвост нужно хранить именно в объекте список, а не в элементах, так как эти поля у всех элементов могут быть разными.
C++
1
2
3
4
5
   
     head=p->next;
        head->prev=NULL;
        free(p);
        p=head;
Другими словами вы изменете поля объекта, который затем удаляете? Круто.
Сейчас попробую набросать реализацию.
Gad
 Аватар для Gad
12 / 0 / 0
Регистрация: 27.01.2014
Сообщений: 31
28.01.2014, 13:25  [ТС]     Удаление структуры из двусвязного списка #9
Цитата Сообщение от Ilot Посмотреть сообщение
C++
1
2
3
4
5
   
     head=p->next;
        head->prev=NULL;
        free(p);
        p=head;
Другими словами вы изменете поля объекта, который затем удаляете? Круто.
Сейчас попробую набросать реализацию.
Мы указателю head присваиваем указатель на следующую структуру, а в этой структуре указатель на предыдущую затираем и она у нас становиться первой. Я не очень большой спец, но как-то так.
Вся соль, что так в учебнике написано было) Я вроде как еще не знаю о классах и конструкторах\деструкторах
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
28.01.2014, 15:34     Удаление структуры из двусвязного списка #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Примерно так:
Кликните здесь для просмотра всего текста
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
#include <iostream>
 
struct Element{
    int data;
    Element* next;
    Element* prev;
    Element(): next(NULL), prev(NULL), data(0)
    {}
    Element(int d): next(NULL), prev(NULL), data(d)
    {}
};
struct List{
    Element* head;
    Element* tail;
    List(): head(NULL), tail(NULL)
    {}
    void AddElement(int d)
    {
        Element* NewElement = new Element(d);
        if (tail == NULL && head == NULL) {
            tail = NewElement;
            head = NewElement;
        }
        else {
            NewElement->next = tail;
            tail->prev = NewElement;
            tail = NewElement;
        }
    }
    void RemoveElement(int d)
    {
         Element* temp = tail;
         while (temp!= NULL)
         {
            Element* remove = NULL;
            if (temp->data == d) {
                if (temp->prev != NULL)
                    temp->prev->next = temp->next;
                if (temp->next != NULL)
                    temp->next->prev = temp->prev;
 
                if (temp == tail)
                    tail = temp->next;
                if (temp == head)
                    head = temp->prev;
                remove = temp;
            }
            temp = temp->next;
            if (remove != NULL)
                delete remove;
         }
    }
};
int main(void)
{
    List list1;
    list1.AddElement(1);
    list1.AddElement(2);
 
    list1.AddElement(3);
    list1.AddElement(4);
    list1.AddElement(5);
    list1.AddElement(6);
 
    Element* temp = list1.tail;
    while(temp != NULL)
    {
        std::cout << temp->data << ' ';
        temp = temp->next;
    }
    std::cout << std::endl;
 
    list1.RemoveElement(5);
    list1.RemoveElement(3);
    list1.RemoveElement(6);
 
    temp = list1.tail;
    while(temp != NULL)
    {
        std::cout << temp->data << ' ';
        temp = temp->next;
    }
    std::cout << std::endl;
 
    return 0;
}

Новые элементы добавляются в хвост.
Gad
 Аватар для Gad
12 / 0 / 0
Регистрация: 27.01.2014
Сообщений: 31
04.02.2014, 12:33  [ТС]     Удаление структуры из двусвязного списка #11
Цитата Сообщение от Ilot Посмотреть сообщение
Новые элементы добавляются в хвост.
Спасибо! Не совсем то, что надо было, но очень помогло, особенно в отношении понимания классов. Так, что ваш ответ лучший. Свою же задачу выполнил вот так. Может кому потом пригодится.
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
void del()   // udalenie zapisi
{
spis *temp, *p=head; // vvodim vremennuu peremenuu temp, nugna dla udalenia tekushei strukturi, p=head - na nachalo spiska.
    int g;
        clrscr();
    printf("\n Vvedite god:");
    scanf("%10d",&g);
    printf("\n Delete zapisi menshim godom ");
 
    do{
        if(p->year<=g)  // esli nashli zapis
        {
            printf("Udalaem Zapis: %20c",p->name);
            printf("Udalaem Zapis: %20c",p->author);
            printf("Udalaem Zapis: %18d",p->year);
            if (head==tail) // esli zapis edinstvennaya
            {
                head=NULL;
                tail=NULL;
 
            }
            else if (p->prev==NULL) //esli zapis pervaya 
            {
                head=p->next;
                p->next->prev=NULL;
 
            }
            else if (p->next==NULL)  //esli zapis poslednaya
            {
                tail=p->prev;
                p->prev->next=NULL;
 
            }
            else  // udalaem zapis iz serediny
            {
                p->prev->next=p->next; // v predydushei i posleduyshey strukturah mi perepisyvaem ukazateli
                p->next->prev=p->prev; //  drug na druga minuy tekushuu
 
            }
            temp=p;
            p=p->next;
            free(temp); // osvobogdaem pamat
        }
        else{
        p=p->next;  // perehodim k sleduushemu elementu
        }
    } while(p!= NULL); // poka ne konec
}
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
04.02.2014, 12:40     Удаление структуры из двусвязного списка #12
Ilot, а зачем мучаться с классами ради одного списка, если проект написан без ООП?
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
04.02.2014, 12:56     Удаление структуры из двусвязного списка #13
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
void del()   // udalenie zapisi
{
spis *temp, *p=head; // vvodim vremennuu peremenuu temp, nugna dla udalenia tekushei strukturi, p=head - na nachalo spiska.
    int g;
        clrscr();
    printf("\n Vvedite god:");
    scanf("%10d",&g);
    printf("\n Delete zapisi menshim godom ");
 
    do{
        if(p->year<=g)  // esli nashli zapis
...

Вот так делать нельзя. Если в списке нет элементов схватите краш. У вас нет проверки, что указатель p не ссылается на ноль.
Вот этот блок:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  else if (p->prev==NULL) //esli zapis pervaya 
            {
                head=p->next;
                p->next->prev=NULL;
 
            }
            else if (p->next==NULL)  //esli zapis poslednaya
            {
                tail=p->prev;
                p->prev->next=NULL;
 
            }
            else  // udalaem zapis iz serediny
            {
                p->prev->next=p->next; // v predydushei i posleduyshey strukturah mi perepisyvaem ukazateli
                p->next->prev=p->prev; //  drug na druga minuy tekushuu
 
            }

Я бы переписал вот так:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
           
if (p->prev==NULL) //esli zapis pervaya 
{
        head=p->next;
        p->next->prev=NULL;
}
if (p->next==NULL)  //esli zapis poslednaya
{
    tail=p->prev;
    p->prev->next=NULL;
}
if ((p->prev !=NULL)
&& (p->next != NULL))   // udalaem zapis iz serediny
{
    p->prev->next=p->next; // v predydushei i posleduyshey strukturah mi perepisyvaem ukazateli
    p->next->prev=p->prev; //  drug na druga minuy tekushuu
}

Это не принципиально однако так легче понять код. Мое мнение.

Вот здесь:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
if(...)
{
...
            temp=p;
            p=p->next;
            free(temp); // osvobogdaem pamat
        }
        else{
        p=p->next;  // perehodim k sleduushemu elementu
        }

Не грамотно использовать один и тот же код дважды. Может лучше так:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
    if(...)
    {
    ...
        temp=p;
 
    }
p=p->next;  // perehodim k sleduushemu elementu
if (temp != NULL)
            free(temp); // osvobogdaem pamat
}
Gad
 Аватар для Gad
12 / 0 / 0
Регистрация: 27.01.2014
Сообщений: 31
04.02.2014, 13:19  [ТС]     Удаление структуры из двусвязного списка #14
Цитата Сообщение от Ilot Посмотреть сообщение
Вот так делать нельзя. Если в списке нет элементов схватите краш. У вас нет проверки, что указатель p не ссылается на ноль.
Эээ... вот о об этом я как-то не подумал)) из-за невнимательности видимо, очень долго рождалось это решение, остальные замечания учту на будущее, сама же работа уже ушла на проверку. Спасибо!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.10.2014, 13:39     Удаление структуры из двусвязного списка
Еще ссылки по теме:

"Сортировка двусвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка C++
Реверс двусвязного списка C++
C++ Удаление из двусвязного циклического списка

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

Или воспользуйтесь поиском по форуму:
Fear1911
6 / 3 / 7
Регистрация: 05.02.2014
Сообщений: 131
02.10.2014, 13:39     Удаление структуры из двусвязного списка #15
Ilot, восхитительно) два дня убивался)) нашел реализацию)

Можно узнать реализацию, чтобы наконец-то понял, что куда идет?)
Yandex
Объявления
02.10.2014, 13:39     Удаление структуры из двусвязного списка
Ответ Создать тему
Опции темы

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