Сортировка методом вставки.

В данном алгоритме используется методика «вставки» очередного элемента массива в уже отсортированную часть массива в нужную позицию.

Основная идея следующая: на 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; просмотров: 718;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.027 сек.