Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Правила Карта форума Темы раздела Блоги Социальные группы Поиск Сообщения за день  
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 06.03.2017
Сообщений: 11
1

Кольцевые списки на базе двунаправленных списков

06.03.2017, 08:13. Показов 1198. Ответов 6
Метки нет (Все метки)
Студворк — интернет-сервис помощи студентам
Всем привет! Помогите решить задачу:
Пусть L обозначает кольцевой двунаправленный список с включенным заглавным звеном. Написать функцию удаления из списка L первого звена , содержащего отрицательный элемент (если такое звено найдется).

Добавлено через 36 минут
есть набросок, но выдает системную ошибку

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
129
130
131

#include "StdAfx.h"
#include <iostream>
#include < conio.h >
 
using namespace std;
 
struct node
{
  int elem;
  node *sled;
  node *pred;
};
 
class Spisok
{
  private:
    node *nsp;
  public:
    Spisok() {nsp=NULL;}
    void BuiltRing ();
    void VyvodLeftRight();
    void Poisk ();
    void Delete (node*);
    void Ochistka ();
};
 
void main ()
{ 
    setlocale(LC_ALL,"RUS");
  
    Spisok A;
    A. BuiltRing ();   
       cout<< "До удаления: \n";
    A. VyvodLeftRight ();   
    A. Poisk();
       cout<< "После удаления: \n" ; 
    A. VyvodLeftRight ();
 
  getch (); 
  A.Ochistka ();
}
 
void Spisok::BuiltRing ()
// Построение двунаправленного кольцевого списка nsp 
{
  node *r;
  int el;
  //Построим заглавное звено кольцевого списка.
  nsp = new(node);
  r = nsp; (*nsp).pred = NULL; (*nsp).sled = NULL;
 
  cout<<"Введите элементы списка: \n";
    cin>>el;
  while  (el!=0)
  {
    (*r).sled = new (node);
    (*((*r).sled)).pred = r; r = (*r).sled;
    (*r).sled = NULL; (*r).elem = el;
    cin>>el;
  }
  //А теперь - образуем кольцевой список!
  if  ((*nsp).sled!=NULL)
    { (*((*nsp).sled)).pred = r; (*r).sled = (*nsp).sled; }
  else
    cout<<"Кольцевой список пуст!\n";
}
 
