Массивы


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Министерство образования и науки РФ


Федеральное г
осударственное
бюджетное
образовательное
учреждение

высшего профессионального образования

«Тихоокеанский государственный университет»










Р
АБОТА С МАССИВАМИ В
C
/
C
++






Методические указания к выполнению
лабораторных работ по курсу

«Алгоритмические языки и программирование» для студентов
специальности «Программное обеспечение вычислительной техники и
автоматизированных систем» дневной формы обучения















Хабаровск

Издательство ТОГУ

2011


2


УДК 511.3


Работа с массивами в
C
/
C
++͗ методические указания к выполнению лабораторных
работ по курсу «Алгоритмические языки и программирование» для студентов
специальности «Программное обеспечение вычислительной техники и
автоматизированных систем» дневной формы о
бучения

/

сост. В.

В.

Стригунов.


Хабаровск͗ Изд
-
во Тихоокеан. гос. ун
-
та͕ 2011.


24 с.



Методические указания составлены на кафедре «
Информатика
». В них приведены
задания к двум лабораторным работам͕ посвященным одномерным и двумерным
массивам в языках

программирования
C
/
C
++͕ основным алгоритмам сортировки и
поиска.



Печатается в соответствии с решениями кафедры «
И
н
ф
о
р
м
а
т
и
к
а
» и методического
совета факультета
компьютерных и фундаментальных
наук
.




© Тихоокеанский
государственный университет͕
2011





Р
АБОТА С МАССИВАМИ В
C
/
C
++


Методические указания к выполнению лабораторных работ

по курсу
«Алгоритмические языки и программирование»

для студентов

специальности «Программное обеспечение вычислительной техники и

автоматизированных систем» дневной формы обучения


Стригунов Валерий Витальевич


Главный редактор Л.

А. Суевалова

Редактор Л.

А. Суевалова

Компьютерная верстка В.

В. Стригунов


Подписано в пе
чать
0
7
.
1
0
.
1
1
. Формат 60
x
84 1/16.

Бумага писчая. Гарнитура «Калибри». Печать офсетная.

Усл. печ. л. 1͕
39
. Тираж 100 экз. Заказ .


Издательство Тихоокеанского государственного университета.

680035͕ Хабаровск͕ ул. Тихоокеанская͕ 136.

Отдел оперативн
ой полиграфии издательства Тихоокеанского государственного университета.
680035͕ Хабаровск͕ ул. Тихоокеанская͕ 136.

3


Общие вопросы


Целью курса лабораторных занятий по дисциплине «Алгоритмические
языки и программирование» является приобретение практических навыков
по составлению алгоритмов решения задач и написания программ на
высокоуровневых языках С или С++.

В данных методических ука
заниях приведены задания к двум
лабораторным работам͕ посвященным работе с массивами в язык
ах

программирования
C

и
С++. В них подробно описаны принципы работы с
одномерными массивами͕ основные алгоритмы сортировки массивов͕
поиска в массиве заданного значе
ния͕ работа с двумерными массивами. Все
примеры и алгоритмы снабжены
детальным

описанием и программным
кодом на С++.

В ходе выполнения каждого лабораторного задания разрабатывается и
отлаживается консольная программа͕ написанная на языке
C

или
С++.
Результ
ат работы оценивается в процессе тестирования программы на
наборе контрольных примеров. Отчет по лабораторной работе должен
содержать͗



титульный лист͖



текст задания на лабораторную работу͖



краткую теоретическую часть по заданию и алгоритм͖



текст программы͖



пример выполнения программы (введенные данные и полученный
результат)͖



вывод по проделанной работе.




4


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

Под
массивом

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

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



это количество
элементов в массиве.

Примеры

описания массива͗

int

mas
[10]; //описан массив с именем
mas
, состоящий из 10


//
целочисленных

элементов

double

A
[5],
B
[7]; //описаны два вещественных массива
A

и
B
,


//
состоящие из 5 и 7 элементов


Примечание.

При описании массива используются те же модификаторы класса памяти͕
const
͕ что и для
простых переменных.

*класс памяти+ *
const
+ тип иден
тификатор
[
размер
]

*инициализация+͖


Одномерный массив соответствует математическому понятию вектора
-
строки или вектора
-
столбца.

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

