В программировании часто встречаются задачи, связанные с хранением и обработкой большого количества однотипных данных. Например, требуется ввести оценки по информатике для 25 студентов группы ИС-09 и определить средний балл. Для решения этой задачи опишем 25 переменных: is09_1, is09_2,is09_3, …, is09_25:
int is09_1, is09_2, is09_3, …, is09_25;
Каждая из них будет соответствовать одному студенту. После этого используем 25 операторов для ввода оценок:
А что произойдет, если нужно будет решить эту задачу для всего университета? Описать и вводить несколько тысяч переменных?
Для решения таких задач используют массивы. Для структур, используемых в алгоритмизации, организация массивов представляется наиболее удобной для программирования. Это связано с возможностью непосредственного логического доступа к любому их элементу без обращения к предыдущим элементам, что обеспечивает простоту интерфейса между логической организацией данных и их физическим представлением, поскольку массив легко проецируется на оперативную память. Это обстоятельство оказалось столь удобным для программирования, что для большинства структур данных разработаны механизмы их эмуляции на базе массивов.
Массив состоит из конечного числа элементов (компонент), содержимое которых относится к некоторому общему, базовому типу. При этом сам базовый тип должен быть таким, что принадлежность к нему гарантирует одинаковые размеры памяти для размещения каждой из компонент. Элементы различаются местом их размещения внутри структуры, иначе говоря, номером или индексом. Обычным является непрерывное представление массива, как логическое, так и физическое, то есть логический (описанный в программе) массив проецируется на непрерывный участок оперативной памяти. Значит, необходимо, чтобы такой участок существовал. Отсюда вытекают ограничения на размер массива, диктуемые организацией оперативной памяти: массив должен поместиться в сегмент данных программы, размеры которого фиксированы. И, конечно, данные в массивах сохраняются только до конца работы программы.
Таким образом, массив представляет собой структуру данных, определяемую на основе следующих своих свойств:
1. массив состоит из однотипных элементов, при этом используемый тип называется базовым,
2. число элементов массива строго фиксировано,
3. элементы массива упорядочены в том смысле, что каждому из них соответствует один или несколько индексов, позволяющих однозначно указать его расположение в составе структуры,
4. количество индексов, которое связано с отдельным элементом массива, определяет его размерность (одномерные, двумерные, трехмерные …),
5. число элементов массива совпадает с общим количеством возможных значений его индексов,
6. массив – именованная совокупность данных, причем использование его имени совместно с индексами позволяет определять значения его элементов,
7. доступ к элементам массива является прямым, то есть любой элемент массива полностью определяется своими индексами, и возможности доступа к нему не зависят от других элементов.
Массивы можно определить и через понятия математики.
В современной математике для описания и решения многих задач используются матрицы и вектора.
МатрицейAnm называется таблица чисел, состоящая из n строк и m столбцов.
Каждый элемент матрицы aij полностью определяется своими индексами – номерами строки i и столбца j , в которых он расположен.
Количество индексов определяет размерность матрицы: одномерная (вектор), двумерная, трехмерная и т.д.
Максимальное значение каждого индекса определяет размер матрицы.
В качестве аналога матриц в программировании выступают массивы.
Массив – это упорядоченный набор фиксированного количества однотипных компонентов, имеющих общее имя – имя массива, и различающихся значениями своих индексов. В зависимости от количества индексов компонентов (элементов) массива различают одномерные (вектора), двумерные (матрицы) и т.д. массивы.
Элементы векторов хранятся в оперативной памяти компьютера в расположенных друг за другом ячейках в том порядке, в котором они размещены в векторе. Таким образом, структура вектора полностью соответствует структуре оперативной памяти компьютера, поэтому остальные структуры данных размещаются в памяти так, как они размещались бы в одномерных массивах.
Двумерный массив состоит из элементов, образующих прямоугольную таблицу, причем первый индекс элемента обозначает номер строки, а второй – номер столбца этой таблицы, на пересечении которых расположен данный элемент:
a11 a12 a13 …
a21 a22 a23 …
a31 a32 a33 …
……………………..
Таким образом, двумерный массив полностью соответствует понятию матрицы. В оперативной памяти элементы двумерного массива расположены последовательно, строка за строкой: сначала элементы первой строки, затем второй и так далее: a11, a12, a13,…, a21, a22, a23,…, a31, a32, a33,… Значит, быстрее изменяется второй индекс (номер столбца), чем первый (номер строки).
Многомерные массивы располагаются в памяти компьютера так, что сначала изменяется последний индекс элемента, затем – предпоследний и так далее.
Массив как структура данных характеризуется тем, что с помощью индексов обеспечивается прямой (непосредственный) доступ к каждому его элементу: чтение или запись любого элемента массива не зависит от того, прочитаны или записаны предшествующие ему элементы.
Тип элементов массива называется его базовым типом. В Си это может быть любой стандартный (целый, вещественный, символьный) или пользовательский (массив структур, файлов, функций) тип данных.
Индексы элементов массива могут быть только целыми положительными числами и начинаются с нуля. Перед использованием массива в программе его необходимо описать – назвать его имя, указать его размеры (количество элементов, строк, столбцов …) и базовый тип:
int vect[5];
float matr[2][3];
char str[20];
Описаны:
- одномерный массив целых чисел (вектор) vect, состоящий из пяти элементов,
- двумерный массив (матрица) вещественного типа matr, имеющая две строки и три столбца,
- строка символов str из 20 элементов.
Как видно, при описании массива в Си каждая его размерность записывается в отдельных скобках, а не перечисляется через запятые, как в Паскале. Размеры массива можно задать именованной константой или указать в директиве #define – это считается хорошим стилем программирования:
#define count 5
#define row 2
#define col 3
#define n_str 20
int vect[count];
float matr[row][col];
char str[n_str];
Индексы элементов массивов в Си всегда начинаются с нуля, поэтому, например, описанный вектор vect имеет следующие элементы:
vect[0] vect[1] vect[2] vect[3] vect[4]
а двумерный массив matr – 6 следующих элементов:
matr[0][0] matr[0][1] matr[0][2]
matr[1][0] matr[1][1] matr[1][2]
То есть, первая строка и первый столбец двумерного массива имеют индекс 0.
Элементы массива можно использовать во всех выражениях, операторах и функциях, определенных для их типа.
Начальные значения элементам массива в Си можно задавать при их описании (инициализировать массив), при этом размеры одномерных массивов (векторов) в квадратных скобках можно не указывать – для их хранения будет отведено столько ячеек оперативной памяти, сколько значений указано в фигурных скобках:
int vect[] = {-5, 3, -2, 8, 1};
float matr[2][3] = {{0.2, -1.5, 3.14},
{-2.73, 25.54, 0.89}};
Если задано значений меньше, чем описано элементов вектора, то недостающие элементы инициализируются нулями:
int vect[5] = {-5, 3, -2};
Последние два элемента вектора vect инициализируются нулями.
Еще раз необходимо обратить внимание на то, что, в отличие от Паскаля, при описании и при работе с многомерными массивами в Си каждый индекс элемента массива заключается в отдельные квадратные скобки:
matr[1][2]=0.89;
Если использовать запись matr[1,2], то она будет интерпретироваться как matr[2]. Согласно правилам языка Си, значением всего выражения в скобках является результат вычисления последнего выражения, перед которым стоит запятая.
В отличие от Паскаля, конкретные размеры массива в Си можно задать с клавиатуры до его описания:
printf(“\n row=”);
scanf(“%d”, &row);
printf(“\n col=”);
scanf(“%d”, &col);
float matr[row][col];
Пример: ввести с экрана элементы целочисленного массива matr33, вывести его на экран, транспонировать (заменить строки соответствующими столбцами) и снова вывести на экран:
#include <stdio.h>
#include <conio.h>
#include <math.h>
{
const int row=3, col=3;
int matr[row][col];
printf(“\nВведите 3 элемента нулевой строки через пробелы: ”);
Алгоритм – это последовательность предписаний (команд), точное выполнение которых приводит к решению поставленной задачи.
Правильно построенные алгоритмы должны обладать следующими свойствами:
дискретность - алгоритм разбит на отдельные элементарные этапы (шаги), возможность выполнения которых не вызывает сомнений,
однозначность - команды, входящие в алгоритм, должны быть точными и понятными, порядок их выполнения должен быть единственно возможным, любая неопределенность или двусмысленность недопустима,
детерминированность - повтор результатов при повторе исходных данных,
результативность - алгоритм должен приводить к результату за конечное число шагов,
массовость - алгоритм должен быть пригоден для решения всех задач данного класса.
