Одномерные массивы – Понятие массива и его свойства, инициализация массива


7.1. одномерные массивы

Характерным признаком простых типов данных является то, что они атомарные, то есть не содержат как составные элементы данные других типов. Типы данных, не удовлетворяющие указанной свойства, называются структурированными. В языке Pascal отмечено такие структурированные типы: массивы, строки, множества, записи и файлы. Структура-ный тип характеризуется множеством элементов, из которых состоят данные этого типа. Элементы структурированного типа называются компонентами (компоненты массивов чаще всего называют элементами массивов). Итак, переменная или константа структурированного типа всегда содержит несколько компонентов. В свою очередь, каждый компонент может принадлежать к структурированному типу, что позволяет говорить о вложенности типов. Из простых элементов данных, или компонентов, более сложные структуры образуются двумя способами: объединением однородных элементов данных с целью создания массивов и объединением разнородных элементов данных с целью создания записей.

Потребность в массивах возникает тогда, когда в оперативной памяти сохраняется большая, но определенное количество однотипных данных. Например, можно задать массив ежедневных значений температуры воздуха в течение месяца с целью определения средней температуры или массив логических значений, изображать наличие билетов на киносеанс на все места в кинозале. Различают одномерные и многомерные массивы. В частности, массив температур является одномерным, а массив билетов — двумерным. Одномерные массивы рассматриваются в разделе 7.1, а многомерные -в разделе 7.2. В разделе 7.3 рассмотрены строки, которые являются разновидностью одномерных массивов.

7.1.1. Понятие массива и его свойства

Дадим определение одномерного массива, различая тип массива и данные этого типа. Термином «массив» в дальнейшем обозначать именно данные некоторого типа массива.

Одномерный массив — это последовательность однотипных данных.
Внимательно проанализировав это определение, можно сделать вывод, что массив фактически сочетает в себе две структуры: множество элементов и заданный на этом множестве порядок. Все элементы массива имеют один и тот же тип, называется базовым. С другой стороны, порядок тоже определяется набором значений одного и того же типа, что называется индексным, а сами эти значения называются индексами. Каждому элементу массива соответствует определенный индекс. Индексный тип должен быть простым порядковым типом данных. Количество элементов в одновимир-ном массиве называется его размерностью, или длиной.

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

·                размерность;

·                базовый тип,

·                индексный тип,

·                множество значений индекса.

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

С точки зрения математики одномерный массив — это вектор. Например, массив или вектор А, имеющий пять элементов, которые записывают в математике в виде индексированных переменных а 1 и а 2, а 3, а 4, а 5, можно изобразить значениями этих переменных в соседних участках оперативной памяти.

а 1 а 2 а 3 а 4 а 5

Идентификатор типа массива можно объявить в разделе type с использованием такого синтаксиса:

<имя типа массива> = array [<нижний индекс> .. <верхний индекс>] of <тип элементов>;

В этом объявлении array, of — зарезервированные слова, которые переводятся как «массив», «с»; <Имя типа массива> — некоторый идентификатор; <Тип элементов> — любой тип данных, кроме файлового типа; <Нижний индекс> и <верхний индекс> — константы, определяющие пределы диапазона допустимых значений индекса. Размерность массива равна величине Оrd (<верхний индeкс>) — Оrd (<нижний индекс>) +1.

В разделе var объявляется переменная, будет ранее объявленный тип массива:

<Имя массива> <имя типа массива>;

Синтаксис языка Pascal дает возможность объединить в разделе var объявления переменной-массива с определением ее типа. При этом идентификатор типа массива не объявляется:

<имя массива>: array [<нижний индекс> .. <верхний индекс>] of <тип элементов>;

Напомним, что объем памяти, выделенной для хранения всех объявленных в разделах var переменных, не должен превышать 64 Кбайт. Поэтому ограничение на максимальное количество элементов в массиве. Так, максимальное количество элементов типа integer не может превышать 32 767, а элементов типа real — 10922.

Объявить переменную типа массива можно и с использованием такого синтаксиса:

<имя массива>: array [<тип индексов>] of <тип элементов>;

Здесь <тип индексов> — целые типы shortint или byte, для которых количество допустимых значений составляет 256, или объявлен в разделе type перечисляемый тип. Как типы индексов не допускается указывать типы integer, word и longint, поскольку размер объявленного таким образом массива составил бы не менее 64 Кбайт.

пример 7.1

Приведем несколько примеров объявлений одномерных массивов.

Program ex7_1;
const
start = 10;
finish = 30;
type
day = (Monday, Tuesday, Wednwsday, Thursday, Friday, Saturday, Sunday)
vector = array [1..10] of integer;
STR = array [byte] of char;
var
a: vector;
str: STR;
digit: array [5..20] of integer;
float: array [start..finish] of real;
temperature: array [day] of real;
begin
writeln ( ‘ex7_1’);
end.

Подытоживая материал раздела 7.1.1, назовем основные свойства массивов, присущие как одномерным, так и многомерным массивам:

·                однородность — все элементы принадлежат одному типу;

