Работа с одномерными (линейными) массивами

Интервальный тип данных. Структурированные типы данных. МаССИВЫ

Рассмотрим вначале интервальный тип данных, который относится к простым порядковым типам.

Интервальный (индексный) тип данных

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

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

Примеры отрезков:

10..21

-99..99

'A'..'Z'

Над переменными, относящимися к интервальному типу, могут выполняться все операции и применяться все стандартные функции, которые допустимы для соответствующего базового типа.

При использовании интервальных типов данных в программах осуществляется проверка того, чтобы значения их переменных не выходили за границы, введенные для них в описании данного интервального типа.

Вопросы для проверки знаний.

1. В чем заключается назначение и какова форма записи величины интервального типа ?

2. Возможно ли задание следующих величин интервального типа (ответ пояснить) ?

а) -10..10; б) 100..-1; в) А..10; г) В..Y; д) 1..D; е)W..C.

Структурированные типы данных. Массивы. Их свойства, описание, ввод и вывод

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

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

1) массивы;

2) строки;

3) множества;

4) записи;

5) файлы.

Наиболее важными для решения расчетных задач являются массивы. Массивами называют ограниченные и упорядоченные совокупности однотипных величин, называемых элементамииликомпонентамимассива.

Массивы обладают следующими общими свойствами:

1) всем элементам массива присваивается общее имя, которое называют именем массива;

2) каждый элемент массива может быть явно обозначен при помощи индексов и к нему имеется прямой доступ;

3) число индексов, используемых для задания адресов его элементов, называют размерностью массива (1 индекс- одномерный массив, 2 –двумерный массив и т.д.),

4) число элементов массива (задаваемое размерностью по каждому измерению - индексу) определяется при его описании и в дальнейшем не меняется;

5) тип элементов называется базовым типом, в языке Паскаль он может быть любым, кроме файлового.

Описание массива можно задать при помощи предварительного описания типа, можно без него.

Синтаксис описания типа массива (квадратные скобки – обязательный элемент записи описания):

имя типа = array[список индексов] of тип

где имя типа- правильный идентификатор языка Паскаль;

список индексов- список одного или нескольких индексных (интервальных) типов, разделенных запятыми;

тип - любой тип данных.

В качестве индексных типов в Паскале можно использовать любые порядковые типы, кроме longint и типов-диапазонов с базовым типом longint.

Пример 1. Описание типа с именем mas, в котором должно быть 10 целых переменных типа integer:

Type

mas = array[1..10] of integer;

Определить переменные (одну или несколько) как массив можно и непосредственно при ее описании, без предварительного описания типа массива.

Синтаксис непосредственного описания переменных как массивов имеет вид:

список переменных:array[список индексов] of тип;

Список переменных может состоять только из одной переменной.

Примеры 2 непосредственного описания переменных как массивов:

Var

a,b,c:array[1..10] of real;{одномерныевещественные массивы a,b,c длины 10}

int_1: array[1..20] of integer;{одномерныецелочисленный массив int_1длины 20}

int_2: array[1..20] of integer;

Matr:array[1..n,1..n] of real;{двумерныйвещественный массив Matr,по каждому измерению размерность равна n }

Если переменные-массивы описаны одним списком (a,b,c в примере 2), то они считаются принадлежащими к одному типу. Если же переменные-массивы описаны в разных строках, то даже при внешнем совпадении они считаются принадлежащими к разным типам – например, переменные-массивы int_1и int_2в примере 2.

Для обеспечения совместимости массивов (принадлежности их к одному типу) при раздельном описании необходимо применять предварительное описание данного типа массивов.

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

Так как тип, идущий за ключевым словом of в описании массива, - любой тип Паскаля, то он может быть и другим массивом. Например, описание типа вида:

Type

massiv = array[1..10] of array[1..20] of real;

можно заменить более компактным описанием массива размерности 2:

Type

massiv = array[1..10, 1..2] of real;

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

Примеры 3 допустимого обозначения элементов массивов, описания которых даны в примере 2:

a[2] b[10] int_1[5] int_2[20] Matr[2,3]

Примеры 4 недопустимого обозначения элементов массивов, описания которых даны в примере 2:

a[12]{описание задает элементы массива a с номерами от 1 до 10, номера 12 не существует}

