Массивы и их виды

МАССИВЫ

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

Обычно двумерные массивы на языке программирования Pascal описываются так: программирование массив матрица рascal.

array [1.m, 1. n] of базовый_тип Однако можно их описывать и по-другому:

array [1.m] of array [1.n] of базовый_тип При этом описание может быть в разделе type и тогда создается новый тип, который можно использовать при объявлении переменных. Или массив может быть описан непосредственно в разделе переменных. m и n — это константы, их можно опустить и вставить конкретные значения, но лучше так не делать. Обычно подразумевают, что в интервале от 1 до m определяется количество строк, а в интервале от 1 до n — количество столбцов массива.

1 вариант — описание массива через раздел type:

const.

M = 10;

N = 5;

type.

matrix = array [1.M, 1. N] of integer;

var.

a: matrix;

2 вариант — описание массива в разделе переменных:

const.

M = 10;

N = 5;

var.

a: array [1.M, 1. N] of integer;

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

type a = array[1.10] of byte;

var b: array[1.100] of a;

Для обращения к элементу двухмерного массива необходимо указать имя массива и в квадратных скобках через запятую — значения двух индексов (первый указывает номер строки, а второй — номер столбца), на пересечение которых стоит элемент (например, a[i, 2]: =6). В языке программирования Pascal допустимо разделение индексов с помощью квадратных скобок (например, a[i][5]: = 7) Если описывается двумерный массив как типизированная константа, то при задании значений его элементов он рассматривается как массив массивов. При этом в общих круглых скобках через запятую перечисляются заключенные в круглые скобки значения элементов строк (каждая строка в своих скобках):

type.

arr = array[1.4, 1.3] of integer;

const.

cords: arr = ((1,-1,3), (0,0,0), (1,4,0), (4,-1,-1));

Рассмотрим простой пример работы с двумерным массивом. Сначала заполним его данными, а затем выведем их на экран в виде таблицы.

var.

matrix: array[1.3,1.5] of integer;

i, j: integer;

begin.

writeln ('Введите 15 чисел: ');

for i := 1 to 3 do.

for j := 1 to 5 do.

read (matrix[i, j]);

for i := 1 to 3 do begin.

for j := 1 to 5 do.

write (matrix[i, j], ' ');

writeln.

end;

Размерность массива (т.е. количество содержащихся в нем значений) определяется произведением количества строк на количество столбцов. В примере выше в массив помещается 15 значений. Когда пользователь вводит очередное число, то процедура read считывает его и помещает в ячейку с текущими индексами i и j. Когда i равна единице, значение j меняется пять раз, и, значит, заполняется первая строка таблицы. Когда i равна двум, значение j снова меняется пять раз и заполняется вторая строка таблицы. Аналогично заполняется третья строка таблицы. Внутренний цикл for в общей сложности совершает 15 итераций, внешний только 3. Как пользователь вводит значения — не важно. Он может их разделять либо пробелом, либо переходом на новую строку. Вывод значений двумерного массива организован в виде таблицы. Выводятся 3 строки по 5 чисел в каждой. Внутри строк числа разделяются пробелом. На самом деле, это не совсем корректно написанная программа. Мы несколько раз используем цифры 3 и 5. А что если мы захотим поменять размерность массива? Придется просмотреть всю программу (представьте, что она очень большая) и исправить значения. Это неэффективно. Поэтому в программе следует использовать константы. В случае чего их значения можно поменять всего лишь в одном месте. Вторая проблема — это «кривость» выводимой на экран таблицы значений матрицы, в случае если есть значения разной разрядности (однозначное, двузначное и т. д. числа). Неплохо бы под каждое число отводить равное количество знаков. Вот так может выглядеть подправленный вариант программы:

const.

M = 3;

N = 5;

var.

matrix: array[1.M, 1. N] of integer;

i, j: integer;

begin.

writeln ('Введите 15 чисел: ');

for i := 1 to M do.

for j := 1 to N do.

read (matrix[i, j]);

for i := 1 to M do begin.

for j := 1 to N do.

write (matrix[i, j]: 5);

writeln.

end;

procedure LowCase (var s: string);{приведение к нижнему регистру}.

var i: byte;

begin.

for i:=1 to length (s) do.

if s[i] in ['A'.'Z','А'.'П'] then s[i]: =chr (ord (s[i])+32).

else if s[i] in ['Р'.'Я'] then s[i]: =chr (ord (s[i])+80).

else if s[i]='Ё'then s[i]: ='ё';

end;

