Пусть L обозначает кольцевой (циклический) двунаправленный список с заглавным звеном и пусть E обозначает величину типа элементов, входящих в список. Описать функцию или процедуру, которая: в списке L переставляет в обратном порядке все элементы между первым и последним вхождениями элемента Е, если E входит в L не менее двух раз.
ЛИСТИНГ ПРОГРАММЫ
Program Revers_Spiska;
type
spisok=^zap;
zap=Record
inf:integer;
next:spisok;
end;
var
nach,p,q:spisok;
E:integer;
Procedure Input_L(var nach:spisok);
var p,q:spisok; N,i:integer; X:integer;
begin
Randomize;
write('n:');
readln(N);
writeln('spisok:');
X:=random(20)+1;
new(p);
nach:=p;
p^.inf:=X;
p^.next:=nil;
for I:=2 to N do
begin
new(q);
p^.next:=q;
X:=random(20)+1;
q^.inf:=X;
q^.next:=nil;
p:=q;
end;
end;
Procedure Print_L(var nach:spisok);
var p,q:spisok;
begin
writeln('spisok:');
p:=nach;
if p=nil then writeln('spisok pust')
else while p<>nil do
begin
writeln(p^.inf);
p:=p^.next;
end;
end;
Procedure Destroy(nach_p:spisok);
var p,p1:spisok;
begin
p:=nach_p;
while p<>nil do begin
p1:=p;
p:=p^.next;
Dispose(p1);
end;
end;
Procedure V_ob(var nach_p:spisok; pn,pk:spisok);
var p,q,q1,q2,r:spisok;
begin
p:=pn;
q:=p^.next;
q1:=q;
q2:=pk^.next;
r:=q^.next;
while q<>pk do
begin
q^.next:=p;
p:=q;
q:=r;
r:=r^.next;
end;
pn^.next:=p;
q1^.next:=pk;
end;
Procedure Obr_sp(var nach_p:spisok; E:integer);
var p,p_p,p_v:spisok;
begin
p:=nach_p;
p_p:=nil; p_v:=nil;
while p<>nil do
begin
if p^.inf=E then
begin
if p_p=nil then p_p:=p
else p_v:=p;
end;
p:=p^.next;
end;
if p_v<>nil
then V_ob(nach,p_p,p_v);
end;
begin
Input_L(nach);
Print_L(nach);
write('E=');
readln(E);
Obr_sp(nach,E);
Print_L(nach);
readln;
end.
НАБОР ТЕСТОВ
Если в списке нет повторяющихся элементов, то просто выводится список элементов. Например, в списке с помощью случайной генерации сформировался список элементов: 14; 18; 20; 13. То выведется на экран этот же список.
Если в списке есть два и больше одинаковых элементов и мы хотим перевернуть числа находящиеся между двумя крайними заданными элементами. Например: 6, 6, 17, 9, 6, 3, 5, 19. Получим: 6, 9, 17, 6, 6, 3, 5, 19.
Если дан список: 20, 13, 14, 9, 18, 13. Выведется: 20, 13, 18, 9, 14, 13.
ГЛАВА 4. ЗАДАЧА V 1 с
Описать процедуру или функцию, которая: подсчитывает число вершин на n- ном уровне непустого дерева T (корень считать вершиной 0-го уровня).
ЛИСТИНГ ПРОГРАММЫ
program K_vo_elementov;
type
tl=^Tree;
Tree=Record
data:real;
L,R:tl;
end;
Var
kd:tl;
E,d,sm:real;
s:string;
code:integer;
k,n,m:integer;
Procedure InsTree(n:real;var t:tl);
begin
if t=nil then
begin
new(t);
with t^ do
begin l:=nil;
r:=nil;
data:=n;
end
end
else if n<=t^.data then InsTree(n,t^.l)
else InsTree(n,t^.r)
end;
Procedure PrintTree(t:tl);
begin
if t<>nil then
begin
write(t^.data:1:1,' ');
PrintTree(t^.l);
PrintTree(t^.r);
end;
end;
Procedure Urov(t:tl; var k:integer; n,m:integer);
begin
if t<>nil then
begin
if m=0 then if m=n then k:=1 else k:=0
else if m=n then k:=k+1 else;
Urov(t^.l,k,n,m+1);
Urov(t^.r,k,n,m+1);
end;
end;
begin
writeln('<Enter> - konec vvoda');
writeln('vvodite derevo: ');
kd:=nil;
readln(s);
val(s,d,code);
while s<>'' do
begin InsTree(d,kd);
readln(s); val(s,d,code);
end;
write('n='); readln(n);
Urov(kd,k,n,0);
writeln('k-vo: ',k);
{ PrintTree(kd);}
readln;
end.
НАБОР ТЕСТОВ
Например, имеем дерево: 30, 40, 20, 25, 17, 63, 19, 24, 56.
Необходимо узнать число вершин на 2 и 7 уровне.
Число вершин на втором уровне равно 3.
Для проверки изобразим схематично:
Число вершин на 7 уровне равно нулю.
Число вершин на 0 уровне всегда равно 1 (по условию задачи – дерево не пустое).
ВЫВОДЫ
1) Была сделана программа для списков, которая включает в себя создание пустого списка, добавление элемента (в начало списка, в конец списка и после элемента с заданным номером, после ключа (вывод на экран дисплея), удаление элемента из списка (из начала, из конца, удаление элемента с заданным номером, с заданным ключом).
2) Создана программа для кольцевого списка, в которой переворачивались все элементы стоящие между двумя крайними заданными элементами.
3) К третьей задаче представлена программа, которая находит число вершин на n-ном уровне непустого дерева T.