uses crt;
type TLine=
record
number:integer;
line:string;
isSelected :boolean;
end;
type PNode=^TNode;
TNode=
record
data:TLine;
next:PNode;
end;
procedure push(var head:PNode;l:TLine);
var newNode:PNode;
begin
new(newNode);
newNode^.data.number:=l.number;
newNode^.data.line:=l.line;
newNode^.data.isSelected :=l.isSelected ;
newNode^.next:=head;
head:=newNode;
end;
procedure pop(var head:PNode);
var temp:PNode;
begin
if(head<>nil) then
begin
temp:=head;
head:=head^.next;
dispose(temp);
end;
end;
procedure printList(head:PNode);
var temp:PNode;
begin
temp:=head;
while(temp<>nil) do
begin
if temp^.data.isSelected then
writeln(temp^.data.number,' ',temp^.data.line);
temp:=temp^.next;
end;
end;
procedure split(head:PNode;var front:PNode;var back:PNode);
var slow:PNode;
fast:PNode;
begin
if((head=nil) or(head^.next=nil)) then
begin
front:=head;
back:=nil;
end
else
begin
slow:=head;
fast:=head^.next;
while(fast<>nil) do
begin
fast:=fast^.next;
if(fast<>nil) then
begin
slow:=slow^.next;
fast:=fast^.next;
end;
end;
front:=head;
back:=slow^.next;
slow^.next:=nil;
end;
end;
function sortedMerge(a:PNode;b:PNode):PNode;
var result:PNode;
tmp:PNode;
begin
tmp:=nil;
result:=nil;
if(a^.data.line<=b^.data.line) then
begin
result:=a;
a:=a^.next;
tmp:=result;
end
else
begin
result:=b;
b:=b^.next;
tmp:=result;
end;
while ((a<>nil)and(b<>nil)) do
begin
if(a^.data.line<=b^.data.line) then
begin
tmp^.next:=a;
tmp:=tmp^.next;
a:=a^.next;
end
else
begin
tmp^.next:=b;
tmp:=tmp^.next;
b:=b^.next;
end;
end;
if(a=nil) then tmp^.next:=b
else tmp^.next:=a;
sortedMerge:=result;
end;
procedure mergesort(var head:PNode);
var h1:PNode;
h2:PNode;
begin
h1:=nil;
h2:=nil;
if((head<>nil) and (head^.next<>nil)) then
begin
split(head,h1,h2);
mergesort(h1);
mergesort(h2);
head:=sortedMerge(h1,h2);
end;
end;
var f1,f2,f3:text;
l:TLine;
head1,head2:PNode;
it1,it2:PNode;
i:integer;
line:string;
path1,path2,path3:string;
begin
head1:=nil;
head2:=nil;
writeln('Podaj scezke do pierwszego pliku');
readln(path1);
writeln('Podaj scezke do drugiego pliku');
readln(path2);
writeln('Podaj scezke do pliku wynikowego');
readln(path3);
assign(f1,path1);
assign(f2,path2);
reset(f1);
i:=1;
while not eof(f1) do
begin
readln(f1,line);
l.number:=i;
l.line:=copy(line,1,pos('(',line));
l.isSelected :=true;
push(head1,l);
i:=i+1;
end;
close(f1);
reset(f2);
i:=1;
while not eof(f2) do
begin
readln(f2,line);
l.number:=i;
l.line:=copy(line,1,pos('(',line));;
l.isSelected :=true;
push(head2,l);
i:=i+1;
end;
close(f2);
clrscr;
printList(head1);
readkey;
clrscr;
printList(head2);
readkey;
mergesort(head1);
mergesort(head2);
it2:=head2;
while it2<>nil do
begin
it1:=head1;
while it1<>nil do
begin
if(it1^.data.line=it2^.data.line) then
it1^.data.isSelected :=false;
it1:=it1^.next;
end;
it2:=it2^.next;
end;
clrscr;
printList(head1);
readkey;
assign(f3,path3);
rewrite(f3);
it1:=head1;
while it1<>nil do
begin
if it1^.data.isSelected then
writeln(f3,it1^.data.number,' ',it1^.data.line);
it1:=it1^.next;
end;
close(f3);
it1:=head1;
it2:=head2;
while it1<>nil do
pop(it1);
while it2<>nil do
pop(it2);
end.
Można by zrezygnować z tego pola isSelected gdyby napisać procedurę usuwającą węzeł
Problem w tym że lista kroków u Wałaszka jest napisana błędnie
Algorytm usuwania wybranego elementu listy jednokierunkowej
Wejście
head – zmienna wskazująca początek listy
e – wskazanie elementu listy do usunięcia
Wyjście:
Lista bez elementu wskazywanego przez e.
Dane pomocnicze:
p – wskazania elementu listy
Lista kroków:
K01: Jeśli head ≠ e, to idź do K04 ; sprawdzamy, czy usuwany element jest pierwszym na liście
K02: Usuń pierwszy element listy ; jeśli tak, usuwamy go z listy
K03: Zakończ
K04: p ← head ; w p ustawiamy początek listy
K05: Dopóki (p→next) ≠ e, wykonuj p ← (p→next) ; w p ustawiamy adres elementu poprzedzającego e
K06: (p→next) ← (e→next) ; odłączamy e od listy
K07: Usuń z pamięci element wskazywany przez e
K08: Zakończ