b[-1]{то же самое для массива b}

Вводить и выводить массивы можно только поэлементно. Для этого в список ввода или вывода помещается переменная массива с индексом, а сами операторы ввода или вывода выполняются в цикле, который проходит по всем элементам массива.

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

Пример 5. Ввод и вывод одномерного массива, описанного с предварительным описанием типа. При вводе и выводе на экран выдаются поясняющие сообщения:

const n = 4;

type mas = array[1..n] of integer;

var a: mas; i: integer;

Begin

writeln('Vvedite elementi massiva');

for i:=1 to n do begin write(' a[',i,']=');readln(a[i]); end;

writeln('Vivod elementov massiva:');

for i:=1 to n do writeln(' a[',i,']=',a[i]:5);

End.

В зависимости от числа индексов в массивах, их делят на одномерные (один индекс) и многомерные (два и более индекса).

Вопросы для проверки знаний.

1. В чем заключается назначение структурированных типов ?

2. Какое свойство называют вложенностью типов ?

3. Назовите структурированные типы языка Паскаль.

4. Что называют массивом и его элементами (компонентами)?

5. Какимиобщими свойствами обладают массивы ?

6. Что такое индекс и размерность массива, какие массивы называют одномерными и многомерными ?

7. Каков синтаксис описания типа массива ?

8. Каков синтаксис непосредственного описания переменных-массивов ?

9. Назовите два возможных способа описания переменных-массивов, принадлежащих к одному типу.

10. Как обозначают элементы массива ?

11. Как вводят и выводят массивы ?

Инициализация массивов

Инициализацией массиваназывают присвоение начальных значений всем его элементам. Обычно инициализацию выполняют вначале работы программы для того, чтобы использовать значения элементов массива в производимых расчетах.

Простейшим случаем инициализации является присвоение всем элементам массива одинакового значения (в числовых массивах чаще всего – нулевого) путем непосредственной засылки в элементы необходимой величины.

Пример 1. Обнулить элементы двумерного вещественного массива a:array[1..5, 1..5]:

var a:array[1..5,1..5] of real;

i,j:integer;

for i:=1 to 5 do

for j:=1 to 5 do a[i,j]:=0;

Данный метод используют на практике для инициализации матриц, у которых мало ненулевых элементов: вначале всем элементам присваивается нулевое значение, а затем нескольким элементам присваивают требуемые ненулевые значения.

Для решения подобной задачи для типов величин, занимающих один байт памяти используют процедуру FillChar(var Vr; NBytes: Word; Chr: Byte). Она предназначена для заполнения в переменной Vr первых ее NBytes байт значением Chr.

Пример 2. Обнулить все элементы одномерного символьного массива ch:array[1..20]:

FillChar(ch, 20, 0);

Более сложная инициализация массива различными значениями может быть выполнена в Паскале с использованием типизированных констант, когда после описания типа массива создается константа такого же типа, в которую заносятся все требуемые значения элементов массива.

Пример 3. Необходимо сформировать одномерный вещественный массив a[1..6], у которого элементы равны, соответственно: 1.2, 4.5, -2.4, 5.7, -8.0, 10.5:

Type

array_6 = array[1..6] of real;

const a:array_6 = (1.2, 4.5, -2.4, 5.7, -8.0, 10.5);

Вопросы для проверки знаний.

1. Какое действие называют инициализацией массива?

2. Назовите два возможных метода присвоения всем элементам массива одинакового значения ?

3. Как выполнить инициализацию массива при помощи типизированных констант?

Работа с одномерными (линейными) массивами

Одномерный массив имеет один индекс, задающий номера всех его элементов. Так как все элементы одномерного массива могут быть упорядочены по возрастанию значений их индекса (выстроены в одну линию), то эти массивы также называют линейными.

Описания линейных массивов даны в примерах 1 и 2. Ввод и вывод одномерного массива рассмотрены в примере 5. Методы инициализации даны выше. Рассмотрим решение характерных задач по линейным массивам.

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

Пример 1. Ввести с клавиатуры значения элементов (не превышающих по модулю 1000) целочисленного линейного массива A[1..10]. Определить в нем максимальный по модулю элемент с нечетным номером. Найденный элемент и его номер выдать на экран.

