МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ, ОРИЕНТИРОВАННЫЕ НА СТРУКТУРЫ ДАННЫХ
Часто на технологию разработки алгоритма влияют структуры данных, используемых в программе. Удачный выбор структур данных позволяет зачастую легко строить эффективные алгоритмы. Методы программирования, в которых такое влияние доминирует, называют методами, ориентированными на структуры данных. Рассмотрим некоторые классы задач, где полезны такие структуры как связные списки, очереди, стеки, деревья.
Сортировка массивов данных, т.е. расположение их элементов в определенном порядке, являясь одной из важнейших прикладных задач при эксплуатации информационных систем, требует больших временных затрат и ресурсов памяти ЭВМ. Легко представить возникающие трудности, когда в массиве данных происходят удаления и внесения новых записей. Обычные подходы заставят нас осуществлять заново сортировку измененного массива с физическими перестановками записей согласно известным процедурам упорядочивания.
Попробуем проблему решить с помощью линейного связанного списка. Массив преобразуют в двумерный, в котором по второму индексу (целые неотрицательные числа, называемые связями или указателями) располагают номера элементов массива.
| Info | Link | ||||
| 1 Петров
2 Смирнов 3 Алексеев | 3
4 1 | Линейный связанный список - это конечный набор пар, состоящих из информационной части (Info) и указующей части (Link). | |||
| N Кузнецов | 2 |
Линейные связанные списки являются эффективной структурой данных для моделирования ситуаций, в которых подвергаются изменениям упорядоченные массивы элементов данных. Особенно важно их использование при процедурах внесения или удаления элементов из середины массива. Когда модификации касаются лишь начала или/и конца, то необходимость в связанных списках отпадает, и становится достаточным использование одномерного исходного массива. Здесь на помощь приходят стеки и очереди.
Пусть, например, задано арифметическое выражение. Требуется определить, правильно ли расставлены в выражении скобки.
Для решения подобных задач используют стековую память (называемую просто «стек»). Стек представляет последовательность данных и имеет лишь одну границу для добавления и удаления элементов. В нашем случае в стек помещаются и удаляются скобки.
Первым необходимым условием правильности расстановок скобок является совпадение количества левых и правых скобок. Такой контроль легко осуществить введя счетчик top, который при просмотре выражения и обнаружении левой скобки (допустим, что имеем только круглые скобки '(' ) увеличивается на +1. Если на очередном месте встретилась правая скобка, то значение счетчика уменьшается на 1. Тогда правильность расстановки определяется по итоговому значению top.
Программа 36
program skobkal; (*проверка скобок по количеству*)
var top, i, n: integer; slovo: string[100]; skob: string[100];
begin
write('введи арифметическое выражение: ');
readln(slovo); n:length(slovo);
top:=0; skob:=''; i:=l;
while (i<=n) do begin
if slovo[i]=')' then begin top:=top+1; skob:=skob+slovo[i] end;
if slovo[i]=')' then begin
top:=top-l; skob:=skob+slovo[i] end;
i:=i+l
end;
writeln(skob) ;
if top=0 then write('выражение
правильное') i else write('выражение
неправильное');
readln .
end.
Строковая переменная skob предназначена "для визуализации всех имеющихся скобок в выражении.
В случае, когда в выражении используются фигурные, квадратные и круглые скобки, задача усложняется тем, что необходим еще контроль соответствия левых и правых скобок. В этой связи удобно использовать стек, в котором помещаются очередные левые скобки. При обнаружении правой скобки из вершины стека извлекается левая скобка, помещенная последней, и проводится их идентификация. Полный текст программы представлен ниже.
Программа 37
program skobka2; (*проверка расстановок скобок*) var top, i, n: integer;
slovo: string[100];
store: array [1. . 100] of char; -x: char.; sicob: string[100];
p: boolean;
begin
write('введи арифметическое выражение: ');
readln(slovo); n:=length(slovo) ;
top:=0; p:=true; skob:=''; i:=1;
while (i<=n)and(p) do
begin if (slovo[i]='(') or (slovo[i]='[') or (slovo[i]='(') then begin top:=top+l; store[top]:=slovo[i];
skob:=skob+slovo[i] end;
if slovo(i]='}' then begin x:=store(top];
if x<>'(' then p:=false
else begin top:=top-l; skob:=skob+slovo{i] end;
end;
if slovo[i]=']' then begin x:=store[top] ;
if x<>'[' then p:=false
else begin top:=top-l; skob:=skob+slovo[i] end;
end;
if slovo(i]=')' then begin x:=store(top] ;
if x<>'(' then p:=false
else begin top:=top-l; skob:=skob+slovo[i] end;
end;
i:=i+l end;
writeln(skob); if top=0 then write('выражение
правильное') else write('выражение
неправильное');
readln
end.
Структура данных «очередь» используется для моделирования систем массового оослужнвания: очереди людей в магазинах, транспортных потоков, производственных линий и т.п. Рассмотрим модельную ситуацию с формированием очереди в ком-нибудь учреждении сферы обслуживания, например, в банке.
Пусть задана скорость поступления клиентов в банк и известна скорость обслуживания. Вместо скорости поступления клиентов будем задавать вероятность р их появления в единицу времени. За скорость обслуживания примем число v, соответствующее времени обслуживания одного клиента. Для простоты примем в качестве массива данных о клиентах банка числовой массив со случайными числами из интервала 1..100. Для формирования очереди достаточно ввести две переменные, которые указывают на начало и конец списка данных.
Следующая программа демонстрирует динамику обслуживания очереди.
Программа 38
program bank;
uses crt;
type item = integer;
var qq:array[l..100] of item; i, t, v, L, R; integer;
р, x: real; st: string[10];
begin
(*начальное состояние очереди*)
qq[l]:=random(100); qq[2]:=random(100); qq[3]:=random(100);
L:=l; R:=3; р:0,6 v:=2; randomize; t:=0;
repeat
t:=t+l; x:=random; if x<p then begin R:=R+1;
qq[R]:=random(100);
end;
if (t mod v=0) then L:=L+1;
until keypressed or (R>100) ;
(*вывод состояния очереди на момент прерывания*) for i:=L to R
do writeln(qq(i]);
readin;
end.