void Spisok::VyvodLeftRight ()
// Вывод содержимого двунаправленного кольцевого списка
// с  заглавным звеном "по часовой стрелке".
// nsp - указатель на заглавное звено списка.
{
  node *r;
 
  cout<<"Кольцевой список: ";
  if  ((*nsp).sled!=NULL)
  {
    cout<<(*((*nsp).sled)).elem<<" ";
    r = (*((*nsp).sled)).sled;
    while  (r!=(*nsp).sled)
      { cout<<(*r).elem<<" "; r = (*r).sled; }
    cout<<endl;
  }
  else cout<<"пуст!";
}
void Spisok::Poisk ()
    //поиск отрицательного элемента
{ node *p;
 
  p = (*nsp).sled;
    
  while ( p!= nsp && (*p).elem >0) 
    {
     p = (*p).sled;
    }
 
   if (p!= nsp)
 
       Delete(p);
 
}
void Spisok::Delete (node *Res)
// Удаление из кольцевого двунаправленного списка
// звена, на которое указывает ссылка Res.
// nsp - указатель на заглавное звено списка.
{
  if  ((*Res).sled==Res)
    { (*nsp).sled = NULL; delete Res; }
  else
  {
    (*(*Res).sled).pred = (*Res).pred;
    (*(*Res).pred).sled = (*Res).sled;
    if  ((*nsp).sled==Res)
      // Удаляем "первое" звено кольца.
      (*nsp).sled = (*Res).sled;
    delete Res;
  }
}
 
 
void Spisok::Ochistka()
{
  node *q,*q1;
 
  q = (*((*nsp).sled)).sled;
  q1 = (*q).sled;
  while (q1!=(*((*nsp).sled)).sled)
    { delete q; q=q1; q1=(*q1).sled; }
  delete q;
  delete nsp;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 06.03.2017, 08:13
Ответы с готовыми решениями:

Использование двунаправленных списков
Здравствуйте. Помогите решить задачу. Задание: Переместить во второй список все элементы,...

Кольцевые списки
люди добрые, написал программу, теперь надо в ней сделать эти три списка в один кольцевой, но при...

Реализация двунаправленных списков в компьютере
Задание: 1. инициализация списка: присвоение текущему, начальному и конечному указателю...

Реализация двунаправленных списков в компьютере
Привет, ув. форумчане. Необходима помощь в реализации задачи &quot;получение значения текущего элемента&quot;...

6
Helper C/C++
286 / 163 / 122
Регистрация: 22.09.2016
Сообщений: 518
06.03.2017, 10:00 2
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

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
 
typedef struct List
{
    int n_val;
    List* prev;
    List* next;
} LIST;
 
LIST* pList = NULL, *pHead = pList, *pTail = pList;
 
int main(int argc, char** argv)
{
    srand((unsigned)time(NULL));
    
    for (int i = 0; i < 10; i++)
    {
        LIST* pNode = new LIST;
        pNode->n_val = (rand() % 10 + 1) - (rand() % 10 + 1);
        pNode->prev = pTail; pNode->next = NULL;
 
        printf("%d ", pNode->n_val);
 
        if (pList != NULL)
        {
            pTail->next = pNode;
            pTail = pNode;
        }
 
        else
        {
            pList = pNode;
            pHead = pTail = pList;
        }
    }
 
    pTail->next = pList;
 
    printf("\n\n");
 
    bool found = false;
    while (pList != NULL && !found)
    {
        if (pList->n_val < 0)
        {
            found = true;
            if (pList->prev != NULL)
                pList->prev->next = pList->next;
            else {
                pList->next->prev = NULL;
                pTail->next = pList->next;
            }
        
            if (pList->next != NULL)
                pList->next->prev = pList->prev;
            else {
                pList->prev->next = pTail;
            }
 
            pList = pList->next;
        }
 
        else pList = pList->next;
    }
 
    int n = 0;
    while (pList != NULL)
    {
        printf("n_val[%d] = %d\n", n, pList->n_val);
        _getch();
        
        pList = pList->next;
        n++;
    }
 
    return 0;
}
0
0 / 0 / 0
Регистрация: 06.03.2017
Сообщений: 11
06.03.2017, 10:08  [ТС] 3
спасибо, все работает. Но можно сделать без рандома? Ввод данных должен осуществляться пользователем
0
Helper C/C++
286 / 163 / 122
Регистрация: 22.09.2016
Сообщений: 518
06.03.2017, 10:20 4
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 <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
 
typedef struct List
{
    int n_val;
    List* prev;
    List* next;
} LIST;
 
LIST* pList = NULL, *pHead = pList, *pTail = pList;
 
int main(int argc, char** argv)
{
    srand((unsigned)time(NULL));
    
    for (int i = 0; i < 10; i++)
    {
        LIST* pNode = new LIST;
        printf("Enter a value n_val = "); scanf("%d",&pNode->n_val);        
        pNode->prev = pTail; pNode->next = NULL;
 
        if (pList != NULL)
        {
            pTail->next = pNode;
            pTail = pNode;
        }
 
        else
        {
            pList = pNode;
            pHead = pTail = pList;
        }
    }
 
    pTail->next = pList;
 
    printf("\n\n");
 
    bool found = false;
    while (pList != NULL && !found)
    {
        if (pList->n_val < 0)
        {
            found = true;
            if (pList->prev != NULL)
                pList->prev->next = pList->next;
            else {
                pList->next->prev = NULL;
                pTail->next = pList->next;
            }
        
            if (pList->next != NULL)
                pList->next->prev = pList->prev;
            else {
                pList->prev->next = pTail;
            }
 
            pList = pList->next;
        }
 
        else pList = pList->next;
    }
 
    int n = 0;
    while (pList != NULL)
    {
        printf("n_val[%d] = %d\n", n, pList->n_val);
        _getch();
        
        pList = pList->next;
        n++;
    }
 
    return 0;
}
0
0 / 0 / 0
Регистрация: 06.03.2017
Сообщений: 11
07.03.2017, 16:53  [ТС] 5
все равно реализация не такая, очень все за мудрено написано( , но все равно спасибо, старались, писали.
0
0 / 0 / 0
Регистрация: 06.03.2017
Сообщений: 11
13.03.2017, 07:18  [ТС] 6
маленький недочет в поиске отрицательного элемента, не могу исправить, помогите пожалуйста!


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

#include "StdAfx.h"
#include <iostream>
#include < conio.h >
 
using namespace std;
struct node
{
  int elem;
  node *sled;
  node *pred;
};
 
class Spisok
{
  private:
    node *nd;//Указатель на начало дека.
    node *kd;//Указатель на конец  дека.
    int klad;//Информационное поле удаленного элемента.
  public:
    void BuiltDeck ();
    void VyvodDeck ();
    void Poisk();
    void DelLeft(node*Res);
    void Ochistka();
};
 
void main ()
{ setlocale(LC_ALL,"RUS");
 
  Spisok A;
 
  A.BuiltDeck ();
  cout<< "До удаления: \n" ; 
  A.VyvodDeck ();
  A.Poisk();
  cout<< "После удаления: \n" ; 
   A.VyvodDeck ();
    getch (); 
  A.Ochistka();
}
 
void Spisok::BuiltDeck ()
// Построение дека на базе двунаправленного
// списка с заглавным звеном.
// nd - указатель на начало дека,
// *kd - указатель на конец дека.
{
  node *q;
  node *z;
  int  el;
 
  nd = new(node);
  z = nd;
  (*nd).pred = (*nd).sled = NULL;
  cout<<"Введите последовательность: \n";
  cin>>el;
  while  (el!=0)
  { (*z).sled = new (node);
    (*((*z).sled)).pred = z;
    z = (*z).sled; (*z).sled = NULL;
    (*z).elem = el; cin>>el;}
    if  ((*nd).sled!=NULL)
      { q = nd; nd = (*nd).sled; (*nd).pred = NULL;
        kd = z; delete q; }
    else 
      { delete nd; nd = kd = NULL; }
}
 
void Spisok::VyvodDeck ()
// Вывод содержимого дека.
// nd - указатель на начало дека.
{
  node *z;
 
  z = nd; cout<<"Содержимое дека: ";
  if  (z!=NULL)
    while  (z!=NULL)
     { cout<<(*z).elem<<" "; z = (*z).sled; }
  else  cout<<"он пуст!\n";
  cout<<endl;
}
 
void Spisok::Poisk()
    // поиск отрицательного элемента
{ node *p;
 
 p=(*nd).sled;
 
while (p!=nd && (*p).elem >= 0)
 {
     p=(*p).sled;
 }
 
 if (p!=nd)
     DelLeft (p);
 
}
 
void Spisok::DelLeft(node*Res)
// Удаление звена из дека слева с помещением
// элемента удаляемого звена в переменную klad.
// nd - указатель на начало дека,
{node *p;
  if  ((*nd).sled!=NULL)
    { p = nd; klad =(*p).elem;
      nd = (*nd).sled; (*nd).pred = NULL; delete p; }
  else
    { // В деке находится один элемент.
      p = nd; klad =(*p).elem;
      nd = kd = NULL; delete p;cout<<"Дек пуст!\n"; 
    }
}
 
void Spisok::Ochistka()
{
  node *q,*q1;
 
  q = nd;
  q1 = (*q).sled;
  while (q1!=NULL)
    { delete q; q = q1; q1 = (*q).sled;}
  delete q;
  nd = kd = NULL;
}
0
0 / 0 / 0
Регистрация: 06.03.2017
Сообщений: 11
27.03.2017, 08:44  [ТС] 7
задача решена, спасибо за помощь.
0
27.03.2017, 08:44
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 27.03.2017, 08:44
Помогаю со студенческими работами здесь

Реализация двунаправленных списков в компьютере
Задание: 1. инициализация списка: присвоение текущему, начальному и конечному указателю...

Кольцевые списки
Здравствуйте, как реализовать удаление в кольцевом списке ? Читал, что можно сделать так, чтобы при...

Кольцевые списки
Зачем нужны кольцевые односвязные и двусвязные списки? Когда они могут понадобиться? Ведь, если...

Двунаправленные кольцевые списки
Здравствуйте, уважаемые форумчане! Нужна помощь в доработке Двунаправленного кольцевого списка ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru