Что такое индекс в одномерном массиве

Введение

Линейные алгоритмы

Алгоритмы с ветвлением

Алгоритмы с повторением

Одномерный массив (вектор)

Двумерный массив (матрица)

Пользовательские процедуры и функции

Строки

Множества

Записи

Файлы

Одномерные массивы

I. Объявление массивов

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

Количество элементов и их номера задаются с помощью типа индекса ( индексом называется значение, по которому элементы массива отличают один от другого, например, индексами могут быть 1, 2, 10, ‘a’, false и т.д.). Тип индекса — это один из следующих: ограниченный целый тип ( byte может быть без ограничения), символьный тип (ограниченный или целиком), логический тип и любой перечислимый тип. Вещественный тип типом индекса служить не может. Чаще всего используется целый ограниченный тип, тогда об индексе элемента говорят как о его номере. Пример описания массива:

var A: array [1..10] of integer;

Здесь тип элементов — integer, тип индекса — ограниченный целый тип 1..10. В этом массиве индексами элементов будут целые числа 1, 2, 3, 4,5, 6, 7, 8, 9, 10.

А в массиве var A: array [5..12] of integer;

индексами являются 5, 6, 7, 8, 9, 10, 11, 12.

Назначение индекса — указать, какой из элементов массива имеется в виду, ведь имя-то у всех одно и тоже. Поэтому если написано A[7], то очевидно, что это элемент массива A с индексом 7. Причем в первом массиве это будет седьмой элемент, а во втором — третий, так что порядковый номер элемента в массиве и его индекс — это далеко не одно и тоже. Как определить, сколько в массиве элементов? Их там столько же, сколько различных индексов в типе индекса (в первом массиве — 10, во втором — 8).

Синтаксис описания одномерного (т.е. с одним индексом) массива:

Если в качестве индексов используются номера (целые числа), синтаксис можно несколько конкретизировать:
array [.. ] of
и задают первый и последний номер элемента соответственно.
Примеры:
var A, B: array [‘a’..’z’] of integer;
var C: array [ boolean] of real;
var D: array [(red, green, blue)] of char;
var E: array [100..150] of boolean;

Внимание! В описании типа индексов нельзя использовать переменные. Во многих задачах необходимо «ввести массив из n элементов». Однако нельзя объявить массив как var A: array [1.. n] of integer;
если n — переменная. Границы изменения индекса должны задавать только константы . Рекомендуется в таких случаях вместо n в объявлении массива указывать максимально возможное (в пределах разумного) число элементов, например:
var A: array [1..50] of integer;
а потом указать, что n не должно превышать 50-ти.
Рекомендуется также давать имена типам массивов, если массивов в задаче больше одного. Например, так:
type massiv = array [1..50] of integer;
var A, B: massiv;
Иначе может возникнуть несовместимость типов.

II. Имена элементов массива

Следующий вопрос: как указать имя конкретного элемента массива? Имен-то у них нет?
Необходимо указать имя массива, откуда берется элемент и индекс этого элемента в данном массиве:
[]
Например, для массива
var A: array [1..50] of integer;
5-тый элемент имеет имя A[5], а для массива С из предыдущего пункта второй элемент называется С[ true]. В квадратных скобках может указываться не только константа, но и выражение (выражение должно иметь результат того же типа, что и тип индекса). Для массива A это целое выражение, например A[i+k-1], а для массива C — логическое (т.к. типом индекса у него служит логический), например С[(y>0) and (x
<>2)]. В таком случае индексом будет результат вычисления этого выражения. Если i = 7, k = 3, x = 11, y =5.5, это будут соответственно элементы A[9] и C[true].

III. Ввод и вывод одномерных массивов

Массивы нужно вводить (и выводить) поэлементно. Почему? Да потому, что оператор readln способен прочитать только значения типов integer, real и char и их простых производных. А массив — это несколько переменных, и их нужно читать по одной.
Массивы вводят и выводят с помощью цикла (понятно, почему ввод массива — циклическое действие?). Для любых одномерных массивов эти циклы очень похожи. Их общий вид:

Здесь: должна иметь тип индекса или базовый для него (например, для индекса ограниченного целого типа может быть целой).
Замените названия в <> на названия и значения Вашей задачи — и получите нужные циклы ввода и вывода массива.
Например, для массива

var A: array [1..50] of integer;
var i: integer;
они выглядят так:

for i := 1 to 50 do
begin
write(‘Введите A[‘, i, ‘]=’);
readln(A[i]);
end;

IV. Примеры решения задач с использованием массивов.

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

«Линейная» схема решения:
1. Ввести массив.
2. Подсчитать количество нечетных положительных элементов.
3. Вывести результат.

Ввод-вывод уже разобран. Только: чтобы ввести n элементов, надо сначала ввести n, и в цикле ввода задать его в качестве верхней границы (если нижняя равна 1). Осталось только выяснить, как считать требуемые элементы. Это просто: для каждого элемента проверить, является ли он положительным и не делится ли на два, и если оба условия выполнены, добавить к количеству положительных нечетных чисел единицу. Не правда ли, очевидно циклические действия? Перед тем, как начать цикл проверки, количество положительных нечетных надо, конечно, обнулить. Получаем следующий алгоритм:

1. Ввести n. Если n меньше нуля или больше максимального значения то вывести сообщение «Неверные исходные данные», иначе
2. Ввести массив из n элементов
3. Обнулить количество положительных нечетных элементов
4. Для каждого элемента массива от 1 до n:
если элемент > 0 и не делится на 2 то увеличить количество положительных нечетных элементов на 1
5. Вывести количество положительных нечетных элементов
На основании которого напишем программу на Паскале (количество положительных нечетных элементов будем хранить в переменной count):

program prim1;
uses crt;
type massiv: array [1..50] of integer;
var a: massiv;
n, i, count: integer;
begin
clrscr;
textcolor(yellow);
writeln(‘Определение количества положительных нечетных элементов’);
write(‘Введите n=’);
readln(n);
if (n<0) or (n>50) then writeln(‘n должно быть больше 0 и меньше 50’)
else
begin
for i := 1 to n do
begin
write(‘Введите a[‘, i, ‘]=’);
readln(a[i]);
end;
count := 0;
for i := 1 to n do
begin
if (a[i] > 0) and (a[i] mod 2 = 0) then count := count + 1;
end;
writeln(‘В этом массиве таких элементов ‘, count);
end;
readln;
end.

Еще один пример.

Ввести массив из вещественных чисел длины n и преобразовать по правилу: от каждого положительного элемента взять sin, от каждого отрицательного — cos. Нули не трогать. Получившийся массив вывести.

1. Ввести n. Если n меньше нуля или больше максимального значения, вывести сообщение «Неверные исходные данные», иначе
2. Ввести массив из n элементов
3. Для каждого элемента массива от 1 до n:
4. если элемент > 0 то занести на его место sin от него
если элемент < 0 то занести на его место cos от него
5. Вывести массив

Индексы одномерного массива.

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

Пример 30. Дана последовательность вещественных чисел X1, Х2, X3. Х24. Требуется вычислить U = X1 • Х2 • Х3 • X4 + X4 • Х6 • Х7 • Х8 + . + Х21 • Х22 • X23 • Х24

Для программирования необходимо линейную формулу U преобразовать к следующему виду:

Нетрудно заметить, что задача сведена к двойному арифметическому циклу. Для накопления суммы по I используется переменная U, исходное состояние которой равно 0. Для накопления произведения используется рабочая переменная Р, которая рассчитывается шесть раз для значений индекса I=1,2,…,6. Вы можете скачать realtek hd, новую версию драйверов, которая подойдет для Windows 8.1. Для накопления произведения начальное значение J принимается равным 1.

PROGRAM PR30;
VAR
X: ARRAY [1.. 24] OF REAL;
I, J: INTEGER;
U, P: REAL;
BEGIN
WRITELN(‘Введите массив X, из 24 вещественных чисел’);
FOR I := 1 ТО 24 DO READ(X[I]);
U := 0;
FOR I := 1 TO 6
DO BEGIN
P := 1;
FOR J := 1 TO 4
DO P:=P*X[4*(I-1)+J];
U := U + P
END;
WRITELN(‘U =’, U:10:2)
END.

Индексный массив

Индексный массив (в некоторых языках программирования также таблица, ряд) — именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу (в отличие от списка).

Индекс массива — целое число, либо значение типа, приводимого к целому, указывающее на конкретный элемент массива.

В ряде скриптовых языков, например JavaScript, PHP, Ruby применяются также ассоциативные массивы, в которых переменные не обязаны быть однотипными, и доступ к ним не обязательно осуществляется по индексу.

