Лабораторная работа №5 Обработка на пк одномерных массивов.
Цель лабораторной работы – освоение методики обработки информации в одномерных массивах.
Перед выполнением лабораторной работы студент должен знать:
- определение и правила описания одномерных массивов разных типов;
- способы доступа к элементам массива данных;
- способы инициализации элементов массива;
- способы работы с одномерными массивами;
- способы алгоритмизации поиска минимальных и максимальных значений в одномерных массивах;
- обобщенные способы формирования таблиц различной конфигурации с помощью псевдосимволов.
После выполнения лабораторной работы студент должен уметь:
- выполнять инициализацию массивов разных типов и размерности;
- использовать средства языка С++ для преобразования типов данных;
- выполнять алгоритмизацию поиска минимальных и максимальных значений в одномерных массивах;
5.1. Краткие теоретические сведения
Массив – это совокупность логически взаимосвязанных данных одного типа, объединенных общим именем. Массив в С++ — это набор однотипных данных (объектов), имеющих общее имя и различающихся местоположением в этом наборе (или индексом, присвоенном каждому элементу массива).
В программе могут быть массивы целых чисел или чисел с плавающей точкой, символьные массивы и т. д.
Описание одномерного массива
Описание состоит из спецификации типа, идентификатора и размерности массива:
int myArray [ 3 ];
Инициализация массива и доступ к элементам массива
Обращение к элементам массива выполняется по их индексам, которые всегда начинаются от нуля. Если, например, объявить в программе массив по имени imas из 100 целых чисел
int imas[100];
то самый первый элемент массива получает обозначение imas[0], следующий – imas[1] и т. д. до последнего элемента imas[99].
Точно так же можно объявить массивы данных любых других типов:
char cSy[20]; //Массив из 20 символов
float fWe[16]; //Массив из 16 чисел с плавающей точкой.
После объявления массива его можно заполнить числами, используя индексный оператор [ ], например:
int myArray [ 3 ]; // Объявление массива
myArray [ 0 ] = -12; // Инициализация первого элемента (его индекс // равен нулю) значением -12
myArray [ 1 ] = 5;
myArray [ 2 ] = 37;
Доступ к отдельным элементам массива осуществляется также с помощью индексного оператора:
int result = myArray [ 0 ] + myArray [ 1 ] + myArray [ 2 ];
Массив можно объявить и заполнить одновременно, например:
int myArray [ 3 ] = { -12, 5, 37 } ;
Если размерность задана, то число значений в списке инициализации не должно ее превышать.
Если размерность массива больше числа значений в списке, то не инициализированные явно элементы массива будут установлены в 0, например:
int myArray[ 5 ] = { 0, 1, 2 }; // myArray будет равно { 0, 1, 2, 0, 0 }
Значение размерности должно быть константным выражением, т.е. размерность должна быть известна на этапе трансляции. Это означает, что переменная не может использоваться для задания размерности массива.
Если в массиве не слишком много элементов и их значения известны заранее, массив можно инициализировать вместе с его объявлением, заключив перечень значений в фигурные скобки:
int iNs[10]={0,1,2,3,4,5,6,7,8,9};
Если же массив большой, заполнить его придется программно в цикле. Пусть мы хотим образовать массив из 100 элементов, заполненных натуральным рядом чисел. Это делается следующим образом:
int imas[100];
for (int i=0;i<100;i++) imas[i]=i;
К элементам массива можно обращаться и выборочно, например
test[50]=0x7FFA;
Сохранение одномерных массивов
В С++ одномерный массив логически сохраняется как последовательность упорядоченных элементов в памяти. Каждый элемент относится к одному и тому же типу данных. Например, массив А располагается в памяти следующим образом:
A[0] A[i]
. . .
Address A[0] Address A[i]
В С++ имя массива является константой и рассматривается как адрес первого элемента этого массива. Так, в объявлении
type A[arraySize];
имя массива А является константой и определяет местоположением в памяти первого элемента A[0]. Элементы A[1], A[2] и т.д. следуют за ним последовательно.
Допустим, что sizeof(type) = M, тогда весь массив А занимает М*arraySize байтов.
Компилятор задает таблицу, называемую дескриптор массива (dope vector), для ведения записи характеристик массива.
Таблица включает информацию о размере каждого элемента массива, начальный адрес массива и количество элементов в этом массиве:
Начальный адрес: А
Количество элементов массива: arraySize
Размер типа: M = sizeof(type)
Эта таблица используется компилятором также для реализации функции доступа (access function) , которая определяет адрес элемента в памяти.
A[0] A[1] A[I] A[ArraySize - 1]
.
. . . . .
0 1 I
A A+1*M A+I*M A+(ArraySize-1)*M
Пример.
Предположим, что переменная типа float сохраняется с использованием 4 байт (т.е. sizeof(float) = 4 ) и массив Macizo[ ] начинается в памяти по адресу 20000. Пусть
float Macizo[18];
Тогда элемент массива Macizo[18] размещается по адресу
20000 + 18*4 = 20072
Символьные массивы могут представлять набор отдельных символов или представлять связную символьную строку.
В первом случае массив можно инициализировать так же, как и числовой, перечислением всех его элементов:
char cSz[17]={'С','и','м','в','о', 'л','ь','н','ы', 'й',' ','м','а','с','с','и','в'};
Такой массив занимает в памяти точно 17 байт.
Во втором случае массив инициализируется символьной строкой:
char cSz[20]="Символьный массив";
При такой инициализации компилятор записывает в память в конце строки двоичный нуль, который служит символом-ограничителем. Многие функции для работы со строками (например, копирования строки или вывода строки на экран) по этому символу определяют, где кончается строка. Это избавляет нас от необходимости определять и указывать при вызове функции фактическую длину строки. Таким образом, массив занимает в памяти на 1 байт больше, чем в нем есть значащих символов. Это обстоятельство необходимо учитывать при задании длины массива в его объявлении, которая должна выбираться на единицу больше максимально возможной длины строки.
Объявление длины символьного массива с запасом целесообразно лишь в тех случаях, когда он будет заполняться программно строками разной длины. Если же данная текстовая строка изменяться не будет, удобнее объявить ее без указания длины, оставив в объявлении пару квадратных скобок, которые скажут компилятору, что переменная cSz является не одиночным символом, а символьным массивом:
char cSz[]="Символьный массив";
Компилятор, выделяя память под этот массив, сам определит его длину, которая в данном случае будет равна 18 байтам.
Типичные действия над массивами можно представить следующими фрагментами программ:
1. Инициализация массива нулями.
for (i = 0; i < n; i ++)
m [ i ] = 0;
2. Печать массива в строку.
for (i = 0; i < n; i ++)
cout << setw(7) << m[ i ] <<endl;
3. Вычисление суммы элементов массива.
int sum = 0;
for (i = 0; i < n; i ++)
sum + = m[ i ];
4. Вывод элементов массива в виде гистограммы.
. . . . . . .
cout << “Элемент” << setw(13)
<< “Значение” << setw(17)
<< “Гистограмма” << endl;
for (i = 0; i < n; i ++)
{
cout << setw(7) << i << setw(13) << m[ i ] << “…..” ;
for ( int j = 0; j <= m[ i ]; j++ )
cout << “ * ”;
cout << endl;
}
5. Сортировка массива методом “пузырька”.
int temp;
cout << “Исходный порядок элементов” << endl;
for (i = 0; i < n; i ++)
cout << setw(7) << m[ i ];
// сортировка
for ( int p = 1; p << n; p++ ) // кол-во проходов по массиву
for ( i = 0; i < n – 1; i ++ )
if ( m[ i ] > m[ i + 1] )
{ temp = m[ i ];
m[ i ] = m[ i + 1] ;
m[ i + 1] = temp; }
cout << “Массив после сортировки” << endl;
for (i = 0; i < n; i ++)
cout << setw(7) << m[ i ];
cout << endl;
6. Линейный поиск в массиве.
. . . . . . . .
int key, flag = n;
cout << “Введите ключ поиска” << endl;
cin >> key;
for (i = 0; i < n; i ++)
if ( m[ i ] == key ) flag = i;
if ( flag != n )
cout << “Искомый элемент имеет индекс” << flag << endl;
else cout << “”Элемент не найден” << endl;
7. Поиск максимального и минимального элементов массива.
int max, min;
max = min = m[ 0 ];
for (i = 1; i < n; i ++)
{
if ( m[ i ] > max ) max = m[ i ];
if ( m[ i ] < min ) min = m[ i ];
}
cout << “Максимальный элемент =” << max << endl;
cout << “Минимальный элемент =” << min << endl;
8. Перестановка элементов массива в обратном порядке.
int j, temp;
//первый способ перестановки
for ( i = 0, j = n – 1; i < j; ++ i, -- j )
{
temp = m[ i ];
m[ i ] = m[ j ];
m[ j ] = temp;
}
//печать
//второй способ перестановки
for ( i = 0; i < (n / 2); i ++ )
{
temp = m[ i ];
m[ i ] = m[ n – 1 – i];
m[ n – 1 – i ] = temp;
}
// печать
9. Двоичный поиск в отсортированном массиве.
int low, high, middle, key, flag = 0;
low = 0;
high = n – 1;
cout << “Введите ключ” << endl;
cin >> key;
// поиск
while ( low <= high )
{
middle = ( low + high ) / 2;
if ( key == m[ middle ] ) flag = 1;
else if ( key < m[ middle ]
high = middle – 1;
else low = middle + 1;
} // while
if ( flag ) cout << “Искомый элемент имеет индекс” << middle << endl;
else cout << “”Элемент не найден” << endl;
10. Заполнение массива данными, выбираемыми случайным образом
При отладке программ часто бывает удобным инициировать массив данными (числами или символами ), выбираемыми случайным образом. Для этого можно использовать специальные функции из библиотеки stdlib.h. Рассмотрим их подробнее.
Функция rand() генерирует псевдослучайные числа в диапазоне 0 .. RAND_MAX, где RAND_MAX – константа, обычно совпадающая с максимальным целым значением для данной реализации.
Функция random ( int num ) генерирует случайные числа в диапазоне 0 .. num – 1.
Функция randomize() инициирует генератор случайных чисел от таймера.
Функция srand ( unsigned seed ) инициирует генератор случайных чисел так, что генерируемая последовательность зависит от аргумента; если аргумент этой функции не изменять, то всегда будет генерироваться одна и та же последовательность.
Примеры:
-
int i = 1 + rand() % 6; //генерируются случ. числа в диапазоне 1.. 6
-
i = rand() & 2; // генерируются случ. числа в диапазоне 0..1
ЗАДАНИЯ
!!! Обработку массива выполнить в функции!!!
Задача 1. Составить программу, выполняющую с одномерным массивом следующие действия:
Вариант 1
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) сумму отрицательных элементов массива;
2) произведение элементов массива, расположенных между максимальным и минимальным элементами.
Упорядочить элементы массива по возрастанию.
Вариант 2
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) сумму положительных элементов массива;
2) произведение элементов массива, расположенных между максимальным по модулю и минимальным по модулю элементами.
Упорядочить элементы массива по убыванию.
Вариант 3
В одномерном массиве, состоящем из « целых элементов, вычислить:
1) произведение элементов массива с четными номерами;
2) сумму элементов массива, расположенных между первым и последним нулевыми элементами.:
Преобразовать массив таким образом, чтобы сначала располагались все положительные элементы, а потом — все отрицательные (элементы, равные 0, считать положительными).'
Вариант 4
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) сумму элементов массива с нечетными номерами;
2) сумму элементов массива, расположенных между первым и последним отрицательными элементами.
Сжать массив, удалив из него все элементы, модуль которых не превышает 1. Освободившиеся в конце массива элементы заполнить нулями.
Вариант 5
В одномерном массиве, состоящем из п вещественных элементов, вычислить: 1) максимальный элемент массива;
2) сумму элементов массива, расположенных до последнего положительного элемента.
Сжать массив, удалив из него все элементы, модуль которых находится в интервале [а,Ь]. Освободившиеся в конце массива элементы заполнить нулями.
Вариант 6
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) минимальный элемент массива;
2) сумму элементов массива, расположенных между первым и последним положительными элементами.
Преобразовать массив таким образом, чтобы сначала располагались все элементы, равные нулю, а потом — все остальные.
Вариант 7
В одномерном массиве, состоящем из п целых элементов, вычислить:
1) номер максимального элемента массива;
2) произведение элементов массива, расположенных между первым и вторым нулевыми элементами.
Преобразовать массив таким образом, чтобы в первой его половине располагались элементы, стоявшие в нечетных позициях, а во второй половине — элементы, стоявшие в четных позициях.
Вариант 8
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) номер минимального элемента массива;
2) сумму элементов массива, расположенных между первым и вторым отрицательными элементами.
Преобразовать массив таким образом, чтобы сначала располагались все элементы, модуль которых не превышает 1, а потом — все остальные.
Вариант 9
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) максимальный по модулю элемент массива;
2) сумму элементов массива, расположенных между первым и вторым положительными элементами.
Преобразовать массив таким образом, чтобы элементы, равные нулю, располагались после всех остальных.
Вариант 10
В одномерном массиве, состоящем из п целых элементов, вычислить:
1) минимальный по модулю элемент массива;
2) сумму модулей элементов массива, расположенных после первого элемента, равного нулю.
Преобразовать массив таким образом, чтобы в первой его половине располагались элементы, стоявшие в четных позициях, а во второй половине — элементы, стоявшие в нечетных позициях.
Вариант 11
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) номер минимального по модулю элемента массива;
2) сумму модулей элементов массива, расположенных после первого отрицательного элемента.
Сжать массив, удалив из него все элементы, величина которых находится в интервале [а,Ь]. Освободившиеся в конце массива элементы заполнить нулями.
Вариант 12
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) номер максимального по модулю элемента массива;
2) сумму элементов массива, расположенных после первого положительного элемента.
Преобразовать массив таким образом, чтобы сначала располагались все элемент ты, целая часть которых лежит в интервале [а,Ь], а потом — все остальные.
Вариант 13
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) количество элементов массива, лежащих в диапазоне от А до В;
2) сумму элементов массива, расположенных после максимального элемента.
Упорядочить элементы массива по убыванию модулей элементов.
Вариант 14
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) количество элементов массива, равных 0;
2) сумму элементов массива, расположенных после минимального элемента.
Упорядочить элементы массива по возрастанию модулей элементов.
Вариант 15
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) количество элементов массива, больших С;
2) произведение элементов массива, расположенных после максимального по модулю элемента.
Преобразовать массив таким образом, чтобы сначала располагались все отрицательные элементы, а потом — все положительные (элементы, равные 0, считать положительными).
Вариант 16
В одномерном массиве, состоящем из п вещественных элементов, вычислить: 1) количество отрицательных элементов массива;
2) сумму модулей элементов массива, расположенных после минимального по модулю элемента.
Заменить все отрицательные элементы массива их квадратами и упорядочить элементы массива по возрастанию.
Вариант 17
В одномерном массиве, состоящем из п целых элементов, вычислить:
1) количество положительных элементов массива;
2) сумму элементов массива, расположенных после последнего элемента, равного нулю.
Преобразовать массив таким образом, чтобы сначала располагались все элементы, целая часть которых не превышает 1, а потом — все остальные.
Вариант 18
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) количество элементов массива, меньших С;
2) сумму целых частей элементов массива, расположенных после последнего отрицательного элемента.
Преобразовать массив таким образом, чтобы сначала располагались все элементы, отличающиеся от максимального не более чем на 20%, а потом — все остальные.
Вариант 19
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) произведение отрицательных элементов массива;
2) сумму положительных элементов массива, расположенных до максимального элемента.
Изменить порядок следования элементов в массиве на обратный.
Вариант 20
В одномерном массиве, состоящем из п вещественных элементов, вычислить:
1) произведение положительных элементов массива;
2) сумму элементов массива, расположенных до минимального элемента.
Упорядочить по возрастанию отдельно элементы, стоящие на четных местах, и элементы, стоящие на нечетных местах.
Задача 2. Последовательность из десяти целых чисел (как положительных, так и отрицательных) представлена в виде одномерного массива. Найти и вывести на экран подпоследовательность подряд идущих чисел, сумма которых максимальна. Например, для последовательности : 1 -8 3 2 -1 4 -6 2 1 -5 ответом будет следующая подпоследовательность: 3 2 -1 4
Задача 3. Дана целочисленная последовательность (одномерный массив целых чисел). Написать программу нахождения количества различных элементов этой последовательности. Вывести все элементы, встречающиеся более одного раза.
На 11-12 баллов
Задача 4. В заданной последовательности чисел длиной n (n≤100) определить длину самой большой упорядоченной по возрастанию подпоследовательности соседних элементов.
Контрольные вопросы
1.Дайте определение массива.
2.Как располагается массив в памяти?
3.Укажите примеры задания размерности массива.
4.Как можно инициализировать элементы массива?
5.Какую информационную нагрузку несет имя одномерного массива?
6.Какая операция используется для определения адреса произвольного элемента массива?