DINAMICO (Методичка С++), страница 3

program ex_ochered;

type ukp=^cpisel; {указатель на элемент списка}

cpisel= record { запись типа «элемент списка»}

inf:integer;

p:ukp

end;

var spis:boolean;

pb:ukp; {первый элемент списка}

k,l:integer;

procedure formspsl(n:integer;var pob:ukp);

{процедура формирование списка целых чисел в виде очереди с помощью датчика случайных чисел}

var i,c:integer;

po, { текущий элемент списка}

poe:ukp; { последний элемент списка}

begin

randomize;

c:=random(20);

new(po); {запрос на выделение памяти для размещения элемента списка}

pob:=po; {фиксация адреса первого элемента}

poe:=po; {фиксация последнего элемента списка}

po^.inf:=c; {занесение информации в элемент списка}

po^.p:=nil; {занесение в поле указателя элемента списка адреса nil}

for i:=2 to k do {цикл добавления остальных элементов}

begin

new(po);

c:=random(20);

po^.inf:=c;

po^.p:=nil;

poe^.p:=po; {занесение в поле указателя последнего элемента адреса очередного}

poe:=po {текущий элемент становится последним элементом}

end;

end;

procedure udalsp(l:integer;var pob:ukp;var spis:boolean);

{ удаление всех элементов списка, кратных l }

var po,pot:ukp;

begin

spis:=true;

while ((pob^.inf mod l)=0) and (pob^.p<>nil) do {цикл, пока первый элемент списка кратен l и не конец списка}

begin

po:=pob;pob:=pob^.p;

dispose(po)

end;

po:=pob;pot:=pob;

while po^.p<>nil do begin {пока не конец списка}

if (po^.inf mod l)=0 then begin {если элемент кратен l}

pot^.p:=po^.p;dispose(po);

po:=pot^.p end

else begin

pot:=po;po:=po^.p end

end;

if po=pob then begin {если остался один первый элемент и он кратен l}

if (po^.inf mod l )=0 then

begin

dispose(pob);

writeln(' список ликвидирован ');

spis:=false;

end end

else begin

if (po^.inf mod l)=0 then begin {если последний элемент кратен l}

pot^.p:=po^.p;

dispose(po); end

end;

end;

procedure pechsp(pob:ukp);

var po:ukp;

{процедура печати сформированного в виде очереди списка }

begin

po:=pob; {присвоение текущему указателю адреса начала списка}

while po^.p<>nil do {цикл пока не конец списка}

begin write(po^.inf:5); {печать информации элемента списка}

po:=po^.p {переадресация на следующий элемент}

end;

writeln(po^.inf:5);

end;

{ Основная программа }

begin

{ формирование списка}

writeln(' введите длину списка k <= 15');

readln(k);

formspsl(k,pb);

{ печать сформированного списка }

writeln(' сформированный список ');

pechsp(pb);readln;

writeln('введите число для удаления кратных ему');

readln(l);

udalsp(l,pb,spis);

{ печать списка после удаления чисел кратных l}

if spis then begin

writeln(' список после удаления чисел, кратных ',l:5);

pechsp(pb);end;

readln

end.

Пример 3. Программа формирует двунаправленный список в виде очереди, вводя информацию для формирования списка с клавиатуры и организует его печать в прямом и обратном направлении.

program spisok2;

type

point2=^dvspis; { указатель на элемент двунаправленного списка}

str1=string[20]; { элемент двунаправленного списка}

dvspis=record

fam:string;

pred,posl:point2

end;

var first, { указатель на начало списка}

last:point2; { указатель на конец списка}

function fio(ss:str1):str1;

{функция выравнивания фамилии по левой границе}

var i:integer;

begin

for i:=length(ss)+1 to 20 do

ss:=ss+' ';

fio:=ss

end;

{ процедура печати списка в прямом направлении }

procedure pechspf(f:point2);

var q:point2;

begin

q:=f;

writeln(' печать списка в прямом направлении ');

while q<>nil do begin

writeln(fio(q^.fam));

q:=q^.posl

end

end;

{ процедура печати списка в обратном направлении }

procedure pechspl(l:point2);

var q:point2;

begin

q:=l;

writeln(' печать списка в обратном направлении ');

while q<>nil do begin

writeln(fio(q^.fam));

q:=q^.pred

end

end;

procedure formspd(var first,last:point2); {процедура формирования двунапрвленного списка}

var

tek,tk:point2; { рабочие указатели списка}

st:str1;

i,j:integer;

begin

writeln(' введите фамилию из списка в конце списка - пустая строка');

{ начало формирования списка в процедуре}

readln(st); {чтение очередной фамилии}

new(tek); {запрос памяти под текущий элемент}

tek^.fam:=st; {заполнение информационного поля текущего элемента}

tek^.pred:=nil; {заносим в указатель на предыдущий элемент nil}

