Тема 7. Структурированные типы данных
Массивы. Множества. Записи. Файлы
7.1 Массивы
Массив – это структура данных, которая представляет собой однородную, фиксированную по размеру и конфигурации совокупность элементов простой или составной структуры, упорядоченных по номерам.
Массив определяется именем (идентификатором) и количеством размерностей (координат), необходимых для указания местонахождения требуемого элемента массива. Имя массива является единым для всех его элементов.
Поскольку конфигурация элементов массива фиксирована, то к отдельному элементу можно обращаться с помощью одного или некольких индексов, в зависимости от количества размерностей массива. В качестве индексов могут использоваться константы и переменные порядковых типов. Элементами массивов могут быть как простые переменные любых типов, так и переменные составных типов (масивов, строк, записей и.т.д.). При решении задач используют одномерные, двумерные и n-мерные массивы.
Одномерный массив (вектор)
Направление изменения индекса
A
1 |
2 |
3 |
4 |
5 |
6 |
. . . . |
n |
|
|
|
|
|
|
|
|
А[6] или
А[i] (если i=6)
Пример: Описание массива.
Const
N=100;
Var
A: array[1. . n] of real;
или
const
n=100;
type
T_Vector = array [1 . . n] of real;
Var
A: T_Vector;
Двумерный массив (матрица)
Направление изменения индекса
A
Н |
|
1 |
2 |
3 |
4 |
5 |
6 |
. . . . |
n |
1 |
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
. . . |
|
|
|
|
|
|
|
|
|
m |
|
|
|
|
|
|
|
|
аправление
изменения индекса
А[3,5] или
А[i,j] (если i=3
и j=5)
Пример:
Const
M=30; n=50;
Var
A: array[1. .m, 1. . n] of real;
Или
Const
M=30; n=50;
Type
T_matr = array[1 . . m, 1. . n] of real;
Var
A: T_Matr;
Классическими примерами для демонстрации возможностей массивов являются задачи сортировки и поиск.
Все методы сортировки можно разделить на две большие группы:
прямые методы сортировки;
улучшенные методы сортировки.
Прямые методы сортировки делятся на сортировку вставкой (включением), сортировку выбором (выделением), сортировку обменом («пузырьковую» сортировку). Улучшенные – основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса сортировки.
Сортировка вставкой:
Массив раделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной части – все остальные элементы.
Пример
Program InsertionSort;
Uses crt;
Const
N=20; {длина масива}
Type
Tvector = array [1. .n] of real;
Var
Vector: Tvector;
B: real;
I,j,k: integer;
Begin
Clrscr;
Writeln (‘Введите элементы массива:’);
For i:=1 to n do read (vector[i]); readln;
For i:=2 to n do
Begin
B:=vector[i]; {Взятие неотсортированного элемента}
J:=1;
While (b>vector[j]) do
J:=j+1; {После окончания цикла индекс j фиксирует позицию вставки}
{ Цикл сдвига элементов для освобождения позиции вставки}
For k:=i-1 downto j do
Vector [k+1]:=vector[k]; {Вставка взятого элемента на найденную позицию}
Vector [j]:=b;
End;
Writeln (‘Отсортированный массив:’);
For i:=1 to n do write (vector[i]:8:2);
Writeln;
End.
Сортировка выбором
Находим в массиве элемент с минимальным значением на интервале от 1 – го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минмальным значением на интервале от 2 – го до n – го элемента и меняем его местами со вторым элементом.
Пример
Program Selectionsort;
Uses crt;
Const n=20;
Type Tvector = array [1. .n] of real;
Var
Vector: tvector;
Min: real;
Imin, S: integer;
I: integer;
Begin
Clrscr;
Writeln (‘Введите элементы массива:’);
For i:=1 to n do read (vector[i]);readln;
For s:=1 to n-1 do
Begin {Поиск минимального элемента в диапазоне }
Min:=vector[s];
Imin:=S;
For i:=s+1 to n do
If vector[i]< min then
Begin
Min:=vector[i];
Imin:=i
End;
{Обмен местами минимального и S – го элементов }
Vector[imin]:=vector[s];
Vector[s]:=min;
End;
Writeln (‘отсортированный массив:’);
For i:=1 to n do write (vector[i]:8:2);
Writeln;
End.
Сортировка обменом (“пузырьковая сортировка”)
Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соотвествует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
Пример
Program Bubblesort;
Uses Сrt;
Const n=20;
Type Tvector = array [1. .n] of real;
Var
Vector: tvector;
Min: real;
Imin, S: integer;
I: integer;
Begin
Clrscr;
Writeln (‘Введите элементы массива:’);
For i:=1 to n do read (vector[i]);readln;
For k:=n downto 2 do
{“Всплывание” очередного максимального элемента на k –ю позицию}
For i:=1 to k-1 do
If vector[i]>vector[i+1] then
Begin
B:=vector[i];
Vector[i]:=vector[i+1];
Vector [i+1]:=B
End;
Writeln (‘отсортированный массив:’);
For i:=1 to n do write (vector[i]:8:2);
Writeln;
End.
Двоичный поиск (бинарный поиск, поиск делением пополам)
Алгоритм двоичного поиска допустим использовать для нахождения заданного элемента только в упорядоченных массивах.
Исходный массив делится пополам и для сравнения выбирается средний элемент. Если он совпадает с искомым, то поик заканчивается. Если же средний элемент меньше искомого, то все элементы левее его также будут меньшего искомого. Следовательно, их можно исключить из зоны дальнейшего поиска, оставив только правую часть массива. Аналогично, если средний элемент больше искомого, то отбрасывается правая часть и остается левая. На втором этапе выполняются аналогичные действия над оставшейся половиной массива. В результате после второго этапа остается ¼ часть массива и.т.д.
Пример:
Program binsearch;
Uses crt;
Const
N=20; {длина массива}
Type
Tvector = array[1. .n] of real;
Var
Vector: Tvector; {}
X: real;
L, R: Integer;
I: integer;
Begin
Clrscr;
Writeln (‘Введите элементы массива:’);
For i:=1 to n do read (vector[i]);readln;
Write (‘введите искомый элемент:’);
Readln (X);
L:=1; r:=n;
While (L<=R) do {Пока не пересекутся границы }
Begin
I:=(L+r) div 2; {Индекс стеднего элемента}
If vector[i]=X then
Break {выход из цикла поиска, т.к. элемент не найден}
Else
If vector[i]<X then l:=i+1
Else R:=i-1;
End; { while}
If vector[i]=x then
Writeln (‘Искомый элемент найден на позиции’, i:3)
Else
Writeln (‘Искомый элемент не найден’);
End.