Как упорядочены элементы массива в памяти компьютера

Обновлено: 08.07.2024

5. ОДНОМЕРНЫЕ И ДВУМЕРНЫЕ МАССИВЫ (ТАБЛИЦЫ)

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

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

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

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

Пример: числовая последовательность четных натуральных чисел 2, 4, 6, . N представляет собой линейный массив, элементы которого можно обозначить А[1]=2, А[2]=4, А[3]=6, . А[К]=2*(К+1), где К — номер элемента, а 2, 4, 6, . N — значения. Индекс (порядковый номер элемента) записывается в квадратных скобках после имени массива.

Например, A[7] — седьмой элемент массива А; D[6] — шестой элемент массива D.

Для размещения массива в памяти ЭВМ отводится поле памяти, размер которого определяется типом, длиной и количеством компонент массива. В языке Pascal эта информация задается в разделе описаний. Массив описывается так:

— описывается массив В, состоящий из 5 элементов и символьный массив R, состоящий из 34 элементов. Для массива В будет выделено 5*6=30 байт памяти, для массива R — 1*34=34 байта памяти.

Базовый тип элементов массива может быть любым, за исключением файлового.

Заполнить массив можно следующим образом:

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

Задача 1. Заполнить одномерный массив элементами, отвечающими следующему соотношению:

a ₁ =1; a ₂ =1; a _i =a _i _-2 +a _i _-1 (i = 3, 4, . n).

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

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

2) ввод значений элементов массива с клавиатуры используется обычно тогда, когда между элементами не наблюдается никакой зависимости. Например, последовательность чисел 1, 2, -5, 6, -111, 0 может быть введена в память следующим образом:

Над элементами массивами чаще всего выполняются такие действия, как

а) поиск значений;

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

в) подсчет элементов в массиве, удовлетворяющих заданному условию.

Cумму элементов массива можно подсчитать по формуле S=S+A[I] первоначально задав S=0. Количество элементов массива можно подсчитать по формуле К=К+1, первоначально задав К=0. Произведение элементов массива можно подсчитать по формуле P = P * A[I], первоначально задав P = 1.

Задача 3. Дан линейный массив целых чисел. Подсчитать, сколько в нем различных чисел.

Тест: N = 10; элементы массива - 1, 2, 2, 2, -1, 1, 0, 34, 3, 3. Ответ: 6.

Задача 4. Дан линейный массив. Упорядочить его элементы в порядке возрастания.

Тест: N = 10; элементы массива - 1, 2, 2, 2, -1, 1, 0, 34, 3, 3.

Ответ: -1, -1, 0, 1, 2, 2, 2, 3, 3, 34.

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

типы переменных A, B эквивалентны, и поэтому данные переменные совместимы по присваиванию; тип переменных C, D также один и тот же, и поэтому данные переменные также совместны по присваиванию. Но тип переменных C, D не эквивалентен типам переменных A, B, E, поэтому, например, A и D не совместны по присваиванию. Эти особенности необходимо учитывать при работе с массивами.

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

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

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

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

Массив является структурированным (составным) типом данных. Это означает, что величина, описанная как массив, состоит из конечного числа других величин. Так, например, можно создать массивы из 10 целых или 100 вещественных чисел. Тип элементов массива называют базовым типом. Все элементы массива упорядочены по индексам (номерам элементов), определяющим местоположение элемента в массиве. В языке С++ элементы массива всегда нумеруются с нуля.

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

Впервые тип данных массив появился в языке Фортран (создан в период с 1954 по 1957 г. в корпорации IBM). Уже первые версии языка поддерживали трехмерные массивы (в 1980 г. максимальная размерность массива была увеличена до 7). Массивы были необходимы для создания математических библиотек, в частности содержащих процедуры решения систем линейных уравнений.

Пример 11.1. В 10 А классе 25 учащихся. Известен рост каждого в сантиметрах. Для хранения значений роста можно использовать массив А, состоящий из 25 целых чисел.

Индекс каждого элемента — порядковый номер учащегося из списка в классном журнале. Поскольку элементы массива нумеруются от нуля, то запись а[5] — рост ученика, который в журнале записан под номером 6.

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

Индекс элемента — номер дня в декабре со сдвигом на 1. Запись t[15] — температура воздуха 16 декабря.

Пример 11.3. В 10 Б классе 27 учащихся. В классном журнале указаны фамилия и имя каждого учащегося. Для хранения списка учащихся можно использовать массив s , состоящий из 27 строк.

Индекс каждого элемента — порядковый номер ученика из списка в классном журнале. Тогда запись s[5] — фамилия и имя учащегося под № 6.

Пример 11.4. Обращение к элементу массива: а[3], t[i], s[n-1] .

Язык программирования С++ поддерживает работу с массивами, которые достались ему в наследство от языка С. Однако работа с такими массивами требует глубокого понимания того, как они размещаются в памяти компьютера. В качестве альтернативы рекомендуется использовать шаблоны классов, которые описаны в стандартной библиотеке: array<> и vector<>.

11.2. Описание массивов

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

