Алгоритмический язык Паскаль

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

Для последовательного представления можно использовать одномерный массив А[1], А[2],..., А[N], причем длина N этого массива выбирается с таким запасом, чтобы длина очереди не превышала N.

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

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

Пусть I - индекс элемента массива, хранящего "голову" очереди, а J - индекс первого свободного элемента массива, куда поступает новый элемент очереди ("хвост"). Тогда выборка очередного элемента очереди для обработки сводится к выполнению операций:

X:=А[I]; I:=I+1.

После этого индекс I указывает на следующий элемент очереди, т.е. "головой" ее становится следующий по порядку элемент. Запись нового элемента Y в очередь сводится к выполнению операций:

А[J]:=Y; J:=J+1.

Теперь индекс J снова указывает на первый свободный элемент массива.

Элементы очереди могут поступать и обрабатываться неравномерно, поэтому длина ее будет изменяться. В частности, возможен случай, когда очередь окажется пустой. Признаком этого может служить равенство I = J после чтения головного элемента очереди.

В процессе обработки очереди ее элементы будут смещаться к концу массива, т.к. J увеличивается после каждой записи в очередь. Поэтому возможен случай J > N после записи в очередь очередного элемента. При этом надо сместить очередь в начало массива, т.е. положить I = 1 и последовательно переписать все элементы очереди в элементы массива, начиная с А[1].

Чтобы избежать этой работы, можно замкнуть массив (очередь) по кольцу, т.е. элементом, следующим за последним элементом массива, считать его первый элемент:

При такой закольцовке просто определить переполнение очереди. Признаком этого факта является условие J = I, т.е. признак того, что "хвост" совпал с "головою" очереди.

Связанное представление очереди позволяет разбрасывать ее элементы по памяти. Здесь необходимо вместе с каждым элементом хранить указатель на местоположение следующего. Помимо этих двух указателей есть еще два дополнительных: указатели на начало и конец очереди. Последний служит для облегчения включения элементов в конец очереди.

Стек - это структура данных, организованная по принципу "последним пришел - первым ушел". В стеке, в отличие от очереди, доступен только один элемент, называемый вершиной стека. При записи в стек очередной элемент заносится в его вершину, а остальные продвигаются вниз без изменения порядка. При выборке из стека удаляется элемент из его вершины, а все остальные сдвигаются вверх без изменения порядка, так что в вершину попадает элемент, поступивший в стек предпоследним. Пример для аналогии: стопка книг на столе, обойма (магазин) автомата.

Для стеков используют два представления - ПОСЛЕДОВАТЕЛЬНОЕ и СВЯЗАННОЕ.

ПОСЛЕДОВАТЕЛЬНОЕ представление требует резервирования блока памяти - одномерного массива А[1], А[2],..., А[N] - по тому же принципу, что и очередь. Величина N должна быть такой, чтобы стек мог расти до своего максимального размера без переполнения блока. Первый элемент блока - это указатель вершины стека, который можно задать с помощью индекса I. При записи в стек указатель вершины стека будет сдвигаться в сторону конца массива, при чтении из стека указатель вершины будет перемещаться в сторону начала массива. Значение I = 0 перед чтением из стека служит признаком его пустоты, а значение I = N перед записью в стек - признаком переполненности стека.

Представление стека в памяти:

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

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

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

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

1. Представление с одной связью: каждый элемент списка соединен со следующим; имеется указатель на первый элемент, который обычно находится в отдельной ячейке, называемой головой списка. Это представление идентично представлению очереди, рассмотренное нами ранее:

2. Представление с двумя связями: каждый элемент списка соединен с последующим и предыдущим; в голове списка имеются указатели и на первый, и на последний элементы. Такие двусвязные списки принято называть деками.

СХЕМА ПРЕДСТАВЛЕНИЯ ДВУХСВЯЗНОГО СПИСКА

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

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

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

Ниже следуют фрагменты программ на Паскале записи и чтения элементов в очереди и стеке.