Например
,

const int N = 100;

double Ar1[N];

long int Ar2[2*N];


Примечание
.

Задание р
азмер
а

массива с помощью именованных констант

позволяет в дальнейшем
упростить модификацию программы͕

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


При описании массива
его можно инициализировать. Для этого
и
нициализ
ирующие значения записываются

в фигурных скобках через
запятую. Значения элементам присваиваются по порядку. Если элементов в
массиве больше͕ чем инициализирующих значений͕ то оставшиеся элементы
обнуляются.

5


Н
ап
ример͕

int

mas
[10] = {
-
3, 1, 5};

//первые 3 элемента массива
mas


//
инициализируются значениями
-
3, 1, 5,


//
а остальные значением 0

double

A
[
5] = {0.1, 0.2, 0.3, 0.4, 0.5},


B
[7] = {0.0}; //
все элементы
массив
а

A

инициализированы


//
значениями из
списка
,
все 7 элементов


//
массива
B

инициализированы значением 0


Примечание.

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

int

C
[] = {9, 5, 1}; //
описан
массив
C

из трех элементов


Для доступа к элементу массива используется операция индексации͗
после имени массива в квадратных скобках указывается индекс (номер)
элемента.

Элементы массива нумеруются с
нуля͕ т.е. и
ндекс может
принимать значения от 0 до количеств
а

элементов массива
минус единицу
.

Обработка массива͕ как правило͕ производится в циклах.

Например
,

A
[0
] =
A
[
0
] + 10;

A[1] = A[2]*B[6];

for (int i = 0; i 10; i++) mas[i] *= 2;


В оперативной
памяти э
лементы массива располагаются непрерывно

в
соседних ячейках
.



Приме
чание.

Типичной ошибкой
начинающих программистов
при использовании массивов является
обращение к несуществующему элементу͕ т.е. выход индекса за допустимое значение.
Компилятор
яз
ыков
C
/
C
++ такие ошибки
не
отслеживает
.


Рассмотрим принципы работы с одномерными массивами на
следующих примерах.

6


Пример

1.

Вычисление суммы

квадратов элементов массива.


#include "iostream"

int main()

{


const int N = 10;


int i;


double mas[N] = {0.0},
Sum = 0.0;


//ввод массива


cout << "Введите элементы массива:
\
n";


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


{



cout "mas[" i "]
-
� ";



��cin mas[i];


}



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


for (i = 0; i N; i++) Sum = Sum + mas[i]*mas[i];



cout

"Сумма квадратов элементов
равна

" Sum "
\
n";



}


На рис. 1 показана экранная форма
приложения

с введенными исходными
данными и результатом выполнения
.



Рис. 1
.

Экранная форма приложения


Пример

2.

В
ычисл
ение

диапазон
а

значений элементов

массива

иапазон значений
равен разности

значени
я

максимального элемента
и

значени
я

минимального элемента
)
.

...

const int N = 10;

int i;

double mas[N], masMin, masMax, range;

7



//ввод массива

...

//находим минимальное и максимальное значение элементов мас
сива

masMin = mas[0]; masMax = mas[0];

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

{

if (mas[i] masMin) masMin = mas[i];

�if (mas[i] masMax) masMax = mas[i];

}


//
вычисляем

диапазон

range = masMax


masMin;


Пример

3.

Поиск индекса минимального элемента.

...

const int N =
10;

int i, indMin;

double

mas
[
N
];

...

//находим индекс минимального элемента массива

indMin = 0;

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


if (mas[i] mas[indMin]) indMin = i;

...


Методы сортировки массива

Сортировка



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


Сортировка методом выбора

Алгоритм состоит в следующем. Среди элементов массива выбирается
наименьший и меняется местами с первым. Далее рассматриваются
элементы͕ начиная со второго͕ и наименьший из них меняется местами со
вторым элементом. Так прод
олжается
N
-
1 раз. При последнем проходе
цикла при необходимости меняются местами предпоследний и последний
элементы массива.


8


#include "iostream"

int main ()

