Сортировка данных строкового типа методом перестановок с использованием процедур и функций

Рисунок 1.13 - Окно работающей консольной программы

     5 Нажмите в этом окне клавишу Enter – консольное приложение завершится.

     Теперь, когда есть основа для проверки изучаемого материала, рассмотрим операторы консольного  ввода-вывода. К ним относятся Write, Writeln, Read, Readln.

     Консольный  вывод.

     Инструкции Write и Writeln служат для вывода чисел, символов, строк и булевских значений на экран. Они имеют следующий формат:

• Write (Y1, Y2, ... ,Yn);
• Writeln (Y1, Y2, ... , Yn), где Y1, Y2,..., Yn – константы, переменные и результаты выражений. Инструкция Writeln аналогична Write, но после своего выполнения переводит курсор в начало следующей строки.

     Если  инструкции Write и Writeln записаны без параметров:

• Write;
• Writeln, то это вызывает пропуск на экране соответственно одной позиции и одной строки.

     Инструкции  ввода обеспечивают ввод числовых данных, символов, строк для последующей  обработки в программе. Формат их прост:

     Read(X1, X2, ... ,Xn);

     Readln(X1, X2, ... ,Xn), где X1, X2, ..., Xn – переменные, для которых осуществляется ввод значений

     Пример:

     

     Если  одна инструкция вводит несколько значений:

     Read(A, B), то все эти значения надо набрать на клавиатуре, отделяя одно значение от другого пробелом, и нажать клавишу Enter.

     Если  вводится одно значение:

     Read(C), то его следует набрать и нажать клавишу Enter. С этого момента программа может обрабатывать введенное значение в соответствии с алгоритмом решаемой задачи.

     Инструкция Readln отличается от Read только одним свойством: каждое выполнение инструкции Readln переводит  курсор в начало новой строки, а  после выполнения Read курсор остается в той же строке, где и был (потренеруйтесь – и вы быстро поймете разницу).

     В простейшем случае в инструкциях Read и Readln параметры можно вообще не указывать:

     Read;

     Readln;

     Оба этих оператора останавливают выполнение программы до нажатия клавиши Enter.

     1.6 Компиляция и выполнение

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

     Для ввода значений переменных с клавиатуры в программе можно использовать два оператора:

• read (имя1, имя2, имя3, …);
• readln (имя1, имя2, имя3, …).

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

     1.7 Массивы на языке  Delphi

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

     Объявление массива:

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

     Имя: array [нижний_индекс. .верхний_индекс] of тип

     где:

     имя — имя массива;

     array — зарезервированное слово языка  Delphi, обозначающее, что объявляемое имя является именем массива;

     нижний_индекс и верхний_индекс — целые константы, определяющие диапазон изменения индекса элементов массива и, неявно, количество элементов (размер) массива;

     тип — тип элементов массива.

     Примеры объявления массивов:

     name: array[1..30] of string[25];

     При объявлении массива удобно использовать именованные константы. Именованная  константа объявляется в разделе  объявления констант, который обычно располагают перед разделом объявления переменных. Начинается раздел объявления констант словом const. В инструкции объявления именованной константы указывают  имя константы и ее значение, которое  отделяется от имени символом "равно". Например, чтобы объявить именованную  константу нв, значение которой равно 10, в раздел const надо записать инструкцию: нв=ю. После объявления именованной  константы ее можно использовать в программе как обычную числовую или символьную константу. Ниже в  качестве примера приведено объявление массива названий команд-участниц чемпионата по футболу, в котором используются именованные константы.

     const

     NT = 18; // число команд

     SN = 25; // предельная длина названия команды var

     team: array[1..NT] of string[SN];

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

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

     Обратите  внимание, что количество элементов  списка инициализации должно соответствовать  размерности массива. Если это будет  не так, то компилятор выведет сообщения  об ошибке: Number of elements differs from declaration (количество элементов не соответствует указанному в объявлении).

     При попытке инициализировать локальный  массив компилятор выводит сообщение  об ошибке: Cannot initialize local variables (локальная  переменная не может быть инициализирована). Локальный массив можно инициализировать только во время работы программы, например, так:

     For i := 1 to 10 do

     a [i]:= 0;

     Операции с массивами

     Типичными операциями при работе с массивами  являются:

1. вывод массива
2. ввод массива
3. поиск максимального или минимального элемента массива
4. поиск заданного элемента массива.

     1.8 Алгоритм ввода массива

     Для ввода значений переменных с клавиатуры в программе можно использовать два оператора:

• read (имя1, имя2, имя3, …);
• readln (имя1, имя2, имя3, …).

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

     1.9 Алгоритм вывода массива

     Для вывода информации на экран используются операторы:

• write(выражение1, выражение2, выражение3, …)
• writeln(выражение1, выражение2, выражение3, …).

     В качестве выражений могут выступать:

1. Имена переменных. В этом случае на экран будет выведено значение этой переменной
2. Арифметические выражения (желательно заключать в скобки). На экран выведется значение выражения
3. Произвольная текстовая строка (обязательно заключать в апострофы).

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

     1.10 Поиск минимального элемента массива

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

     1.11 Алгоритм сортировки

     Сортировка  перестановкой (англ. Exchange selection) – метод  сортировки, при котором все строки в списке устанавливаются в определенный порядок, путем перестановки двух соседних строк.

     Сортировка  перестановками состоит в следующем:

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

     1.12 Реализация алгоритмов с использованием подпрограмм

     Описание  подпрограммы состоит из трех частей: заголовка подпрограммы, локального описания и тела подпрограммы. Заголовок используется, чтобы явно ввести в программу новую подпрограмму и обозначить начало ее описания. Локальные описания представляют собой набор описаний типов, переменных, констант и других подпрограмм, которые действуют только в рамках данной подпрограммы. Тело подпрограммы – это логический блок begin/end, содержащий операторы и команды Паскаля и реализующий нужную логику работы.

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

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

     1.13 Алгоритм решения задачи

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

     На  первом шаге находим минимальный  элемент массива и меняем его  местами с первым элементом массива. Остаются неупорядоченными n-1 элемент. Проводим поиск минимального элемента среди элементов со 2 по n-1 и делаем перестановку.

     Повторяем процедуру поиска минимального элемента среди оставшихся неупорядоченных  элементов многократно.  Повторение реализуем с помощью цикла со счетчиком, максимальное значение которого составляет n-1. В результате массив сортируется по возрастанию.

 

      2 Разработка программы

     2.1 Создание консольного  приложения

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

     Выберем в диалоговом окне New items (Создать объект) категорию Delphi for. NET Projectsе (проекты Delphi для NET) и дважды щелкнем на значке Console Application (Консольное приложение). Система Delphi создаст новый проект, откроет его и переключится в редактор исходного текста создаваемой программы(рисунок 2.1).

     

Рисунок – 2.1 – Окно среды Delphi для создания нового проекта