Линейная сортировка (сортировка отбором)

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

Пример программы линейной сортировки:

const n = 10;

var

a: array[1..n] of integer;

i,j,m: integer;

begin

for i:= 1 to n do

begin

write('a[',i,']= ');

readln(a[i]);

end;

for i:= 1 to n - 1 do

for j:= i + 1 to n do

begin

if a[i] > a[j] then

begin

m:= a[i];

a[i]:= a[j];

a[j]:= m;

end;

for i:= 1 to n do

writeln(a[i]);

readln;

end.

Сортировка обменами (метод "пузырька")

При сортировке обменами организуется последовательный перебор массива A₁, A₂, A₃, …, A_N и сравнение значений двух соседних элементов на выполнение условия A_i< A_i_+1.При выполнении условия элементы меняются местами, и просмотр возобновляется с очередного элемента - A_i₊₁. По завершении цикла сравнений наибольший элемент массива придвигается на последнее место, а просмотр массива возобновляется с первого элемента при уменьшении на единицу количества просматриваемых элементов (до N-1 элемента), т.к. наибольший из оставшихся элементов после каждого просмотра будет оказываться в конце. Массив будет упорядочен до конца после просмотра, в котором участвуют только первый и второй элементы, следовательно, количество просмотров ограничено значением N-1.

program massor2;

var

j,i,m,n: integer;

a: array[1..10] of integer;

begin

readln(n);

for i:= 1 to n do

readln(a[i]);

for i:= 1 to n-1 do

begin

for j:= 1 to n-1 do

if a[j] > a[j+1] then

begin

m:= a[j];

a[j]:= a[j+1];

a[j+1]:= m;

end;

for i:= 1 to n do

writeln('***** ',a[i]:3);

readln;

end.

Лекция №11. Символьный и строковый типы данных

Для работы с текстом в ТР имеется два типа данных: char – литерный или символьный тип; string – строковый или стринговый тип.

Значением переменных символьного типа является один символ. Каждому символу соответствует код символа – целое число в диапазоне от 0 до 255. Из этого следует, что символьный тип – это порядковый тип, т.е. каждому символу соответствует целое число, лежащее в диапазоне от 0 до 255. Это первый момент, который нужно уяснить – все действия по обработке символов сводятся к действиям над целыми числами, расположенными строго по порядку.

Над данными символьного типа определены операции отношения:

=, <>, <, >, <=, >=, вырабатывающие результат логического типа.

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

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

- Chr(x) –возвращает значение символа по его коду;

Chr(129) à 'Б'.

- Ord(ch) – возвращает код заданного символа;

Ord('A') à 65.

- Pred(ch) – возвращает предыдущий символ;

Pred('Б') à 'А'.

- Succ(ch) – возвращает следующий символ;

Succ('Г') à 'Д'.

- Upcase(ch) – преобразует строчную букву в прописную.

Upcase('n') à 'N'. Обрабатывает буквы только латиницы.

Строки. Обработка строковых данных

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

Строка – это последовательность символов. Максимальное количество символов в строке (длина строки) может изменяться от 1 до 255. переменную строкового типа можно определить в разделе определения типов или в разделе объявления переменных.

Type

ИмяТипа = string [максимальная длина строки];

Var

Идентификатор1, Идентификатор2, …: ИмяТипа;

Или строковые переменные указываются только в разделе объявлений после слова VAR, например:

VAR

FIO: STRING[15];

STROK: STRING;

Если строковая константа используется в программе несколько раз, то ее целесообразно объявить в разделе констант, например:

CONST

STR = 'STROKA';

Если максимальная длина строки не указывается, то она равна 255 байт.

Строка в языке ТР трактуется, как массив символов. Для строки из n символов в памяти ПК отводится n+1байт, nбайтов для хранения символов строки, а один дополнительный байт – для значения текущей длины строки. Этот дополнительный байт имеет номер 0, соответственно первый символ строки имеет номер 1, второй – 2 и т.д.

Например, переменная strokтипа string[15]хранится в памяти таким образом:

Strok:= 'университет;

Номер байта

Его значение

Вся строка занимает 16 байтов, из них 2 байта остались незанятыми, т.к. реальная длина строки составляет 13 символов, это значение и хранится в нулевом байте строки. Незанятые байты составляют "хвост" строки, в котором может находиться любой "мусор", однако программа не будет обращаться к "хвосту", т.к. реальный размер строки ей известен.

Из этого примера становиться понятным, почему максимальная длина строки может быть равна 255 символам, т.к. для хранения длины строки отведен всего лишь один байт, а число 255 в двоичном представлении выглядит как восемь единиц, т.е. 1111 1111.

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

FIO[5]; STROK[24];

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

В отличие от массивов переменные строкового типа могут целиком участвовать в операторах ввода/вывода. Например:

Readln(st1); writeln(st2);

Строковые данные используются в строковых выражениях. Операндами строковых выражений могут быть строковые константы, переменные, встроенные функции для обработки строк. Над строковыми данными могут выполняться операции присваивания, сцепления, отношения.

