Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на 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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
добавления элемента в начало списка; добавления элемента в конец списка; удаления элемента из начала списка; удаления элемента из конца списка; удаления из списка элемента, указанного его порядковым номером; изменение данных элемента списка, указанного его порядковым номером; вывода элементов списка на экран
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] = { "" };
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;
}
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;
}
2
p = *list;
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");
}
lst->field = a;
завершится ошибкой.
Правильнее было бы всегда проверять значение, возвращаемое malloc() на NULL. То же самое относится и к функции addelem(list *lst, int number).
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();
...
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); // добавляем новый элемент в конец списка
// тут какой то код
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
//Поток 1
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
prevMin->next = Max;
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;
}
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;
}
Допустим, при инициализации списка известен адрес корня, который и есть последним узлом. Теперь, допустим, у меня возникла необходимость добавить в этот список еще узел. Тут все понятно. Узел root имеет адрес. Я создаю вашей функцией новый. Заполняю его. Сохраняю в промежуточном указателе адрес поля рут т.е NULL.
Далее меняю указатель рута на адрес нового узла, и потом переписываю указатель добавленного узла на NULL.
Теперь я еще добавляю узел. Знаю о существовании рута. Если я воспользуюсь вашей функцией то перепишу указатель рута и нового узла. Опс...Все понял спасибо.
Но тогда еще вопрос. Таким образом, я получу список задом наперед. Если я имею словарь с уже отсортированными словами от а до я. То в памяти буква я станет в начале списка, а А в конце. Можете помочь разобраться с этим?
Я только учусь. Поэтому вопросы могут быть простыми для вас...
2
3
4
5
6
7
struct list *temp;
temp = (struct list*)malloc(sizeof(list));
temp->ptr = root; // создаваемый узел на предыдущий корень
temp->field = number; // сохранение поля данных добавляемого узла
return(temp); // возвращаем новый корень списка
}
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;
}
}
}