Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).
Узел ОЛС можно представить в виде структуры
{
int field; // поле данных
struct list *ptr; // указатель на следующий элемент
};
Основные действия, производимые над элементами ОЛС:
- Инициализация списка
- Добавление узла в список
- Удаление узла из списка
- Удаление корня списка
- Вывод элементов списка
- Взаимообмен двух узлов списка
Инициализация ОЛС
Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит нулевое значение.
2
3
4
5
6
7
8
9
{
struct list *lst;
// выделение памяти под корень списка
lst = (struct list*)malloc(sizeof(struct list));
lst->field = a;
lst->ptr = NULL; // это последний узел списка
return(lst);
}
Добавление узла в ОЛС
Функция добавления узла в список принимает два аргумента:
- Указатель на узел, после которого происходит добавление
- Данные для добавляемого узла.
Процедуру добавления узла можно отобразить следующей схемой:
Добавление узла в ОЛС включает в себя следующие этапы:
- создание добавляемого узла и заполнение его поля данных;
- переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
- установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).
Таким образом, функция добавления узла в ОЛС имеет вид:
2
3
4
5
6
7
8
9
10
{
struct list *temp, *p;
temp = (struct list*)malloc(sizeof(list));
p = lst->ptr; // сохранение указателя на следующий узел
lst->ptr = temp; // предыдущий узел указывает на создаваемый
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент
return(temp);
}
Возвращаемым значением функции является адрес добавленного узла.
Удаление узла ОЛС
В качестве аргументов функции удаления элемента ОЛС передаются указатель на удаляемый узел, а также указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.
Удаление узла может быть представлено следующей схемой:
Удаление узла ОЛС включает в себя следующие этапы:
- установка указателя предыдущего узла на узел, следующий за удаляемым;
- освобождение памяти удаляемого узла.
2
3
4
5
6
7
8
9
10
11
12
{
struct list *temp;
temp = root;
while (temp->ptr != lst) // просматриваем список начиная с корня
{ // пока не найдем узел, предшествующий lst
temp = temp->ptr;
}
temp->ptr = lst->ptr; // переставляем указатель
free(lst); // освобождаем память удаляемого узла
return(temp);
}
Удаление корня списка
Функция удаления корня списка в качестве аргумента получает указатель на текущий корень списка. Возвращаемым значением будет новый корень списка - тот узел, на который указывает удаляемый корень.
2
3
4
5
6
7
{
struct list *temp;
temp = root->ptr;
free(root); // освобождение памяти текущего корня
return(temp); // новый корень списка
}
Вывод элементов списка
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.
2
3
4
5
6
7
8
9
{
struct list *p;
p = lst;
do {
printf("%d ", p->field); // вывод значения элемента p
p = p->ptr; // переход к следующему узлу
} while (p != NULL);
}
Взаимообмен узлов ОЛС
В качестве аргументов функция взаимообмена ОЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого элемента списка.
Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:
- заменяемые узлы являются соседями;
- заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один элемент.
При замене соседних узлов переустановка указателей выглядит следующим образом:
При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:
При переустановке указателей необходима также проверка, является ли какой-либо из заменяемых узлов корнем списка, поскольку в этом случае не существует узла, предшествующего корневому.
Функция взаимообмена узлов списка выглядит следующим образом:
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
{
// Возвращает новый корень списка
struct list *prev1, *prev2, *next1, *next2;
prev1 = head;
prev2 = head;
if (prev1 == lst1)
prev1 = NULL;
else
while (prev1->ptr != lst1) // поиск узла предшествующего lst1
prev1 = prev1->ptr;
if (prev2 == lst2)
prev2 = NULL;
else
while (prev2->ptr != lst2) // поиск узла предшествующего lst2
prev2 = prev2->ptr;
next1 = lst1->ptr; // узел следующий за lst1
next2 = lst2->ptr; // узел следующий за lst2
if (lst2 == next1)
{ // обмениваются соседние узлы
lst2->ptr = lst1;
lst1->ptr = next2;
if (lst1 != head)
prev1->ptr = lst2;
}
else
if (lst1 == next2)
{
// обмениваются соседние узлы
lst1->ptr = lst2;
lst2->ptr = next1;
if (lst2 != head)
prev2->ptr = lst2;
}
else
{
// обмениваются отстоящие узлы
if (lst1 != head)
prev1->ptr = lst2;
lst2->ptr = next1;
if (lst2 != head)
prev2->ptr = lst1;
lst1->ptr = next2;
}
if (lst1 == head)
return(lst2);
if (lst2 == head)
return(lst1);
return(head);
}
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
using namespace std;
struct NODE {
char value;
struct NODE* next;
};
struct DbCircleList {
size_t size;
struct NODE* head;
};
void addNode(DbCircleList* list, char elem)
{
NODE* newElem = new NODE;
newElem->value = elem;
if (list->size == 0)
{
list->head = newElem;
list->head->next = list->head;
}
else
{
struct NODE* temp;
temp = list->head;
list->head = newElem;
newElem->next = temp;
}
++list->size;
}
void printList(DbCircleList* list)
{
NODE* tmp = list->head;
cout << "List values: " << endl;
for (int i = 0; i < list->size; ++i)
{
cout << "Value: " << tmp->value << endl;
tmp = tmp->next;
}
}
int main()
{
DbCircleList* list = new DbCircleList;
list->size = 0;
list->head = NULL;
DbCircleList* list1 = new DbCircleList;
list1->size = 0;
list1->head = NULL;
DbCircleList* list2 = new DbCircleList;
list2->size = 0;
list2->head = NULL;
addNode(list, 'b');
addNode(list, 'b');
addNode(list, '3');
addNode(list, 'c');
addNode(list, '3');
addNode(list, '7');
printList(list);
printList(list1);
printList(list2);
delete list;
delete list1;
delete list2;
return 0;
}
Помогите !Сформировать однонаправленный список, элементами которого являются цифры и буквы. Выделить из него два списка: S1, в состав которого входят только буквы и список S2, состоящий исключительно изцифр. Вывести все списки на печать.
Здравствуйте. Есть задание: Создать список, который хранит информацию о книгах (название, автора, количество страниц, год выпуска и стиль). Вывести со списка книги художественного стиля.
Помогите, пожалуйста.
Вот мой код, если нужно:
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
#include <Windows.h>
#include <stdio.h>
#include <math.h>
#include <malloc.h>
struct book
{
char name[30];
char author[30];
int num_page;
int year;
char style[30];
struct book* next;
};
struct book* poperedbook, * element, * pershiy, * novii, * ostan;
void Stvorutu(void)
{
element = (struct book*)malloc(sizeof(struct book));
pershiy = element;
do
{
poperedbook = element;
printf("Введіть назву книги, автора, кількість сторінок, рік випуску та стиль \n");
scanf("%s %s %d %d %s", element->name, element->author, &element->num_page, \
& element->year, element->style);
element->next = (struct book*)malloc(sizeof(struct book));
element = element->next;
} while (poperedbook->num_page != 0);
ostan = poperedbook;
poperedbook->next = NULL;
}
void hood(void)
{
element = pershiy;
do
{
//if (element->style == "худ")
//{
printf("Назва книги: %s , Автор: %s , Кількість Сторінок: %d , Рік випуску: %d , Стиль: %s \n", \
element->name, element->author, &element->num_page, &element->year, element->style);
poperedbook = element;
element = element->next;
//}
} while (element != NULL);
}
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
Stvorutu();
hood();
return 0;
}
Сравнение с "худ" нужно делать посимвольное. С++ строки сравнивать сам не умеет, или нужна библиотека для обработки строк.
Здравствуйте, есть функция добавления элемента струкруты в список. А как сделать так, чтобы во время добавления элемент сразу вставал в нужное место, например чтобы добавление сразу сортировалось по фамилиям студента. Если ввел фамилию, начинающуюся на "А" и т.д., то элемент добавляется в начало списка?
//Добавление нового элемента
2
3
4
5
6
7
8
9
10
11
12
13
14
{
List* element = new List;
element->info = elem;
if (end == NULL)
{
beg = element;
end = element;
return;
}
end->next = element;
end = element;
cout << endl;
}
В функцию нужно передать два параметра: значение элемента и указатель на элемент, после которого нужно вставить элемент с заданным значением.
Здравствуйте. Вы описали работу со списками в одно-поточном случае, но современные многоядерные процессоры более эффективны для мульти-поточных приложений. А там при использовании списков без синхронизации не обойтись — все манипуляции выполняются под закрытым семафорным элементом (как правило, мьютексом). Возникает вопрос: существует ли алгоритм работы (представляют интерес только операции добавления в хвост и изъятие с головы) с односвязными списками типа "очередь" (FIFO, два описателя — "голова" и "хвост"), не использующий семафорные элементы, а только атомарные операции (например, типа "сравнить-и-обменять")? Для списков типа "стек" (LIFO, один описатель — "голова") такая реализация не вызывает затруднений и работает без проблем.
Добрый день. Не понимаю список в чужом коде. Как он работает?
В нем нет поля данных, только указатель на такой же узел в списке:
2
struct _P_NEXT { P_NEXT* p_el; };
Я тоже не понимаю
Здравствуйте. Помогите пожалуйста. Не работает функция разбиения списка на четные и нечетные.
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
int ptr;
list *next;
};
void input_list(list *&first, int n) {
first = new list;
cinn >> first->ptr;
list *q = first;
for (int i = 0; i < n — 1; i++) {
q->next = new list;
q = q->next;
cin>>q->ptr;
}
q->next = 0;
}
void print_list(list *q) {
while (q) {
cout << q->ptr << " ";
q = q->next;
}
cout << endl;
}
void razbienie_list(list *&first){
list *q = first;
list *chet = new list;
list *nechet = new list;
list *q1 = chet;
list *q2 = nechet;
list *w1 = q1;
list *w2 = q2;
while (p) {
if (q->ptr % 2) {
q2->ptr = p->ptr;
q2->next = new list;
w2 = q2;
q2 = q2->next;
}
else {
q1->ptr = p->ptr;
q1->next = new list;
q1 = q1;
q1 = q1->next;
};
q = q->next;
}
w1->next = 0;
w2->next = 0;
}
int main(){
list *first = 0;
int n = 5;
input_list(first, n);
print_list(first);
razbienie_list(first);
print_list(first);
return 0;
}
Добрый день! Подскажите пожалуйста как мне в main найти указатель pos чтобы удалить элемент структуры:
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
#include <string>
using namespace std;
const int maxSize = 100;
//Описываем структуру Wood со следующими полями:
//index — номер дерева в базе;
//name — название дерева;
//type — его тип;
//MaximumHeight — максимальная высота;
//lifespan — продолжительность жизни;
struct Wood
{
char name[maxSize];
char type[maxSize];
double MaximumHeight;
double lifespan;
Wood* Next;
};
Wood* Head;
//Функция для ввода информации об очередном дереве.
void WoodInput(char name[maxSize], char type[maxSize], double& MaximumHeight, double& lifespan)
{
cout << "Name = ";
cin.get();
cin.get(name, sizeof(name));
cout << "Type = ";
cin.get();
cin.get(type, sizeof(type));
cout << "MaximumHeight = ";
cin >> MaximumHeight;
cout << "lifespan = ";
cin >> lifespan;
cout << endl;
}
//Функция для вывода массива деревьев.
void PrintWood(Wood* Head)
{
Wood* j = Head; // j указывает на начало
while (j != NULL); // Пока не конец списка
{
cout << "Wood: " << j->name << ";" << j->type << ";" << j->MaximumHeight << ";" << j->lifespan << ";";
j = j->Next; // переход к следующему элементу
}
cout << endl;
}
//Функция для поиска в базе деревьев с определенной продолжительностью жизни.
//Выводит найденные деревья и возвращает их количество.
//Входные параметры:
//ar — массив деревьев;
//n — число деревьев в массиве;
//age — возраст для поиска;
Wood* WoodSearch(Wood* Head, double lifespan)
{
Wood* p = Head; // указывает на начало
while (p != NULL) //Пока не конец списка
{
if (p->lifespan == lifespan) //Если элемент найден, то
break; //прерываем цикл
p = p->Next; //Переход к следующему элемент
}
return p;
}
//Функция удаления дерева по значению поля
void DeleteWood(Wood*& pbeg, Wood* pos)
{
//если список пуст или pos равен NULL
if (pbeg == NULL || pos == NULL)
return; //выходим
//Если pos указывает
//на начало
if (pos == pbeg)
{ //Пусть pbeg укажет на
//следующий элемент
pbeg = pbeg->Next;
//Освобождаем память,
//на которую указывает
//pos
delete pos;
}
else
{
Wood* prev = pbeg;
while (prev != NULL && prev->Next != pos)
prev = prev->Next;
if (prev != NULL)
{
prev->Next = pos->Next;
delete pos;
}
}
}
void FreeWood(Wood*& pbeg)
{
Wood* p;
while (pbeg != NULL)
{
p = pbeg;
pbeg = pbeg->Next;
delete p;
}
}
int main()
{
char name[maxSize] = {'\0'};
char type[maxSize] = {'\0'};
double MaximumHeight;
double lifespan;
Wood* Head = nullptr;
int n;
//Вводим число деревьев, которые будем хранить в массиве
cout << "Number of Wood = ";
cin >> n;
//Вводим информацию о всех деревьях с помощью реализованной функции
for (int i = 0; i < n; i++)
{
WoodInput(name, type, MaximumHeight, lifespan);
}
// удаление элемента
cout << " deleted Woods = ";
cin >> lifespan;
DeleteWood(Head, WoodSearch(Head, lifespan)); // ЗДЕСЬ ОШИБКА
PrintWood(Head);
FreeWood(Head);
system("pause");
return 0;
}
А Head как был nullptr, так и остался…
И следующая проблема возникнет, когда при выводе будут все деревья, равные последней записи. Потому что память выделяется один раз, а дальше только ссылки на нее создаваться будут.
Добрый день, не подскажете функцию вычитания из двух списков?
Это как?
Что-то вроде такого, только на си.
Мне просто задали сделать вычитание из двух списков, но я сам не понимаю как это сделать.
Создать 3 списка: A, B и C. Заполнить списки A и B исходными данными.
Сделать вложенный цикл.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
do {
a=A;
int flag = 0; // есть ли элемент списка B в списке A
do {
if(a->num == b->num)
{
flag = 1; // такой элемент имеется
… // удалить a, чтоб второй элемент с таким же значением из списка B с ним не сравнивался
break;
}
a = a->ptr;
}while(a!=NULL);
if(flag == 0)
…//Добавляем элемент в список C
b = b->ptr;
} while(b!=NULL);
Вот мой код, но первый элемент не удаляется.
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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <locale.h>
struct list
{
int field;
struct list* ptr;
};
// Инициализация списка (ОЛС)
struct list* init(int a)
{
struct list* head = (struct list*)malloc(sizeof(struct list));
head->field = a;
head->ptr = NULL;
return (head);
}
// Добавление элемента (возвращает добавленный элемент) (ОЛС)
struct list* addelem(struct list* lst, int number)
{
struct list* temp, * p;
temp = (struct list*)malloc(sizeof(struct list)); // выделение памяти под узел списка
p = lst->ptr; // временное сохранение указателя
lst->ptr = temp; // предыдущий узел указывает на создаваемый
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент
return(temp);
}
// Удаление корня списка (возвращает новый корень) (ОЛС)
struct list* deletehead(struct list* root)
{
struct list* temp;
temp = root->ptr;
free(root);
return(temp); // новый корень списка
}
// Удаление элемента списка (возвращает предшествующий элемент) (ОЛС)
struct list* deletelem(struct list* lst, struct list* root)
{
struct list* temp;
temp = root;
while (temp->ptr != lst) // просматриваем список начиная с корня
{ // пока не найдем узел, предшествующий lst
temp = temp->ptr;
}
temp->ptr = lst->ptr; // переставляем указатель
free(lst); // освобождаем память удаляемого элемента
return(temp);
}
// Вывод элементов списка (ОЛС)
void listprint(struct list* lst)
{
struct list* p;
p = lst;
do {
printf("%d ", p->field); // вывод значения элемента p
p = p->ptr; // переход к следующему элементу
} while (p != NULL);
}
struct list* add(struct list* head, int data)
{
struct list* temp, * p;
p = head->ptr;
temp = (struct list*)malloc(sizeof(struct list));
head->ptr = temp;
temp->field = data;
temp->ptr = p;
return (temp);
}
void print(struct list* a)
{
struct list* p = a;
while (p != NULL)
{
printf(" %d", p->field);
p = p->ptr;
}
}
void del(struct list* p, int v)
{
if (p == NULL)
return;
struct list* t = p;
if (t->ptr == v)
{
p = t->ptr;
free(t);
return;
}
struct list* t1 = t->ptr;
while (t1)
{
if (t1->field == v)
{
t->ptr = t1->ptr;
free(t1);
return;
}
t = t1;
t1 = t1->ptr;
}
}
void sub(struct list* a, struct list* b)
{
struct list* p2;
for (struct list* p2 = b; p2; p2 = p2->ptr)
del(a, p2->field);
/*struct list* p2;
p2 = b;
while (p2)
{
del(a, p2->field);
p2 = p2->ptr;
}*/
/* struct list* p1, * p2;
p1 = a;
p2 = b;
while (p1)
{
while (p2)
{
if (p1->field == p2->field)
deletelem(p1, p1->field);
p2 = p2->ptr;
}
p1 = p1->ptr;
}*/
}
int main()
{
setlocale(LC_ALL, "Russian");
/* struct list* p1 = (struct list*)malloc(sizeof(struct list));
struct list* p2 = (struct list*)malloc(sizeof(struct list));
p1 = init(5);
add(p1, 6);
add(p1, 9);
p2 = init(6);
add(p2, 7);
sub(p1, p2);
print(p1);
putchar('\n');
print(p2);*/
struct list* head, * head1, * r;
int a, n, e, l;
struct list* p1 = (struct list*)malloc(sizeof(struct list));
struct list* p2 = (struct list*)malloc(sizeof(struct list));
system("chcp 1251");
system("cls");
printf("n= ");
scanf_s("%d", &n);
head = 0;
head1 = 0;
p2 = 0;
p1 = 0;
// Создание списка
for (int i = 0; i < n; i++)
{
printf("Введите элемент:");
scanf_s("%d", &a);
if (i == 0)
{
head = p1 = init(a);
head1 = init(a);
head = p1;
}
else
p1 = add(p1, a);
}
// Вывод списка
listprint(head);
putchar('\n');
printf("e= ");
scanf_s("%d", &e);
for (int i = 0; i < e; i++)
{
printf("Введите элемент:");
scanf_s("%d", &l);
if (i == 0)
{
head1 = p2 = init(l);
head1 = init(l);
head1 = p2;
}
else
p2 = add(p2, l);
}
listprint(head1);
putchar('\n');
sub(head, head1);
sub(p1, p2);
print(head);
putchar('\n');
//print(head1);
free(p1);
free(p2);
//getch();
return 0;
}
Для удаления первого элемента есть функция deletehead(). Надо проверить, если элемент является корнем, то ее вызвать
Здравствуйте, подскажите, пожалуйста, почему у меня не работает вставка
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
using namespace std;
struct list
{
char inf;
list* next;
};
list* creat_1(char sym);
list* creat_ost();
void print(list* head);
void insert(list* head,char x,char y);
int main()
{
struct list* head,*cur,*u=NULL;
head = creat_ost();
print(head);
cout << endl;
cout << "after!!!" << endl;
char x, y;
cout << "vvedi y" << endl;
cin >> y;
cout << "vvedi x" << endl;
cin >> x;
insert(head, x, y);
print(head);
return 0;
}
list* creat_1(char sym)
{
list* first;
first = new list;
first->inf = sym;
first->next = NULL;
return first;
}
void print(list* head)
{
list* tmp;
tmp = head;
cout << "PRINT" << endl;
while (tmp != NULL)
{
cout << tmp->inf;
tmp = tmp->next;
}
}
list* creat_ost()
{
list* cur;
struct list* head;
char ch;
cin.get(ch);
head = creat_1(ch);
cur = head;
cin.get(ch);
while (ch != '.')
{
cur->next = new list;
cur = cur->next;
cur->inf = ch;
cur->next = NULL;
cin.get(ch);
}
return head;
}
void insert(list* head, char x, char y)
{
struct list* cur,*tmp;
cur = head;
while (cur->next = NULL)
{
if (cur->inf == y)
{
tmp = new struct list;
tmp->inf = x;
tmp->next = cur->next;
cur->next = tmp;
}
else
cur = cur->next;
}
return head;
}
while (cur->next = NULL)
Скорее всего, должно быть !=
Подскажите, как можно добавить или удалить элемент в конец списка?
Реализовать динамическую структуру данных, описывающую предметную область в виде линейного односвязного списка, и процедуры:
добавления элемента в начало списка;
добавления элемента в конец списка;
удаления элемента из начала списка;
удаления элемента из конца списка;
удаления из списка элемента, указанного его порядковым номером;
изменение данных элемента списка, указанного его порядковым номером;
вывода элементов списка на экран
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
#include <forward_list>
#include<climits>
#include <windows.h>
#include <cstring>
#include <iomanip>
using namespace std;
struct Facult
{
char facultet[70];
int kolvo_student;
float sr_ball;
int kolvo_otlich;
};
std::forward_list<Facult> facultList;
Facult f;
/*ФУНКЦИЯ ЗАНОСИТ ДАННЫЕ В НАЧАЛО СПИСКА*/
void GetData(std::forward_list<Facult>& v)
{
// вводим поля f
std::cout << "\n";
std::cout << "Факультет: ";
std::cin >> f.facultet;
std::cout << "Кол-во студентов: ";
std::cin >> f.kolvo_student;
std::cout << "Средний балл: ";
std::cin >> f.sr_ball;
std::cout << "Кол-во отличников: ";
std::cin >> f.kolvo_otlich;
v.push_front(f); // добавляем введённую структуру в начало списка
}
/*ФУНКЦИЯ ЗАНОСИТ ДАННЫЕ В КОНЕЦ СПИСКА*/
void GettData(std::forward_list<Facult>& v)
{
// вводим поля f
std::cout << "\n";
std::cout << "Факультет: ";
std::cin >> f.facultet;
std::cout << "Кол-во студентов: ";
std::cin >> f.kolvo_student;
std::cout << "Средний балл: ";
std::cin >> f.sr_ball;
std::cout << "Кол-во отличников: ";
std::cin >> f.kolvo_otlich;
auto iter = v.end();
iter = v.insert_after(iter, f); // добавляем введённую структуру в начало списка
}
/*ФУНКЦИЯ ИЗВЛЕКАЕТ ЗАПИСЬ*/
void ShowData(const std::forward_list<Facult>& v)
{
std::cout << "\n";
std::cout << "Список факультетов\n";
std::cout << '\n';
/*ЯЧЕЙКИ-ЗАГОЛОВКИ*/
std::cout << std::setw(20) << "Факультет" << '|';
std::cout << std::setw(16) << "Кол-во студентов" << '|';
std::cout << std::setw(14) << "Средний балл" << '|';
std::cout << std::setw(18) << "Кол-во отличников" << '|';
/*КОНЕЦ ЯЧЕЕК-ЗАГОЛОВКОВ*/
std::cout << '\n';
/*ВЫВОДИМ МАССИВ СТРУКТУР ПОСТРОЧНО*/
for (const auto& f : v)
{
std::cout << std::setw(20) << f.facultet << '|';
std::cout << std::setw(16) << f.kolvo_student << '|';
std::cout << std::setw(14) << f.sr_ball << '|';
std::cout << std::setw(18) << f.kolvo_otlich << '|';
std::cout << std::endl;
}
/*КОНЕЦ ПОСТРОЧНОГО ВЫВОДА*/
std::cout << '\n';
}
int main()
{
SetConsoleOutputCP(1251);
SetConsoleCP(1251);
while (true) {
int variant;
std::cout << "Выберите вариант\n" << std::endl;
std::cout << "1. Добавить элемент в начало списка\n"
<< "2. Добавить элемент в конец списка\n"
<< "3. Удалить элемент из начала списка\n"
<< "4. Удалить элемент из конца списка\n"
<< "5. Удалить элемент по порядковому номеру\n"
<< "6. Изменить данные элемента списка\n"
<< "7. Вывести элементы списка\n" << std::endl;
std::cout << ">>> ";
std::cin >> variant;
switch (variant) {
case 1:
{
GetData(facultList); //Добавление элемента в начало списка
break;
}
case 2:
{
GettData(facultList); //Добавление элемента в начало списка
break;
}
case 3:
{
facultList.pop_front(); //Удаление элемента из начала списка
break;
}
case 7:
{
ShowData(facultList); //Вывод элементов экран
break;
}
}
}
return 0;
}
здравствуйте! подскажите, пожалуйста, что не так с моим кодом. Программа вроде бы читает его, но выводит какой-то бред. Спасибо большое!
если это важно, то я программирую на маке в Xcode
Задание:
для односвязного списка груп (поля title, amount_of_students) реализовать функции :
а)добавление элемента в голову списка
б)удаление элемента из головы списка
в)изменить порядок следования элементов
г)напечатать весь список, фомат: "Group: title(amount_of_students)";
д)удалить весь список
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
#include <stdlib.h>
const char delim[] = "_________________________________________\n";
const char menu[] = "\nChoose option:\n1. Add before head\n2. Delete head\n3. Reverse list\n4. Print list\n5. Clear list\n0. Quit\n";
typedef struct list_node {
char title[20];
int amount;
struct list_node* next;
} Node;
Node* add_in_head(Node* cur) {
Node* new_head;
new_head = (Node*)malloc(sizeof(Node));
printf("Enter group: ");
getchar();
gets(new_head->title, 20);
printf("Enter amount of students: ");
scanf("%d", &(new_head->amount));
new_head->next = cur;
return new_head;
}
Node* delete_head(Node* head) {
Node* t;
t = head->next;
printf("Element deleted: %s (%d)\n", head->title, head->amount); free(head);
return t;
}
Node* reverse(Node* head) {
Node* n_head = NULL, *t = NULL; while (head) {
n_head = head; head = head->next; n_head->next = t; t = n_head;
}
return n_head;
}
void show(Node* head) {
if (!head) printf(" Listis empty!!!!!\n");
while(head){
} }
Node* delete_all(Node* head)
{
if (!head) return NULL;
delete_all(head->next);
printf("Element deleted: %s (%d)\n", head->title, head->amount); free(head);
return NULL;
}
int main() {
int opt = -1, count = 0; Node *head = NULL;
do {
printf(delim);
printf(menu);
printf(">> ");
count = scanf("%d", &opt); printf(delim); printf("\n");
switch (opt)
{
case 1:
head = add_in_head(head);
break;
case 2:
head = delete_head(head);
break;
case 3:
head = reverse(head);
break;
case 4:
show(head);
break;
case 5:
head = delete_all(head);
break;
case 0:
head = delete_all(head);
printf("Quitting……..\n");
break;
default:
printf("Unknown option!!!!\n"); break;
}
} while (count && opt);
return 0;
}
"Виснет" функция вывода элементов списка, поскольку не реализован сам вывод и переход к следующему элементу.
2
3
4
5
6
7
if (!head) printf(" Listis empty!!!!!\n");
while (head) {
printf("%s %d\n", head->title, head->amount);
head = head->next;
}
}
Пожалуйста помогите.В консоль выводит только последний элемент структуры.
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
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <iostream>
using namespace std;
struct list
{
char *name;
char* author;
char* edition;
char* year;
char* type;
// поле данных
struct list* next; // указатель на следующий элемент
};
//list* Head = NULL;
struct list* init(char name1[20],char author1[20],char edition1[20],char year1[10],char type1[20]) // а- значение первого узла
{
struct list* lst;
// выделение памяти под корень списка
lst = (struct list*)malloc(sizeof(struct list));
lst->name = name1;
lst->author = author1;
lst->edition = edition1;
lst->year = year1;
lst->type = type1;
lst->next = lst;; // это последний узел списка
return(lst);
}
struct list* addelem(list* lst,char str_n[20],char str_a[20],char str_e[20],char str_y[10],char str_t[20])
{
struct list* temp, * p;
temp = (struct list*)malloc(sizeof(list));
p = lst->next; // сохранение указателя на следующий узел
lst->next = temp; // предыдущий узел указывает на создаваемый
temp->name = str_n;
temp->author = str_a;
temp->edition = str_e;
temp->year = str_y;
temp->type = str_t;
temp->next = p; // созданный узел указывает на следующий элемент
return(temp);
}
void listprint(list* lst)
{
struct list* p;
p = lst;
do {
printf(" %s %s %s %s %s", p->name,p->author,p->edition,p->year,p->type); // вывод значения элемента p
p = p->next; // переход к следующему узлу
} while (p != lst);
}
int main() {
struct list* head, * r, * p;
head = 0;
p = 0;
char name_[20] = { "" };
char author_[20] = { "" };
char edition_[20] = { "" };
char year_[10] = { "" };
char type_[20] = { "" };
cout << "how many elements?\n";
int k;
cin >> k;
for (int i = 0; i < k; i++) {
cout << "Name of a book: ";
cin >> name_;
cout << "Name of author: ";
cin >> author_;
cout << "Name of edition: ";
cin >> edition_;
cout << "Year: ";
cin >> year_;
cout << "Name of a type: ";
cin >> type_;
if (i == 0)
{
p = init(name_,author_,edition_,year_,type_);
head = p;
}
else
p = addelem(p,name_, author_, edition_, year_, type_);
}
listprint(head);
return 0;
Проблема тут:
2
3
4
5
char author_[20] = { "" };
char edition_[20] = { "" };
char year_[10] = { "" };
char type_[20] = { "" };
Нельзя выделять память статически. После того, как Вы вели новые значения, они заменились для всех элементов.
Используйте указатели.
Добрый день. Можете помочь с реализацией кода. Дано два непересекающихся линейных списка. В списке №1 имеется указатель t, в списке №2 – указатель х. Вставить в список №1 после указателя t все узлы списка №2, следующие после указателя х.
Могу, если покажете свой вариант и сообщите, что конкретно не получается. Делать задачу за Вас не буду.
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
#include <string>
using namespace std;
struct node
{
double value;
node *next = NULL;
};
struct stack
{
node *head = NULL;
} stck;
void add(double value)
{
node *n = new node();
n->value = value;
n->next = stck.head;
stck.head = n;
}
double get()
{
if(stck.head)
{
double output = stck.head->value;
stck.head = stck.head->next;
return output;
}
else
return 0;
}
void parse_string(string str)
{
int i = 0;
string tmp = "";
while(str[i] != '\0')
{
if(str[i] != ' ')
{
switch(str[i])
{
case '+':
add(get() + get());
break;
case '-':
add(get() — get());
break;
case '*':
add(get() * get());
break;
case '/':
add(get() / get());
break;
default:
tmp += str[i];
break;
}
}
else if(tmp != "")
{
add(stod(tmp.c_str()));
tmp = "";
}
i++;
}
printf("Answer is: %f\n", get());
}
int main()
{
string str;
while(true)
{
stck.head = NULL;
cout << "Enter exspression ('E' to exit)\n";
getline (cin, str);
if(str[0] == 'E')
return 0;
else
{
parse_string(str);
}
}
return 0;
}
Можете ли вы код что представленный сверху объединить в одно целое. Я что-то не могу понять как все работает
https://prog-cpp.ru/wp-content/uploads/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80-1-2.docx
Добрый день! Подскажите пожалуйста, верно ли реализована функция добавления в конец списка, с трудом доходит эта тема…
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
{
int key;
Elem *next;
};
bool AddtoTail(int key, Elem **list)
{
Elem *ptr = new Elem;
if (ptr)
{
ptr->key = key;
ptr->next = NULL;
if(list == NULL)
{
*list = ptr;
return true;
}
else
{
Elem *p = new Elem;
p = *list;
while (p->next)
p = p->next;
p->next = ptr;
return true;
}
}
return false;
}
Похоже на правду. Строчка Elem *p = new Elem; лишняя.
2
p = *list;
Добрый день.А функция удаления узла должна возвращать указатель на элемент<следующий за удаляемым,то есть temp->ptr?А если вернуть просто temp,то получится предшествующий узел.
Сейчас в примере и возвращается предшествующий узел.
Здравствуйте! Не могу понять, как вывести на консоль элемент кольцевого односвязного списка вместе с его порядковым номером. Можете помочь?
Для этого нужен счетчик элементов списка при его просмотре.
А вообще кольцевой список подробно рассмотрен здесь.
Здравствуйте, как будет выглядеть задача с такими условиями:
Создать односвязный список, потом проверить есть ли в списке узел, содержащий 0, и если есть, то вставить после него еще 3 узла со значением 0.
Заранее спасибо!!
Затрудняюсь ответить.
Нужно реализовать функции инициализации списка, добавления элемента и вывода списка.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int num;
scanf("%d",&num);
head=init(num);
lst = head;
for(int i=0;i<9;i++)
{scanf("%d",&num);
lst = addelem(lst, num);
}
listprint(head);
lst = head;
while(lst != NULL)
{if(lst->field ==0)
{
lst =addelem(lst,0);
lst =addelem(lst, 0);
lst =addelem(lst, 0);
}
}
listprint(head);
помогите пожалуйста, не работает этот код что нужно поменять ?
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
struct Node{
Node* next;
int data;
};
void push_back(Node **head, Node **last, int data){
Node *node = new Node;
node->next = NULL;
node->data = data;
if (*last != NULL)
(*last)->next = node;
*last = node;
if (*head == NULL)
*head = *last;
}
void print(Node *head){
while (head != NULL){
std::cout <data <next;
}
}
int main(){
Node *head = NULL, *last = NULL;
for (int i = 0; i < 100; i++){
push_back(&head, &last, i);
}
print(head);
return 0;
}
Вроде работает.
Правда, скопировался с ошибками. Но это — мой недосмотр.
Как рабить указаный список на два по указанному элементу . Вот код :
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
#include "stdio.h"
#include "locale.h"
#include "stdlib.h"
typedef struct Node {
int value;
struct Node *next;
}Node;
void push(struct Node** head, int num)
{
struct Node* current = *head;
Node *newNode = (Node*)malloc(sizeof(struct Node));
newNode->value = num;
newNode->next = NULL;
if (current == NULL) {
*head = newNode;
}
else {
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
}
void printFromHead(const Node* list) {
if (list) {
printf("%d ", list->value);
printFromHead(list->next);
}
}
void main()
{
setlocale(LC_ALL, "ukr");
int x, z;
Node *head = NULL;
printf("Вкажiть розмiр списку — ");
if ((scanf("%d", &x)) != 1) {
printf("Неверное введенное значение");
}
printf("\n");
for (int i = 0; i < x; i++)
{
z = 0 + rand() % 100;
push(&head, z);
}
printf("\n");
printFromHead(head);
printf("\n");
system("pause");
}
Створити зв’язаний список з n-елементі (де n-випадкове число).
Видаляти по кругу кожен третій елемент, доки не залишиться 1. Кожен крок повертати на екран.Как это сделать помогите пожалуйста.
Не могу понять условие, записанное на незнакомом мне языке 🙁
Здравствуйте!
В функции [prog]init([/prog][kwd]int[/kwd][prog] a)[/prog] нельзя исключать возможность того, что функция [prog]malloc()[/prog] не сможет выделить память и вернет [prog]NULL[/prog].
В таком случае значение первого узла а присваивается непонятно чему, т.к. [prog]lst = NULL[/prog] и инструкция
[prog]lst->field = a;[/prog]
завершится ошибкой.
Правильнее было бы всегда проверять значение, возвращаемое [prog]malloc()[/prog] на [prog]NULL[/prog]. То же самое относится и к функции [prog]addelem(list *lst, [/prog][kwd]int[/kwd][prog] number)[/prog].
2
3
4
5
6
7
8
9
10
11
{
struct list *lst;
// выделение памяти под корень списка
lst = (struct list*)malloc(sizeof(struct list));
// Проверяем успешность выделения памяти под корень списка
if( NULL == lst) return NULL;
lst->field = a;
lst->ptr = NULL; // это последний узел списка
return(lst);
}
Согласна, можно добавить эту проверку.
Прошу простить великодушно за мою настырность, но позволю себе обозначить еще один источник потенциальных проблем. Если рассматривать многопоточную среду исполнения, то все данные функции не обладают свойством реентерабельности, т.е. не потокобезопасны. В том плане, что процедура связывания или удаления узлов списка должна быть атомарной операцией, т.е. код в той части, где выполняются манипуляции над указателями и полями данных должен быть расположен в критической секции, что-то типа
2
3
4
5
6
7
8
p = lst->ptr; // сохранение указателя на следующий узел
lst->ptr = temp; // предыдущий узел указывает на создаваемый
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент
Exit_Critical();
…
Рассмотрим такой пример. Пусть наш список состоит из 3-х элементов:
Предположим существует два параллельных потока (задачи, нити и т.д. на разных платформах это называется по-разному, но сути не меняет), в которых мы хотим добавить элемент в конец списка (далее псевдокод в порядке его выполнения во времени)
2
3
4
5
6
7
8
9
10
11
// тут какой-то код
last_element = find_last_elem(root); // Получаем указатель на последний элемент
addelem(last_elem, number); // добавляем новый элемент в конец списка
// тут какой-то код
//Поток 2
// тут какой-то код
last_element = find_last_elem(root); // Получаем указатель на последний элемент
addelem(last_elem, number); // добавляем новый элемент в конец списка
// тут какой то код
пусть в данный момент поток 1 исполняется и мы получили указатель на последний элемент списка, в нашем случае это элемент 3, а затем вызвали функцию addelem(), которая начинает исполняться:
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
temp = (struct list*)malloc(sizeof(list));
p = lst->ptr; // сохранение указателя на следующий узел, в нашем случае он последний p = NULL
// Уупс! Исполнение переключилось на поток 2 никто не гарантирует, что этого не может случиться именно в этом месте
// поток 2 — теперь мы в потоке 2
// нашли последний элемент списка — это (какая неожиданность !!) элемент 3, т.к. мы просто не успели переназначить //указатели
// теперь мы вошли в функцию addelem() повторно
temp = (struct list*)malloc(sizeof(list));
p = lst->ptr; // сохранение указателя на следующий узел, это NULL
lst->ptr = temp; // предыдущий узел указывает на создаваемый, теперь это элемент 4
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент, в нашем случае NULL
return(temp);
// вернулись в функцию потока 2
// у нас должен быть следующий список root => elem1 => elem2 => elem3 => elem4 => NULL
// выполняем какой-то код потока 2
// упс!!! опять переключение на поток 1!!!!
// Поток 1
// Продолжаем с того места на котором прервались
// lst у нас по-прежнему указывает на element 3, хотя это уже не последний элемент списка!!!!
lst->ptr = temp; // предыдущий узел указывает на создаваемый, но это не элемент 4 добавленный в потоке 2
// таким образом указатель на элемент 4, созданный в потоке 2 затирается
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент
return(temp);
// возврат в функцию потока 1, выполняем какой-то код потока 1
Итак, подытоживая, что мы видим. Мы видим, что в поле ptr элемента 3 указатель на элемент 4, добавленный в конец списка в потоке 2, затирается старым значением в потоке1, а сам он безвозвратно теряется. Помимо потери самого элемента, это создает опасную ситуацию утечки памяти, т.к. указатель на элемент 4 созданный в потоке 2 безвозвратно утерян, и мы никак уже не сможем освободить память выделенную под него.
возможно, я не правильно выразился. Функции то в принципе могут быть реентерабельны, но не потокобезопасны, тк. не обеспечивают в данном случае правильный доступ к разделяемым данным (в нашем случае списку).
Из Вашего комментария проблема ясна, но не понятны пути ее решения.
Я приводила пример для однопоточного приложения.
Извините, ошибка в коде 34 строка должна быть такой:
[prog]prevMin->next = Max;[/prog]
Здравствуйте. Спасибо за хорошую статью. Применяю Ваш метод перестановки двух звеньев, чтобы поменять минимум и максимум в списке. Для нахождения звеньев использую другие функции. На данный момент все работает, но только если звенья в середине, т.е. не первое и не последнее. Причем не важно, рядом элементы или нет. Посоветуйте, какое условие написать для обоих вариантов, чтобы все работало. Заранее спасибо.
Вот мой код:
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
{
Node *prevMax, *prevMin, *postMax, *postMin, *tmp;
Node *Max, *Min;
Max = getMax(head);
Min = getMin(head);
prevMax = head;
prevMin = head;
if (prevMax == Max)
prevMax = NULL;
else
while (prevMax->next != Max)
prevMax = prevMax->next;
if (prevMin == Min)
prevMin = NULL;
else
while (prevMin->next != Min)
prevMin = prevMin->next;
postMax = Max->next;
postMin = Min->next;
if (Min == postMax)
{ //Соседние узлы
Min->next = Max;
Max->next = postMin;
if (Max != head)
prevMax->next = Min;
if (Max == head)
prevMin = NULL;
}
else if (Max == postMin)
{ //Соседние узлы
Max->next = Min;
Min->next = postMax;
if (Min != head)
prevMin->next = Min;
if (Min == head)
prevMax == NULL;
}
else
{ //В разных местах
if (Max != head)
prevMax->next = Min;
Min->next = postMax;
if (Min != head)
prevMin->next = Max;
Max->next = postMin;
}
}
Для того, чтобы поменять корневой узел с каким-либо, нужно вернуть новый корень списка. В текст вставлен блок определения нового корня и исправлено несколько недочётов.
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
Node * switchMinMax(Node *head)
{
Node *prevMax, *prevMin, *postMax, *postMin, *tmp;
Node *Max, *Min;
Max = getMax(head);
Min = getMin(head);
// — — — Добавилось — определение нового корня
Node *newhead = head;
if (Max == head)
newhead = Min;
if (Min == head)
newhead = Max;
// — — — — — — — — — — — — — —
prevMax = head;
prevMin = head;
if (prevMax == Max)
prevMax = NULL;
else
while (prevMax->next != Max)
prevMax = prevMax->next;
if (prevMin == Min)
prevMin = NULL;
else
while (prevMin->next != Min)
prevMin = prevMin->next;
postMax = Max->next;
postMin = Min->next;
if (Min == postMax)
{ //Соседние узлы
Min->next = Max;
Max->next = postMin;
if (Max != head)
prevMax->next = Min;
//else // не нужно
// prevMin = NULL;
}
else if (Max == postMin)
{ //Соседние узлы
Max->next = Min;
Min->next = postMax;
if (Min != head)
prevMin->next = Max; // изменилось
//if (Min == head) // не нужно
// prevMax == NULL;
}
else
{ //В разных местах
if (Max != head)
prevMax->next = Min;
Min->next = postMax;
if (Min != head)
prevMin->next = Max;
Max->next = postMin;
}
return newhead;
}
Спасибо за быстрый ответ, буду разбираться.
Все таки сделал по своему, но передал в функцию указатель на указатель. Спасибо большое за подсказку где искать. Долго пытался. Извините что не воспользовался вашим кодом, свой роднее и понятнее :-). Ну и если кому то понадобится, собственно код:
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
{
Node *prevMax, *prevMin, *postMax, *postMin, *tmp;
Node *Max, *Min;
Max = getMax(*head); //Передаем значение Max и Min
Min = getMin(*head);
prevMax = *head;
prevMin = *head;
if (prevMax == Max)
prevMax = NULL;
else
while (prevMax -> next != Max) //Находим элементы перед Max и Min
prevMax = prevMax ->next;
if (prevMin == Min)
prevMin = NULL;
else
while(prevMin -> next != Min)
prevMin = prevMin -> next;
postMax = Max -> next; //Определяем элементы стоящие после Max и Min
postMin = Min -> next;
if (Min == postMax)
{ //Соседние узлы
Min -> next = Max;
Max -> next = postMin;
if (Max != *head)
prevMax -> next = Min;
else *head = Min;
prevMin = NULL;
}
else if (Max == postMin)
{ //Соседние узлы
Max -> next = Min;
Min -> next = postMax;
if (Min != *head)
prevMin -> next = Max;
else *head = Max;
prevMax = NULL;
}
else
{ //В разных местах
if (Max != *head)
prevMax -> next = Min;
Min -> next = postMax;
if (Min != *head)
prevMin -> next = Max;
Max -> next = postMin;
}
if (Max == *head)
*head = Min;
prevMin = NULL;
Min -> next = postMax;
if (Min == *head)
*head = Max;
prevMax = NULL;
Max -> next = postMin;
}
А вызывать функцию так: switchMinMax(&head);
Уважаемая Елена, спешу Вам сообщить, что в коде, который Вы нам предоставили имеются ошибки. Так, в строке 42 не выполняется оператор ветвления, а в следующей за ней строке не выполняется операция присвоения.
Честно говоря, не поняла, к какому коду относится Ваш комментарий.
Здравствуйте! не могли бы вы помочь ?! Задание такое: дан линейный список, в нем нужно найти максимальный элемент и потом его поставить в начало списка.
Могла бы. Только в чем будет заключаться помощь?
Создать односвязный список на основе класса, объекты которого будут формировать этот список. В описание класса должны входить данные для хранения комплексных чисел; функции для доступа к отдельным компонентам списка, вывод на экран элементов списка в формате ai+b, добавление элемента в начало списка, удаление элемента списка. Использовать указатель [kwd]this[/kwd].
Интересная задача. Удачи в решении.
Можно посмотреть весь код программы
Добрый день! Может кто поможет, не получается никак решить задачу такого типа, нужно сформировать стек чисел и занести в новый список до максимума из первого стека — списка. Мое решение, все работает, кроме копирования в новый список.. вот сама функция записи (стек уже заполнен)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void task(struct Stack*begin) {
struct Stack *temp = begin; // создали указатель на стек
int max = 0;
printf("\n От вершины до максимального значения:\n");
while (temp != NULL) { // заносим значения в новый стек до max
if ((temp->number) > max) {
new_list = (struct Stack*)malloc(sizeof(struct Stack));
new_list->number = temp->number;
new_list->next = new_list;
max = (temp->number);
}
temp = temp->next;
}
printf("\nПросмотр\n");
while (new_list != NULL) {
printf("%4d", new_list->number);
new_list = new_list->next;
}
Нужно в цикле определить максимальный элемент и запомнить его указатель.
2
3
4
5
6
7
8
9
10
11
int max = maxelem->number;
while (temp != NULL)
{
if ((temp->number) > max)
{
maxelem = temp;
max = (temp->number);
}
temp = temp->next;
}
Только после этого, когда мы знаем максимальный элемент и указатель на него, можно формировать новый список.
Большое спасибо за быстрый ответ.. наверное, я что-то не понял, определил указатель на макс элемент, занес в новый список значения, но на консоли не отображается. Не могли бы вы посмотреть, очень благодарен вам за помощь.
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
void task(struct Stack*begin)
{
struct Stack *temp = begin;
struct Stack *maxelem = begin;
int max = maxelem->number;
printf("\n От вершины до максимального значения:\n");
while (temp != NULL)
{
if ((temp->number) > max)
{
maxelem = temp;
max = (temp->number);
}
temp = temp->next;
}
struct Stack*temp2 = begin;
while (temp2 != maxelem)
{
new_list = (struct Stack*)malloc(sizeof(struct Stack));
new_list->number = temp2->number;
new_list->next = new_list;
temp2->next = temp2;
}
printf("\nПросмотр\n");
while (new_list != NULL)
{
printf("%4d", new_list->number);
new_list = new_list->next;
}
}
Ошибка в выделенной строчке. Вы зацикливаете указатель на сам элемент. Поле указателя на следующий элемент нужно инициализировать в момент создания этого «следующего» элемента.
Так в цикле я создаю структуру и инициализирую ее поля ,т.е. присваиваю в новую структуру адрес предыдущей.. запутался..
2
3
4
5
6
7
8
9
10
11
12
new_list->number = begin->number; // это корень нового списка
new_list->next = NULL;
while (temp2 != maxelem)
{
struct Stack *temp3 = new_list;
new_list = (struct Stack*)malloc(sizeof(struct Stack));
new_list->number = temp2->number;
temp3->next = new_list;
new_list->next = NULL;
temp2 = temp2->next;
}
В функции [prog]addelem()[/prog] уже известен адрес узла, который содержит [prog]NULL[/prog]. А я не понимаю как его найти.
Допустим, при инициализации списка известен адрес корня, который и есть последним узлом. Теперь, допустим, у меня возникла необходимость добавить в этот список еще узел. Тут все понятно. Узел [prog]root[/prog] имеет адрес. Я создаю вашей функцией новый. Заполняю его. Сохраняю в промежуточном указателе адрес поля рут т.е [prog]NULL[/prog].
Далее меняю указатель рута на адрес нового узла, и потом переписываю указатель добавленного узла на [prog]NULL[/prog].
Теперь я еще добавляю узел. Знаю о существовании рута. Если я воспользуюсь вашей функцией то перепишу указатель рута и нового узла. Опс…Все понял спасибо.
Но тогда еще вопрос. Таким образом, я получу список задом наперед. Если я имею словарь с уже отсортированными словами от а до я. То в памяти буква я станет в начале списка, а [prog]А[/prog] в конце. Можете помочь разобраться с этим?
В функцию addelem() Вы передаете указатель на элемент, после которого необходимо осуществить добавление. Указатель корня списка при этом должен быть сохранен в другой переменной, и вывод списка необходимо осуществлять с корня.
Значит я должен реализовать просмотр списка и как только я найду узел с [prog]NULL[/prog] передать его указатель в функцию добавления узла. Благодарю за помощь. Со словарем не понятно. Имею файл с отсортированными словами от А до Я. Мне нужно его загрузить в память так что бы возле корня была буква А. С [prog]NULL[/prog] буква Я. Ваша функция добавляет новый узел в конец списка. А как сделать наоборот?
Я только учусь. Поэтому вопросы могут быть простыми для вас…
В этом случае нужна функция, которая будет добавлять элемент в начало списка, наподобие этой
2
3
4
5
6
7
struct list *temp;
temp = (struct list*)malloc(sizeof(list));
temp->ptr = root; // создаваемый узел на предыдущий корень
temp->field = number; // сохранение поля данных добавляемого узла
return(temp); // возвращаем новый корень списка
}
У меня вопрос. В самом начале в списке один узел и его указатель = NULL. После добавления в список еще одного узла, указатель корневого станет показывать адрес добавленного узла, а у того, что добавился станет NULL. Как добавить следующий узел? Ведь единственный известный — это корневой
Для этой цели в статье предлагается использовать функцию addelem()
Мне кажется в описании функции удаления узла есть ошибка: «Функция возвращает указатель на узел, следующий за удаляемым», но в приведенной функции возвращается как раз предшествующий, т.е. тот, чей ptr и переписали ("пока не найдем узел, предшествующий lst"). и, в принципе, зачем что-то возвращать, если можно просто сделать функцию как void.
Вы можете использовать функции по своему усмотрению.
Например, можно было бы объединить функции удаления узла и удаления корня и возвращать всегда новый корень списка.
Большое спасибо!
Здравствуйте!) Можете пожалуйста объяснить что означает (struct list*) перед функцией mallocа в строчке
когда мы создаем корень списка?
Это — приведение типа. Поскольку функция malloc() возвращает указатель неопределенного типа, чтобы не возникало ошибки его нужно привести к требуемому значению. Значение типа должно совпадать с тем, что стоит в левой части равенства. В данном случае это указатель lst, имеющий тип (struct list *).
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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <math.h>
using namespace std;
#define pi 3.141592653
int x;
long double low, high, step;
unsigned long long SS;
struct person { //описание структуры
char f[30]; //фамилия
char d[30]; //должность
float zp,pr; //зарплата, премия
char prof; //профсоюз
float SS;
long double low, high, step;
int x;
person *next; //указатель на следующего в списке
};
person vvesti() { //ввод элемента с клавиатуры
person p;
low=0;
high=pi/4;
step=pi/40;
return p;
}
int show (person *head) { //показ всего списка с определением количества элементов
unsigned long long count=0;
if (head) while (1) {
std::cout << " X | Y(X) |\n———-+—————+" << std::endl;
for ( double x = low; x <= high; x += step ){
std::cout << ' ' << std::fixed << std::setprecision(3) << std::left << std::setw(9) << x << "| "
<< std::left << std::setw(14) << sin(3*x)+cos(2*x)
<< "\n———-+—————+" << std::endl;
}
count++;
if (head->next == NULL) break;
head = head->next;
}
printf ("\nAll=%d",count);
return count;
}
void search (person *head, char *st) { //поиск в списке строки st
if (head==NULL) return;
person *next = head;
do {
char *find = strstr (next->f, st);
if (find!=NULL) printf ("\n%s",next->f);
if (next->next==NULL) break;
next = next->next;
} while (1);
}
void copy1 (person *to, person *from) { //копирование одной записи
strcpy (to->f, from->f);
strcpy (to->d, from->d);
to->zp = from->zp; to->pr = from->pr; to->prof = from->prof;
}
person *add1 (person *head, person *st) { //добавление элемента st в начало списка
//*st уже заполнен данными
person *current = new person;
copy1 (current, st); //копирует 1 запись
if (head==NULL) current->next = NULL;
else {
current->next = head;
head = current;
}
return current;
}
person *add2 (person *head, person *st) { //добавление элемента st в конец списка
person *last = NULL;
if (head!=NULL) {
last=head;
while (last->next!=NULL) last=last->next;
}
person *current = new person;
copy1 (current,st);
current->next = NULL;
if (last) last->next = current;
return current;
}
person *delete1 (person *head0, int n) { //удаление элемента по номеру 1..N
// удалит элемент номер n и вернет указ.на нач.
person *head = head0;
if (head==NULL) return NULL;
if (n==1) { //удаляем первый
person *ptr = head->next;
delete head;
return ptr;
}
person *prev = NULL, *start = head; int i=1;
while (i<n) { //Ищем n-ый элемент
prev = head; head = head->next;
if (head==NULL) return start;
i++;
}
person *ptr = head->next;
delete head;
prev->next = ptr;
return start;
}
person *sort (person *ph) { //сортировка списка методом вставок
person *q, *p, *pr, *out=NULL;
while (ph != NULL) {
q = ph; ph = ph->next; //исключить эл-т
//ищем, куда его включить:
for (p=out,pr=NULL ; p!=NULL &&
strcmp(q->f,p->f)>0; pr=p,p=p->next) ;
//или ваш критерий, когда переставлять!
if (pr==NULL) { q->next=out;out=q; } //в нач.
else { q->next=p; pr->next=q; } //после пред.
}
return out;
}
int main() { //меню и главная программа
person *head = NULL;
while (1) {
printf ("\n 1. Show all \
\n 2. Add in head \
\n 3. Add in tail \
\n 4. Delete by number \
\n 5. Sort by name \
\n 0. Exit ");
fflush (stdin);
char c;
scanf ("%c",&c);
person p;
person *cur;
int n, all;
switch (c) {
case '1': show (head);
break;
case '2': p = vvesti(); head=add1(head,&p);
break;
case '3': p = vvesti();
cur = add2 (head,&p);
if (head==NULL) head=cur;
break;
case '4':
all = show(head);
while (1) {
printf ("\nVvedi nomer (1-%d): ",all);
fflush (stdin); scanf("%d",&n);
if (n>=1 && n<=all) break;
}
head = delete1 (head,n);
break;
case '5': head = sort (head);
break;
case '0': exit (0); break;
}
}
}
помогите мне реализовать так чтоб можно било удалять елементи вивода буду благодарен