Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.72/25: Рейтинг темы: голосов - 25, средняя оценка - 4.72
-2 / 0 / 0
Регистрация: 12.11.2015
Сообщений: 60
1

Реализовать кольцевой список. Как закольцевать список обычный?

12.11.2015, 20:00. Просмотров 4671. Ответов 8
Метки нет (Все метки)

Помогите пожалуйста реализовать кольцевой список. Я так понимаю, он может быть двусвязным и односвязным?
Меня интересует односвязный. Односвязный список реализовывать умею, а как указать, что это кольцо, вопрос большой.Заранее спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.11.2015, 20:00
Ответы с готовыми решениями:

Односвязный кольцевой список, реализовать
Помогите написать и реализовать кольцевой список

Используя кольцевой однонаправленный список, реализовать детскую считалку
Всем привет. Есть задача: Используя кольцевой однонаправленный список, реализовать детскую...

Закольцевать и отсортировать двунаправленный список
создать двунаправленный список с числами из диапазона от - 50 до + 50. после создания списка...

Создать класс «Квартира», в котором список комнат реализовать как односвязный список
Добрый день,написал фот такой клас по заданию:Создать класс «Квартира», в котором список комнат...

8
5 / 5 / 3
Регистрация: 19.09.2010
Сообщений: 173
12.11.2015, 20:11 2
Для односвязного: полю next последнего элемента присвойте указатель на первый элемент списка. В моем понимании - это и будет кольцо.
0
259 / 86 / 30
Регистрация: 29.10.2015
Сообщений: 196
12.11.2015, 20:16 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
25
26
27
28
29
30
31
typedef struct _MyList{
int data;
MyList * next;
}MyList;
 
......
 
MyList * AddAfter(int a, MyList * current)//вставим элемент в подготовленный закольцованный список в позицию current
{
MyList * newel = new MyList;
newel->data = a;
 
//теперь вклиним элемент в цепочку
newel->next = current->next;
current->next = newel;
return newel;
}
 
.....
//а вот так делается инициализация и подготовка
MyList list;
list.data=1;
list.next = &list; //первый элемент - закольцован сам на себя
 
//и далее добавляем к нему элементы
MyList * lst = &list;
for(int i=0;i<10;i++)
if(lst)
{
lst = AddAfter(i,lst);
}
0
-2 / 0 / 0
Регистрация: 12.11.2015
Сообщений: 60
13.11.2015, 14:40  [ТС] 4
а как удалить элемент из такого списка? я всё реализую в классе
0
259 / 86 / 30
Регистрация: 29.10.2015
Сообщений: 196
13.11.2015, 17:57 5
1. Есть небольшая сложность в том, что список однонаправленный - поэтому придется сделать функцию поиска предыдущего элемента, в которой нужно пробежать список по кругу, пока next не будет равен удаляемому элементу.
2. У предыдущего элемента - next присвоить значению next текущего элемента.
3. Сделать очистку памяти у текущего элемента.

И все.

я всё реализую в классе
Это ни о чем не говорит, так как реализаций может быть великое множество.
0
-2 / 0 / 0
Регистрация: 12.11.2015
Сообщений: 60
14.11.2015, 09:25  [ТС] 6
спасибо,работает такой вариант.
int Ring:J(int n,int name)
{
if(first==NULL) return false;
Node *plast=first, *p=first;
int i=0;
do
{
while(i<name)//нахожу заданное число, т.е name
{
p=p->next;
i++;
}
}while(plast!=first);
do
{
if(i>size())
i=0;
i+=n;
printf("i=%d, ",i);
printf("p->data=%d\n",p->data);
del(i);
p=p->next;
}while(p!=first);
return true;
}
мне нужно реализовать задачу Джозефуса. Элементы(name) становятся в круг, вводится некоторое число n. Необходимо, начиная с первого, отсчитать n-й элемент списка и удалить его. Далее отсчет начинается с (n+1)-го элемента и опять удаляется n-ый. Так продолжается до тех пор, пока в списке не останется один элемент. Выдать содержимое последнего элемента.
Написала только это, но работает вообще очень странно, что изменить нужно?
0
259 / 86 / 30
Регистрация: 29.10.2015
Сообщений: 196
14.11.2015, 14:06 7
Оформите код, и дайте более полную версию. По неоформленным выжимкам понять ход ваших мыслей трудно.
0
-2 / 0 / 0
Регистрация: 12.11.2015
Сообщений: 60
15.11.2015, 10:31  [ТС] 8
//Seq.h
#pragma once

