-1 / 18 / 7
Регистрация: 21.04.2019
Сообщений: 493
|
|
1
|
Объяснить, как работает код
24.04.2022, 15:22. Показов 221. Ответов 0
Что тут делает Node** head_reference в функции удаления? Не совсем понятно, как тут работает двойной указатель.
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
| // C ++ программа для удаления каждого k-го узла
#include <include>
using namespace std;
//структура для узла
struct Node {
int data;
Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
//вывод
void printList(Node* head)
{
if (head == NULL)
return;
Node* temp = head;
do {
cout << temp->data << "->";
temp = temp->next;
} while (temp != head);
cout << head->data << endl;
}
// Функция для удаления каждого k-го узла
void deleteK(Node** head_reference, int k) //Node** head_reference
{
Node* head = *head_reference;
// Если список пуст, просто вернемся.
if (head == NULL)
return;
// взять два указателя - текущий и предыдущий
Node *current = head, *previous;
while (true) {
// Проверяем, является ли Node единственным Node
// Если да, то мы достигли цели, поэтому
// возвращение.
if (current->next == head && current == head)
break;
// Распечатать промежуточный список.
printList(head);
// Если в списке присутствует более одного узла,
// Сделать предыдущий указатель указателем на текущий
// Итерировать текущий указатель k раз, т.е. текущий узел должен быть удален.
for (int i = 0; i < k; i++) {
previousious = current;
current = current->next;
}
// Если удаляемый узел - это голова
if (current == head) {
previous = head;
while (previous->next != head)
previous = previous->next;
head = current->next;
previous->next = head;
*head_reference = head;
free(current);
}
// Если удаляемый узел - последний узел.
else if (current->next == head) {
previous->next = head;
free(current);
}
else {
previous->next = current->next;
free(current);
}
}
}
//Функция для вставки узла в конце
//Круговой связанный список
void insertNode(Node** head_reference, int x)
{
// Создаем новый узел
Node* head = *head_reference; //
Node* temp = new Node(x);
// если список пуст, сделать новый заголовок узла
// Также он укажет на себя.
if (head == NULL) {
temp->next = temp;
*head_reference = temp;
}
// пройти список до последнего узла
// и вставляем узел
else {
Node* temp1 = head;
while (temp1->next != head)
temp1 = temp1->next;
temp1->next = temp;
temp->next = head;
}
}
int main()
{
// вставляем узлы в круговой связанный список
struct Node* head = NULL;
for(int i=1;i<11;i++)
insertNode(&head, i);
int k;
cin>>k;
// Удалить каждый k-й узел из
// круговой связанный список.
deleteK(&head, k);
return 0;
} |
|
0
|