Предположим, что программа работает с большим количеством однотипных данных. Скажем около ста разных целых чисел нужно обработать, выполнив над ними те или иные вычисления. Как вы себе представляете 100 переменных в программе? И для каждой переменной нужно написать одно и тоже выражение вычисления значения? Это очень неэффективно. Есть более простое решение. Это использование такой структуры (типа) данных как массив. Массив представляет собой последовательность ячеек памяти, в которых хранятся однотипные данные. При этом существует всего одно имя переменной связанной с массивом, а обращение к конкретной ячейке происходит по ее индексу (номеру) в массиве. Нужно четко понимать, что индекс ячейки массива не является ее содержимым. Содержимым являются хранимые в ячейках данные, а индексы только указывают на них. Действия в программе над массивом осуществляются путем использования имени переменной, связанной с областью данных, отведенной под массив. Итак, массив — это именованная группа однотипных данных, хранящихся в последовательных ячейках памяти. Каждая ячейка содержит элемент массива. Элементы нумеруются по порядку, но необязательно начиная с единицы (хотя в языке программирования Pascal чаще всего именно с нее). Порядковый номер элемента массива называется индексом этого элемента. Помним, все элементы определенного массива имеют один и тот же тип. У разных массивов типы данных могут различаться. Например, один массив может состоять из чисел типа integer, а другой — из чисел типа real. Индексы элементов массива обычно целые числа, однако могут быть и символами, а также описываться другими порядковыми типами. Т. е. для индекса можно использовать тип, в котором определена дискретная последовательность значений, и все эти значения можно пересчитать по порядку. Индексировать можно как константами и переменными, так и выражениями, результат вычисления которых дает значение перечислимого типа. Если индекс массива может приобретать все допустимые значения определенного перечислимого типа, то при описании массива возможно задание имени типа вместо границ изменения индекса. При этом границами индекса будут первое и последнее значения в описании типа индекса. Границы изменения индексов могут задаваться с помощью ранее объявленных констант. Рекомендуется предварительно объявлять тип массива в разделе описания типов. Массив можно создать несколькими способами.

…

const n = 200;

type.

months = (jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec);

years = 1900.2100;

people = array[years] of longint;

var.

growth: array[months] of real;

hum: people;

notes: array[1.n] of string;

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

var ch: array [1.11] of char;

h: char;

i: integer;

begin.

for i := 1 to 11 do read (ch[i]);

for i := 1 to 11 do write (ch[i]: 3);

readln.

end.

