1151644_1113575_4.-odnomernie-massivi-(1) (3)

1. ОДНОМЕРНЫЕ МАССИВЫ

2. КЛАССИФИКАЦИЯ ДАННЫХ ПО СТРУКТУРЕ

ДАННЫЕ
КОНСТАНТЫ
ПЕРЕМЕННЫЕ
(защита от записи)
ДАННЫЕ
ПРОСТЫЕ
1 ячейка
СЛОЖНЫЕ
МАССИВ
СТРУКТУРА
несколько
ячеек
...

3. ОПРЕДЕЛЕНИЕ

Массив – структурированный тип данных,
состоящий из фиксированного числа элементов
одного типа
Размер - количество элементов массива.
Индекс – порядковый номер элемента массива,
начинается с 0.

4.

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

Чтобы использовать одномерный массив в
программе, необходимо:
1. объявить массив
2. проинициализировать массив, т.е. задать каждому
элементу конкретное числовое значение;
3. провести вычисления, исследования.

6. Объявление массива

Синтаксис объявления массива:
тип массива имя массива [размер массива];
Тип – тип элементов массива;
Имя – это допустимый и уникальный в данной области видимости
идентификатор;
Размер – это положительный литерал, переменная или константное
выражение.
Примеры:
int mas[ ];
const int N=5
dooble А[ N ]

7. Инициализация массива

1 способ:
int mas[ ] = {3, -7, 9, 135, -805};
2 способ:
double a[n];
int i;
for(i=0; i<n; i++)
{
cout<< "a[“ << i << "]=";
cin>>a[i];
}

8. Инициализация массива, функция rand()

В С++ для заполнения элементов массива
случайными числами применяются специальные
функции: rand() и srand(). Функция rand() возвращает
псевдослучайное число из диапазона 0 .. 32535.
Для того, чтобы использовать данные функции,
необходимо подключить библиотечный файл: #include
<cstdlib> или #include <stdlib.h> (для старых
компиляторов).

9. функция rand()

Чтобы добиться “настоящей” случайности чисел
при повторных запускаx программы, необходимо
применить функцию srand() до функции rand().
srand(time(NULL))
Для использования time() необходимо
подключить библиотечный файл ctime.
#include <ctime> или #include <time.h>
Для задания другого диапазона следует
использовать формулу:
rand() % (max-min+1)+min,
где min и max – нижняя и верхняя границы требуемого
диапазона

10. Инициализация массива, при помощи функций rand(), srand()

#include <iostream>
#include <cstdlib>
#include <ctime> // содержит time()
using namespace std;
int main() {
int A[100];
srand(time(NULL));
for (int i = 0; i < 100; i++)
{
A[i] = rand();
cout << A[i] << endl;
}
}

11. Примеры программ с использованием массивов

ПРИМЕРЫ ПРОГРАММ С
ИСПОЛЬЗОВАНИЕМ МАССИВОВ

12. Пример 1

Дан массив А из n элементов, n 20. Вычислить
сумму элементов массива.

13.

#include <iostream>
using namespace std;
int main()
{
float A[ n ],sum;
int k, i, n;
cout << “Введите кол-во элементов массива";
cin >> n;
/* цикл для поэлементного ввода массива*/
for (i = 0; i < n; i++)
{
cin >> A[ i ];
}
sum=0;
/* цикл для вычисления суммы элементов массива */
for (i=0; i<n; i++)
{
sum=sum+a[i];
}
cout<< " Сумма эл-ов массива = “ << sum << endl;
}

14. Пример 2

Дан массив А из n элементов, n 20. Вычислить
сумму положительных и количество отрицательных
элементов массива.

15.

#include <iostream>
using namespace std;
int main()
{
float A[ n ], sum;
int k, i, n;
cout << “Введите кол-во элементов массива";
cin >> n;
/* цикл для поэлементного ввода массива*/
for (i = 0; i < n; i++)
{
cin >> A[ i ];
}
sum = 0; k = 0;
/* цикл для вычисления суммы положительных и количества
отрицательных элементов массива */
for (i = 0; i < n; i++) {
if (A[ i ] > 0) // проверяем является ли число положительным
sum = sum + a[ i ];
else
k = k + 1; }
cout <<" Сумма положительных эл-ов массива = “ << sum << endl;
cout << ” Кол-во отрицательных эл-ов массива = “ << k << endl;
}

