Массивы

Если 2-й элемент меньше 1-го, то они меняются местами. Этот процесс  повторяется для каждой пары соседних элементов массива, пока все N элементов  не будут обработаны. За один "проход" массива самый большой элемент  встанет на старшее (N-е) место. Далее  алгоритм повторяется, причем например "проходе" первые (N-p) элементов сравниваются со своими правыми соседями. Если на очередном "проходе" перестановок не было, то алгоритм свою работу закончил. Таким образом, самые "легкие" элементы в процессе исполнения алгоритма постепенно "всплывают".

Сортировка вставками. Вначале  упорядочиваются два первых элемента массива. Они образуют начальное  упорядоченное множество S. Далее  на каждом шаге берется следующий  по порядку элемент и вставляется  в уже упорядоченное множество S так, чтобы слева от него все  элементы были не больше, а справа не меньше обрабатываемого. Место для  вставки текущего элемента в упорядоченное  множество S ищется методом деления  пополам. Алгоритм сортировки заканчивает  свою работу, когда элемент, стоящий  на N-м месте, будет обработан. (Именно таким образом игроки в бридж  обычно упорядочивают свои карты).

Сортировка выбором. Находится  наибольший элемент в массиве  из N элементов (пусть он имеет номер  р) и меняется местами с элементом, стоящим на N-м месте, при условии, что N<>p. Из оставшихся (N-1) элементов снова выделяется наибольший и меняется местами с элементом, стоящим на (N-1)-м месте и т. д. Алгоритм заканчивает свою работу, когда элементы, стоящие на 1-м и 2-м местах в массиве, будут упорядочены (для этого понадобится N-1 "проход" алгоритма). Аналогично данный алгоритм можно применять и к наименьшим элементам.

 

Действия над массивами

Для работы с массивом как  единым целым используется идентификатор  массива без указания индекса  вквадратных скобках. Массив может участвовать только воперациях отношения "равно", "не равно" и воператоре присваивания. Массивы, участвующие вэтих действиях, должны быть идентичны по структуре, т. е. иметь одинаковые типы индексов и одинаковые типы компонентов.Например, если массивы А и Вописаны как var А, В: array[1..20] of real;то применение к ним допустимых операций даст следующий результат:выражение результат А=ВTrue,если значение каждого элемента массива А равно соответствующему значению элемента массива ВА<>ВTrue, если хотя бы одно значение элемента массива А не равно значению соответствующего элемента массива ВА:=В все значения элементов массива В присваиваются соответствующим элементам массива А. Значения элементов массива В остаются неизменны.

Действия над элементами массива После объявления массива каждый его элемент можно обработать, указав идентификатор (имя) массива и индекс элемента в квадратных скобках. Например, запись Mas[2], VectorZ[10] позволяет обратить- ся ко второму элементу массива Mas и десятому элементу массива VectorZ.

При работе с двумерным  массивом указываются два индекса, с n-мерным массивом - n индексов. Например, запись MatrU[4,4] дела- ет доступным для обработки значение элемента, находящегося в чет- вертой строке четвертого столбца массива MatrU. Индексированные элементы массива называются индексированными пе- ременными и могут быть использованы так же, как и простые пере- менные. Например, они могут находиться в выражениях в качестве операндов, использоваться в операторах for, while, repeat, вхо- дить в качестве параметров в операторы Read, Readln, Write,

 

Массивы в языках Pascal и Basic

С понятием "массив" приходится сталкиваться при решении научно-технических  и экономических задач обработки  совокупностей большого количества значений.

Массив в Бейсике. Описывать  массив DIM A(N) - это значит предоставить < N > свободных ячеек в памяти ЭВМ для массива с именем А. Если описание массива отсутствует, то под одномерный массив выделяется 10 ячеек памяти. Каждый элемент массива в общем виде описывается как А(I), где А - имя массива, I -номер или индекс массива (0<=I<= N, но практически употребляется 1<=I<=N) A(I) - значение элемента массива.

 Массив в Паскале. <имя  массива>:= array <количество элементов> of <тип переменной>; Каждый элемент массива в общем виде описывается как А[I], где А - имя массива, I - номер или индекс массива (0<=I<=N, но практически употребляется 1<=I<=N) A[I] - значение элемента массива.

 Wri- teln; им можно присваивать любые значения, соответствующие их типу.

 

Двумерные массивы Паскаля  – матрицы

Двумерный массив в Паскале  трактуется как одномерный массив, тип элементов которого также  является массивом (массив массивов). Положение  элементов в двумерных массивах Паскаля описывается двумя индексами. Их можно представить в виде прямоугольной  таблицы или матрицы.

 