Решение. Обозначим искомый номер элемента через NMax, его значение – черезMaxMod. При поиске оптимального по заданному признаку элемента вначале в качестве оптимального принимают самый первый элемент, удовлетворяющий всем требованиям (в примере – элемент с номером 1), а затем перебором всех подходящих элементов уточняют его. Смена текущего оптимального элемента на новый A[i]производится в том случае, когда его модуль больше, чем у текущего (abs(A[i])>abs(MaxMod)) и номер элемента нечетный ((i mod 2)=1).

var a: array[1..10] of integer;{описание массива}

i,MaxMod,NMax: integer; {описание вспомогательных переменных i, MaxMod и NMax}

Begin

writeln('Vvedite elementi massiva A');

for i:=1 to 10 do begin write(' A[',i,']=');readln(A[i]);end; {ввод элементов А}

writeln(' Entert massiv A:');

for i:=1 to 10 do write(' A[',i,']=',A[i]:4); writeln; {вывод элементов А}

MaxMod:=A[1];NMax:=1; {начальное присваивание элемента и его номера}

for i:=2 to 10 do if (abs(A[i])>abs(MaxMod))and((i mod 2)=1) {проверка на оптимальность выбранного элемента массива и нечетности текущего значения номера элемента i}

then begin MaxMod:=A[i]; NMax:=i end; {замена элемента и его номера}

writeln(' Rezult: NMax=',NMax,' MaxMod=', MaxMod);{вывод результатов расчета}

End.

Рассмотрим другие характерные задачи, решаемые с помощью линейных массивов, и фрагменты кода, решающие их на примере массива a[1..n]. Для вспомогательных операций используется дополнительная переменная t.

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

Например, необходимо вставить в достаточно объемный массив a со счетчиком n после элемента с номером k новый элемент, равный b. Для того, чтобы не потерять значения элементов массива и минимизировать число операций, присваивания лучше выполнять с конца массива:

n:=n+1; for i=n downto k+2 do a[i]:=a[i-1]; a[k+1]:=b;

Удаление из массива a со счетчиком n элемента с номером k:

n:=n-1; for i=k to n do a[i]:=a[i+1];

2. Циклический сдвиг элементов в рамках массива. Обычно применяют сдвиг слева направо с возрастанием номеров элементов: a[1]®a[2]; a[2]®a[3];… a[n-1]®a[n]; a[n]®a[1].

Как и при вставке, меньшее число операций затрачивается при выполнении операции, начиная со старших элементов (при этом необходимо запомнить только последний элемент a[n]):

t:=a[n]; for i=n downto 2 do a[i]:=a[i-1]; a[1]:=t;

Cдвиг справа налево с убыванием номеров элементов (a[2]®a[1]; a[3]®a[2];… a[n]®a[n-1]; a[1]®a[n]) выполняется аналогично:

t:=a[1]; for i=1 to n-1 do a[i]:=a[i+1]; a[n]:=t;

3. Вычисление средних значений элементов массива. Важнейшей статистической характеристикой элементов числового массива a[1..n]является среднее значение его элементов:m=(a[1]+a[2]+…+a[n])/n. С использованием текущего значения суммы элементов S код для расчета m имеет вид:

S:=0; for i=1 to n do S:=S+a[i]; m:=S/n;

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

Пример 2. Инициализировать в программе значения элементов целочисленного линейного массива A[1..10]величинами {81,-54,-72,295,-85,10,44,58,-32,59}. Сформировать из массива A два массива размером 5, в первый с названием Bпоместить все элементы с нечетными номерами, во второй С– c четными. Перед обработкой распечатать исходный массив A[1..10], после обработки – новые массивы Bи С.

Решение. Инициализацию массива A выполняем с использованием типизированной константы, предварительно введя тип массива. Для задания номеров элементов вводим в программе дополнительные счетчики jи k, которым вначале задаем нулевые значения. Массивы B[1..5]и С[1..5] формируем, поочередно занося в них элементы массива A и наращивая соответствующие счетчики.

type array_10 = array[1..10] of integer; {описание типа массива A}

const a:array_10 = (81, -54, -72, 295, -85, 10, 44, 58, -32, 59);

var b,c: array[1..5] of integer;{описание массивов B,C}

i,j,k: integer; {описание вспомогательных переменных i,j,k }