В примере выделяется область памяти под массив из 11 символов. Их индексы от 1 до 11. В процессе выполнения программы пользователь вводит 11 любых символов (например, `q', 'w', 'e', '2', 't', '9', 'u', 'I', 'I', 'o', 'p'), которые записываются в ячейки массива. Текущее значение переменной i в цикле for используется в качестве индекса массива. Второй цикл for отвечает за вывод элементов массива на экранФункция sizeof, примененная к имени массива или имени массивного типа, возвращает количество байтов, отводимое под массив. В задачах по программированию очень часто встречается необходимость заполнить массив данными и вывести их потом на экран. Методов этого не так уж много и особым разнообразием они не отличаются.

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

Программа на языке Паскаль:

const.

n = 10;

type.

miniarr = array[1.n] of integer;

var.

a, b: miniarr;

procedure arr_rand (k:integer; var arr: miniarr);

var i: byte;

begin.

writeln ('Заполнение массива случайными числами.');

randomize;

for i := 1 to k do.

arr[i] := random (100);

end;

procedure arr_user (k:integer; var arr: miniarr);

var i: byte;

begin.

write ('Введите ', k, ' чисел через пробел: ');

for i := 1 to k do.

read (arr[i]);

end;

procedure arr_out (k:integer; var arr: miniarr);

var i: byte;

begin.

write ('Вывод массива: ');

for i := 1 to k do.

write (arr[i]: 4);

writeln;

end;

begin.

arr_rand (n, a);

arr_out (n, a);

writeln;

arr_user (n, b);

arr_out (n, b);

readln.

end.

Массивы — это совокупности однотипных элементов. Характеризуются они следующим: каждый компонент массива может быть явно обозначен и к нему имеется прямой доступ; число компонент массива определяется при его описании и в дальнейшем не меняется. Для обозначения компонент массива используется имя переменной-массива и так называемые индексы, которые обычно указывают желаемый элемент. Тип индекса может быть только порядковым (кроме longint). Чаще всего используется интервальный тип (диапазон). Описание типа массива задается следующим образом:

type.

имя типа = array[ список индексов ] of тип Здесь имя типа — правильный идентификатор; список индексов — список одного или нескольких индексных типов, разделенных запятыми; тип — любой тип данных. Вводить и выводить массивы можно только поэлементно.

Пример 1. Ввод и вывод одномерного массива.

const.

n = 5;

type.

mas = array[1.n] of integer;

var.

a: mas;

i: byte;

begin.

writeln ('введите элементы массива');

for i:=1 to n do readln (a[i]);

writeln ('вывод элементов массива:');

for i:=1 to n do write (a[i]: 5);

end.

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

var a, b, c: array[1.10] of integer;

Если массивы a и b описаны как:

var.

a = array[1.5] of integer;

b = array[1.5] of integer;

то переменные a и b считаются разных типов. Для обеспечения совместимости применяйте описание переменных через предварительное описание типа. Если типы массивов идентичны, то в программе один массив может быть присвоен другому. В этом случае значения всех переменных одного массива будет присвоены соответствующим элементам второго массива. Вместе с тем, над массивами не определены операции отношения. Сравнивать два массива можно только поэлементно. Так как тип, идущий за ключевым словом of в описании массива, — любой тип Турбо Паскаль, то он может быть и другим массивом. Например:

type.

mas = array[1.5] of array[1.10] of integer;

Такую запись можно заменить более компактной:

type.

mas = array[1.5, 1.10] of integer;

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

for i:=1 to m do.

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

Для «красивого» вывода матрицы на экран используйте такой цикл:

for i:=1 to m do begin.

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

writeln;

end;

Строки При работе со строками, как правило, возникает необходимость выполнять их копирование, вставку, удаление или поиск. Для эффективной реализации этих действий в Паскале предусмотрены стандартные процедуры и функции. Они кратко описаны ниже. Функция Concat (s1, s2, …, sn) возвращает строку, являющуюся слиянием строк s1, s2, …, sn. Функция Copy (s, start, len) возвращает подстроку длиной len, начинающуюся с позиции start строки s. Процедура Delete (s, start, len) удаляет из строки s, начиная с позиции start, подстроку длиной len. Процедура Insert (subs, s, start) вставляет в строку s подстроку subs, начиная с позиции start. Функция Length (s) возвращает фактическую длину строки s, результат имеет тип byte. Функция Pos (subs, s) ищет вхождение подстроки subs в строку s и возвращает номер первого символа subs в s или нуль, если subs не содержится в s. Процедуры преобразования типовПроцедура Str (x, s) преобразует числовое значение x в строку s, при этом для x может быть задан формат, как в процедурах вывода write и writeln. Например:

x := 123;

s := str (x:6,s);

Результат: s = ' 123'.

Процедура Val (s, x, errcode) преобразует строку s в значение числовой переменной x, при этом строка s должна содержать символьное представление числа. В случае успешного преобразования переменная errcode равна нулю. Если же обнаружена ошибка, то errcode будет содержать номер позиции первого ошибочного символа, а значение x не определено. В языке программирования Паскаль переменная типа array of char может рассматриваться как строка постоянной длины. Переменные такого типа могут свободно использоваться в любых строковых выражениях. При этом компилятор автоматически преобразует такой массив в строку, длина которой равна количеству элементов массива. Массивы типа char можно сравнивать друг с другом и обращаться с ними почти так же, как с переменными типа string. Можно в операторе присваивания в левой части указывать имя такого массива, а в правой — строковую константу с длиной, равной количеству элементов в массиве. Кроме того, в Pascal массивам типа array of char разрешено присваивать строковые константы, длина которых меньше количества элементов массива; в оставшиеся при этом незаполненные элементы заносится символ #0. Однако нельзя переменной типа array of char присвоить значение строковой переменной или строкового выражения (кроме выражений над строковыми константами с результирующей длиной, равнойразмерности массива). Массивы типа array of char могут использоваться в процедуре val и функциях concat, copy и length.

var.

s: string;

i, id, len, max, count: byte;

begin.

readln (s);

len := length (s);

max := 0;

id := 0;

count := 0;

for i:=1 to len do.

if s[i] ' ' then.

count := count + 1.

else begin.

if count > max then begin.

max := count;

id := i — count;

end;

count := 0.

end;

if count > max then begin // for last word.

max := count;

id := i — count;

end;

for i:=id to id+max do.

if s[i] = 'a' then.

s[i] := 'b'; writeln (s);

Во введенной строке удалить пробелы между первым и вторым вопросительным знаком.

var.

str: string;

q1, q2, l, i: byte;

begin.

readln (str);

l := length (str);

q1 := 0; q2 := 0;

for i:=1 to l do.

if str[i] = '?' then begin.

q1 := i;

break;

end;

for i:=q1+1 to l do.

if str[i] = '?' then begin.

q2 := i;

break;

end;

if (q1 0) and (q2 0) then begin.

q1 := q1 + 1;

while q1 < q2 do.

if str[q1] = ' ' then begin.

delete (str, q1,1);

q2 := q2−1;

end.

else.

q1 := q1 + 1;

writeln (str);

Оставить в строке только один экземпляр каждого встречающегося символа.

var.

s1,s2,s3: string;

i: byte;

begin.

write ('String: ');

readln (s1);

s2 := '';

for i:=1 to length (s1) do begin.

s3 := copy (s1,i, 1);

if pos (s3,s2) = 0 then.

s2 := s2 + s3.

end;

writeln ('String: ', s2);

Найти максимальный элемент численного массива.

var.

arr: array[1.m] of byte;

max_num, max_index: byte;

i: byte;

begin.

randomize;

for i := 1 to m do begin.

arr[i] := random (100);

write (arr[i]: 3);

end;

max_index := 1;

max_num := arr[1];

for i := 2 to m do.

if arr[i] > max_num then begin.

max_index := i;

max_num := arr[i];

end;

writeln;

writeln ('Max = ', max_num);

writeln ('position: ', max_index);