Для работы с типом данных vector необходимо подключить одноименную библиотеку:

Для создания вектора используется следующая команда:

vector < тип элементов > имя_массива ( количество элементов );

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

Тип элементов задает значение базового типа для данного массива. Базовый тип может быть любым из известных вам типов (примеры 11.5–11.7).

Размер массива — количество элементов в нем.

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

Пример 11.5. Опишем массив, рассмотренный в примере 11.1. Размер описанного массива 25 элементов.

vector < int > a ( 25 );

Пример 11.6. Опишем массив, рассмотренный в примере 11.2. Размер описанного массива — 31 элемент.

vector < double > t ( 31 );

Пример 11.7. Опишем массив, рассмотренный в примере 11.3.

vector < string > s ( 27 );

Пример 11.8. Опишем массив, всем элементам которого вначале присваивается значение –1:

vector < int > a ( 25 , -1 );

11.3. Операции над массивами

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

Векторы можно сравнивать. При сравнении используют операции сравнения «==» и «!=». Векторы равны, если они содержат одинаковые элементы на тех же позициях, иначе они не равны.

Другие операции для массива как для типа данных не определены.

Пример 11.9. Пусть массивы a и b описаны следующим образом:

vector < int > a ( 25 ), b ( 30 );

В результате выполнения команды:

размер массива a будет увеличен до 30 элементов, все элементы в массиве a будут иметь те же значения, что и в массиве b .

В результате выполнения команды:

размер массива b будет уменьшен до 25 элементов, все элементы в массиве b будут иметь те же значения, что и в массиве a . Значения последних 5 элементов, которые исходно были в векторе b , будут потеряны.

Пример 11.10. Операции над индексированными переменными:

sr = ( t [ 0 ] + T [ 29 ]) / 2 ;

b [ k ] = a [ k ] * 2 ;

if ( s [ i ] < 0 ) …

n = s [ i ]. length ();

11.4. Ввод и вывод элементов массива

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

1) определение элементов массива как констант;

2) ввод элементов массива с клавиатуры;

3) использование случайных чисел для определения значений;

4) использование функций (собственных или стандартных) для определения значений;

5) ввод элементов массива из текстового файла.

Элементам массива можно задать значения при описании (примеры 11.11, 11.12). В этом случае количество элементов не задается, а определяется автоматически.

При вводе элементов массива с клавиатуры каждый элемент должен вводится отдельно. Если количество вводимых элементов определено, то можно воспользоваться циклом for (пример 11.13).

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

При вводе строк нужно помнить, что пробел используется как разделитель. Если использовать для ввода команду cin , то элементами массива могут быть только отдельные слова строки ( пример 11.15). Если нужно, чтобы элементами массива были строки с пробелами, то для ввода необходима команда getline (пример 11.16).

Иногда бывает удобно задавать элементы массива случайным образом. Для этого используется функция rand(), которая генерирует случайное целое число из промежутка [0 ; 32768). Если элементы массива должны принадлежать отрезку [a ; b], то можно определить значение элемента массива как a[i]= rand() % (b – a + 1) + a ; (пример 11.17).

Вещественное случайное число в промежутке [0, 32.768) можно получить так: a[i]= 1. * rand() / 1000 ;

Выводить элементы массива можно в строку (пример 11.18) или в столбец (пример 11.19). Если элементы массива выводятся в строку, то между ними нужно выводить символ-разделитель (чаще всего используют пробел), иначе все числа будут распечатаны подряд как одно число с большим количеством цифр. Выводить элементы массива можно не только в прямом порядке, но и в обратном (пример 11.20).

Пример 11.21. Написать программу, которая сформирует массив из n четных чисел из отрезка [20, 70] случайным образом. Записать числа из массива в текстовый файл. Вывести на экран k -й элемент массива.

Этапы выполнения задания

I. Исходные данные: количество элементов n и массив a.

II Результат: искомый элемент.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Генерация массива.

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

3. Ввод значения k и вывод результата.

IV. Описание переменных:

n, k – int, a – vector <int>.

Пример 11.22. Написать программу, которая прочитает из текстового файла список фамилий учащихся, запишет их в массив и выведет из списка фамилии с номерами от k1 до k2 .

Этапы выполнения задания

I. Исходные данные: массив s и количество учащихся n, номера фамилий – k1 и k2 .

II. Результат: список заданных фамилий.

III. Алгоритм решения задачи.

Ввод исходных данных.
2. Вывод результата.

IV. Описание переменных:

n, k1, k2 – int, a – vector <string>.

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

Пример 11.11. Описание числового массива, элементы которого являются константами.

Пример 11.12. Описание массива, элементы которого являются строковыми константами.

Пример 11.13. Ввести элементы массива a с клавиатуры.

vector < int > a ( 10 );

cout << "vvedi 10 chisel" << endl ;

for ( int i = 0 ; i < 10 ; i ++)

Пример 11.14. Ввести заданное количество элементов массива a .

cout << "kol-vo chisel" << endl ;

vector < int > a ( n );

cout << "vvedi chisla" << endl ;