{


const int N = 9;


int mas[N] = {420, 79, 429, 53, 908, 140, 897, 594, 682};


int i, j, indMin,
temp;



for

(
i

= 0;
i


N
-
1;
i
++)


{



//принимаем за наименьший первый из рассматриваемых



//элементов



indMin = i;






//поиск номера минимального элемента из неупорядоченных



for (j = i + 1; j N; j++)




if (mas[j] mas[indMin]) indMin = j;






//обмен элементов с номерами i и indMin



temp = mas[i];



mas[i] = mas[indMin];



mas
[
indMin
] =
temp
;


}



0;

}


На рис
.

2
продемонстрирован процесс выполнения алгоритма сортировки
методом выбора. Минимальные во время поиска элементы выделены
полужирным шрифтом. Как видно͕ массив из 9 элементов сортируется за 8
проходов внешнего цикла
for
.


Исходный массив










indMin




|
420 79 429
53

908 140 897 594

682


3

1
-
й проход цикла


53
|
79

429 420 908 140 897 594

682


1

2
-
й проход цикла


53 79
|
429 420 908
140

897 594

682


5

3
-
й проход цикла


53 79

140
|
420

908 429 897 594

682


3

4
-
й проход цикла


53 79 140

420
|
908
429

897 594

682


5

5
-
й проход цикла


53 79 140 420

429
|
908 897
594

682


7

6
-
й проход цикла


53 79 140 420 429

594
|
897 908

682


8

7
-
й проход цикла


53 79 140 420 429 594

682
|
908

897


8

8
-
й проход цикла


53 79 140 420 429 594 682

897
|
908

Рис. 2
.

Пример
с
ортировк
и

методом выбора



9


Сортировка методом «пузырька»

Метод «пузырька» (или метод простого обмена) заключается в
сравнении пары соседних элементов и замене их местами͕ если первый
оказался больше второго. После этого сравнивается следующая пара и т.д.
При выполнении этой последовательности действий элементы с большими
значениями будут продвигаться (“всплывать” как пузырьки) в конец массива.


#include

iostream


int main ()

{


const int N = 9;


int mas[N] = {420, 79, 429, 53, 908, 140, 897, 594, 682};


int bound, t, j, temp;



bound = N


1;


do


{



t = 0;



for(j = 0; j = bound


1; j++)




�if (mas[j] mas[j + 1])




{





temp = mas[j];





mas[j] = mas[j + 1];





mas[j + 1] = temp;





t = j;




}



bound = t;



} while (t);



}


В начале

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

В переменной
bound

хранится индекс самого правого элемента массива͕
о котором не известно͕ занял ли он свою окончательную позицию или нет.

В переменной
t

хранится индекс самого последнего элемента массива͕
который участвовал в обмене. Если после просмотра массива переменная
t

равна 0͕ то все элементы массива упорядочены и сортировка завершена. В
противном случае͕ продолжаем просмотр массива͕ исключая элеме
нты с
индексом от
t

до
N
-
1͕ которые уже заняли свои окончательные позиции.

Пример выполнения сортировки методом пузырька для массива из 9
элементов ,420͕ 79͕ 429͕ 53͕ 908͕ 140͕ 897͕

594͕ 682- приведен на рис
.

3
.


10


Исходный массив









bound



420 79
429 53 908 140 897 594

682
|


8

1
-
й проход

цикла
do
-
while




79 420 53 429 140 897 594 682
|
908


7

2
-
й проход

цикла
do
-
while




79 53 420 140 429 594 682
|
897

908


6

3
-
й проход

цикла
do
-
while




53 79 140
|
420 429 594 682 897

908


2

4
-
й проход

цикла
do
-
while



|
53 79 140 420 429 594 682 897

908


0

Рис. 3
.

Пример с
ортировка методом «пузырька»


Как видно͕ после каждого прохода массива все элементы͕
расположенные правее самого последнего͕ который участвовал в обмене͕ и
сам этот элемент занимают св
ои окончательные позиции (на рис
. 3

эта часть
массива отделена вертикальной чертой). При следующих просмотрах их
проверять уже не нужно. Обратите внимание на то͕ что после третьего
прохода еще четыре правых элемента ,420͕ 429͕ 594͕ 682- сразу заняли свои
п
озиции͕ а при последнем проходе перемещений элементов вообще не
было.


Сортировка методом простых вставок

Пусть существующие
m

из
N