13. СТРУКТУРЫ ПРЯМОГО ДОСТУПА. СПОСОБЫ СОРТИРОВКИ МАССИВА

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

При решении ее возможны два подхода: использование промежуточного (вспомогательного) массива и сортировка внутри самого массива.

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

Выделяют 3 основных способа сортировки:

1. Прямое включение.

2. Прямой выбор.

3. Прямой обмен.

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

13.1 Прямое включение

Суть этого способа такова: в массиве берется i-й элемент и включается (вставляется) на свое место между 1-м и i-м элементами. Эта идея может быть выражена в виде следующего цикла:

FOR I:=2 TO N DO

BEGIN X:=A[I];

<включить X на свое место между A[1] и A[I]> END.

Из указанного видно, что на каждом шаге i все элементы с 1-го до (I-1)-го уже упорядочены, следовательно, при I = N произойдет последняя сортировка и N-й элемент встанет на свое место. Алгоритм должен быть таким, что если I-й элемент стоит в ряду, т.е. не нарушает порядка, то никаких действий совершать не надо, а следует перейти к I+1-му элементу.

Например, рассмотрим сортировку следующего массива:

Здесь все элементы до четвертого уже упорядочены и сортировка должна произойти при I = 4. Суть метода состоит в том, что среди элементов с 1-го по 4-й ищется такой, который меньше четвертого, равного 1. В нашем случае этим элементом является первый, равный -3. В ходе поиска четвертый элемент 1 запоминается в специальной переменной X, а все элементы циклически сдвигаются на одну позицию вправо:

1-й шаг: 1<4? - да => сдвиг

2-й шаг: 1<2? - да => сдвиг

3-й шаг: 1<-3? - нет

На третьем шаге сдвига не происходит и после него запомненный элемент ставится на свое место, т.е. на место второго элемента ставится четвертый из исходного массива. Поиск и сдвиг идут по циклу WHILE, в котором в качестве условия берется сравнение X < А[I-1].

Продолжая наш пример, заметим, что на пятом шаге никаких действий происходить не будет, а на шестом элемент А[6]=3 должен пойти на четвертое место, сдвигая пятый элемент на шестое место, а четвертый элемент - на пятое место:

3<6? - да => сдвиг

3<4? - да => сдвиг

3<2? - нет=>

Прежде чем переходить к самой программе, заметим, что если I-й элемент должен передвинуться на 1-е место, то в нашем алгоритме для окончания процесса сдвига нужно иметь элемент слева от А[1] для сравнения (барьер). Таким элементом является А[0]. Отсюда заключаем, что в цикле FOR от 2 до N нужно для каждого шага I предусмотреть засылку в А[0] сортируемого элемента.

procedure PRVKLUCH (var MM:MAS);

var I,J,X: integer;

begin

¦ for I:= 2 to N do

¦ begin

¦ ¦ X:=MM[I]; MM[0]:=X; J:=I;

¦ ¦ while X < MM[J-1] do

¦ ¦ begin

¦ ¦ ¦ MM[J]:=MM[J-1]; J:=J-1;

¦ ¦ end;

¦ ¦ MM[J]:=X;

¦ end;

end.

Из этой процедуры видно, что выход из нее происходит тогда, когда (J-1)-й элемент становится меньше I-го элемента. Слева от I-го уже не может быть меньшего элемента, т.к. на каждом шаге все элементы до него уже отсортированы ранее в цикле FOR.

13.2 Прямой выбор

Суть метода состоит в том, что среди всех элементов массива выбирается наименьший и ставится на первое место, а элемент, занимавший первое место, перемещается на место наименьшего. Затем среди оставшихся элементов от второго до N-го проводится та же операция, а именно: среди элементов массива от второго до N-го выбирается наименьший и перемещается на второе место, а элемент, стоящий на втором месте, занимает место наименьшего.

Эта идея реализуется в виде вложенных циклов: внешний - по I от 1 до N-1; внутренний - по J от I+1 до N.