Рассмотрим двумерный  массив Паскаля размерностью 3*3, то есть в ней будет три строки, а в каждой строке по три элемента:

Каждый элемент имеет  свой номер, как у одномерных массивов, но сейчас номер уже состоит из двух чисел – номера строки, в  которой находится элемент, и  номера столбца. Таким образом, номер  элемента определяется пересечением строки и столбца. Например, a 21 – это элемент, стоящий во второй строке и в первом столбце.

 

Описание двумерного массива  Паскаля.

Существует несколько  способов объявления двумерного массива  Паскаля.

Мы уже умеем описывать  одномерные массивы, элементы которых  могут иметь любой тип, а, следовательно, и сами элементы могут быть массивами. Рассмотрим следующее описание типов  и переменных:

 

Пример описания двумерного массива Паскаля

 

Type

Vector = array [1..5] of <тип_элементов>;

Matrix= array [1..10] of vector;

Var m: matrix;

Мы объявили двумерный  массив Паскаля m, состоящий из 10 строк, в каждой из которых 5 столбцов. При этом к каждой i -й строке можно обращаться m [ i ], а каждому j -му элементу внутри i -й строки – m [ i , j ].

Определение типов для  двумерных массивов Паскаля можно  задавать и в одной строке:

Type

Matrix= array [1..5] of array [1..10] of < тип элементов >;

или еще проще:

type

matrix = array [1..5, 1..10] of <тип элементов>;

Обращение к элементам  двумерного массива имеет вид: M [ i , j ]. Это означает, что мы хотим получить элемент, расположенный в i -й строке и j -м столбце. Тут главное не перепутать строки со столбцами, а то мы можем снова получить обращение к несуществующему элементу. Например, обращение к элементу M [10, 5] имеет правильную форму записи, но может вызвать ошибку в работе программы.

 

Основные действия с двумерными массивами Паскаля

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

type

matrix= array [1..5, 1..10] of integer;

var

 a , b : matrix ;

то в ходе выполнения программы  можно присвоить матрице a значение матрицы b ( a := b ). Все остальные действия выполняются поэлементно, при этом над элементами можно выполнять все допустимые операции, которые определены для типа данных элементов массива. Это означает, что если массив состоит из целых чисел, то над его элементами можно выполнять операции, определенные для целых чисел, если же массив состоит из символов, то к ним применимы операции, определенные для работы с символами.

 

Ввод двумерного массива  Паскаля

Для последовательного ввода  элементов одномерного массива  мы использовали цикл for, в котором изменяли значение индекса с 1-го до последнего. Но положение элемента в двумерном массиве Паскаля определяется двумя индексами: номером строки и номером столбца.

Это значит, что нам нужно  будет последовательно изменять номер строки с 1-й до последней и в каждой строке перебирать элементы столбцов с 1-го до последнего. Значит, нам потребуется два цикла for , причем один из них будет вложен в другой.

Рассмотрим пример ввода  двумерного массива Паскаля с  клавиатуры:

type

matrix= array [1..5, 1..10] of integer;

var

a, : matrix;

 i, j: integer; { индексы массива }

begin

 for i :=1 to 5 do {цикл для перебора всех строк}

 for j :=1 to 10 do {перебор всех элементов строки по столбцам}

 readln ( a [ i , j ]); {ввод с клавиатуры элемента, стоящего в i -й строке и j -м столбце}

Двумерный массив Паскаля  можно заполнить случайным образом, т.е. использовать функцию random (N), а также присвоить каждому элементу матрицы значение некоторого выражения. Способ заполнения двумерного массива Паскаля выбирается в зависимости от поставленной задачи, но в любом случае должен быть определен каждый элемент в каждой строке и каждом столбце.

 

Вывод двумерного массива  Паскаля на экран

Вывод элементов двумерного массива Паскаля также осуществляется последовательно, необходимо напечатать элементы каждой строки и каждого  столбца. При этом хотелось бы, чтобы  элементы, стоящие в одной строке, печатались рядом, т.е. в строку, а  элементы столбца располагались  один под другим. Для этого необходимо выполнить следующую последовательность действий (рассмотрим фрагмент программы  для массива, описанного в предыдущем примере):

Пример программы вывода двумерного массива Паскаля

for i :=1 to 5 do {цикл для перебора всех строк}

begin

 for j :=1 to 10 do {перебор всех элементов строки по столбцам}

 write ( a [ i , j ]:4); {печать элементов, стоящих в i -й строке матрицы в одной экранной строке, при этом для вывода каждого элемента отводится 4 позиции}

 writeln ; {прежде, чем сменить номер строки в матрице, нужно перевести курсор на начало новой экранной строки}

