Пример сортировки простым выбором
| Номер элемента | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
 Исходная последовательность
| 72 | 14 | 6 | 98 | 17 | 51 | 25 | 33 |
 После выбора среди 8 элементов
| 6 | 14 | 72 | 98 | 17 | 51 | 25 | 33 |
| 7 элементов | 6 | 14 | 72 | 98 | 17 | 51 | 25 | 33 |
 6 элементов
| 6 | 14 | 17 | 98 | 72 | 51 | 25 | 33 |
 5 элементов
| 6 | 14 | 17 | 25 | 72 | 51 | 98 | 33 |
 4 элементов
| 6 | 14 | 17 | 25 | 33 | 51 | 98 | 72 |
| 3 элементов | 6 | 14 | 17 | 25 | 33 | 51 | 98 | 72 |
| 2 элементов | 6 | 14 | 17 | 25 | 33 | 51 | 72 | 98 |
| Упорядоченная последовательность | 6 | 14 | 17 | 25 | 33 | 51 | 72 | 98 |
4.1.3. Строковый тип данных
Строки в Паскале – это данные типа string. Они используются для хранения последовательностей символов. В Паскале длина стандартной строки ограничена 255 символами. Под каждый символ отводится по одному байту, в котором хранится код символа. Кроме того, каждая строка содержит еще дополнительный байт, в котором хранится длина строки. Если заранее известно, что длина строки будет меньше 255 символов, то программист может сам задать максимальную длину строки.
Примеры описания строк:
type str_type = string[12];
const n = 50;
var s1: string;
s2, s3: str_type;
s4: string[n];
s5, s6, s7: string[7];
В Паскале существует три типа строк:
· стандартные (string);
· определяемые программистом на основе string;
· строки в динамической памяти
Длина строки хранится в первом байте, индекс которого равен 0.
Строку можно рассматривать как массив с элементами типа char, но они отличаются от массивов тем, что с ними можно выполнять операции как над единым объектом.
|
|
|
К отдельному символу строки можно обращаться как к элементу массива символов, например s1[3]. Символ строки совместим с типом char, их можно использовать в выражениях одновременно, например:
s1[3] := 'h'; writeln (s2[3] + 'r');
Операции над строками
1. Присваивание. Строки можно присваивать друг другу. Если максимальная длина переменной слева меньше длины присваиваемой строки, то лишние символы справа отбрасываются.
s1 := 'this is text';
s2 := s1;
2. Склеивание. Строки можно объединять с помощью операции конкатенации, которая обозначается знаком +.
s1 := 'John'; s2 := 'Black'; s1 := s1 + ' ' + s2;
3. Сравнение. Строки можно сравнивать друг с другом с помощью операций отношения. При сравнении строки рассматриваются посимвольно слева направо, при этом сравниваются коды соответствующих пар символов. Строки равны, если они имеют одинаковую длину и посимвольно эквивалентны. В строках разной длины существующий символ всегда больше соответствующего ему отсутствующего символа. Меньшей будет та строка, у которой меньше код первого несовпадающего символа (вне зависимости от максимальных и текущих длин сравниваемых строк).
'Balkon'<'balkon'(Ord(' B' )<Ord('b'));
|
|
|
'balkon'>'balken'(Ord('o')>0rd('e')) ;
'balkon'>'balk' (длина первой строки больше);
'кошка '>'кошка' (длина первой строки больше);
'кот'='кот' (равны по длине и совпадают посимвольно).
Элементы строки нумеруются с единицы, т.к. в каждой строковой переменной имеется элемент с номером 0, в котором в виде символа хранится длина текущей строки. Чтобы узнать текущую длину, достаточно применить функцию ord к нулевому элементу строки. Например: writeln(ord(st[0])).
Нулевой элемент строковой переменной можно корректировать. При этом будет изменяться текущая длина строки. Например, выражение str[0]:=#50 устанавливает текущую длину равной 50.
Процедуры и функции для работы со строками
При работе со строками, как правило, возникает необходимость выполнять их копирование, вставку, удаление или поиск. Для эффективной реализации этих действий в Паскале предусмотрены стандартные процедуры и функции.
Функция Concat (s1, s2, ..., sn) возвращает строку, являющуюся слиянием строк s1, s2, ..., sn.
Функция Copy (s, start, len) возвращает подстроку длиной len, начинающуюся с позиции start строки s.
Процедура Delete (s, start, len) удаляет из строки s, начиная с позиции start, подстроку длиной len.
Процедура Insert (subs, s, start) вставляет в строку s подстроку subs, начиная с позиции start.
|
|
|
Функция Length (s) возвращает фактическую длину строки s, результат имеет тип byte.
Функция Pos (subs, s) ищет вхождение подстроки subs в строку s и возвращает номер первого символа subs в s или нуль, если subs не содержится в s.
Процедуры преобразования типов
Процедура Str (x, s) преобразует числовое значение x в строку s, при этом для x может быть задан формат, как в процедурах вывода write и writeln. Например: x := 123; s := str(x:6,s). Результат: s = ' 123'.
Процедура Val (s, x, errcode) преобразует строку s в значение числовой переменной x, при этом строка s должна содержать символьное представление числа. В случае успешного преобразования переменная errcode равна нулю. Если же обнаружена ошибка, то errcode будет содержать номер позиции первого ошибочного символа, а значение x не определено.
Пример 1. Сколько раз в строке встречается символ ‘a’.
Program Example_1;
Var i, k:Byte; st:String
Begin
k:=0;
For i:=1 To Length(st) Do If st[i]='a' Then Inc(k);
Write(‘Количество сиволов А =’, k);
End.
Пример 2. Дана строка, состоящая из нескольких слов, между словами один пробел, в конце строки − точка. Подсчитать количество слов и вывести на экран только те из них, которые начинаются с буквы 'а' (слов не больше 30).
Решение
Разобьем предложение на отдельные слова и каждое будем хранить как элемент массива строк.
|
|
|
Program Example_2;
Const n=30;
Type Myarray_Str=Array [1..n] Of String;
Var A: Myarray_Str; str: String[255]; k: Byte;
Procedure Init(Var b: Myarray_Str);
Var i: Integer;
Begin
k:=1; {Пока не встретится пробел, формируем очередное слово k, прибавляя по одной букве}
For i:=1 To Length(str)-1 Do
If str[i]<>' ' Then b[k]:=b[k]+str[i]
Else
{Если это не последний символ, то увеличиваем счетчик слов и начинаем формировать очередное слово}
If i<>Length(str)-1 Then Begin Inc(k); b[k]:=' ' End;
End;
Begin
Writeln('Введите предложение'); Readln(str); Init(A);
Writeln('Всего слов: ',k); {Просматриваем все слова, если первый символ очередного слова равен букве 'а', то выводим его}
For i:=1 To k Do If A[i][1]='a' Then Write(A[i],' ');
End.
4.1.4. Комбинированный тип данных - записи
Паскаль характерен тем, что имеет хорошо развитую концепцию типов данных, позволяющую создавать достаточно сложные структуры, объединяющие данные различных типов.
В частности, в Паскале существует возможность объединения компонент, принадлежащих разным произвольным типам, в один составной или комбинированный тип. Это так называемый комбинированный тип называется записью (RECORD). Записи часто используются при создании различного рода информационных систем.
Примером может служить информационная система отдела кадров. Она содержит сведения об анкетных данных сотрудников: фамилия, имя, отчество, дата рождения, домашний адрес, номер телефона (рабочий и домашний), образование, специальность и т.д. Эти сведения могут быть описаны с помощью следующих типов данных:
- телефоны, дата рождения – целые числа;
- остальные данные – символьные строки.
Запись − это структурированный тип, описывающий набор данных разных типов. Составляющие запись объекты называются ее полями. Каждое поле имеет уникальное (в пределах записи) имя. Чтобы описать запись, необходимо указать ее имя, имена объектов, составляющих запись, и их типы. Общий вид описания записи следующий:
Type <имя записи>=Record
<поле 1>:<тип 1>;
<поле 2>:<тип 2>;
…
<поле n>:<тип n>
End;
Например описать строку в ведомости хранящей успеваемость студента в сессию можно следующим образом:
Type pupil=Record
fam: String[15]; { поле фамилии студента }
b1, b2, b3, b4, b5: 2..5; {поля баллов по дисциплинам}
sb: Real{поле среднего балла}
End;
Переменная типа pupil будет хранить структуру, содержащую информацию об одном студенте.
Чтобы хранить в памяти ЭВМ информацию обо всех 25 студентах группы, необходимо ввести массив gruppa, представляющий массив записей: Var gruppa : Array [1..25] Of pupil .
Примечания.
1. Имена полей, составляющих запись, не должны повторяться.
2. Каждое поле записи может иметь любой тип (кроме файлового), в частности, оно может быть снова записью.
Доступ к полям записи можно осуществить двумя способами:
1 способ. С указанием имени переменной и имени поля. Например, gruppa[2].fam, gruppa[3].sb, gruppa[1].b4. Ввод фамилий и оценок учащихся, то есть элементов массива gruppa, можно записать так:
For i:=1 To 25 Do
Begin Readln(gruppa[i].fam);
Readln(gruppa[i].b1);
Readln(gruppa[i].b2);
Readln(gruppa[i].b3);
Readln(gruppa[i].b4);
Readln(gruppa[i].b5);
End;
2 способ. С использованием оператора присоединения. Имеется возможность осуществлять доступ к полям записи таким образом, как если бы они были простыми переменными. Общий вид оператора присоединения:
With <имя записи> Do <оператор>;
Внутри оператора присоединения к компонентам записи можно обращаться только с помощью имени соответствующего поля.
For i:=1 To 25 Do With klass [i] Do
Begin
Readln(fam); Readln (b1, b2, b3, b4, b5);
End;
4.1.5. Множества
Кроме массивов и записей в Паскале имеется еще одна фундаментальная структура данных: множество. В математике это одно из основных понятий. Необходимость введения множественного типа возникает при решении ряда задач, в которых упорядоченность элементов массива в соответствии с их местоположением (индексом) является излишне строгим требованием к структуре данного.
Пусть, например, выигрышные номера в игре "3 из 15" – 3, 7, 11. При этом неважно, в каком порядке назовет их игрок: 7, 11, 3 или 11, 3, 7. В любом случае они будут угаданы. Если же рассматривать эти последовательности как массивы, то они будут разными, так как нарушен порядок их взаимного расположения (задачу можно решать и через массивы, но алгоритм будет длиннее). Для определения таких данных удобно использовать множественный тип.
Служебное слово для описания такого типа: set (множество). Множество – любой неупорядоченный набор объектов одного типа. Объекты называют элементами множества. Тип объектов, из которых состоит множество, называют базовым типом. На базовый тип в Паскале накладывается ограничение: это может быть любой простой (скалярный) тип, кроме real, то есть integer, char, boolean, интервальный и перечислимый. В практических реализациях языка возможны и другие ограничения, например, на число элементов множества.
Определение типа выглядит так:
type <имя> = set of <базовый тип>;
Пример.
const ogr = 15;
type vid = 1 .. ogr; lotocart = set of vid;
var posl 1, posl 2 : lotocart ;
Здесь базовый тип задается как интервальный. Переменные posl1 и posl2 – два множества, элементами которых могут быть целые числа из ограниченного диапазона от 1 до 15.
Значения переменных множественного типа задаются как заключенные в квадратные скобки последовательности выражений базового типа, отделяемые друг от друга запятыми. Так, для нашего примера значениями переменных posl1 и posl2 могут быть такие конкретные множества:
[1, 7, 11, 5] - множество из четырех элементов,
[13, 15] - множество из двух элементов,
[9] - множество из одного элемента,
[] - пустое множество.
Имена переменных и значения множественного типа могут использоваться в операторах присваивания.
Над переменными множественного типа могут выполняться те же операции, что и над множествами. При этом знаки операций:
+ - объединение множеств,
* - пересечение множеств,
- - разность множеств.
Операции отношения:
= - равенство множеств (совпадение их элементов);
<> - неравенство множеств;
>= - множество содержит …
<= - множество содержится в …
Удобной операцией для данных множественного типа является операция in – проверка на принадлежность элемента множеству. Это двуместная операция. В ней первый операнд – базового типа, а второй – множественного. Результат операции равен TRUE, если первый операнд является элементом второго и FALSE – в противном случае. Эта операция помогает в программе обходиться без проверки длинных и сложных условий. В отличие от множества, для проверки вхождения какого-либо элемента в массив нужно сравнивать его со всеми элементами массива.
Ранги операций над множествами:
+, - - тот же, что и для операции сложения,
* - тот же, что и для операции умножения.
Достоинством данных множественного типа является компактность записи программных преобразований и быстрота их выполнения.
Отметим, что сам по себе язык Паскаль не налагает никаких ограничений на количество элементов множества. Размер множества ограничивается памятью ЭВМ.
Рассмотрим несколько примеров выражений с данными множественного типа (множественных выражений):
[1, 2, 5, 6, 7]*[2 .. 6] + [3, 9] равно [2, 3, 5, 6, 9],
( [3, 4, 5] + [1, 3, 6, 7] ) * [5 .. 7] – [6] равно [5, 7].
Пусть множественный тип задан как set of 1 .. 3. Тогда значениями переменной этого типа являются
[ ], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3].
Если множество задано как SET OF BOOLEAN, то этот тип определяет совокупность значений:
[ ], [TRUE], [FALSE], [TRUE, FALSE].
Пусть переменная М описана как SET OF 1 ..10 и выполнен оператор
M := [2, 3, 5, 7];
Тогда возможны выражения:
6 in M - равно FALSE
[3, 5, 7] <= M - равно TRUE
M = [1, 2, 3, 7] - равно FALSE
[ ] <= M - равно TRUE
(7 in M) and ([7] <= M) - равно TRUE
В большинстве версий языка Паскаль в процедуре write нельзя выводить переменные множественного типа.
Примеры использования множеств
Пример 1. В заданной последовательности символов (литер), состоящей из букв латинского алфавита и оканчивающейся точкой, определить общее число вхождений в нее букв A, E, C, H.
Идея решения состоит в следующем: будем по очереди вводить символы исходной последовательности и для каждой очередной литеры проверять, является ли она одной из интересующих нас букв. Сравнивать ее с каждой из букв слишком громоздко. Проще работать с множеством и операцией IN.
program Example_1;
var chisbk: integer; litera: char;
begin chisbk := 0;
read (litera);
while litera <> ‘.’ Do begin
if litera in [‘a’, ’e’, ‘c’, ‘h’] then chisbk:=chisbk+1;
read (litera); end;
writeln (‘ общее число вхождений равно : ’chisbk’)
end.
Пример 2. Найти и напечатать в убывающем порядке все простые числа из диапазона 2 .. 201.
Существует метод, называемый "решето Эратосфена" и заключающийся в следующем. Из последовательности чисел вычеркивают числа, делящиеся на 2, затем на 3, на 5 и т.д., пока не кончится последовательность. Мы используем его в следующем варианте. Пусть No – множество анализируемых чисел, Pr – множество простых чисел. Начальные значения множеств:
No = [2, 3, 4, 5, 6, 7, 8, 9, 10, …, 201],
Pr = [].
Рассмотрим первое число из No. Это 2 – простое число. Заносим его в Pr, а из No удаляем 2 и все числа, делящиеся на 2. Тогда получим
No = [3, 5, 7, 9, 11, … , 201],
Pr = [2].
Теперь из No берем наименьшее число 3 – оно простое – и добавляем его в Pr, а из No удаляем 3 и все числа, кратные трем. Получим
No = [5, 7, 11, … , 199]
Pr = [2, 3]
В конце концов, множество No станет пустым, а в Pr перейдут все простые числа. Остается их просмотреть и напечатать в порядке убывания.
Удаление и добавление чисел запишется с помощью операторов
No :=No – [K];
Pr := Pr + [K];
а вся программа:
Program example_2;
const n = 201;
type mnochis = set of 2 .. n;
var pr, no : mnochis; p,k: 2 .. n;
Begin
no:= [2 .. n]; {присвоение начальных значений}
pr := [ ]; p:=2; {первое простое число}
Repeat
while not (p in no) do p:= p+1; pr:=pr+[p]; k:=p;
Repeat
no:=n-[k]; k:=k+p;
until k>n;
until no = [ ];
for k:=n downto 2 do if k in pr then write (k);
end.
4.1.6. Файловый тип данных
Очевидно, что программа не предоставляющая возможности пользователю сохранять данные на внешних носителях и считывать с них не представляет особой ценности.
В программировании под файлом понимается именованная область памяти на внешнем носителе либо логическое устройство – потенциальный источник или приемник информации.
Файлы с которыми можно работать в Паскале делятся следующим образом:
1. Стандартные (текстовые(text) и бестиповые (file))
2. Определяемые программистом (компонентные или типизированные (file of …)).
Примеры описания файлов:
var ft : text ;
fb : file;
fc : file of real;
Текстовые файлы хранят данные в виде строк символов. При выводе данные преобразуются из внутренней формы представления в символьную, при вводе выполняется обратное преобразование.
Бестиповые и компонентные файлы хранят данные в том же виде, в котором они представлены в оперативной памяти, то есть при обмене с файлом происходит побитовое копирование информации.
Доступ к файлам может быть последовательным, когда очередной элемент можно прочитать (записать) только после аналогичной операции с предыдущим элементом, и прямым, при котором выполняется чтение (запись) произвольного элемента по заданному адресу. Текстовые файлы позволяют выполнять только последовательный доступ, в бестиповых и компонентных можно использовать оба метода.
Прямой доступ возможен благодаря тому, что данные в этих файлах условно разделены на блоки одинакового размера, и перед операцией обмена выполняется установка текущей позиции файла на заданный блок. Прямой доступ обеспечивает высокую скорость получения информации.
Чтобы не путать файлы в программе и файлы на диске, переменные файлового типа называют логическими файлами, а реальные устройства и файлы на диске — физическими файлами. Их имена задаются с помощью строк символов, например:
'primer.pas' — имя файла в текущем каталоге;
'd:\pascal\input.txt' — полное имя файла;
'CON' 'NUL' 'COM1' 'PRN' — имена устройств.
Для того чтобы не запутаться, при работе с файлами можно пользоваться таблицей:
Таблица 8
Дата добавления: 2018-09-22; просмотров: 328; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!