Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 3

Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр

стр.: 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

Полный текст лекций можно скачать здесь

---

5. Пока P>=R (приход клиента после ближайшей разгрузки очереди) и очередь не пуста, выполнить:

1) S:=S+R-M[J], где J-номер клиента из начала очереди;

2) разгрузить очередь, убрав клиента из ее начала, и выдать сообщение на экран;

3) если очередь не пуста, то R:=R+T[J+1] - следующий момент разгрузки очереди.

6. Если очередь пуста, то

R:=M[I]+T[I].

7. Постановка в очередь I-го клиента и выдача сообщения.

8. I:=I+1; если I<=N, то переход к шагу 4.

9. Если очередь не пуста, то ее полная разгрузка с выдачей сообщений.

10. H:=S/N - среднее время обслуживания клиента.

11. Выдача H; конец.

Приведем текст программы. Очередь реализована с помощью массива. Начало очереди соответствует первому элементу массива, а конец - последнему элементу.

Program Ochered;

Uses Crt;

Type

klient=record

Name: string; { имя }

M: integer; { момент прихода }

T: integer { время обслуживания }

end;

Var

H: real; { среднее время обслуживания клиента }

I, J, R, S, P, N, L: integer;

Och: array [1..100] of integer; { очередь }

Bego, Endo: integer; { начало и конец очереди }

Kli: array [1..100] of Klient;

{ список клиентов по возрастанию моментов прихода }

Procedure Razgruz;

Begin

J:=Och[Bego]; { номер клиента из начала очереди }

S:=S+R-Kli[J].M;

{ учет времени его нахождения в очереди }

Write('Время: ', R, ', обслужен клиент ', Kli[J].Name);

Endo:=Endo-1; { разгрузка очереди }

For L:=Bego to Endo do

Och[L]:=Och[L+1];

if Endo>0 then { очередь не пуста }

begin

WriteLn(', следующий клиент ', Kli[J+1].Name);

R:=R+Kli[J+1].T

{ следующий момент разгрузки }

end

else WriteLn(', очередь пуста !');

ReadLn { пауза }

End;

Begin

ClrScr; { очистка экрана }

For N:=1 to 100 do

begin

with Kli[N] do

Begin

WriteLn('Введите информацию об очередном клиенте:');

Write('Введите имя (к-признак конца): ');

ReadLn(Name);

if Name='к' then Break; { конец списка клиентов }

Write('Укажите момент прихода: ');

ReadLn(M);

Write('Сообщите время обслуживания: ');

ReadLn(T)

end

end;

WriteLn;

WriteLn(' ПРОТОКОЛ РАБОТА БАНКА');

N:=N-1; { число клиентов }

S:=0; { для общего времени обслуживания }

Bego:=1; { начало очереди всегда здесь ! }

Endo:=0; { критерий пустой очереди }

R:= Kli[1].M+ Kli[1].T; { ближайший момент разгрузки очереди }

For I:=1 to N do

begin

P:=Kli[I].M; { момент прихода следующего клиента }

While (P>=R) and (Endo>0) do

Razgruz;

{ очередь сокращается до прихода следующего клиента }

{ и больше не разгружается }

if Endo=0 then R:=Kli[I].M+Kli[I].T;

{ следующий момент разгрузки }

Endo:=Endo+1; { постановка в очередь i-го клиента }

Och[Endo]:=I;

Write('Время: ', Kli[I].M,', прибыл клиент ', Kli[I].Name);

if Endo=1 then

WriteLn(', очереди нет, ура !')

else

WriteLn(', встал в очередь за клиентом ',

Kli[Och[Endo-1]].Name);

ReadLn { пауза }

end;

While Endo>0 do

Razgruz;

H:=S/N;

WriteLn('Обслуживание закончено, перерыв на обед !');

WriteLn('Среднее время обслуживания клиента: ',h:5:2);

ReadLn { пауза }

End.

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

Рассмотрим кольцевую очередь, заданную массивом Och с N элементами. Начало и конец очереди заданы индексами Bego и Endo. Следующим после N-го элемента будем считать первый элемент массива. Тогда постановка в очередь выполняется командами

Endo:= Endo mod N + 1;