#include <stdio.h>

class Ring
{
struct Node
{
int data;
Node *next;
};
Node *first;
// int sz;
public:
Ring(): first(NULL){};

int get();
bool del(int k);
void add(int n);
void next(int n=1);
bool find(int n);
void clear();
int size();
int DJ(int n,int name);
void show();
};

//Seq.cpp
#include "stdafx.h"
#include "Seq.h"

int Ring::get()
{
if(first==NULL) return 0; // error
return first->data;
}

void Ring::next(int n)
{
if(first==NULL) return;
int sz=0;
Node *p=first;
while(n-- && (first=first->next)!=p)++sz;
if(n<=0) return;
n%=sz;
while(n--) first=first->next;
}
bool Ring::del(int n)
{
if(first==NULL) return false;
Node *plast=first, *p=first;
int i=0;
do
{
while(i<n-1)
{
p=p->next;
i++;
}
Node*buf=p->next;
p->next=buf->next;
delete buf;
}while(plast!=first);
return true;
}
int Ring:J(int n,int name)
{
if(first==NULL) return false;
Node *plast=first, *p=first;
int i=0;
do
{
while(i<name)
{
p=p->next;
i++;
}
}while(plast!=first);
int k=i;
printf("\n%d\n",p->data);
do
{
if(i>size())
i=0;
i=i+n;
printf("i=%d, ",i);
printf("p->data=%d\n",p->data);
del(i);
p=p->next;
}while(p!=first);
return true;
}
bool Ring::find(int n)
{
if(first==NULL) return false;
Node *p=first;
while((first=first->next)!=p)
if(first->data==n) return true;
return false;
}

//bool Ring::del()
//{
// if(first==NULL) return false;
// Node *p=first->next;
// first->data=p->data;
// first->next=p->next;
// if(first==p) first=NULL;
// delete p;
// // --sz;
// return true;
//}

void Ring::clear()
{
if(first!=NULL){
Node *plast=first, *p;
do {
p=first->next;
delete first;
first=p;
} while(plast!=first);
first=NULL;
}
// sz=0;
}

void Ring::add(int n)
{
Node *p=new Node;
p->data=n;
if(!first)
{
p->next=p;
first=p;
}
else
{
p->next=first->next;
first->next=p;
}
// ++sz;
}

int Ring::size()
{
if(first==NULL) return 0;
int sz=1;
Node *p=first;
while((first=first->next)!=p) ++sz;
return sz;
}


void Ring::show()
{
if(first!=NULL)
{
Node *p=first;
do
{
printf("%d ", first->data);
} while((first=first->next)!=p);
}
else printf("empty");
printf("\n");
}
//main()

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include "Seq.h"

int main()
{
Ring a;
a.add(1);
a.add(5);
a.add(4);
a.add(3);
a.add(2);
a.add(6);
a.add(7);
printf("Size of ring: %d\n", a.size());
int S=0;
for(int i=a.size()*2; i>0; --i)
{
a.show();
a.next();
}

//a.del(4);
//a.show();
int n=2;
int name=1;
int k=a.size();
a.DJ(n,name);
a.show();
a.clear();


system("pause");
return 0;
}


вот код

Добавлено через 2 часа 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
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
//Seq.h
#pragma once
 
#include <stdio.h>
 
