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
| program Project1;
{Задача:
Слияние двух списков в третий таким образом, чтобы в третьем списке элементы
оказались упорядоченными по неубыванию. Слияние оформлено в виде отдельной процедуры.}
type
{Тип основных данных.}
TData = Integer;
{Тип, описывающий указатель на элемент.}
TPElem = ^TElem;
{Тип, описывающий элемент списка.}
TElem = record
Data : TData;
PNext : TPElem; {Указатель на следующий элемент.}
end;
{Тип, описывающий список.}
TDList = record
PFirst, PLast : TPElem; {Указатели на первый и на последний элементы списка.}
end;
{Процедуры для работы со списком.}
{Начальная инициализация списка. Внимание! Эту процедуру можно выполнять
только в отношении пустого списка. Иначе будут утечки памяти.}
procedure Init(var aL : TDList);
begin
aL.PFirst := nil;
aL.PLast := nil;
end;
{Освобождение памяти, занятой для элементов списка и инициализация.}
procedure LFree(var aL : TDList);
var
P, PDel : TPElem;
begin
P := aL.PFirst; {Указатель на первый элемент списка.}
while P <> nil do
begin
PDel := P; {Запоминаем указатель на текущий элемент.}
P := P^.PNext; {Получаем указатель на следующий элемент.}
Dispose(PDel); {Освобождаем память, занятую текущим элементом списка.}
end;
Init(aL);
end;
{Добавление элемента в список согласно сортировочному правилу - по неубыванию,
в данном случае.}
procedure AddAsc(var aL : TDList; const aData : TData);
var
PNew, PCur, PPrev : TPElem;
begin
New(PNew); {Выделяем паямять для элемента.}
PNew^.Data := aData; {Записываем данные.}
{Ищем элемент, который больше или равен новому - перед ним следует вставить
новый элемент.}
PCur := aL.PFirst;{Указатель на текущий элемент.}
{Указатель на предыдущий элемент. Этот указатель мы должны знать для того,
чтобы мы могли вставить новый элемент между PPrev и PCur.}
PPrev := nil;
while (PCur <> nil) and (PCur^.Data < aData) do
begin
PPrev := PCur;
PCur := PCur^.PNext;
end;
{Теперь, в зависимости от результатов поиска выполняем вставку нового элемента
в нужное место списка.}
PNew^.PNext := PCur;
if PPrev <> nil then {Добавление между PPrev и PCur, либо - в конец списка.}
PPrev^.PNext := PNew
else {Добавление в начало списка.}
aL.PFirst := PNew;
if PNew^.PNext = nil then {Если новый элемент стал последним элементом в списке.}
aL.PLast := PNew;
end;
{Слияние списков aL1 и aL2 в список aL3 с упорядочиванием элементов по неубыванию.}
procedure MergeAsc(const aL1, aL2 : TDList; var aL3 : TDList);
var
P : TPElem;
begin
{Очистка результирующего списка - освобождение памяти, занятой для элементов этого списка.}
LFree(aL3);
{Слияние первого списка.}
P := aL1.PFirst;
while P <> nil do
begin
AddAsc(aL3, P^.Data);
P := P^.PNext;
end;
{Слияние второго списка.}
P := aL2.PFirst;
while P <> nil do
begin
AddAsc(aL3, P^.Data);
P := P^.PNext;
end;
end;
{Распечатка списка.}
procedure LWriteln(const aL : TDList);
var
P : TPElem;
begin
P := aL.PFirst; {Указатель на первый элемент списка.}
if P <> nil then
repeat
{Если это не первый элемент, то в распечатке ставим перед ним запятую.}
if P <> aL.PFirst then
Write(', ');
Write(P^.Data); {Распечатываем данные текущего элемента.}
P := P^.PNext; {Получаем указатель на следующий элемент.}
until P = nil
else
Write('Список пуст.');
Writeln;
end;
const
M = 5; {Количество элементов, которые мы будем добавлять в списки.}
var
L1, L2, L3 : TDList;
i : Integer;
S : String;
begin
{Начальная инициализация списков.}
Init(L1);
Init(L2);
Init(L3);
repeat
{Создаём исходные списки.}
Randomize; {Инициализируем генератор случайных чисел.}
for i := 1 to M do
begin
AddAsc(L1, Random(100)); {Случайные целые числа из диапазона: 0..99.}
AddAsc(L2, Random(100));
end;
Writeln('Заданы списки: ');
LWriteln(L1);
LWriteln(L2);
{Слияние списков L1 и L2 в список L3 с упорядочиванием элементов по неубыванию.}
MergeAsc(L1, L2, L3);
{Ответ.}
Writeln('Результат слияния:');
LWriteln(L3);
{Освобождение памяти, занятой для элементов списков.}
LFree(L1);
LFree(L2);
LFree(L3);
Writeln('Память, выделенная для списков, освобождена.');
Writeln('Повторить - Enter, выход - любой символ + Enter.');
Readln(S);
until S <> '';
end. |
(
Сообщение было отмечено LexaVRN как решение