16. Пример 3

Дан массив A из n элементов,
n 20.Найти максимальное значение
элементов массива.

17.

#include <iostream>
using namespace std;
int main()
{
float A[ n ], max;
int i, n;
cout << " Введите кол-во элементов массива ";
cin >> n;
/* цикл для поэлементного ввода массива*/
for (i = 0; i < n; i++) {
cin >> A[ i ]; }
max = A[ 0 ];
/* цикл для вычисления максимального элемента массива */
for (i = 0; i < n; i++)
{ if (A[ i ] > max)
max = a[ i ];
}
cout << " max= “ << max << endl;
}

18. Пример 4

Задан массив B, содержащий 20
вещественных чисел. Найти сумму элементов
массива, которые лежат на парных позициях.

19.

#include <iostream>
using namespace std;
void main()
{
float B[ 20 ],sum;
int i;
/* цикл для поэлементного ввода массива*/
for (i = 0; i < n; i++)
cin >> B [ i ];
sum = 0;
/* цикл для вычисления суммы элементов массива, которые лежат
на парных позициях */
for (i = 0; i < 20; i++)
if ( i % 2 == 0 ) // определяем парный(чётный) индекс массива B
sum+= B [ i ];
cout << " sum= “ << sum << endl;
}

20. Пример 5

Дан одномерный массив, вывести его
элементы в обратном порядке.

21.

#include <iostream>
#include <cstdlib>
#include <time.h>
using namespace std;
void main()
{
const int N = 10; // количество элементов массива
float B [ N ];
int i;
/* заполняем массив случ. числами в диапазоне от -40 до 40 */
srand(time(NULL));
for (i=0; i<N; i++){
B [ i ] = rand() % 81 + - 40;
cout << B [i] << " ";
}
cout << endl;
cout << endl;
/* вывод элементов массива в обратном порядке*/
for (i=N-1; i>=0; i--)
cout << B [ i ] << endl;
}

22. Пример 6

В одномерном массиве найти
сумму элементов между
максимальным и минимальным
элементами.

23.

const int N = 20; // количество элементов массива
float B [ N ],sum;
int i, max=0, min=0, indmin = 0, indmax = 0, sum = 0;
/* заполняем массив случ. числами в диапазоне от -40 до 40 */
srand(time(NULL));
for (i=0; i<N; i++){
B [ i ] = rand() % 81 + - 40;
cout << B [i] << " ";
}
cout << endl;
/* находим максимальный элемент массива и его индекс */
for (i=0; i<N; i++) {
if (B [i] > max) {
max = B [i];
indmax=i;
}
/* находим минимальный элемент массива и его индекс */
if (B [i] < min){
min = B[i];
indmin=i;
}
}

24.

cout<< “max=”<<max;
cout<< “min=”<<min;
if (indmin > indmax) {
for (i = indmax+1; i< indmin; i++) {
sum = sum + B [i]; // находим сумму элементов массива
между max и min
}
else {
for (i = indmin+1; i < indmax; i++) {
sum = sum + B [i]; // находим сумму элементов
массива между min и max
}
}
cout<<endl;
cout<<”sum=”<<sum;
}

25. Сортировка одномерного массива

Сортировка — это перестановка элементов
массива с целью расположения этих элементов в
определённом порядке, например: по возрастанию или
по убыванию.
«пузырьковая» сортировка
сортировка методом Шелла
пирамидальная сортировка
быстрая сортировка Хоара

26. «Пузырьковая» сортировка

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

27. «Пузырьковая» сортировка

Пример. Дан массив из n целых чисел.
Упорядочить этот массив по возрастанию.

28.