Операция присваивания. При записи операции присваивания строка символов заключается с двух сторон в апострофы, например:

FIO:= 'Иванов И.И.';

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

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

READLN(STROK);

На клавиатуре набрать STROKA и нажать клавишу Enter.

Для исключения ошибок надо использовать для ввода оператор READLN, а не READ.

Операция сцепления.Операция сцепления применяется для объединения нескольких строк в одну результирующую строку. Для обозначения операции сцепления применяется знак '+'.

Пример:

STR1:= 'Студенты';

STR2:= 'университета';

STR:= STR1 + ' ' +STR2;

В результате получится Студенты университета'.

Операции отношения.Операции отношения осуществляют сравнение двух строковых операндов и имеют более низкий приоритет, чем операции сцепления. Сравнение строк производится слева направо до первого несовпадающего символа, и та строка считается большей, в которой первый несовпадающий символ имеет больший номер в кодовой таблице ПК. Результат выполнения операций отношения над строковыми операндами всегда имеет логический тип и принимает значение TRUE или FALSE.

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

program primer;

var

str1: string[6];

str2: string[8];

begin

str1:= 'stroka';

str2:= str1;

if str1 = str2 then

writeln('str1 равна str2')

else

writeln('str1 не равна str2');

end.

будет выведено Str1 равна Str2.

Необходимо учитывать, что одинаковые строчные (маленькие) и прописные (большие) буквы имеют разные номера в кодовой таблице ПК, поэтому они определяют разные значения строковых переменных. Так, если ST1:= 'abc', а ST2:= 'ABC', то строки ST1 и ST2 не равны.

Для обработки строковых переменных применяются процедуры и функции, которые специально предназначены для работы со строками. Для упрощения описания примем, что STR, STR1 и STR2 переменные типа STRING, а I, K – переменные типа INTEGER.

1. LENGTH(STR) – функция, которая вычисляет фактическое количество символов в строке.

2. COPY(STR,I,K) - функция, которая выделяет из строки STR подстроку длиной K, начиная с позиции I. Если I > LENGTH(STR), то результат будет пробел.

3. DELETE(STR,I,K) – процедура, которая удаляет из строки STR подстроку, начиная с позиции I, длиной K символов.

4. INSERT(STR1,STR2,I) –процедура, которая вставляет строкуSTR1в строку STR2, начиная с позиции I.

5. POS(STR1,STR2) – функция, которая определяет наименьший номер (позицию) символа в строке STR2, начиная с которого строка STR1входит в строку STR2.

6. STR(I,STR) – процедура, которая преобразует численное значение Iв строку STR.

Пример программы, использующей строковый тип данных: Ввести с клавиатуры n строк, каждая из которых содержит фамилию, имя и отчество уч-ся. Ввод каждой строки завершается нажатием клавиши Enter. Вывести список уч-ся в алфавитном порядке.

program fio;

var

i,n,j: integer;

st: string;

fios: array[1..30] of string;

begin

readln(n);

for i:= 1 to n do

readln(fios[i]);

for i:= 1 to n-1 do

for j:= 1 to n-1 do

begin

if fios[j] > fios[j+1] then

begin

st:= fios[j];

fios[j]:= fios[j+1];

fios[j+1]:= st;

end;

for i:= 1 to n do

writeln(fios[i]);

end.

Числа и строки

Часто возникает необходимость получить строковое представление числа и наоборот (например, получить строку '13' из числа 13). Для работы с числами и строками применяются две процедуры.

1. Str(N, St) − переводит числовое значение N в строковое и присваивает результат строке St, причем можно переводить как целые числа, так и вещественные.

Примеры

- Str(1234, St) − после выполнения St='1234';

- Str (452.567, St) − переводим вещественное число с фиксированной запятой, результат St='452.567';

- Str(4.52567е+2, St) − переводим вещественное число в экспоненциальной форме, результат St='4.52567e+2'.

2. Val(Str, N, К) − переводит строковое значение в числовое. Если данная строка действительно является записью числа (целого или вещественного), то значение К=0, а N − это искомое число, иначе К будет равно номеру первого символа, с которым процедура Val "не справилась".

Примеры

- Val('1234', n, k) - n=1234, k=0;

- Val('234.56', n, k) - n=234.56, k=0;

- Val('2.3456e+2', n, k) - n=2.3456e+2, k=0;

- Val('12-45', n, k) k=3, так как знак "−" в записи чисел может быть только на первом месте;

- Val('2,567m', n, k) k=2, так как разделительным знаком между целой и дробной частями является точка, а не запятая;

- Val ('5.87с-5') k=5, так как символ 'с' не должен встречаться в записи вещественного или целого числа.

Пример программы на закрепление темы:

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

uses crt;

var

c: string;

d,k,m: integer;

begin

writeln('Введите год поступления);

readln(d);

writeln('Введите текущий год');

readln(k);

writeln('Введите текущий месяц');

readln(m);

case m of