15. Структурированный тип данных. Двумерные массивы. Примеры.

Массив — это пронум-ая послед-ть величин одинакового типа, обозн-ая одним именем. Эл-ты массива располагаются в послед-ых ячейках памяти, обозн-ся именем массива и индексом. Каждое из значений, состав-их массив, наз-ся его компонентой (или эл-том массива).

Массив данных в программе рассматривается как переменная структурированного типа. Двумер-ые массивы (матрицы) - это массивы размерности 2. Эл-т определяется 2-мя инд-ми. Var иден-тор переноса = Array [тип индекса 1..тип индекса 2] Of базовый тип;

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

Дана целочисленная квадратная матрица. Пример: Найти в каждой строке наибольший эл-т и поменять его местами с эл-том главной диагонали.

Program Obmen;

Var N, I, J, Max,Ind, Vsp : Integer;A : Array [1..15, 1..15] Of Integer;

Begin

WRITE('Вв. ко-во эл-тов в массиве: '); READLN(N);

for i := 1 to n do

for j := 1 to n do

begin

write('a[', i, ',', j, '] '); readln(a[i, j])

end;

for i := 1 to n do

begin

max := a[i, 1]; ind := 1;

for j := 2 to n do

if a[i, j] > max then

begin

max := a[i, j]; ind := j

end;

vsp := a[i, i]; a[i, i] := a[i, ind]; a[i, ind] := vsp

end;

for i := 1 to n do

begin

writeln;

for j := 1 to n do write(a[i, j] : 3);

end; writeln

end.

16.Сортировка массивов. Метод выбора. Двоичный поиск в массиве.

Под сортировкой понимают перестановку эл-тов массива в заданном порядке. Отсортировать числовую таблицу по возрастанию это значит переставить эл-ты так, чтобы они шли в порядке возрастания значений, при возрастании номеров эл-тов. Отсортировать символьную таблицу – это, значит, расположить эл-ты этой таблицы в алфавитном порядке. Любой метод сортировки оценивается по двум показателям:

1. учитывает количество присваиваний, которые используются при реализации этого метода;

2. число сравнений.

Сортировка выбора.

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

Procedure vibor(n:byte; var a:mas1);

Var I,j,min:byte; vsp:integer;

Begin

For i:=0 to n-2 do begin

Min:=I;

For j:=i+1 to n-1 do

If a[j]<a[min] then min:=j;

Vsp:=a[i];

A[i]:=a[min];

A[min]:=vsp;

End;

End;

Поиск в массиве.

1. Линейный поиск. Если массив не отсортирован, то для того чтобы найти эл-т, обладающим заданным св-ом, нужно просмотреть весь массив. В этом случае кол-во действий пропорционально кол-ву эл-тов.

2. Двоичный поиск(применяется для отсортированных массивов). В массиве выбирается средний эл-т. Возможны 3 случая:

   • Искомый эл-т больше чем средний, тогда поиск будет продолжен в правой части массива;

   • Искомый эл-т меньше чем средний, тогда поиск будет продолжен в левой части массива;

   • Искомый эл-т совпадает со средним, тогда поиск завершается.

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

L-левая часть, R-правая часть.

Procedure Dv_Poisk(n:integer; const a:mas1; x:integer; var k:integer);

Var L,R,C:integer;

Begin

L:=C; R:=n-1;

Repeat C:=(L+R) div 2;

If x>a[C] then L:=C+1

else if x<a[C] then R:=C-1;

until (a[C]=x) or (R<L);

if a[C]=x then k:=C

else k:=-1;

end;