const int N = 5; // количество элементов массива
float x [ N ];
int i, a;
/* заполняем массив */
for (i=0; i<N; i++){
cout << “ x[ “ << i << “ ]= ";
cin>>x[ i ];
}
cout << endl;
/* сравниваем 1 и 2 элементы массива и т. д.*/
for (i=0; i<N-1; i++) {
for (i=0; j<N-1; j++) {
if (x [ j ] > x [ j+1 ]) {
a = x [ j ];
x [ j ] = x [ j+1 ];
x [ j+1] = a;
}
}
}
/* выводим отсортированный массив на экран */
for (i=0; i<N; i++){
cout << x[ i ] << “ ”; }

29. Удаление данных из массива

Достаточно часто из массива необходимо удалить
ненужные элементы. Что означает слово удалить?
Иногда бывает приемлемо «заменить», но чаще всего
под этим подразумевают именно удаление, т.е. на место
удалённого элемента должен быть записан тот элемент
массива, который должен остаться. Элементы массива
необходимо сдвинуть к какому-нибудь краю массива.
Обычно сдвиг делается в сторону начала массива, чтобы
индексация снова была с нуля.

30. Пример 6

Дан массив из n целых чисел. Удалить из
него все числа, меньше нуля. Массив сжать. На рисунке
ниже приведён массив x из 5 чисел до и после удаления
отрицательных чисел.
Просматриваем массив слева на право, как только
находим подходящий для удаления элемент, так сразу же
сдвигаем все элементы правее его на одну позицию влево.

31. Вариант 1

int n = 5; int x[n]; int i, j, k;
cout << "Input " << n << " numbers:" << endl;
for(i = 0; i < n; i++)
cin >> x[i];
k = n; // Первоначально в массиве все элементы.
/* Затем k будет означать количество оставшихся после удаления.*/
for(i = 0; i < k; i++) {
if(x[i] < 0) { // удаление отрицательного элемента массива
k--;
// уменьшаем количество
for(j = i; j < k; j++) // сдвиг влево
x[j] = x[j+1];
i--;
// Снова просматриваем i-й элемент
} }
cout << "Otvet:" << endl; // выводим получившийся массив
for(i = 0; i < k; i++)
cout << x[i] << endl;

32. Вариант 2

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

33.

int n = 5; int x[n]; int i, j, k;
cout << "Input " << n << " numbers:" << endl;
for(i = 0; i < n; i++)
cin >> x[i];
k = n; // Первоначально в массиве все элементы.
/*Затем k будет означать количество оставшихся после удаления.*/
for(i = k-1; i >= 0; i--) {
if(x[i] < 0) { // условие на удаление элемента массива
k--;
// уменьшаем количество
for(j = i; j < k; j++) // сдвиг
x[j] = x[j+1];
}
}
cout << "Otvet:" << endl; // выводим получившийся массив
for(i = 0; i < k; i++)
cout << x[i] << endl;

34. Вариант 3

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

35.

int n = 5; int x[n]; int i, j, k;
cout << "Input " << n << " numbers:" << endl;
for(i = 0; i < n; i++)
cin >> x[i];
k = 0; /*Вначале это позиция, в которую отправляем оставшийся
элемент.
Затем k будет означать количество оставшихся после
удаления элементов. */
for(i = 0; i < n; i++) {
if(!(x[i] < 0)) { // условие не на удаление элемента из массива, а
на оставление его в массиве
x[k] = x[i]; k++;
}
}
cout << "Otvet:" << endl; // выводим получившийся массив
for(i = 0; i < k; i++)
cout << x[i] << endl;

36. Вставка (добавление) данных в массив

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

37. Пример 7

Дан массив из n целых чисел. Перед каждым
положительным числом добавить число 0.

38.

int n = 5; int x[2*n]; int i, j, k;
cout << "Input " << n << " numbers:" << endl;
for(i = 0; i < n; i++)
cin >> x[i];
k = n; /* Первоначально в массиве все элементы. Затем k будет
означать количество после добавления. */
for(i = 0; i < k; i++) {
if(x[i] > 0) { // условие на вставку элемента массива
for(j = k; j > i; j--) // сдвиг в право
x[j] = x[j-1];
x[i] = 0; // вставка нового элемента
k++;
// увеличиваем количество
i++;
// делаем обход уже обработанного элемента
} }
cout << "Otvet:" << endl; // выводим получившийся массив
for(i = 0; i < k; i++)
cout << x[i] << endl;