Особенность языка Паскаль

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

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

На следующем уроке мы рассмотрим основные алгоритмы, которые используются при обработке данных, хранящихся в массиве.

Действия над элементами массива

После объявления массива каждый его элемент можно обработать, указав идентификатор (имя) массива и индекс элемента в квадратных скобках. Например, запись Mas[2], Vector[10] позволяет обратиться ко второму элементу массива Mas и десятому элементу массива Vector.

Индексированные элементы массива называются индексированными переменными и могут быть использованы так же, как и простые переменные. Например, они могут находиться в выражениях в качестве операндов, использоваться в операторах for, while, repeat, входить в качестве параметров в операторы Read, Readin, Write, Writeln; им можно присваивать любые значения, соответствующие их типу.

Рассмотрим типичные ситуации, возникающие при работе с данными типа array. Для этого опишем три массива и четыре вспомогательные переменные:

Var

A,D :array[l.,4] ofreal;

В : array[1..10,1..15] of integer;

I, J, К : integer;

S :real;

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

Инициализация элементов одномерного массива А:

for I := 1 to 4 do

A[I] := 0;

Ввод-вывод элементов массива

Паскаль не имеет средств ввода-вывода элементов массива сразу, поэтому ввод и вывод значений производится поэлементно. Значения элементам массива можно присвоить с помощью оператора присваивания, как показано в примере инициализации, однако чаще всего они вводятся с экрана с помощью оператора Read или Readln с использованием оператора организации цикла for:

Ввод элементов одномерного массива А:

for I:=l to 4 do

Readln(A[I]) ;

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

Read(A[3]);

вводится значение третьего элемента массива А.

Вывод значений элементов массива выполняется аналогичным образом, но используются операторы Write или Writeln:

Вывод элементов одномерного массива А:

for I := I to 4 do

Writeln (A[I]);

Копированием массивов называется присваивание значений всех элементов одного массива всем соответствующим элементам другого массива. Копирование можно выполнить одним оператором присваивания, например А:=D; или с помощью оператора for:

for I := 1 to 4 do

A[I] := D[I];

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

Иногда требуется осуществить поиск в массиве каких-либо элементов, удовлетворяющих некоторым известным условиям. Пусть, например, надо выяснить, сколько элементов массива А имеют нулевое значение.

К := 0;

for I := 1 to 4 do

if A[I] = 0 then К := К + 1;

После выполнения цикла переменная К будет содержать количество элементов массива А с нулевым значением.

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

Например, так запишется фрагмент программы, обменивающий значения первого и пятого элементов массива А:

Vs:= A[5]; {Vs - вспомогательная переменная}

А[5]:= А[1];

А[1]:= Vs;

11/12

Поиск — обработка некоторого множества данных с целью выявления подмножества данных, соответствующего критериям поиска.

Все алгоритмы поиска делятся на

· поиск в неупорядоченном множестве данных;

· поиск в упорядоченном множестве данных.

Упорядоченность – наличие отсортированного ключевого поля.

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

Цель сортировки — облегчить последующий поиск элементов в отсортированном множестве при обработке данных.

Все алгоритмы сортировки делятся на

· алгоритмы внутренней сортировки (сортировка массивов);

· алгоритмы внешней сортировки (сортировка файлов).

 

Сортировка массивов

Массивы обычно располагаются в оперативной памяти, для которой характерен быстрый произвольный доступ. Основным критерием, предъявляемым к алгоритмам сортировки массивов, является минимизация используемой оперативной памяти. Перестановки элементов нужно выполнять на том же месте оперативной памяти, где они находятся, и методы, которые пересылают элементы из массива A в массив B, не представляют интереса.

Методы сортировки массивов можно разбить на три класса:

· сортировка включениями;

· сортировка выбором;

· сортировка обменом.

 

Сортировка файлов

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

12.

В этой части мы посмотрим на пять основных алгоритмов сортировки данных в массиве. Начнем с самого простого — сортировки пузырьком — и закончим «быстрой сортировкой» (quicksort).

Для каждого алгоритма, кроме объяснения его работы, мы также укажем его сложность по памяти и времени в наихудшем, наилучшем и среднем случае.

Также смотрите другие материалы этой серии: бинарное дерево, стеки и очереди, динамический массив, связный список, оценка сложности алгоритма и множества.

Метод Swap

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

void Swap(T[] items, int left, int right){if (left != right) { T temp = items[left];items[left] = items[right];items[right] = temp;}}