Сортировка методом вставки.
В данном алгоритме используется методика «вставки» очередного элемента массива в уже отсортированную часть массива в нужную позицию.
Основная идея следующая: на i-ом этапе итерации производится вставка j-того элемента массивав нужную позицию среди элементов a[1], a[2],. . ., a[j-1], которые уже упорядочены (j = i - 1). После этой вставки первые j элементов массива a будут упорядочены.
При использовании данного алгоритма сортировки предыдущая задача будет выглядеть следующим образом:
Var
i,j,n, key: integer;
a: array [1..10] of integer;
Begin
{Инициализация датчика случайных чисел}
randomize;
n:=10;
{Заполнение массива и вывод его на экран}
for i := 1 to n do
a[i] := Random(10);
WriteLn('Исходный массив');
for i := 1 to n do
Write(a[i],' ');
WriteLn;
{Сортировка массива методом вставки}
for i := 2 to n do
begin
key:=a[i];
j := i – 1;
while (j >= 1) and (a[j] > key) do
Begin
a[j+1] := a[j];
j := j – 1;
a[j+1] := key;
End;
End;
{Вывод на экран отсортированного массива}
WriteLn('Otsortirovannyi massiv');
for i := 1 to n do
Write(a[i],' ');
WriteLn;
ReadLn;
End.
Записи и файлы
Данные типа записи
Запись – это сложный тип данных, представляющий собой структуру, состоящую из фиксированного числа компонент, называемых полями. При этом в разных полях могут быть данные разных типов. Данные типа запись описываются следующим образом:
Type
tr = record
f11, f12,…, f1l: t1;
f21, f22,…, f2m: t2;
…
fk1, fk2,…,fkn: tk;
end;
Var
mp: tr;
Здесь tr – имя типа; mp – имя записи; l – число полей типа t1; m – число полей типа t2; n – число полей типа tk; fij – имена полей (элементов записи); служебные слова record, end – выполняют роль операторных скобок, открывающей и закрывающей соответственно.
Обращение к элементу записи (полю) fij осуществляется следующим образом: mp.fij, где mp – имя записи, fij – имя элемента (поля). Между именем записи и именем поля ставится точка.
Например, описать сведения о книге как данные типа запись. Пусть требуется хранить о книге следующие сведения: шифр книги (shg), название книги (ng), авторы (avt), год издания (GI).
Type
kniga = record
shg: string[10];
ng: string[100];
avt: string[100];
gi: integer;
end;
Var
a: kniga;
Begin
…
a.shg := ‘ВМ-991’;
a.ng := ‘Информатика 2002’;
a.avt := ‘Алексеев А.П.’;
a.gi := 2002;
end.
Элементы массива также могут иметь тип запись. Для обращения к полям элемента массива указывают mp[i].fij, где mp – имя элемента массива, i – номер элемента массива; fij – имя элемента записи (поля). Например, требуется описать сведения о 10-ти книгах:
Var
a: array [1..10] of kniga;
Begin
…
a[1].shg := ‘831.3 а45’;
a[1].ng := ‘информатика 2002’;
a[1].avt := ‘алексеев а.п.’;
a[1].gi := 2002;
End.
Примеры программ, работающих с данными типа запись.
Пример 1. Составить программу, которая вводит о каждом студенте следующие данные: номер зачетки, фамилия, оценка за контрольную. Данные оформить как массив из 10 записей. Элементы массива имеют тип запись. Вывести сведения о студентах, у которых оценка больше средней оценки.
Type
st = record
nz: string [6];
fio: string [20];
ok: real;
end;
Var
a: array [1..10] of st;
sr: real;
k, i: integer;
Begin
{присвоение сумме оценок значения 0}
sr := 0;
for i := 1 to 10 do
Begin
{ввод данных}
Write(‘Номер зачетки=’);
ReadLn(a[i].nz);
Write (‘Фамилия=’);
ReadLn(a[i].fio);
Write(‘Оценка=’);
ReadLn(a[i].ok);
{суммирование оценок}
sr := sr + a[i].ok
end;
{расчет средней оценки}
sr := sr/10;
WriteLn(‘Средняя оценка=’, sr:5:2);
WriteLn(‘Список студентов, у которых оценка
выше средней’);
{вывод сведений о студентах, у которых оценка больше
средней по группе}
for i := 1 to 10 do
if a[i].ok > sr then
WriteLn(a[i].nz,’ ‘, a[i].fio,’ ‘, a[i].ok:3:1);
{вывод списка всех студентов}
WriteLn(‘Общий список’);
for i := 1 to 10 do
WriteLn(a[i].nz,’ ‘, a[i].fio,’ ‘, a[i].ok:3:1);
ReadLn;
End.
Для удобства работы с переменными типа записи используется оператор присоединения with, формат которого:
with x do op;
где х – имя записи, ор – оператор. При этом в операторе ор при ссылках на элементы записи имя х опускается.
Пример 2. Ввести сведения о студентах: шифр группы, фамилия, оценки за последнюю сессию. Вывести список студентов, имеющих средний балл больше среднего балла по группе.
Type
stud = record
shg: string [7];
fio: string [20];
f, m,c: integer;
cr: real
end;
Var
st: array [1..25] of stud;
k, i: integer;
s: real;
Begin
{ввод количества студентов}
Write(‘Введите количество студентов=’);
ReadLn(k);
{ввод в цикле исходных данных}
for i := 1 to k do
with st[i] do
Begin
Write(‘’);
ReadLn(shg);
Write(‘’);
ReadLn(fio);
Write(‘’);
ReadLn(f, m, c);
{расчет среднего балла студента}
cr := (f + m + c)/3;
end;
{расчет среднего балла по группе}
s:=0;
for i := 1 to k do
s := s + st[i].cr;
s := s/k;
WriteLn(‘Средний балл по группе=’, s:5:2);
{вывод сведений о студентах с высоким баллом}
Writeln(‘Студенты со средним баллом больше
среднего балла по группе’);
for i := 1 to k do
with st[i] do
if cr > s then
WriteLn(shg, ’ ‘, fio,’ ‘, cr:5:2);
{вывод сведений о всех студентах}
WriteLn(‘Общий список’);
for i := 1 to k do
with st[i] do
WriteLn(shg, ’ ‘, fio, ’ ‘, cr:5:2);
End.
Работа с файлами
Под файлом понимается либо именованная область на носителе информации (локальном, сетевом или съемном диске), содержащая данные определенного вида.
Любой файл имеет три характерные особенности. Во-первых, у него есть имя, что дает возможность программе работать одновременно с несколькими файлами. Во-вторых, он содержит компоненты одного типа. Типом компонентов может быть любой тип Турбо Паскаля, кроме файлов (т.е. нельзя создать файл, состоящий из других файлов). В-третьих, размер вновь создаваемого файла никак не оговаривается при его объявлении и ограничивается только емкостью устройств внешней памяти.
Для организации ввода-вывода информации в файл в программе используются специальные переменные файлового типа. Переменные файлового типа описываются следующим образом:
Var
имя переменной: file of тип элементов файла;
Например,
Var
a: file of integer;
b: file of real;
В отличие от массива длина файла, то есть количество элементов, не задается, место элемента не определяется индексом.
С каждой переменной файлового типа связано понятие текущего указателя. Текущий указатель указывает на некоторый конкретный элемент файла. Все действия с файлами (чтение из файла, запись в файл) производятся поэлементно, причем в этих действиях участвует тот элемент файла, на который указывает указатель. В результате совершения операций текущий указатель может перемещаться.
Все элементы файла считаются пронумерованными, начальный элемент имеет нулевой номер.
Дата добавления: 2017-01-29; просмотров: 660;