Begin

writeln(' Entert massiv a:');

for i:=1 to 10 do write(' a[',i,']=',a[i]:4); writeln; {вывод элементов a}

j:=0;k:=0; {начальные присваивания текущих номеров элементов в массивах B и С}

for i:=1 to 10 do if (i mod 2)=1 {проверка нечетности текущего номера элемента i}

then begin j:=j+1;b[j]:=a[i] end{засылка очередного элемента в массив B}

else begin k:=k+1;c[k]:=a[i] end;{засылка очередного элемента в массив С}

writeln(' Rezult massiv B:');

for i:=1 to 5 do write(' b[',i,']=',b[i]:4); writeln; {вывод элементов B}

writeln(' Rezult massiv C:');

for i:=1 to 5 do write(' c[',i,']=',c[i]:4); {вывод элементов C}

End.

Пример 3. Пузырьковая сортировка. Алгоритмы сортировки, которые упорядочивают все элементы линейного массива по возрастанию или убыванию заданного их признака, составляют отдельный класс. Самым простым (но не очень эффективным) из них является сортировка простыми обменами (пузырьковая сортировка, англ. - bubble sort) ). Данная сортировка относится к классу обменных сортировок, в котором все перестановки осуществляются на месте, в пределах массива за счет перемены мест его элементов. Работа алгоритма заключается в осуществлении последовательных проходов по массиву с обменом местами пар соседних элементов, у которых нарушен требуемый порядок. Заканчивается его работа после очередного прохода, на котором не было выявлено ни одного нарушения порядка относительного положения элементов. Алгоритм оформлен в виде процедуры сортировки по возрастанию числового массива A типа Num_Array с элементами типа integer и заданной длиной count. Для контроля окончания сортировки (завершения проходов по массиву) дополнительно введен логический ключ key. При смене местами элементов A[i]и А[i-1]использована круговая пересылка с использованием вспомогательной величины con: A[i]®con; А[i-1]®A[i]; con®А[i-1]:

{ сортировка пузырьковым методом}

procedure Bubble_sort(var A:Num_Array; count:integer);

var con,i: integer; key: boolean;

Begin

key:= true; {начальное задание истинного значения ключа}

while key do{цикл с предусловие по значению ключа}

Begin

key:= false; {задание ложного значения ключа, пока не найдено нарушения порядка}

for i:= 2 to count do{проход по массиву}

if A[i]<A[i-1] then{ проверка правильности рядом стоящих элементов}

begin{регистрация нарушения порядка и смена двух подряд стоящих элементов}

key:= true; {задание истинного значения ключа - найдено нарушения порядка }

con:= A[i-1];{ круговая пересылка значений A[i-1],A[i],con}

A[i-1]:= A[i];

A[i]:= con;

end; {окончание действий при нарушении порядка соседних элементов}

end; {окончание тела цикла while }

end;{окончание тела процедуры}

Пример 4. Ввести с клавиатуры значения элементов (не превышающих по модулю 1000) двух целочисленных массивов A[1..5]и B[1..5]. Преобразовать их по правилу: больший из каждой пары элементов A[i]и B[i]принять в качестве нового значения A[i], а меньший – в качестве нового значения B[i]. Перед обработкой распечатать исходные массивы A[1..5]и B[1..5], после обработки – новые значения элементов массивов.

Решение. При необходимости смены местами элементов A[i]и B[i]использована круговая пересылка с использованием дополнительной величины con: A[i]® con; B[i]® A[i]; con ® B[i]. Код для ввода и начального вывода значений массивов Aи B совпадает с аналогичным кодом из примера 1, вывод результирующих массивов – по примеру 2.

var a,b: array[1..5] of integer;{описание массивов}

i,con: integer; {описание вспомогательных переменных iи con }

Begin

…//ввод и начальный вывод массивов Aи B - по примеру 1

for i:=1 to 5 do

if A[i]<=B[i] then{преобразование элементов массивов}

begin con:=A[i]; A[i]:= B[i]; B[i]:= con end;

…//вывод результирующих массивов Aи B - по примеру 2

End.

Вопросы для проверки знаний.

1. Какие массивы называют линейными ?

2. Как контролируется в простейшем варианте размер массива при вставке и удалении из него отдельных элементов ?