элементов массива уже упорядочены͕ т.е.

mas
*0+ ≤
mas
*1+ ≤ ͙ ≤
mas
[
m
-
1],

а элементы
mas
[
m
],
mas
[
m
+1+͕ ͙͕
mas
[
N
-
1+ не
известны. Метод сортировки
вставкой применяется в тех случаях͕ когда массив надо заполнить так͕ чтобы
после вставки каждого нового элемента сохранилась его упорядоченность.
Для этого осуществляется поиск подходящего для вставки места в уже
заполненной част
и массива. Место для нового элемента освобождается
путем сдвига больших элементов к концу массива.



#include "iostream"

int main ()

{


const int N = 9;


int mas[N] = {79, 420, 429};


int i, j, m, el;



m = 3;

11



//заполнение пустой части массива


for

(
i

=
m
;
i


N
;
i
++)


{



//ввод нового элемента



cin

��
el
;




//поиск и высвобождение места под новый элемент



j = i
-

1;



�while (j = 0 && el mas[j])



{




//перемещение элемента mas[j] в позицию mas[j+1]




mas[j+1] = mas[j];




j
--
;



}






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



mas
[
j
+1] =
el
;


}



}


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

сравнивается по очереди с элементами
mas
[
m
-
1],
mas
[
m
-
2],
mas
[
m
-
3+͕ ͙ До тех пор͕ пока
el

меньше текущего элемента и не
достигнуто начало массива͕ происходит высвобождение под него места
путем перемещения большего элемента
mas
[
j
+ на одну позицию к концу
массива. Новый элемент помещается в освободившуюся позицию.

Пример заполнения массива с пом
ощью алгоритма сортировки вставкой
приведен на рис
. 4
. Здесь к уже существующим элементам ,79͕ 420͕ 429-
(
m
=3) добавляются новые͗ 53͕ 908͕ 140͕ 897͕ 594͕ 682.



79 420 429 : 53

^


53 79 420 429 : 908


^


53 79

420

429

908 : 140


^


53 79

140

420

429

908 : 897


^


53 79

140

420

429

897

908 : 594


^


53 79

140

420

429

594

897

908 : 682


^


53 79

140

420

429

594

682

897

908

Рис. 4
.

Пример с
ортировк
и

методом
простых
встав
о
к



12


Для
заполнения пустого массива нужно прежде ввести первый элемент
(
m
=1)͕ а после выполнить действия алгоритма сортировки вставкой.


...

��cin mas[0];

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

{


��cin el;


j = i
-

1;


�while (j = 0 && el mas[j])


{



mas[j+1] = mas[j];



j
--
;


}


mas[j+1] = el;

}

...


Поиск

элемента по заданному значению

Рассмотрим два алгоритма поиска заданного элемента
k

в массиве
mas

из
N

элементов. Результатом поиска может быть одно из двух͗ либо поиск
заверши
т
ся успешно͕ и элемент
k

в массиве найден͕ либо поиск ока
жет
ся
неудачным͕ и элемент
k

не найден. Для хранения индекса найденного
элемента будет использова
ться

целая переменная
ind
͕ которая в случае
успешного поиска будет содержать индекс͕ в противном случае



значение
-
1.


После
довательный поиск

В данном алгоритме последовательно просматривается весь массив.
Начинаем поиск с начала массива и продолжаем до конца͕ пока не будет
найден искомый элемент͖ затем останавливаемся. Если элемент найден͕ то
переменной
ind

присваиваем номер э
того элемента.


#include "iostream"


int main()

{


const int N = 9;


int k, ind, i;


//задание значений элементов массива


int mas[N] = {420, 79, 429, 53, 908, 140, 897, 594, 682};




cout << "Введите значение для поиска: ";


��cin k;

13



//поиск значения k
в массиве


ind =
-
1;


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



if (mas[i] == k) { ind = i; break;}



//вывод результата поиска


if (ind < 0) cout << "Искомое значение в массиве не
найдено!
\
n";


else cout "
Искомый

элемент

mas[" ind "] = "
mas[ind] "
\
n";



r

0;

}


Бинарный поиск

Если массив упорядочен͕ то можно использовать более эффективный
алгоритм поиска͕ например͕ бинарный поиск (или метод деления пополам).

Обозначим через
l



левую границу поиска͕
r



правую границу поиска и
sr



индекс элемента͕ находящегося в середине массива. Сравним искомый
элемент
k

со средним элементом
a
[
sr
+. Если они совпадают͕ то поиск
завершен успешно и местоположение определено. Если искомый элемент
больше͕ то берем правую половину массива (элементы с
индексами от
sr

+ 1
до
r
)͖ если меньше


то левую (элементы с индексами от
l

до
sr



1). Процесс
повторяется до тех пор͕ пока не будет найден нужный элемент или диапазон
поиска не будет исчерпан
.


#include "iostream"


int main()

{


const int N = 9;


int k,

l, r, sr, ind;




//задание значений элементов массива


int mas[N] = {53, 79, 140, 420, 429, 594, 682, 897, 908};




cout << "Введите значение для поиска: ";


��cin k;




//поиск значения k в массиве


ind =
-
1;


l = 0; r = N
-

1;


while ( l = r)


{



sr

= (l + r) / 2;



if (mas[sr] == k) { ind = sr; break;}



if (mas[sr] k) l = sr + 1;

14




else r = sr
-

1;


}



//вывод результата поиска


if (ind < 0) cout << "Искомое значение в массиве не
найдено!
\
n";


else cout "
Искомый

элемент

mas[" ind "] = "


mas[ind] "
\
n";




}


Пример процесса бинарного поиска элемента 594 в упорядоченном
массиве из девяти элементов
{53, 79, 140, 420, 429, 594, 682, 897, 908}

приведен на рис
.

5
. Скобки показывают границы просмотра (элементы с
индексами от
l

до
r
)͕ а подчеркнутое число


середину этого участка массива
(элемент с индексом
sr
).













Переменные

Элементы массива








l

sr

r

[
53 79

140

420

429


594

682

897

908
] 0 4 8


53 79

140

420

429 [594

682


897

908
] 5
6 8


53 79

140

420

429 [
594
]

682 897

908 5 5 5

Рис. 5
.

Пример бинарного поиска элемента в массиве


Лабораторная работа «
ОДНОМЕРНЫЕ МАССИВЫ
»

Вариант 1

Написать программу работы с одномерным массивом из 15 целых элементов
для решения задач͗

1)

вычислить сумму отрицательных элементов массива͖

2)

вычислить произведение элементов массива͕ расположенных между
максимальным и минимальным элементами͖

3)

отсортировать массив по убыванию методом выбора.


Вариант 2

Написать программу работы с одномерным
массивом из 15 вещественных
элементов для решения задач͗

1)

вычислить сумму положительных элементов массива͖

2)