·                постоянство — измеримость массива задается при его объявления и не изменяется в течение работы с ним;

·                равнодоступность — способ доступа ко всем элементам одинаков;

·                последовательность расположения — все элементы массива расположены в последовательных ячейках оперативной памяти;

·                индексованисть — элементы однозначно идентифицируются своими индексами;

·                упорядоченность индекса — индексный тип должен быть простым порядковым типом данных.

7.1.2. Базовые операции обработки одномерных массивов

Любая обработка массивов осуществляется путем выполнения операций над их элементами. Двумя простейшими операциями над элементами одномерного массива является выбор определенного элемента и изменение его значения. Для доступа к отдельному элементу массива применяется операция индексирования [], с помощью которой образуются выражения <и мягкие я массива> [<и ндексний выражение>]. Элемент массива является отдельной переменной, идентифицируется выше указанным выражением. Пример идентификации элементов массива а с индексами 1, 2, …, 10 и массива digit с индексами 5, 6, …, 20 приведены ниже:

a [1], a [2], …, a [10], digit [5], digit [6], …, digit [20].

Значения элементов массива меняются так же, как и значения других переменных. Например, для первого элемента массива а это можно сделать операцией присвоения а [1] = 5 или операцией ввода данных readln (a [1]).

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

·                ввода и вывода массива;

·                инициализация массива;

·                копирования массива;

·                поиск максимального или минимального элемента;

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

·                поиск заданного элемента;

·                перестановка элементов или обмен значениями между элементами массива;

·                вставка и удаление элемента.

Базовые операции обработки массивов удобно реализовывать в виде процедур, которые впоследствии могут быть использованы как «архитектурные блоки» при решении более сложных задач. Среди таких задач важнейшим является задача упорядочения массивов. Несколько алгоритмов решения этой задачи будет рассмотрен в разделе 7.1.3, а остальные раздела 7.1.2 посвятим рассмотрению базовых операций обработки одномерных массивов.

Ввода и вывода массива

Язык Pascal не имеет средств ввода и вывода массива как целостного объекта, эта операция выполняется поэлементно с помощью оператора цикла. При вводе элементов массива необходимо учесть то, что их количество, тип и тип индексов задаются в объявлении массива до начала выполнения программы и не могут быть изменены. Если границы индексов массива точно не известны, их подбирают так, чтобы введенное количество элементов массива во время выполнения программы не превышала верхней границы индекса. Например, после объявления массива а: аrrау [1. .100] of real количество элементов, в него вводятся, не должна превышать 100.

пример 7.2

Рассмотрим реализацию операций ввода и вывода одномерного массива. Для хранения значений элементов массива на этапе компиляции выделяется оперативная память, объем которой равен указанной количества элементов, умноженной на объем памяти, нуждается сохранения одного элемента. Во время выполнения программы пользователь вводит реальное количество элементов, не должна превышать объявленного количества. Приведенный ниже код илюст ри ру ет принцип использования операции ввода и вывода массива.Отметим, что элементы массива следует вводить через пробел, поскольку при этом применяется оператор read.

Program ex7_2;
var
mas: array [1..10] of integer;
n: integer;
i: integer;
begin
writeln ( ‘Enter number of elements <= 10’);
read (n)
writeln ( ‘Enter elements values’);
for i: = 1 to n do
read (mas [i]);
writeln ( ‘Entered array’);
for i: = 1 to n do
write (mas [i], »);
writeln;
end.

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

Ввод значений элементов с клавиатуры фактически является одним из способов инициализации массива. Другой способ инициализации массива заключается в присвоении каждому его элементу некоторого значения. Наиболее эффективно эта операция выполняется с помощью оператора for. Например, в приведенном ниже коде десяти элементам массива аrr присваиваются квадраты целых чисел от 1 до 10.

for i: = 1 to n do
arr [i]: = sqr (i)

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

const a: array [1..5] of integer = (1,3,2, -5,6)

Такая инициализация эквивалентна серии присваиваний
а [1]: = 1; а [2]: = 3; а [3]: = 2; а [4] = — 5; а [5] = — 6:

Для однотипных массивов А и В как для целостных объектов определена операция присваивания А = В. Однотипность массивов означает, что они имеют одинаковые типы индексов и одинаковые типы элементов. В результате выполнения операции присваивания А = В значения элементов массива В присваиваются соответствующим элементам массива А, то есть осуществляется копирования массива В до массива А.

Поиск максимального и минимального значений

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

пример 7.3

В некоторых видах спортивных соревнований выступление спортсмена оценивается несколькими судьями. Из совокупности выставленных ими баллов изымаются высокий и самый низкий баллы. На основе остальных баллов вычисляется среднее арифметическое, которое и засчитывается спортсмену как оценка его выступления. Необходимо по выставленным судейскими оценками определить среднюю оценку выступления спортсмена. Количество судей не превышает десяти.

Оценки судей считать элементами массива действительных чисел. Количество судей, а значит, и количество оценок вводить в переменной n. Если найдено максимальный и минимальный балл (переменные max и min) и накоплен сумму баллов в переменной sum, то по формуле res = (sum — min — max) / (n — 2) можно вычислить искомое значение. Эту задачу решает программа ех7_3. Результаты ее работы изображена на рис. 7.1.