class Ring 
{
struct Node
{
int data;
Node *next;
};
Node *first;
// int sz;
public:
Ring(): first(NULL){};
 
int get();
bool del(int k);
void add(int n);
void next(int n=1);
bool find(int n);
void clear();
int size();
int DJ(int n,int name);
void show();
};
 
//Seq.cpp
#include "stdafx.h"
#include "Seq.h"
 
int Ring::get()
{
if(first==NULL) return 0; // error
return first->data;
}
 
void Ring::next(int n)
{
if(first==NULL) return;
int sz=0;
Node *p=first;
while(n-- && (first=first->next)!=p)++sz;
if(n<=0) return;
n%=sz;
while(n--) first=first->next;
}
bool Ring::del(int n)
{
if(first==NULL) return false;
Node *plast=first, *p=first;
int i=0;
do
{
while(i<n-1)
{
p=p->next;
i++;
}
Node*buf=p->next;
p->next=buf->next;
delete buf;
}while(plast!=first);
return true;
}
int Ring:J(int n,int name)
{
if(first==NULL) return false;
Node *plast=first, *p=first;
int i=0;
do
{
while(i<name)
{
p=p->next;
i++;
}
}while(plast!=first);
int k=i;
printf("\n%d\n",p->data);
do
{
if(i>size())
i=0;
i=i+n;
printf("i=%d, ",i);
printf("p->data=%d\n",p->data);
del(i);
p=p->next;
}while(p!=first);
return true;
}
bool Ring::find(int n)
{
if(first==NULL) return false;
Node *p=first;
while((first=first->next)!=p)
if(first->data==n) return true;
return false;
}
 
//bool Ring::del()
//{
//  if(first==NULL) return false;
//  Node *p=first->next;
//  first->data=p->data;
//  first->next=p->next;
//  if(first==p) first=NULL;
//  delete p;
//  // --sz;
//  return true;
//}
 
void Ring::clear()
{
if(first!=NULL){
Node *plast=first, *p;
do {
p=first->next;
delete first;
first=p;
} while(plast!=first);
first=NULL;
}
// sz=0;
}
 
void Ring::add(int n)
{
Node *p=new Node;
p->data=n;
if(!first)
{
p->next=p;
first=p;
} 
else 
{
p->next=first->next;
first->next=p;
}
// ++sz;
}
 
int Ring::size()
{
if(first==NULL) return 0;
int sz=1;
Node *p=first;
while((first=first->next)!=p) ++sz;
return sz;
}
 
 
void Ring::show()
{
if(first!=NULL)
{
Node *p=first;
do 
{
printf("%d ", first->data);
} while((first=first->next)!=p);
} 
else printf("empty");
printf("\n");
}
//main()
 
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include "Seq.h"
 
int main()
{
Ring a;
a.add(1);
a.add(5);
a.add(4);
a.add(3);
a.add(2);
a.add(6);
a.add(7);
printf("Size of ring: %d\n", a.size());
int S=0;
for(int i=a.size()*2; i>0; --i) 
{
a.show();
a.next();
}
 
//a.del(4);
//a.show();
int n=2;
int name=1;
int k=a.size();
a.DJ(n,name);
a.show();
a.clear();
 
 
system("pause");
return 0;
}
0
259 / 86 / 30
Регистрация: 29.10.2015
Сообщений: 196
15.11.2015, 23:11 9
Вчитывался в код более 10 минут - не очень понял, что вы делаете.
Подпишите комментарии у названий основных функций и у циклов.
И скопируйте код струкрурированный, а не выстроенный в линию. А то читать трудновато.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.11.2015, 23:11

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Реализовать указанные функции-члены для пользовательского класса "Кольцевой двусвязный список"
Сообственно сабж. У списка два закрытых поля: tail-это узел следующий за &quot;последним&quot;(условно,ибо...

Иерархия классов "Структура - Список - Кольцевой Двусвязный список"
Неделю назад получил задание и срок выполнения до конца мая. Разработка иерархии классов....

Как понять что кольцевой список кончился?
Как понять что кольцевой список кончился?

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


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

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

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