вычислить произведение элементов массива͕ расположенных между
максимальным по модулю и минимальным по модулю элементами͖

3)

отсортировать массив по возра
станию методом выбора.

15


Вариант 3

Написать программу работы с одномерным массивом из 15 целых элементов
для решения задач͗

1)

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

2)

выполнить
бинарным методом поиск в массиве введенного
п
ользователем значения и вывести его индекс на экран͖

3)

вычислить сумму элементов массива͕ расположенных между первым и
последним положительными элементами.


Вариант 4

Написать программу работы с одномерным массивом из 15 вещественных
элементов для решения
задач͗

1)

вычислить произведение элементов массива с четными номерами͖

2)

вычислить сумму элементов массива͕ расположенных между первым и
последним отрицательными элементами͖

3)

отсортировать массив по убыванию методом "пузырька".


Вариант 5

Написать программу рабо
ты с одномерным массивом из 15 целых элементов
для решения задач͗

1)

вычислить сумму элементов массива с нечетными номерами͖

2)

отсортировать массив по возрастанию методом "пузырька"͖

3)

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


Вариант 6

Написать программу работы с одномерным массивом из 15 вещественных
элементов для решения задач͗

1)

найти максимальный элемент массива͖

2)

подсчитать количество элементов массива͕ лежащих в диапазоне от
R
1 до
R
2͕ вводимых пользователем͖

3)

отсортировать
массив по возрастанию методом "пузырька".


Вариант 7

Написать программу работы с одномерным массивом из 15 целых элементов
для решения задач͗

1)

найти минимальный элемент массива͖

2)