end ;

Замечание (это важно!): очень  часто в программах студентов  встречается ошибка, когда ввод с  клавиатуры или вывод на экран  массива пытаются осуществить следующим  образом: readln (a), writeln (a), где а – это переменная типа массив. При этом их удивляет сообщение компилятора, что переменную этого типа невозможно считать или напечатать. Может быть, вы поймете, почему этого сделать нельзя, если представите N кружек, стоящих в ряд, а у вас в руках, например, чайник с водой. Можете вы по команде «налей воду» наполнить сразу все кружки? Как бы вы ни старались, но в каждую кружку придется наливать отдельно. Заполнение и вывод на экран элементов массива также должно осуществляться последовательно и поэлементно, т.к. в памяти ЭВМ элементы массива располагаются в последовательных ячейках.

 

Представление двумерного массива  Паскаля в памяти

Элементы абстрактного массива  в памяти машины физически располагаются  последовательно, согласно описанию. При  этом каждый элемент занимает в памяти количество байт, соответствующее его  размеру. Например, если массив состоит  из элементов типа integer , то каждый элемент будет занимать по два байта. А весь массив займет S^2 байта, где S – количество элементов в массиве.

А сколько места займет массив, состоящий из массивов, т.е. матрица? Очевидно: S i^S j , где S i - количество строк, а S j – количество элементов в каждой строке. Например, для массива типа

Matrix = array [1..3, 1..2] of integer ;

потребуется 12 байт памяти.

Как будут располагаться  в памяти элементы этого массива? Рассмотрим схему размещения массива M типа matrix в памяти.

 

Под каждый элемент M [i,j] типа integer выделяется две ячейки памяти. Размещение в памяти осуществляется «снизу вверх». Элементы размещаются в порядке изменения индекса, что соответствует схеме вложенных циклов: сначала размещается первая строка, затем вторая, третья... Внутри строки по порядку идут элементы: первый, второй и т.д.

Как мы знаем, доступ к любой  переменной возможен, только если известен адрес ячейки памяти, в которой  хранится переменная. Конкретная память выделяется для переменной при загрузке программы, то есть устанавливается  взаимное соответствие между переменной и адресом ячейки. Но если мы объявили переменную как массив, то программа  «знает» адрес начала массива, то есть первого его элемента. Как  же происходит доступ ко всем другим элементам  массива?

При реальном доступе к  ячейке памяти, в которой хранится элемент двумерного массива, система  вычисляет ее адрес по формуле:

Addr + Size Elem * Cols *( I -1)+ Size Elem *( J -1),

где Addr – фактический начальный адрес, по которому массив располагается в памяти; I , J – индексы элемента в двумерном массиве; SizeElem – размер элемента массива (например, два байта для элементов типа integer ); Cols – количество элементов в строке.

Выражение SizeElem * Cols *( I -1)+ SizeElem *( J -1) называют смещением относительно начала массива.

Примеры решения задач  с двумерными массивами Паскаля

Задача: Найти произведение ненулевых элементов матрицы.

Решение:

Для решения данной задачи нам потребуются переменные: матрица, состоящая, например, из целочисленных  элементов; P – произведение элементов, отличных от 0; I , J – индексы массива; N , M – количество строк и столбцов в матрице. Входными данными являются N , M – их значения введем с клавиатуры; матрица – ввод матрицы оформим  в виде процедуры, заполнение матрицы  осуществим случайным образом, т.е. с помощью функции random (). Выходными данными будет являться значение переменной P (произведение). Чтобы проверить правильность выполнения программы, необходимо вывести матрицу на экран, для этого оформим процедуру вывода матрицы. Ход решения задачи:

обсудим сначала выполнение основной программы, реализацию процедур обговорим чуть позже:

введем значения N и M ; Введем двумерный массив Паскаля, для этого обращаемся к процедуре vvod ( a ), где а – матрица; Напечатаем полученную матрицу, для этого обращаемся к процедуре print ( a ); Присвоим начальное значение переменной P =1; Будем последовательно перебирать все строки I от 1-й до N -й, в каждой строке будем перебирать все столбцы J от 1-го до M -го, для каждого элемента матрицы будем проверять условие: если a ij ? 0, то произведение P будем домножать на элемент a ij ( P = P * a ij ); Выведем на экран значение произведения ненулевых элементов матрицы – P ;

А теперь поговорим о процедурах.

Замечание (это важно!) Параметром процедуры может быть любая переменная предопределенного типа, это означает, что для передачи в процедуру  массива в качестве параметра, тип  его должен быть описан заранее. Например :

Type

Matrix=array [1..10, 1..10] of integer;

..............................