На практике многие задачи требуют упорядочивания данных, т.к. упорядоченных наборах данных проще и быстрее искать нужную информацию. В теоретической и прикладной информатике, большое внимание уделяется алгоритмам упорядочивания или алгоритмам сортировки данных.
Пусть дан вектор s[1..n].
Вектор отсортирован по возрастанию, если для любого i=1,...,n-1 выполняется условие s[i]<s[i+1].
Вектор отсортирован по не убыванию, если для любого i=1,...,n-1 выполняется условие s[i]<=s[i+1].
Вектор отсортирован по убыванию, если для любого i=1,...,n-1 выполняется условие s[i]>s[i+1].
Вектор отсортирован по не возрастанию, если для любого i=1,...,n-1 выполняется условие s[i]>=s[i+1].
Отсортировать вектор значит переставить его элементы так, чтобы для всех элементов вектора выполнялось заданное условие.
Заметим, что отсортировать строго по возрастанию или убыванию можно только векторы, в которых нет элементов с равными значениями.
Для определенности будем сортировать вектор по не убыванию.
Алгоритм сортировки "пузырек” (bubble-sort)
1. Вектор просматривается слева направо и сравниваются соседние элементы. Если s[i] > s[i+1], то элементы меняются местами.
2. Просмотры продолжаются до тех пор, пока сохраняется неупорядоченность, т.е. находится по крайней мере одна пара, такая что s[i]> s[i+1] для некоторого 1<=i<=n-1.
Просмотр 1.
13 6 8 15 4 13 <-> 6
6 13 8 15 4 13 <-> 8
6 8 13 15 4 15 <-> 4
6 8 13 4 15
Просмотр 2.
6 8 13 4 15 13 <-> 4
6 8 4 13 15
Просмотр 3.
6 8 4 13 15 8 <-> 4
6 4 8 13 15
Просмотр 4.
6 4 8 13 15 6 <-> 4
4 6 8 13 15 Вектор упорядочен!
Сортируется по не убыванию вектор a[1..n].
Sort – переменная, которая получит значение true, когда вектор будет отсортирован.
sort:=false;
while not sort do
begin sort:=true;
for i:=1 TO n-1 do
//Если упорядоченность нарушена, элементы меняются
if a[i]>a[i+1] then
begin sort:=false;h:=a[i];a[i]:=a[i+1];a[i+1]:=h end;
end;//while
Структура данных матрица
Можно объявлять и многомерные массивы, т.е. массивы, элементами которых являются массивы. Например, двумерный массив можно объявить таким образом:
Var A2: array[1..10] of array[1..3] of integer;
Этот оператор описывает двумерный массив, который можно представить себе как таблицу, состоящую из 10 строк и 3 столбцов. То же самое можно объявить более компактно:
Var A2: array[1..10,1..3] of integer;
Обычно используется именно такая форма объявления многомерных массивов. Как и в одномерных массивах, элементы могут иметь любой тип, и индексы тоже могут иметь любой ограниченный тип. Доступ к значениям элементов многомерного массива обеспечивается через индексы, перечисляемые через запятую. Например, А2[4,3] — значение элемента, лежащего на пересечении четвертой строки и третьего столбца.
Функции
Функция — это подпрограмма, т. е. последовательность инструкций, имеющая имя. Процесс перехода к инструкциям функции называется вызовом функции или обращением к функции. Процесс перехода от инструкций функции к инструкциям программы, вызвавшей функцию, называется возвратом из функции.
В общем виде инструкция обращения к функции выглядит так:
Переменная := Функция (Параметры) ;
где: переменная — имя переменной, которой надо присвоить значение, вычисляемое функцией;
Функция — имя функции, значение которой надо присвоить переменной;
Параметры — список формальных параметров, которые применяются для вычисления значения функции. В качестве параметров обычно используют переменные или константы.
Следует обратить внимание на то, что: каждая функция возвращает значение определенного типа, поэтому тип переменной, которой присваивается значение функции, должен соответствовать типу функции; тип и количество параметров для каждой конкретной функции строго определены.
Объявление функции
Объявление функции в общем виде выглядит так:
function Имя (параметр1 : тип1, ..., параметрК : типК) : Тип; var
// здесь объявления локальных переменных begin
// здесь инструкции функции
Имя := Выражение; end;
где:
function — зарезервированное слово языка Delphi, обозначающее, что далее следуют инструкции, реализующие функцию программиста; имя — имя функции. Используется для перехода из программы к инструкциям функции; параметр — это переменная, значение которой используется для вычисления значения функции. Отличие параметра от обычной переменной состоит в том, что он объявляется не в разделе объявления переменных, который начинается словом var, а в заголовке функции. Конкретное значение параметр получает во время работы программы в результате вызова функции из основной программы; тип — тип значения, которое функция возвращает в вызвавшую ее программу.
Следует обратить внимание, что последовательность инструкций, реализующих функцию, завершается инструкцией, которая присваивает значение имени функции. Тип выражения, определяющего значение функции, должен совпадать с типом функции, указанным в ее объявлении.
Листинг 6.3. Примеры функций
// проверяет, является ли символ допустимым
// во время ввода целого числа
function Islnt(ch : char) : Boolean;
begin
if (ch >= '0'} and (ch <= '9') // цифры
or (ch = 113) // клавиша <Enter>
or (ch = #8) // клавиша <Backspace>
then Islnt := True // символ допустим
else Islnt := False; // недопустимый символ
end;
// проверяет, является ли символ допустимым
// во время ввода дробного числа
function IsFloat(ch : char; st: string) : Boolean;
begin
if (ch >= '0') and (ch <= '9') // цифры
or (ch = #13) // клавиша <Enter>
or (ch = #8) // клавиша <Backspace>
then
begin
IsFloat := True; // символ верный
Exit; // выход из функции
end;
case ch of
'-': if Length(st) = 0
then IsFloat := True; ',':
if (Pos(',',st) = 0)
and (st[Length(st)]'>= '0') and (st[Length(st)] <= '9')
then // разделитель можно ввести только после цифры // и если он еще
не введен
IsFloat := True; else // остальные символы запрещены