Program ex7_3;
var
mark: array [1..10] of real;
i, n: integer;
min, max, sum, result: real;
begin
writeln ( ‘grade defining’);
writeln ( ‘enter numbers of arbiters (<= 10)’);
read (n)
writeln ( ‘enter’, n, ‘grades’);
for i: = 1 to n do
read (mark [i]);
min = mark [1];
max = mark [1];
sum = mark [1];
for i: = 2 to n do
begin
if min> mark [i] then min = mark [i];
if max <mark [i] then max = mark [i];
sum = sum + mark [i];
end;
writeln ( ‘margin grades’);
writeln ( ‘max =’, max: 3: 2, «min = ‘, min: 3: 2)
result = (sum-min-max) / (n-2)
writeln ( ‘rezult grade =’, result: 3: 2)
end.

Рис. 7.1. Результаты работы программы ех7_3. Исчисление средней оценки выступления спортсмена

демонстрация примера

При поиске наибольшего или наименьшего элемента массива может возникнуть потребность в определении его индекса. Значение индекса, как правило, используется при дальнейшей перестановке элементов массива, их удалении и тому подобное. Для решения этой задачи применен в примере 7.3 алгоритм нужно модифицировать. А именно, кроме переменной max (min) следует использовать переменную, в которой будут храниться значения индексов. Допустим, это будет переменная nom. Этой переменной сначала присваивается индекс первого элемента массива, а в теле цикла она изменяет значение тогда, когда и переменная max (min). Итак, переменной nom присваивается значение индекса того элемента, который оказался больше текущее значение max (меньше текущее значение min).

пример 7.4

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

Легко увидеть, что время пребывания каждого покупателя в очереди равен суммарному времени обслуживания его и всех предыдущих покупателей. Если обозначить время обслуживания i-го покупателя переменной t i, а время его пребывания в очереди — serv i то это значение определяется по формуле serv i = t 1 + t 2 + … + t i.Можно применить рекуррентную формулу, согласно которой время пребывания покупателя в очереди определяется как сумма времени его обслуживания и времени пребывания в очереди предыдущего покупателя: serv i = serv i-1 + t i.Если время обслуживания n покупателей представить в виде n-элементного массива, то номер покупателя с минимальным временем обслуживания — это индекс минимального элемента в массиве. Программное решение этой задачи приведены ниже.

Program EX7_4;
var
n, i: integer;
t: array [1..10] of real;
serv: array [1..10] of real;
nom: integer;
min: real;
begin
randomize;
Writeln ( ‘defining the number of buyer with a minimum service time’);
writeln ( ‘enter number of the buyers (<= 10)’);
readln (n);
for i: = 1 to n do
t [i]: = random * 10;
writeln ( ‘service time of the buyers’);
for i: = 1 to n do
write (t [i]: 5: 2, »);
writeln;
serv [1] = t [1];
for i: = 2 to n do
serv [i]: = serv [i-1] + t [i];
writeln ( ‘service time’);
for i: = 1 to n do
write (serv [i]: 5: 2, »);
writeln;
nom = 1;
min = t [1];
for i: = 2 to n do
if t [i] <min then
begin
min = t [i];
nom = i;
end;
write ( ‘number of buyer having min service time =’);
writeln (nom)
end.

Рис. 7.2. Результаты работы программы ех7_4. Определение номера покупателя с минимальным временем обслуживания

демонстрация примера

Заметим, что количество циклов и массивов, которые входят в состав программы ех7_4, может быть уменьшена. Попробуйте решить задачу на примере 7.4, используя как можно меньше циклов и массивов.

Поиск в неупорядоченной и упорядоченном массивах

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

пример 7.5

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

Линейный поиск осуществляется путем переборки всех элементов массива и сравнения каждого из них с заданным значением. Если элемент найден, цикл поиска прерывается и выводится найден индекс. А если цикл поиска дошел последнего элемента, и этот элемент не равен заданному значению, выводится сообщение об отсутствии искомого элемента. Описанный алгоритм поиска элемента в неупорядоченной массиве реализовано в программе ех7_5, код которой приведен ниже. На рис. 7.3 изображено результаты работы программы ех7_5.

Program EX7_5;
var n, i: integer;
a: array [1..10] of integer;
value: integer;
begin
randomize;
writeln ( ‘defining the number of the given component’);
writeln ( ‘enter number of the components (<= 10)’);
readln (n);
for i: = 1 to n do
a [i] = random (10);
writeln ( ‘generated array’);
for i: = 1 to n do
write (a [i], »);
writeln;
writeln ( ‘enter value for search’);
readln (value)
for i: = 1 to n do
if a [i] = value then
begin
writeln ( ‘nom =’, i)
break;
end;
if a [i] <> value then writeln ( ‘value not found’);
end.

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

 

 

[Всего голосов: 3    Средний: 5/5]

Читать  Лекция Паскаль 10 – Массивы, Объявления одномерного массива, Индексация элементов