program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils,windows;
const n=10;
k=5;
type
List=^TList; {├У├к├а├з├а├▓├е├л├╝ ├н├а ├╜├л├е├м├е├н├▓ ├▓├и├п├а TList}
TList=record {├С├о├б├▒├▓├в├е├н├н├о "├з├а├п├и├▒├╝"}
c:integer; {├Т├и├п ├╜├л├е├м├е├н├▓├о├в ├к├о├▓├о├░├╗├е ├б├│├д├│├▓ ├╡├░├а├н├и├▓├╝├▒├┐ ├в ├▒├п├и├▒├к├е}
next:List; {├С├л├е├д├│├╛├╣├и├й ├╜├л├е├м├е├н├▓ ├▒├п├и├▒├к├а}
end;
{├п├░├о├╢├е├д├│├░├а ├в├╗├в├о├д├а ├░├│├▒├▒├к├и├╡ ├б├│├к├в}
procedure writeln_cp866(outstr:string);
var ins,outs:PAnsiChar;
begin
ins:=PAnsiChar(outstr);
GetMem(outs, Length(outstr)+1);
ZeroMemory(outs, Length(outstr)+1);
CharToOem(ins, outs);
writeln(outs);
FreeMem(outs);
end;
{├п├░├о├╢├е├д├│├░├а ├д├о├б├а├в├л├е├н├и├┐ ├╜├л├е├м├е├н├▓├а ├в ├▒├п├и├▒├о├к}
procedure AddElem(var spisok1:List;zn1:Integer);
var
tmp:List;
begin
if spisok1=nil then
begin
GetMem(spisok1,sizeof(TList));
tmp:=spisok1;
end
else
begin
tmp:=spisok1;
while tmp^.next<>nil do
tmp:=tmp^.next;
GetMem(tmp^.next,sizeof(TList));
tmp:=tmp^.next;
end;
tmp^.next:=nil;
tmp^.c:=zn1;
end;
{├П├░├о├╢├е├д├│├░├а ├в├╗├в├о├д├а}
procedure Print(spis1:List);
begin
if spis1=nil then
begin
writeln_cp866('├Н├е├▓ ├╜├л├е├м├е├н├▓├о├в!');
exit;
end;
while spis1<>nil do
begin
Write(spis1^.c, ' ');
spis1:=spis1^.next
end;
end;
{├С├о├░├▓├и├░├о├в├к├а ├▒├п├и├▒├к├а}
procedure Sort(var spis1:list);
var
tmp,rab:List;
tmps:integer;
begin
GetMem(tmp,SizeOf(Tlist));
rab:=spis1;
while rab<>nil do
begin
tmp:=rab^.next;
while tmp<>nil do
begin
if tmp^.c<rab^.c then
begin
tmps:=tmp^.c;
tmp^.c:=rab^.c;
rab^.c:=tmps
end;
tmp:=tmp^.next
end;
rab:=rab^.next
end
end;
{├п├░├о├╢├е├д├│├░├а ├п├е├░├е├▒├е├╖├е├н├и├┐ ├м├н├о├ж├е├▒├▓├в(├▒├п├и├▒├к├о├в) }
procedure Merge (var spisok1,spisok2,spisok3:List);
begin
while ((spisok1<>nil) and (spisok2<>nil)) do {├п├о├к├а ├╡├о├▓├┐ ├б├╗ ├о├д├и├н ├н├е ├░├а├в├е├н nill}
if spisok1.c<spisok2.c then {├Е├▒├л├и ├╜├л-├▓ ├п├е├░├в├о├г├о ├м├е├н├╝├╕├е ├в├▓├о├░├о├г├о}
begin
AddElem(spisok3,spisok1^.c); spisok1:=spisok1^.next; {├▓├о├г├д├а ├д├о├б├а├в├л├┐├е├м ├╜├л-├▓ ├п├е├░├в├о├г├о ├м├н├о├ж├е├▒├▓├в├а, ├п├░├о├д├в├и├г├а├е├м├▒├┐ ├в ├п├е├░├в├о├м ├м├н├о├ж├е├▒├▓├в├е}
end
else if spisok1.c>spisok2.c then {├и├н├а├╖├е ├в├▓├о├░├о├г├о, ├п├░├о├д├в├и├г├а├е├м├▒├┐ ├в├о ├в├▓├о├░├о├м ├м├н├о├ж├е├▒├▓├в├е}
begin
AddElem(spisok3,spisok2^.c); spisok2:=spisok2^.next;
end
else
begin {├Е├▒├л├и ├░├а├в├н├╗, ├▓├о├г├д├а ├п├░├о├д├в├и├ж├е├н├и├е ├в ├о├б├о├и├╡ ├м├н├о├ж├е├▒├▓├в├а├╡}
AddElem(spisok3,spisok1^.c); spisok1:=spisok1^.next; spisok2:=spisok2^.next;
end;
if spisok1<>nil then {├Е├▒├л├и ├п├е├░├о├е ├м├о├ж├е├▒├▓├в├о ├н├е ├░├а├в├н├о nill}
while spisok1.next<>nil do
begin {├▓├о├г├д├а ├д├о├б├а├в├л├┐├е├м ├о├▒├▓├а├▓├о├к}
AddElem(spisok3, spisok1.c);
spisok1:=spisok1^.next;
end;
if spisok2<>nil then {├а├н├а├л├о├г├и├╖├н├о, ├▓├о├л├╝├к├о ├▒├о ├в├▓├о├░├╗├м}
while spisok2.next<>nil do
begin
AddElem(spisok3, spisok2.c);
spisok2:=spisok2^.next;
end;
end;
Var spisok1, spisok2, spisok3: List; {├▒├п├и├▒├к├и(├м├н├о├ж├е├▒├▓├в├а)}
i,m: integer; {├▒├╖┬╕├▓├╖├и├к├и}
begin
{├з├а├п├о├л├н├┐├е├м ├▒├п├и├▒├к├и ├░├а├н├д├о├м├н├о}
randomize;
{├п├е├░├в├╗├й}
for i:=1 to n do
begin
m:=random(50);
AddElem(spisok1,m);
end;
{├в├▓├о├░├о├й}
for i:=1 to k do
begin
m:=random(50);
AddElem(spisok2,m);
end;
Sort(spisok1); {├▒├о├░├▓├и├░├│├е├м ├▒├п├и├▒├к├и(├м├н├о├ж├е├▒├▓├в├а)}
Sort(spisok2);
Writeln_cp866('├П├е├░├в├о├е ├м├н├о├ж├е├▒├▓├в├о -->>');
Print(spisok1); Writeln; Writeln;
Writeln_cp866('├В├▓├о├░├о├е ├м├н├о├ж├е├▒├▓├в├о -->>');
Print(spisok2); Writeln; Writeln;
Merge(spisok1, spisok2, spisok3); {├о├б├╝├е├д├и├н├┐├е├м ├м├н├о├ж├е├▒├▓├в├а}
Writeln_cp866('├О├б├╝├е├д├и├н├е├н├и├е ├м├н├о├ж├е├▒├▓├в -->>');
Print(spisok3); Writeln; Writeln;
Writeln_cp866('************ PRESS ENTER TO EXIT ************');
Readln;
end.
На каждом шаге основного цикла возможна одна из трёх ситуаций: текущий элемент множества А меньше, больше или ра-вен текущему элементу множества В. В первом случае в результирующий список добавляется текущий элемент множества А и происходит продвижение в этом множестве, во втором аналогичная операция производится с множеством В, а в третьем случае найдены совпадающие элементы и про-исходит продвижение сразу в обоих множествах. Таким образом, в ре-зультат попадают все элементы обоих множеств, причем совпадающие элементы попадают ровно один раз. По завершении ос¬новного цикла один из указателей pa и pb (но не оба вместе!) может быть не равен nil. В этом случае остаток соответствующего множества без проверки добавляется в результат.