вычислить сумму элементов массива͕ расположенных между первым и
последним нулев
ыми элементами͖

16


3)

отсортировать массив по убыванию методом выбора.


Вариант 8

Написать программу работы с одномерным массивом из 15 вещественных
элементов для решения задач͗

1)

найти максимальный по модулю элемент массива͖

2)

вычислить

сумму элементов массива͕
расположенных после первого
положительного элемента͖

3)

отсортировать массив по возрастанию методом выбора.


Вариант 9

Написать программу работы с одномерным массивом из 15 целых элементов
для решения задач͗

1)

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

2)

найти
методом последовательного поиска в массиве введенное
пользователем значение и вывести его индекс на экран͖

3)

вычислить сумму модулей элементов массива͕ расположенных после
последнего отрицательного элемента.


Вариант 10

Написат
ь программу работы с одномерным массивом из 15 вещественных
элементов для решения задач͗

1)

найти индекс максимального по модулю элемента массива͖

2)

вычислить сумму элементов массива͕ расположенных до последнего
положительного элемента включительно͖

3)

отсортирова
ть массив по возрастанию методом "пузырька".


Вариант 11

Написать программу работы с одномерным массивом из 15 целых элементов
для решения задач͗

1)

вычислить сумму модулей элементов массива͕ расположенных после
первого элемента͕ равного нулю͖

2)

найти
методом
последовательного поиска в массиве введенное
пользователем значение и вывести его индекс на экран͖

3)

отсортировать массив по убыванию методом "пузырька".


Вариант 12

Написать программу работы с одномерным массивом из 15 вещественных
элементов для решения зад
ач͗

17


1)

подсчитать количество элементов массива͕ больших введенного
пользователем значения
R
;

2)

вычислить

сумму элементов массива͕ расположенных между первым и
вторым отрицательными элементами͖

3)

отсортировать массив по возрастанию методом выбора.


Вариант 13

Напи
сать программу работы с одномерным массивом из 15 вещественных
элементов для решения задач͗

1)

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

2)

подсчитать количество элементов массива͕ лежащих в диапазоне от
R
1 до
R
2͕ вводимых
пользователем͖

3)

найти индекс минимального по модулю элемента массива.


Вариант 14

Написать программу работы с одномерным массивом из 15 целых элементов
для решения задач͗

1)

подсчитать количество положительных элементов массива͖

2)

вычислить
произведение элементо
в массива͕ расположенных между
первым и вторым нулевыми элементами͖

3)

отсортировать массив по убыванию методом выбора.


Вариант 15

Написать программу работы с одномерным массивом из 15 целых элементов
для решения задач͗

1)

подсчитать количество элементов массив
а͕ равных 0͖

2)

вычислить сумму элементов массива͕ расположенных после
максимального элемента͖

3)

отсортировать массив по убыванию методом "пузырька".



Многомерные массивы


Размерностью

массива называется количество его индексов. Например͕
массив размерностью два


двумерный массив


соответствует
математическому понятию прямоугольной матрицы.

18


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

Примеры описания многомерных массивов.

int

mas
[3][4]; //описание целочисленного двумерного массива


//из 3
-
х строк и 4
-
х столбцов

const

int

N

= 5;

double

A
[2*
N
][2*
N
]; //описание дв
умерного вещественного массива





//
A

размером 10×10 элементов

int

B
[2][4][2]; //описание трехмерного целочисленного


//массива
B


Примечание.

Стандарт языка С++ не накладывает ограничения на размерность массива͕ но каждый
компилятор задает максимальное количество индексов массива. На практике обычно
используются массивы размерностью не более трех.


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