Общее описание

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

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

Пример статического массива на языке Паскале —

 a: array [1..15] of Integer; multiArray : array [Byte, 1..5] of Char; rangeArray : array [Word] of String;

Пример статического массива на С/С++ —

int Array[10]; // Одномерный массив целых чисел размера 10 // Нумерация элементов от 0 до 9 double Array[12][15]; // Двумерный массив вещественных чисел двойной точности // размера 12 на 10. // Нумерация по столбцам от 0 то 11, по строкам от 0 до 14

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

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

Объявление типа «массив» в языке Паскаль —

type TArrayType = array [0..9] of Integer; (* Объявления типа "массив" *) var arr1, arr2, arr3: TArrayType; (* Объявление трёх переменных-массивов одного типа *)

Специфические типы массивов

Динамические массивы

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

Пример динамического массива на Delphi

byteArray : Array of Byte; // Одномерный массив multiArray : Array of Array of string; // Многомерный массив

Пример динамического массива на Си

float *array1; // Одномерный массив int **array2; // Двумерный массив array1 = (float*) malloc(10 * sizeof(float)); // выделение 10 блоков по sizeof(float) байт каждый array2 = (int**) malloc(16 * sizeof(int*)); // выделение 16 блоков по sizeof(int*) байт каждый. Сюда будут записаны указатели на одномерные массивы-строки for(i = 0; i  16; i++) array2[i] = (int*) malloc(8 * sizeof(int)); // выделение 8 блоков по sizeof(int) байт каждый. Это одномерные массивы - строки матрицы.

Пример динамического массива на С++

float *array1; // Одномерный массив int **array2; // Многомерный массив array1 = new float[10]; // выделение 10 блоков размером типа float array2 = new int*[16]; // выделение 16 блоков размером типа указателя на int for(int i = 0; i  16; i++) array2[i] = new int[8];

Гетерогенные массивы

Гетерогенным называется массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных. Массив, хранящий указатели на значения различных типов, не является гетерогенным, так как собственно хранящиеся в массиве данные относятся к единственному типу — типу «указатель». Гетерогенные массивы удобны как универсальная структура для хранения наборов данных произвольных типов. Отсутствие их поддержки в языке программирования приводит к необходимости реализации более сложных схем хранения данных. С другой стороны, реализация гетерогенности требует усложнения механизма поддержки массивов в трансляторе языка. Гетерогенный массив как встроенный тип данных присутствует в языке PHP.

Массивы массивов

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

Реализация

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

Под массив выделяется непрерывный блок памяти объёмом S*m₁*m₂*m₃…m_n, где S — размер одного элемента, а m₁…m_n — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
При обращении к элементу массива A[i₁, i₂, i₃, …, i_n] адрес соответствующего элемента вычисляется как B+S*((…(i_1p*m₁+i_2p)*m₂+…+i_(n-1)p)*m_n-1+i_np), где B — база (адрес начала блока памяти массива), i_kp-значение k-го индекса, приведённое к целому с нулевым начальным смещением.

Таким образом, адрес элемента с заданным набором индексов вычисляется так, что время доступа ко всем элементам массива одинаково.

Первый элемент массива, в зависимости от языка программирования, может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения заданного программистом (n-based). Отсчет индекса элемента массивов с нуля более характерен для низкоуровневых ЯП, однако этот метод был популяризирован в языках более высокого уровня языком программирования С.

Более сложные типы массивов — динамические и гетерогенные — реализуются сложнее.

Достоинства

легкость вычисления адреса элемента по его индексу (поскольку элементы массива располагаются один за другим)
одинаковое время доступа ко всем элементам
малый размер элементов: они состоят только из информационного поля

Недостатки

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

См. также

Ассоциативный массив
Дерево отрезков
V-список
Параллельный массив

Ссылки

Массив — Array в Delphi
Массив — Array в PHP
Массивы в PHP — Индексные, ассоциативные и многомерные массивы

Структуры данных

ИНФОРМАТИКА 1.1.

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

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

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

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

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

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

Далее, в перечне переменных указывается имя массива и через двоеточие указывается имя нового типа данных:

Массив может быть описан и без представления типа в разделе описания типов данных:

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

Чаще всего в качестве типа индекса используется интервальный целый тип.

Что такое индекс в одномерном массиве