tek^.posl:=nil; {заносим в указатель на последующий элемент nil}

first:=tek; {запоминаем значение адреса первого элемента списка}

tk:=first; {запоминаем адрес элемента как предыдущего}

readln(st);

while length(st)<>0 do {цикл пока есть фамилии}

begin

new(tek); {запрос памяти под текущий элемент}

tek^.fam:=st;

tek^.posl:=nil; {заносим в указатель на последующий элемент nil}

tek^.pred:=tk; {заносим в указатель на предыдущий элемент текущего элемента адрес предыдущего}

tk^.posl:=tek; {заносим в указатель на последующий элемент предыдущего элемента адрес текущего}

tk:=tek; {текущий элемент становится предыдущим}

readln(st);

end;

last:=tk; {последний текущий запоминаем как последний элемент списка}

{ конец формирования списка в программе}

end;

{ Основная программа}

begin

formspd(first,last);

pechspf(first);

pechspl(last);

readln;

end.

Пример 4. Программа формирует из элементов, содержащих сведения о деталях, стек, а затем вычеркивает из него все детали с параметрами, которые не совпадают с требуемыми и печатает оставшиеся в стеке детали

program stek;

type point=^zap; {указатель на запись о деталях}

zap=record {запись о деталях}

det:string[10];

diam:real;

p:point;

end;

var r,q,f:point;

a:zap;

c:integer;

begin {формирование стека}

new(r); {запрос на память}

r^.p:=nil; {запись в указатель признака конца списка}

writeln('Вводите названия деталей и диаметры в порядке:');

writeln(' название детали <enter> диаметр <enter> ');

writeln(' для окончания набрать название детали - end ');

readln(r^.det,r^.diam); {данные о деталях}

read(a.det);

while a.det<>'end' do

begin readln(a.diam);

q:=r; {запоминаем новый элемент как вершину стека}

new(r); {выделяем память под новый элемент}

r^.det:=a.det;

r^.diam:=a.diam;

r^.p:=q; {заносим адрес старой вершины в указатель нового элемента}

read(a.det);

end;

{ Конец формирования списка }

q:=r; {сохранение вершины стека}

c:=0;

repeat

if q^.diam<1 then {если элемент следует удалить}

begin

if c=0 then begin r:=r^.p; q:=r end {удаление "верхнего" элемента}

else begin q:=q^.p; f^.p:=q end {удаление следующего элемента}

end

else begin {элемента не удаляется}

f:=q; q:=q^.p; c:=1 end;

until q=nil; {пока не конец списка}

{фрагмент печати стека с оставшимися элементами}

q:=r; {пересохранение вершины стека}

if q=nil then writeln('список пуст, все детали удалены')

else

while q<>nil do

begin writeln(q^.det:11,q^.diam:5:1);

q:=q^.p;

end;

end.

Пример 5. Программа реализует игру "считалка" используя кольцевой список. В кругу стоят n человек. Каждый раз из круга выходит человек, на которого падает номер m. Счет начинается со следующего. Водит оставшийся. Определить кому "водить". Решение задачи использует особенность всех считалок - характеристическое число. Это число определяется количеством слов считалки. Его можно определить путем простого подсчета слов считалки, введенной с клавиатура. А можно просто ввести это число непосредственно с клавиатуры, что и сделано в программе.

program exkolco;

Function Play(n,m:integer):integer;

type child_ptr=^child;

child=record

name:integer;

p:child_ptr;

end;

var First,Next,Pass:child_ptr;

j,k:integer;

begin { Формирование списка }

new(First);

First^.name:=1;

Pass:=First;

for k:=2 to N do

begin new(Next);

Next^.name:=k;

Pass^.p:=Next;

Pass:=Next;

end;

{ Замыкание круга }

Pass^.p:=First;

{ Повторение считалки N-1 раз }

Pass:=First;

for k:=n downto 2 do

begin for j:=1 to m-1 do

begin Next:=Pass;

Pass:=Pass^.p;

end;

writeln(Pass^.name);

Next^.p:=Pass^.p;

dispose(Pass);

Pass:=Next^.p;

end;

Play:=Pass^.name;

end;

var n1,m1: integer;

begin

writeln(‘введите количество игроков и характеристическое число считалки’);

readln(n1,m1);

writeln('Водит игрок ',play(n1,m1):6);

end.

1. Бинарные деревья.

Бинарное (двоичное) дерево есть конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня. Пример бинарного дерева приведен на схеме.

Корнем бинарного дерева называется вершина (узел), в которую не входит ни одна стрелка, символизирующая, что эта вершина является корнем какого либо поддерева. Каждая вершина бинарного дерева в свою очередь может содержать два поддерева Левая ветвь, исходящая из произвольного узла, ведет в корень левого поддерева, если оно есть, а правая ветвь - в корень правого поддерева этого узла. Узлы, из которых не выходит ни одной ветви называются листьями.