Och[Endo]:=NewElement;

а продвижение производит оператор Bego:=Bego mod N + 1. Индексы Bego и Endo как бы двигаются по кольцу вдогонку друг за другом. Необходимым условием для постановки в очередь в этом случае является NumElement < N, где NumElement – число элементов в очереди, а при продвижении очереди должно быть NumElement >0. Буфер клавиатуры в MS DOS организован в виде кольцевой очереди.

2.3. Двусвязные списки и мультисписки

Часто применяются двусвязные списки, в которых элемент связан как с последующим, так и предыдущим элементами. Двусвязные списки допускают просмотр в любом направлении и менее чувствительны к потере связей.

Мультисписком называют такой список, в котором каждый элемент может входить в несколько подсписков без дублирования данных в памяти. Вместе с указателем типа Next мультисписок имеет дополнительно столько указателей, сколько предусмотрено подсписков. Каждый подсписок может быть просмотрен отдельно. Например, общий список студентов может включать подсписки отличников, ударников и неуспевающих. В этом примере подсписки не пересекаются, но это не обязательно.

3. Деревья

3.1. Организация в памяти и рекурсивный обход

Дерево является частным случаем графа и представляет собой множество вершин, связанных ребрами. Мы будем рассматривать деревья в практическом плане с точки зрения их представления и использования. Есть много определений деревьев. По одному из них, дерево – это связный граф без циклов. Рекурсивное определение: дерево – это либо пустое дерево, либо вершина, связанная ребрами с конечным числом дереьев. Число вершин дерева на единицу превышает число ребер.

Дерево является иерархически организованной структурой. Основой дерева является корень. Каждая вершина, кроме корня, имеет единственного предшественника, называемого отцом. Последователи вершины называются ее сыновьями. Вершины, не имеющие сыновей, называются листьями. Деревья принято изображать корнем вверх.

Степенью вершины называют количество ее сыновей, а степенью дерева – максимально возможную степень вершины. Деревья степени 2 называют бинарными, а большей степени – сильно ветвящимися.

Деревья обязаны своим названием обычным деревьям. С помощью деревьев представляются иерархически организованные объекты. Например, руководителю предприятия можно поставить в соответствие корень. Его заместители соответствуют сыновьям корня. Руководители служб, подчиняющиеся напрямую заместителям, образуют следующий уровень иерархии. Листьям будут соответствовать рядовые сотрудники, не имеющим подчиненных.

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

В программировании используется древовидная структура модулей приложения. Алгебраическое выражение может быть представлено бинарным деревом, переменные и константы которого соответствуют листьям, а знаки операций – остальным вершинам. Данный пример подробнее рассматривается ниже.

Самым простым представлением дерева является список его вершин. Элемент списка содержит информационную часть, указание на отца и список сыновей. Недостаток такого представления в том, что степени вершин дерева могут значительно отличаться. Приходится резервировать память, ориентируясь на максимальную степень, что часто крайне нерационально.

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

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

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

Например, сильно ветвящееся дерево (......)

представляется бинарным деревом (....)

Обходом дерева называется обработка всех его вершин в некотором порядке. Рассмотрим варианты обхода бинарного дерева, состоящего из корня R и листьев A и B. Имеются три стандартных порядка обхода: сверху вниз, снизу вверх и слева направо.

При обходе сверху вниз корень посещается раньше листьев, то есть вершины перечисляются в порядке R,A,B. Обход снизу вверх дает порядок A,B,R. Слева направо вершины обходятся в порядке A,R,B.

Указанные варианты обхода обобщаются на случай любого бинарного дерева. Так если вершина A является корнем поддерева, то на это поддерево рекурсивно распространяется выбранный вариант обхода.

Рассмотрим описанные варианты обхода на примере дерева, представляющего алгебраическое выражение (A+B/C)*(D-E*F). Как указывалось раньше, этому выражению соответствует дерево (.....)

Обход сверху вниз дает префиксную форму записи выражения (знак перед операндами): +A/BC-D*EF. Обход снизу вверх приводит к постфиксной форме (знак после операндов): ABC/+DEF*-*. При обходе слева направо получается инфиксная форма (знак между операндами): A+B/C*D-E*F.

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