Работа с массивами в языках Си и Си++ (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ВОЛЖСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО

УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

КАФЕДРА «ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ»

,

Работа с массивами в языках Си и Си++

Методические указания

Волгоград 2013

УДК 004.056

Рецензент:

канд. тех. наук доцент

Издается по решению редакционно-издательского совета

Волгоградского государственного технического университета

Лясин, О. Ф.. Работа с массивами в языках Си и Си++

[Электронный ресурс]: методические указания / , //Сборник «Методические указания» Выпуск.-Электрон. текстовые дан.(1файл:207 Kb) – Волжский: ВПИ (филиал) ВолгГТУ,2013.-Систем. требования:Windows 95 и выше; ПК с процессором 486+; CD-ROM.

Содержатся сведения, необходимые для знакомства с одним из основных структурированных типов данных в языках программирования высокого уровня - массивами. Рассмотрены синтаксические особенности определения одномерных и двумерных массивов в языках программирования Си и Си++, как для статического, так и для динамического вариантов. Представлены типовые алгоритмы обработки информации в массивах: ввод и вывод, поиск максимума/минимума, суммы элементов, сортировки, перестановки строк и столбцов. В практической части лабораторной работы студенту предлагается самостоятельно программно реализовать обработку информации в одномерном и двумерном массивах. Приведены задания к лабораторной работе, контрольные вопросы для проверки усвоения материала, порядок выполнения лабораторной работы.

Предназначены для студентов, обучающихся по направлению 230100 "Инфор­матика и вычислительная техника" и направлению 231000 "Программная инженерия" всех форм обучения в рамках курса «Основы программирования»

Ил.10. Библиогр.: 7 назв.

Издается по решению редакционно-издательского совета Волгоград­ского государственного технического университета

© Волгоградский государственный

технический университет, 2013

© Волжский политехнический институт, 2013

Лабораторная работа №5

Работа с массивами в языках Си и Си++.

Цель: познакомиться с основными принципами программирования с использованием структурированного типа данных массив, усвоить синтаксические особенности определения и работы с массивами в языках Си и Си++, получить навык практического программирования с использованием одно - и двумерных массивов.

Общие сведения:

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

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

Рассмотрим, как определяется самый массив в языке Си в самом простом – статическом одномерном – случае. Определение подобного массива выглядит следующим образом:

класс_памяти тип имя_массива [константное_выражение]

={иниициализатор};

Тип задает тип элементов объявляемого массива. Элементами массива не могут быть функции (но могут быть указатели на них) и элементы типа void.

Имя_массива – идентификатор, под которым массив будет доступен в программе.

Константное_выражение в квадратных скобках задает количество элементов массива.

Инициализатор позволяет присвоить начальные значения элементам массива еще на этапе определения (необязательная часть определения).

Класс_памяти определяет, к какому классу памяти будет относиться массив (необязательная часть определения). Для массивов допустимыми являются все классы памяти, кроме регистрового.

Примеры определения массивов в программе:

int sample [I0]; //определяем массив из 5-ти целых чисел

static float mas[5]; //определяем статический массив из 5-ти вещественных

//элементов

extern int m[];//описываем массив m, определенный в другом месте программы

const int N=20;

double array[N*2]; //задаем размер массива через именованную константу

#define Nmax 10

int sample [Nmax] //задаем размер массива через макроимя

Определение массива резервирует в памяти непрерывный блок размером количество_элементов_массива*размер_элемента_в байтах. Каждый элемент массива доступен под своим индексом. Важной особенностью языков Си и Си++ является индексирование элементов массива с 0. На рис.1 изображен снимок памяти для массива целых чисел из 5-ти элементов. Стрелкой показано направление возрастание адресов.

int mas[5];

Рис.1. Одномерный массив из пяти целых чисел в памяти.

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

int N;

cout<<”Введите количество элементов массива”;

cin>>N;

int mas[N]; //ошибка, размер массива задается не константой

Если количество элементов N, объединяемых в массив, заранее неизвестно, то придется либо определять массив заведомо большего размера, а использовать только первые N элементов (этот вариант неэффективно расходует память), либо использовать динамические массивы, на которые требование о предопределенности размера не распространяется (динамические массивы будут рассмотрены ниже в настоящих методических указаниях).

При объявлении массива константное_выражение может быть опущено в случаях, если:

- при определении массив явно инициализируется,

- массив объявлен как формальный параметр функции,

- имеет место описание массива, явно определенного в другом месте программы (ниже по тексту текущего модуля или в другом модуле).

Инициализация массива выглядит следующим образом:

int mas[5]={10, 20, 30, 40, 50};

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

int mas[]={1, 2, 3, 4}; //выделяем память под 4 элемента

Размер массива в таком случае всегда можно определить, разделив размер всего массива на размер одного элемента:

int masSize=sizeof(mas)/sizeof(m[0]);

Если количество выражений в инициализаторе K меньше, чем объявленный размер массива N, то начальные значения получат только первые K элементов, а остальные будут инициализированы по умолчанию в соответствии с классом памяти массива. Если же окажется, что K>N, компилятор зафиксирует ошибку.

int mas[5]={1, 2, 3}; //последние два элемента не получат значения

int mas2[6]={1, 2, 3, 4, 5, 6}; //ошибка, слишком длинный инициализатор

int mas3[5]={1, ,2, , 3}; //ошибка, опускать выражения можно только в конце

//списка

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

имя_массива[целочисленное_выражение]

Значение этого выражения равно элементу массива с индексом, равным выражению в скобках. Как уже отмечалось, первый по порядку элемент массива получает индекс 0. Таким образом, для массива mas из n элементов можно обращаться к элементам от mas[0] до mas[n-1]. Необходимо отметить, что программа не отслеживает корректность используемых при обращении к массиву индексов, поэтому если программист будет использовать некорректные значения индексов (отрицательные или большие чем n-1), то это приведет к обращению к ячейкам памяти, располагающихся перед или после массива и может нарушить целостность других объектов программы.

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

int mas[5];
mas[0]=1;
cin>>mas[1];
int i=2;
mas[i+1]=mas[i];

При работе с массивами в программе характерны циклы перебора всех (или какой-то части) элементов массива. Вот как, например, можно присвоить всем элементам массива случайные числа:

const int N=10;

int mas[N];

for(int i=0; i<N;i++) //перебираем все элементы массива от 0 до N-1

mas[i]=rand();

Рассмотрим несколько типовых алгоритмов обработки информации в одномерных массивах. Если необходимо вычислить сумму элементов массива:

const int N=10;

int mas[N];

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

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

cin>>mas[i];

//в переменной Sum будет накапливать сумму

int Sum=0; //начальное значение суммы - 0

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

Sum+=mas[i]; //прибавляем к уже накопленной сумме значение

// i-го элемента массива

cout<<Sum;

Для поиска максимального элемента массива применяем следующий алгоритм: в переменной imax будем хранить номер максимального из всех уже рассмотренных элементов массива. Присвоим этой переменной 0, тем самым делая предположение, что максимален первый по порядку элемент массива. После этого перебираем остальные элементы массива и сравниваем их со значением текущего максимума – значения mas[imax]. Если очередной элемент больше текущего максимума – он сам становится таковым. Когда с текущим максимумом сравним все элементы массива, в imax будет хранится номер максимального элемента всего массива и остается только вывести его и само значение максимума на экран.

Рис.2. Схема алгоритма поиска максимального элемента массива и его программная реализация.

Теперь решим задачу изменения порядка следования элементов массива на обратный. Анализ задачи показывает, что требуется попарно обменивать значения элементов массива: 0-го с последним, 1-го с предпоследним и т. д., а в общем случае: i-го c (N-1-i)-м. С этой задачей справляется следующий код.

int tmp;
for ( i=0;i<N/2;i++)
{ tmp=mas[i];

mas[i]=mas[N-i-1];
mas[N-i-1]=tmp;
}

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

Еще одной важной и одной из самых часто используемых операцией с массивами является сортировка ее элементов. В чем заключается суть этой операции? Пусть необходимо упорядочить N элементов

X1, X2, ..., Xn

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

Задача сортировки: найти такую перестановку записей p1, p2, ..., pn, после которой ключи расположились бы в неубывающем порядке:

Kp(1) £ Kp(2) £...£ Kp(n)

Рассмотрим несколько популярных алгоритмов сортировки массивов.

Алгоритм сортировки пузырьком.

Последовательно сравниваем пары соседних элементов xj, xj+1 (j = 1,2,3,..., n-1) и если xj > xj+1 (здесь и далее подразумевается сортировка элементов массива по возрастанию их значения), то они переставляются. Тем самым наибольший элемент “всплывает” в конец массива. Затем этот метод применяют ко всем элементам, кроме последнего и т. д.

Рассмотрим как будет отсортирован массив из 5-ти целых чисел методом пузырька. Первоначально элементы массива имеют значения

4

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

Рис.3. Сортировка массива методом пузырька.

Программная реализация метода сортировки пузырьком приведена ниже:

const int N=5;
int m[N]={2, 3, 5, 1 ,4},t;

for(int i=N-1;i>0;i--)

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

if (m[ j ]>m[ j+1 ])
{
t=m[ j+1];
m[ j+1 ]=m[ j ];
m[ j ]=t;
}

Алгоритм сортировки выбором.

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

На рис. 4 приведен порядок сортировки того же массива алгоритмом выбором. Здесь на каждом проходе выбирается максимальный элемент (выделен красным) и переставляется с последним элементом еще не отсортированного подмассива. На следующем проходе неостортированный массив сужается на один элемент справа и процедура повторяется.

Рис.4. Сортировка массива методом выбора.

Программная реализация алгоритма сортировки выбором на языке Си:

const int N=5;

int m[N]={2,3,5,1,4};
int t, imax;

for(int i=1;i<N;i++)

{

imax=0;

for(int j=1; j<N-i+1; j++)