ОБЩАЯ СХЕМА ПРОГРАММЫ:

for I:=1 to N-1 do

begin

¦ {Запоминание индекса и самого I-го элемента}

¦ for J:=I+1 to N do

¦ begin

¦ {Поиск минимального элемента от I+1 до N}

¦ end;

¦ {Перестановка I-го и минимального элементов}

end.

ОБЩИЙ ВИД ПРОГРАММЫ:

procedure SELECTION (var MM:MAS);

var I,J,K,X: integer;

begin

¦ for I:= 1 to N-1 do

¦ begin

¦ ¦ { Это тело внешнего цикла }

¦ ¦ K:= I; X:= MM[I];

¦ ¦ { Внутренний цикл - поиск MIN элемента }

¦ ¦ for J:= I+1 to N do

¦ ¦ if X > MM[J] then

¦ ¦ begin

¦ ¦ ¦ { Запоминание номера и значения

¦ ¦ ¦ минимального элемента }

¦ ¦ ¦ X:= MM[J];

¦ ¦ ¦ K:= J;

¦ ¦ end;

¦ ¦ { Минимальный и I-й элементы меняются местами}

¦ ¦ MM[K]:= MM[I]; MM[I]:= X;

¦ end;

end.

Проследим работу этой программы на следующем примере:

I=0

 исходный массив

I=1

1-й шаг: ничего не происходит, т.к. минимальный элемент на своем месте

I=2

2-й шаг: 2-й и 4-й поменялись местами

I=3

3-й шаг: 3-й и 4-й поменялись местами

I=4

4-й шаг: 4-й и 6-й поменялись местами

I=5

5-й шаг: 5-й и 6-й поменялись местами

Всего N-1=5 шагов. Часть из них результативна (2,3,4,5), а первый шаг никаких перестановок не производит. Отметим, однако, что даже при нерезультативных ходах все циклы работают до конца и за время сортировки внутренний цикл выполнится N(N-1)/2 раз.

13.3 Прямой обмен (метод пузырька, всплытие)

Суть его заключается в том, что в отличие от первых двух методов, где просмотр массива шел по увеличению индекса I, т.е. от начала массива к концу, здесь производится проход от конца массива к началу до I-го элемента, и каждый раз, если А[J-1] > А[J], они меняются местами.

В этом методе также есть два вложенных цикла: внешний цикл поидет от 2 до N, а внутренний по J - от N до I:

for I:= 2 to N do

for J:= N downto I do

{ Обмен местами (всплытие) более легкого элемента }

end;

end.

ОБЩИЙ ВИД ПРОГРАММЫ:

procedure BUBLESORT (var MM: MAS);

var I,J,X: integer;

begin

¦ for I:=2 to N do

¦ for J:= N downto I do

¦ if MM[J-1] > MM[J] then

¦ begin

¦ ¦ X:= MM[J-1];

¦ ¦ MM[J-1]:= MM[J];

¦ ¦ MM[J]:= X

end;

end.

Работу программы иллюстрирует пример с тем же исходным массивом, что и ранее:

Все остальные обработки при I = 4, 5, 6 идут впустую, т.к. массив уже упорядочен. В других ситуациях может случиться так, что сортировка закончится только на последнем цикле.

13.4 Сравнительная характеристика методов

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

1. Массив уже отсортирован (но мы не знаем об этом).

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

2. Исходный массив упорядочен по убыванию.

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

ПРИМЕР:

3. Массив дан случайным образом.

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

13.5 Улучшенный метод сортировки. QUICK - сортировка

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

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

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

1-ый - левый элемент: L,

2-ой - правый элемент: R.

На начало процедуры эти параметры должны получить значения:

L = 1; R = N.

В процедуре используется цикл REPEAT по сближению левой и правой границ.

procedure QUICKSORT (L, R: integer; var M: MAS);

var I,J,W,X: integer;

begin

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11