1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
| program Project1;
type
//Указатель на элемент очереди.
TPElem = ^TElem;
//Элемент очереди.
TElem = record
Data : Integer; //Основные данные.
PNext : TPElem; //Указатель на следующий элемент очереди.
end;
//Очередь.
TQueue = record
PFirst, PLast : TPElem; //Указатели на первый и на последний элементы очереди.
end;
//Начальная инициализация очереди. Внимание! Эту процедуру можно выполнять
//только в отношении пустой очереди. Иначе - будут утечки памяти.
//Если очередь непуста, то следует применить вызов Free().
procedure Init(var aQueue : TQueue);
begin
aQueue.PFirst := nil;
aQueue.PLast := nil;
end;
//Добавление элемента в конец очереди.
procedure Push(var aQueue : TQueue; var aPElem : TPElem);
begin
if aPElem = nil then Exit;
aPElem^.PNext := nil;
if aQueue.PFirst = nil then
aQueue.PFirst := aPElem
else
aQueue.PLast^.PNext := aPElem;
aQueue.PLast := aPElem;
end;
//Изъятие элемента из начала очереди.
function Pop(var aQueue : TQueue; var aPElem : TPElem) : Boolean;
begin
Pop := False;
if aQueue.PFirst = nil then Exit;
aPElem := aQueue.PFirst;
aQueue.PFirst := aPElem^.PNext;
if aQueue.PFirst = nil then aQueue.PLast := nil;
Pop := True;
end;
//Удаление очереди из памяти (очистка очереди).
procedure Free(var aQueue : TQueue);
var
PDel : TPElem;
begin
while Pop(aQueue, PDel) do Dispose(PDel);
end;
//Распечатка очереди.
procedure Print(var aQueue : TQueue);
var
Q : TQueue;
PElem : TPElem;
i : Integer;
begin
if aQueue.PFirst = nil then begin
Write('Очередь пуста.');
Exit;
end;
Init(Q);
i := 0;
while Pop(aQueue, PElem) do begin
Push(Q, PElem);
Inc(i);
if i > 1 then Write(', ');
Write(PElem^.Data);
end;
aQueue := Q;
end;
const
//Глубина очереди.
M = 10;
var
Q1, Q2, Q3, Q4 : TQueue;
PElem1, PElem2, PTmp : TPElem;
Data : Integer;
i : Integer;
F : Boolean;
S : String;
begin
//Начальная нициализация очередей.
Init(Q1);
Init(Q2);
Init(Q3);
Init(Q4);
repeat
//Формируем первую и вторую очередь.
Randomize;
for i := 1 to M do begin
New(PTmp);
PTmp^.Data := Random(10); //0..9.
Push(Q1, PTmp);
New(PTmp);
PTmp^.Data := Random(10); //0..9.
Push(Q2, PTmp);
end;
Writeln('Исходные очереди.');
Write('Q1: ');
Print(Q1);
Writeln;
Write('Q2: ');
Print(Q2);
Writeln;
//В третью очередь записываем произведения элементов из первой и второй очередей.
//При этом, элементы, взятые из очередей Q1 и Q2, сохраняем в очередь Q4.
while Pop(Q1, PElem1) do begin
Pop(Q2, PElem2);
New(PTmp);
PTmp^.Data := PElem1^.Data * PElem2^.Data;
Push(Q3, PTmp);
Push(Q4, PElem1);
Push(Q4, PElem2);
end;
//Теперь возвращаем элементы из Q4 в Q1 и Q2.
F := True;
while Pop(Q4, PTmp) do begin
if F then Push(Q1, PTmp)
else Push(Q2, PTmp);
F := not F;
end;
//Распечатка очереди Q3.
Writeln('Очередь Q3 до сортировки: ');
Print(Q3);
Writeln;
//Выполняем сортировку очереди Q3 с помощью очереди Q4.
//Направление сортировки - по неубыванию. Метод сортировки - пузырьковая.
repeat
F := False;
//Переписываем элементы из Q3 в Q4 и при этом прогоняем пузырёк от начала
//очереди к её концу.
//Пузырёк переносит бОльшие значения, в направлении конца очереди.
PTmp := nil; //Это пузырёк.
while Pop(Q3, PElem1) do begin
if PTmp = nil then
PTmp := PElem1 //Пузырёк подхватывает первый элемент очереди.
else begin
//Если элемент пузырька больше текущего элемента очереди,
//то пузырёк перепрыгивает через этот элемент.
if PTmp^.Data > PElem1^.Data then begin
Push(Q4, PElem1); //Текущий элемент записываем в очередь Q4.
F := True; //Флаг показывает, что пузырёк перепрыгнул элемент.
//Если элемент пузырька не больше очередного элемента, то пузырёк
//сбрасывает свой элемент в очередь Q4 и подхватывает текущий элемент.
end else begin
Push(Q4, PTmp); //Пузырёк сбрасывает свой элемент в очередь Q4.
PTmp := PElem1; //Пузырёк подхватывает текущий элемент.
end;
end;
end;
//Дописываем в Q4 элемент, оставшийся в пузырьке.
if PTmp <> nil then Push(Q4, PTmp);
//Возвращаем элементы в очередь Q3.
while Pop(Q4, PElem1) do Push(Q3, PElem1);
//Если во время прохода очереди пузырёк ни разу не перепрыгнул через
//элемент, значит, элементы упорядочены. В этом случае, сортировка заврешена.
until not F;
Writeln('Очередь Q3 после сортировки:');
Print(Q3);
Writeln;
Writeln('Очереди Q1 и Q2.');
Write('Q1: ');
Print(Q1);
Writeln;
Write('Q2: ');
Print(Q1);
Writeln;
//Удаление очередей из памяти.
Free(Q1);
Free(Q2);
Free(Q3);
Free(Q4);
Writeln('Очереди удалены из памяти. Работа завершена.');
Writeln('Повторить - Enter. Выход - любой символ + Enter.');
Readln(S);
until S <> '';
end. |