В программах для реализации бинарных деревьев используются списочные структуры. Узлы бинарного дерева обычно представляются записями, содержащими несколько полей: информационное поле или указатель на него и несколько полей ссылочного типа. В идеале узел дерева может содержать 4 поля:

а).ключ записи (некоторый признак, по которому запись включается в дерево, сортируется, идентифицируется),

б) указатель на информацию, которая ставится в соответствие этой записи (иногда эта информация достаточно объемна, поэтому размещается отдельно от самой записи),

в) два указателя на вершину влево вниз и на вершину вправо вниз (указатели на корни двух поддеревьев этого узла).

Иногда, для простоты реализации (если информация простая и ее не много), поле ключа отбрасывается, а поле указателя на данные заменяется на сами данные. Именно по этим данным ведется идентификация и данные служат ключом для формирования дерева и работа с ним. Такой подход позволяет сократить запись до трех полей - информационное и два ссылочных.

Существуют определенные правила работы с бинарными деревьями. Различают следующие операции:

1. операция включения нового узла в дерево. Алгоритм такого включения следующий. Если дерево пусто, то первый же вводимый узел становится корнем всего бинарного дерева. При добавлении всех остальных узлов, в соответствии с ключом (информацией), отыскивается подходящая вершина, к которой и подсоединяется новый узел. При этом, если ключ записи нового узла меньше значения в очередном узле, то поиск идет по левой ветви или подветви. Если ключ нового узла равен или больше ключа в очередном узле, то поиск места подсоединения ищется в правой ветви или подветви.

Рассмотрим пример формирования бинарного дерева на примере последовательности целых чисел. Пусть дана следующая последовательность целых чисел {10, 2, 4, 11, 15, 3, 6, 8, 1, 2, 5}.Тогда дерево, сформированное по правилам добавления новых элементов, представлено на схеме ниже.

2.Удаление записи с указанным ключом. Непосредственное удаление записи реализуется в зависимости от того, какая вершина удаляется. Можно выделить 4 случая:

а) Удаляемая вершина отсутствует. Выдается соответствующее сообщение.

б) Удаляемая вершина является одной из конечных узлов (листьев). В этом случае просто удаляется ссылка на эту вершину в узле, из которого она выходила.

в) Удаляемая вершина содержит только одну ветвь. Для удаления необходимо скорректировать соответствующую ссылку, в узле из которого она выходила, заменив ее на адрес узла, выходящего из удаляемой вершины.

г) Удаляемая вершина содержит две ветви, исходящие из нее. В Этом случае нужно найти подходящий узел, который можно вставить на место удаляемого, причем этот подходящий узел должен легко перемещаться. Такой узел всегда существует: это либо самый правый элемент левого поддерева, либо самый левый элемент правого поддерева удаляемого узла. Для иллюстрации рассмотрим предыдущий пример. Пусть из дерева необходимо удалить узел, содержащий элемент с числом 4. Удаляемый узел содержит две ветви. По правилу ищем подходящий для замены удаляемого узла. В левой подветви правого элемента нет. Переходим к правой подветви. Крайний левый элемент - узел 5. Именно он заменит узел 4. После преобразования дерево выглядит как показано на схеме слева.

Если вершин, удовлетворяющих условию удаления, в дереве может оказаться несколько, следует заранее обговорить ситуацию. Действия могут быть следующими:

• удаляется первая, обнаруженная вершина:

• удаляется последняя, обнаруженная в дереве вершина:

• удаляются все удовлетворяющие условию вершины.

2.Поиск записи в дереве. В этом случае от корня просматривается дерево по следующему алгоритму. Если значение ключа в искомом узле меньше чем в корневом, то поиск переходит в левую подветвь. Если больше или равно - то в правую подветвь. И так в каждом следующем узле до тех пор, пока не отыщется искомый узел. Узел может отсутствовать. Тогда выдается соответствующее сообщение. В противном случае узел помечается как найденный (запоминается его адрес. После этого узел может обрабатываться в соответствии с алгоритмом программы).

1. Сортировка с использованием дерева. Так как дерево формируется по определенным выше правилам, то сортировка данных, находящихся в дереве, осуществляется соответствующим обходом дерева. Для этого обход начинается с корня. Затем обходятся все левые элементы левых ветвей, а если таких нет то фиксируется значение соответствующей вершины и просматриваются правые узлы. В этих узлах опять просмотр начинается с левых элементов. После того, левое поддерево просмотрено, осуществляется переход к правому поддереву. В нем алгоритм поиска повторяется. Ниже приводится пример формирования и сортировки с помощью бинарного дерева. Представлены полный и рекурсивный варианты обхода бинарного дерева.

Пример 6. Программа строит бинарное дерево из вводимых с клавиатуры целых чисел, а затем осуществляет обход дерева для печати отсортированных данных.