Например͕
mas
[
i
][
j
+ или
A
[0][0].

Для инициализации многомерного массива каждый элемент
-
массив
заключается в свои фигурные скобки͕ либо задается общий список элементов
в том порядке͕ в котором элементы располагаются в памяти.


Например͕

int

mas
[3][4] = { {0,
-
1, 2,
-
7}, {9,
7, 5, 8}, {3, 0, 1,
-
6} };

или

int

mas
[3][4] = {0,
-
1, 2,
-
7, 9, 7, 5, 8, 3, 0, 1,
-
6};


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


во внутреннем цикле.

Рассмотрим работу с двумерными массивами на следующих прим
ерах.

Пример 1.

Ввод и вывод элементов
двумерного
массива



const int kolStr = 3, kolStb = 4;

19



int i, j, mas[kolStr][kolStb] = {0};



//
ввод

элементов

массива


for (i = 0; i kolStr; i++)


{



for (j = 0; j kolStb; j++)



{




cout "mas[" i
"][" j "] = ";




��cin mas[i][j];



}



cout "
----------
\
n";


}



//
вывод

элементов

массива


for (i = 0; i kolStr; i++)


{



for (j = 0; j kolStb; j++)




cout mas[i][j] '
\
t';



cout '
\
n';


}


Пример 2.

Вычисление суммы всех элемент
ов матрицы



sum = 0;


for (i = 0; i kolStr; i++)





for (j = 0; j kolStb; j++)




sum += mas[i][j];


Пример

3.

Поиск максимального элемента матрицы



max

=
mas
[0][0];


for (i = 0; i kolStr; i++)





for (j = 0; j kolStb; j++)




�if (mas[i][j]
max) max = mas[i][j];


Пример 4.

Дан
двумерный массив
mas
. Составить вектор
b

такой͕ что

а)
b
i



максимальный элемент
i
-
й строки



for (i = 0; i kolStr; i++)


{



max = mas[i][0];



for (j = 0; j kolStb; j++)




�if (mas[i][j] max) max = mas[i][j];



b
[
i
] =
max
;


}


б)
b
i



среднее арифметическое отрицательных элементов текущей строки

20



double s;

int k;

for (i = 0; i kolStr; i++)


{



k = 0; s = 0;



for (j = 0; j kolStb; j++)




if (mas[i][j] 0)

{


s +=mas[i][j];


k
++;

}



b
[
i
] =
s
/
k
;


}


Лабораторная работа
«ДВУМЕРНЫЕ МАССИВЫ»

Вариант 1

Написать программу работы с двумерным целочисленным массивом из 5
строк и 7 столбцов для решения задач͗

1)

определить количество строк͕ не содержащих ни одного нулевого
элемента͖

2)

найти максимальное из чисел͕
встречающихся в заданном массиве
более одного раза.


Вариант 2

Написать программу работы с двумерным вещественным массивом из 5
строк и 5 столбцов для решения задач͗

1)

вычислить сумму элементов главной и побочной диагоналей͖

2)

найти номер строки с максимальной

суммой положитель
ных
элементов.


Вариант 3

Написать программу работы с двумерным целочисленным массивом из 5
строк и 7 столбцов для решения задач͗

1)

определить количество столбцов͕ не содержащих ни одного нулевого
элемента͖

2)

найти номер строки͕ в которой на
ходится самое минимальное
количество одинаковых эле
ментов.


Вариант 4

Написать программу работы с двумерным целочисленным массивом из 5
строк и 7 столбцов для решения задач͗

21


1)

определить
количество столбцов͕ содержащих хотя бы один нулевой
элемент͖

2)

вычислить произведение элементов в тех строках͕ которые не
содержат отрицательных эле
ментов.


Вариант 5

Написать программу работы с двумерным вещественным массивом из 7
строк и 7 столбцов для решения задач͗

1)

вычислить сумму отрицательных элементов главной
и побочной
диагоналей͖

2)

найти номер строки с минимальным произведением положитель
ных
четных элементов.


Вариант 6

Написать программу работы с двумерным вещественным массивом из 5
строк и 7 столбцов для решения задач͗

1)

вычислить сумму элементов в тех строках
͕ которые содержат хотя бы
один отрицательный элемент͖

2)

найти минимальные элементы каждого столбца.


Вариант 7

Написать программу работы с двумерным целочисленным массивом из 5
строк и 5 столбцов для решения задач͗

1)

вычислить сумму элементов в тех столбцах͕
которые не содержат
отрицательных эле
ментов͖

2)

найти минимум среди сумм модулей элементов главной и побочной
диагоналей.


Вариант 8

Написать программу работы с двумерным целочисленным массивом из 5
строк и 5 столбцов для решения задач͗

1)

определить номера стр
ок
k

такие͕ что
k
-
я строка массива совпадает с

k
-
ы
м столбцом͖

2)

вычислить сумму элементов в столбцах͕ не содержащих нулей.


Вариант 9

Написать программу работы с двумерным вещественным массивом из 7
строк и 5 столбцов для решения задач͗

22


1)

вычислить сумму элем
ентов в тех строках͕ которые содержат хотя бы
один отрицательный элемент͖

2)

найти номер первой из строк͕ содержащих хотя бы один
положительный элемент.


Вариант 10

Написать программу работы с двумерным вещественным массивом из 7
строк и 5 столбцов для решени
я задач͗

1)

вычислить сумму элементов в тех строках͕ которые содержат хотя бы
один отрицательный элемент͖

2)

найти номер первой из строк͕ содержащих хотя бы один
положительный элемент.


Вариант 11

Написать программу работы с двумерным целочисленным массивом из 7

строк и 5 столбцов для решения задач͗

1)

найти столбец с максимальной суммой модулей его отрицательных
нечетных элементов͖

2)

вычислить сумму элементов в тех строках͕ которые не содержат
отрицательных элементов.


Вариант 12

Написать программу работы с двумерным

целочисленным массивом из 5
строк и 5 столбцов для решения задач͗

1)

найти номер первой из строк͕ содержащих хотя бы один
положительный элемент͖

2)

вычислить сумму модулей элементов͕ расположенных ниже главной
диагонали.


Вариант 13

Написать программу работы с
двумерным вещественным массивом из 5
строк и 5 столбцов для решения задач͗

1)

найти количество строк͕ среднее арифметическое элементов которых
меньше заданной пользователем величины͖

2)

вычислить сумму модулей элементов͕ расположенных выше главной
диагонали.


23


Вариант 14

Написать программу работы с двумерным вещественным массивом из 5
строк и 7 столбцов для решения задач͗

1)

вычислить сумму элементов в тех столбцах͕ которые содержат хотя бы
один отрицательный элемент͖

2)

найти номер первой из строк͕ не содержащих ни о
дного
положительного элемента.


Вариант 15

Написать программу работы с двумерным целочисленным массивом из 5
строк и 7 столбцов для решения задач͗

1)

вычислить сумму элементов в тех столбцах͕ которые содержат хотя бы
один нулевой элемент͖

2)

найти количество отр
ицательных элементов в тех строках͕ которые
содержат хотя бы один нулевой элемент.



Библиографический список

1.

Лафоре Р. Объектно
-
ориентированное программирование в
C
++.
Классика

Computer

Science

/
Р
.

Лафоре.



СПб
.:
Питер
, 2005.


924
с
.

2.

Павловская Т.

А. С/С++. Программирование на языке высокого уровня
/
Т.

А.

Павловская
.



СПб.͗ Питер͕ 2001.


460 с.

3.

Павловская Т.

А. С/С++. Структурное программирование͗ Практикум

/
Т.

А.

Павловская͕ Ю.

А.

Щупак
.


СПб.͗ Питер͕ 2002.


240 с.

4.

Хабибуллин И.
Программирование на языке высокого уровня

C
/
C
++

/
И.

Хабибуллин
.


Спб.͗ БХВ
-
Петербург
, 2006
.


512 с.

5.

Кнут Д. Искусство программирования
.

Т.

3. Сортировка и поиск

/
Д.

Кнут
.


М.͗ Издательский дом «Вильямс»͕ 2000.


832 с.





24


Оглавление


Общие вопросы

................................
................................
................................
........

3

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

4

Методы сортировки массива

................................
................................
...................

7

Сортировка методом выбора

................................
................................
..........

7

Сортировка методом «пузырька»

................................
................................
...

9

Сортировка методом простых вставок

................................
..........................

10

Поиск элемента по заданному значению

................................
.............................

12

Последовательный поиск

................................
................................
..............

12

Бинарный поиск

................................
................................
.............................

13

Лабораторная работа «Одно
мерные массивы»

................................
...................

1
4

Многомерные массивы
................................
................................
..........................

17

Лабораторная работа «Двумерные массивы»

................................
.....................

20

Библиографический список

................................
................................
...................

23



Приложенные файлы

  • pdf 1060899
    Размер файла: 600 kB Загрузок: 0

Добавить комментарий