массивы (1)

1.

Массивы
Если с группой величин одинакового типа требуется
выполнять однообразные действия, им дают одно имя, а
различают по порядковому номеру. Это позволяет
компактно записывать множество операций с помощью
циклов. Конечная именованная последовательность
однотипных величин называется массивом. Описание
массива в программе отличается от описания простой
переменной наличием после имени квадратных скобок,
в которых задается количество элементов массива
(размерность):
float а[10];// описание массива из 10
//вещественных чисел

2.

Элементы массива нумеруются с нуля. Инициализирующие
значения для массивов записываются в фигурных скобках.
Значения элементам присваиваются по порядку. Если
элементов в массиве больше, чем инициализаторов,
элементы, для которых значения не указаны, обнуляются:
int b[5] = {3,2,1};
// b[0]=3; b[1]=2;
//b[2]=1;b[3]=0;b[4]=0;

3.

Размерность массива вместе с типом его элементов
определяет объем памяти, необходимый для размещения
массива, которое выполняется на этапе компиляции, поэтому
размерность может быть задана только целой положительной
константой или константным выражением. Если при описании
массива не указана размерность, должен присутствовать
инициализатор, в этом случае компилятор выделит память по
количеству инициализирующих значений.
Доступ к элементам массива
Можно получать доступ к элементам массива, используя
индексы и оператор [ ]. Допустим, объявили массив marks. К
первому элементу можно обратиться выражением marks[0], ко
второму - выражением marks[1], и так далее.
// Объявляем массив оценок
int marks[5];
marks[0] = 19; marks[1] = 10; marks[2] = 8; marks[3] = 17;
marks[4] = 9;

4.

// Объявляем массив оценок
int marks[5];
marks[0] = 19; marks[1] = 10; marks[2] = 8; marks[3] = 17;
marks[4] = 9;

5.

Для доступа к элементу массива после его имени
указывается номер элемента (индекс) в квадратных скобках.
В следующем примере подсчитывается сумма элементов
массива.
#include <iostream>
using namespace std;
int main(int argc, char* argv[]){
const int n = 10;
int i,sum;
int marks[n] = {3,4, 5, 4, 4};
for (i = 0, sum = 0; i<n; i++)
sum += marks[i];
cout<< "Сумма элементов: "<< sum;
system("pause");
return 0;
}

6.

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

7.

Инициализация массива при объявлении
Можно инициализировать массив при объявлении. Для
этого надо указать в списке столько значений, сколько
вмещает массив, либо одно значение 0, чтобы
заполнить массив нулями:
// Объявляем массив размера 5 иинициализируем
int marks[5] = { 19, 10, 8, 17, 9 }; // Объявляем массив
без указания //размера; размер будет определён из
//списка инициализациии.
int marks[] = { 19, 10, 8, 17, 9 };
// Объявляем массив размера 10 и //заполняем
нулями.
int ages[10] = { 0 };

8.

Идентификатор массива является константным указателем
на его нулевой элемент. Например, для массива из
предыдущего листинга имя marks — это то же самое,что
&marks[0], а к i-му элементу массива можно обратиться,
используя выражение *(marks+i)
Можно описать указатель, присвоить ему адрес начала
массива и работать с массивом через указатель.
Следующий фрагмент программы копирует все элементы
массива а в массив b:
int а[10], b[10];
int *pa = a; // или int *р = &а[0];
int *pb = b;
for (int i = 0; i<10; i++){
*pb++= *pa++; // или pb[i] = pa[i];

9.

Двумерные массивы. Многомерные массивы
Двумерный массив – это список одномерных массивов.
Для доступа к элементам двумерного массива нужно
указать два индекса. Если рассматривать массив как
таблицу, тогда первый индекс определяет строку.
Второй индекс определяет столбец таблицы.
Описание двумерного массива:
тип имя_массива[строк][столбцов];
Пример,
int matr [6][8];
задает описание двумерного массива из 6 строк и 8
столбцов.

10.

В памяти такой массив располагается в
последовательных ячейках построчно. Многомерные
массивы размещаются так, что при переходе к
следующему элементу быстрее
всего изменяется последний индекс. Для доступа к
элементу многомерного массива указываются все его
индексы, например, matr[i][j]. всего изменяется
последний индекс.
Или следующим способом:
*(matr[i]+j) или *(*(matr+i)+j). Это возможно, поскольку
matr[i]
является адресом начала i-й строки массива.

11.

12.

При
инициализации
многомерного
массива
он
представляется либо как массив из массивов, при этом
каждый массив заключается в свои фигурные скобки (в этом
случае левую размерность при описании можно не
указывать), либо задается общий список элементов в том
порядке, в котором элементы располагаются в памяти:
int mass2[][2] = {{1,1},{0, 2},{1,0}};
int mass2[3][2] = {1,1,0,2,1,0};
Пример. Программа определяет в целочисленной матрице
номер строки, которая содержит наибольшее количество
элементов, равных нулю.

13.

const int nstr = 4, nstb = 5; // размерности массива
int b[nstr][nstb]; // описание массива
for (int i = 0; i<nstr; i++) // ввод массива
for (int j = 0; j<nstb; j++) cin>>b[i][j];
int istr = -1, MaxKol = 0;
for (int i = 0; i<nstr; i++){
int kol = 0;
for ( int j = 0; j<nstb; j++)
if ( b[i][j]==0) kol++;
if (kol > MaxKol) {istr = i; MaxKol = kol;}}
cout<< "Mass :"<<endl;
for (int i = 0; i<nstr; i++){
for (int j = 0; j<nstb; j++) cout<<b[i][j];
cout<<" "<<endl;}
if ( istr==-1) cout<<"Нулевых элементов нет";
else cout<<"# str: "<< istr;

14.

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

15.

Динамические массивы создают с помощью
операции new, при этом необходимо указать тип и
размерность, например:

16.

int n = 100;
float *р = new float [n];
В этой строке создается переменная-указатель на float, в
динамической памяти отводится непрерывная область, достаточная
для размещения 100 элементов вещественного типа, и адрес ее
начала записывается в указатель р. Динамические массивы нельзя
при создании инициализировать, и они не обнуляются. Преимущество
динамических массивов состоит в том, что объем памяти,
выделяемой под массив, определяется на этапе выполнения
программы. Доступ к элементам динамического массива
осуществляется точно так же, как к статическим, например, к
элементу номер 5 приведенного выше массива можно обратиться как
р[5] или *(р+5).Память, зарезервированная под динамический массив
с помощью new[], должна освобождаться оператором delete [] .
Например,
delete [ ] р;

17.

Альтернативный способ создания динамического
массива – использование функции mallос библиотеки С:
int n = 100;
float *q =(float *) malloc(n * sizeof( float )) ;
Операция преобразования типа, записанная перед
обращением к функции mallос, требуется потому, что
функция возвращает значение указателя типа void*, а
инициализируется указатель на float.
Память,
выделенная
функцией
mallос
–
высвобождается посредством функции free, например:
free (q);
При
несоответствии
способов
выделения
и
освобождения памяти результат не определен.

18.

Для создания динамического многомерного массива
необходимо указать в операции new все его размерности
(самая левая размерность может быть переменной),
например:
int nstr = 5;
int ** m = (int**)new int[nstr][10];
Более универсальный и безопасный способ выделения
памяти под двумерный
массив, когда обе его размерности задаются на этапе
выполнения программы, приведен ниже:
int nstr, nstb;
cout «" Введите количество строк и столбцов :" ;
cin »nstr »nstb;
int **a = new int* [nstr];//1
for ( int i=0; i<nstr; i++)//2
a[i] = new int [nstb];//3

19.

20.

1 - объявляется переменная типа «указатель на указатель
на int» и выделяется память под массив указателей на
строки массива (количество строк —nstr).
2 - организуется цикл для выделения памяти под каждую
строку массива.
3 - каждому элементу массива указателей на строки
присваивается адрес начала участка памяти, выделенного
под строку двумерного массива. Каждая строка состоит из
nstb элементов типа int.

21.

Массивы и указатели
Массивы и указатели тесно связаны. Имя массива
является указателем-константой на его первый
(нулевой) элемент.
имя_массива[индекс] – выражение с двумя операндами:
имя_массива – константный указатель – адрес начала
массива в памяти; индекс – определяет смещение от
начала массива. Действие бинарной операции [ ] можно
объяснить так:
*(имя_массива + индекс);
int a [10]; //a-адрес массива (указатель-константа)
(a+i) == &a[i]; // (a+i) = (a + i *sizeof (int) );
*(a+i) == a[i]; //нельзя писать a++ или а-// так как а – указатель-константа и его нельзя изменять

22.

int *pa, ai;//инициализация указателя
// pa адресом массива а
pa= &a[0];
pa=a; // нельзя писать a=pa;
//так как а – указатель-константа и его
// нельзя изменять
(pa+1) == &a[1];// и можно писать ра++
// или pa-(pa+i) == &a[i];
*(pa+i) == pa[i] *(pa+i)==a[i];
pa[i] == a[i];
ai= *pa; ai равно a[0];

23.

Правило:
Имя массива и индексное выражение можно
записать как ссылку и смещение и
наоборот:
(a+i) есть &a[i]
*(a+i) == a[i] ==i[a] !!!
имя масс == &имя масс == &имя_масс[0]

24.

Примеры,
int *numbers {new int[4]}; // динамический массив из 4 чисел
// int *numbers = new int[4]; // или так
int *numbers1 {new int[4]{}}; // массив состоит из чисел 0, 0, 0, 0
int *numbers2 {new int[4]{ 1, 2, 3, 4 }}; // массив состоит из чисел 1, 2, 3, 4
int *numbers3 {new int[4]{ 1, 2 }}; // массив состоит из чисел 1, 2, 0, 0
// аналогичные определения массивов
// int *numbers1 = new int[4]{}; // массив состоит из чисел 0, 0, 0, 0
// int *numbers1 = new int[4](); // массив состоит из чисел 0, 0, 0, 0
// int *numbers2 = new int[4]{ 1, 2, 3, 4 }; // массив состоит из чисел 1, 2, 3, 4
// int *numbers3 = new int[4]{ 1, 2 }; // массив состоит из чисел 1, 2, 0, 0
При инициализации массива конкретными значениями следует
учитывать, что если значений в фигурных скобках больше чем
длина массива, то оператор new не сможет создать массив.
Для задания размера динамического массива можем применять
обычную переменную, а не константу, как в случае со
стандартными массивами.

25.

Освобождение памяти для одномерного массива
Для удаления динамического массива и освобождения его
памяти применяется специальная форма оператора
delete:
delete [] указатель_на_динамический_массив;
Например,

26.

#include <iostream>
int main(){
unsigned n{ 5 }; // размер массива
int* p{ new int[n] { 1, 2, 3, 4, 5 } };
// используем индексы
for (unsigned i{}; i < n; i++) {
std::cout << p[i] << "\t";
}
std::cout << std::endl;
delete [] p;
}

27.

Чтобы после освобождения памяти указатель не хранил
старый адрес, также рекомендуется обнулить его:
delete [] p;
p = nullptr; // обнуляем указатель
Освобождение памяти для многомерных массивов

28.

int main(){
unsigned rows = 3;
// количество строк
unsigned columns = 2; // количество столбцов
int** numbers{new int*[rows]{}}; // выделяем память
под двухмерный массив
for (unsigned i{}; i < rows; i++){
numbers[i] = new int[columns]{}; }
// вводим данные для таблицы rows x columns
for (unsigned i{}; i < rows; i++){
std::cout <<"Enter data for "<< (i + 1) << " row"<< std::endl;
// вводим данные для столбцов i-й строки
for (unsigned j{}; j < columns; j++){
std::cout << (j + 1) << " column: ";
std::cin >> numbers[i][j]; }
}

29.

// вывод данных
for (unsigned i{}; i < rows; i++){
// выводим данные столбцов i-й строки
for (unsigned j{}; j < columns; j++){
std::cout << numbers[i][j] << "\t";}
std::cout << std::endl;}
for (unsigned i{}; i < rows; i++)
{
delete [ ] numbers[i];
}
delete [ ] numbers;
}

30.

ПОИСК В МАССИВЕ
Поиск – это просмотр некоторого набора однотипных данных с
целью нахождения одного или более элементов, обладающих
определенным свойством, или с целью установления факта
отсутствия таковых элементов. Все методы поиска
подразделяются на две группы: поиск в неупорядоченном наборе;
поиск в упорядоченном наборе.
Поиск в неупорядоченном наборе заключается в последовательном
переборе элементов массива и сравнении их значений с ключом
до того момента, пока результат сравнения не даст значение
«истина» (разумеется, искомого значения в массиве может и не
быть). При наличии большого числа элементов в наборе процесс
поиска может затянуться. Наиболее эффективные методы поиска
работают только на упорядоченных наборах данных. Если
предполагается вести поиск в большом наборе, этот набор
необходимо предварительно отсортировать.

31.

Принцип двоичного поиска. Исходный массив делится
пополам и для сравнения выбирается средний
элемент. Если он совпадает с искомым, то поиск
заканчивается. Если же средний элемент меньше
искомого, то все элементы левее его также будут
меньше искомого. Следовательно, их можно
исключить из зоны дальнейшего поиска, оставив
только правую часть массива. Аналогично, если
средний элемент больше искомого, то отбрасывается
правая часть, а остается левая. На втором этапе
выполняются аналогичные действия над оставшейся
половиной массива. В результате после второго этапа
остается ¼ часть массива. И так далее, пока или
элемент будет найден, или длина зоны поиска станет
равной нулю. В последнем случае искомый элемент
найден не будет.

32.

Алгоритм:
1.Положить left=0, right=n;
2.Пока left < right выполнять:
найти индекс среднего элемента в массиве mid =
(left+right)/2;
если для элемента массива с индексом mid значение ключа
> искомого, положить right =mid-1, иначе если значение
ключа < искомого, положить left = mid+1, иначе выйти из
цикла (элемент с индексом mid найден);
3.Если значение ключа элемента с индексом mid совпадает
с заданным, поиск успешен, иначе – искомого элемента в
массиве нет.

33.

int main(){
const int n=10; int mas[n];find, i, res=-1;
int left = 0, right = n-1, mid = 0;
for ( i=0; i<n; i++) mas[i] = i*10; //заполнение массива числами
cout << "\n value of find: "; cin >> find;
while (left <= right){
mid = (left+right+1)/2;
if (mas[mid] > find)
right = mid-1;
else if (mas[mid] < find)
left = mid+1;
else break; }

34.

if (mas[mid] == find) res=mid;
else res=-1;
if (res==-1) cout << "\n no element";
else cout << "\nelement nomer " << res<<endl;
system("pause");
return 0;
}
СОРТИРОВКА МАССИВОВ
Сортировка – это процесс упорядочения некоторой
последовательности
нумерованных
объектов
в
соответствии с заданным признаком.
Цель сортировки – облегчить последующий поиск
элементов в отсортированной последовательности.

35.

При решении задачи сортировки обычно выдвигается
требование
минимального
использования
дополнительной памяти, т.е. недопустимость применения
дополнительных массивов. Для оценки быстродействия
алгоритмов различных методов сортировки, как правило,
используют два показателя: количество присваиваний и
количество сравнений.
Все методы сортировки можно разделить на две большие
группы: прямые методы сортировки и улучшенные
методы сортировки. Прямые методы сортировки по
принципу, лежащему в основе метода, подразделяются
на три подгруппы:
• сортировка обменом («пузырьковая» сортировка);
• сортировка вставкой (включением);
• сортировка выбором (выделением).

36.

Сортировка обменом («пузырьковая» сортировка)
Это один из простейших методов. Метод хорошо работает
на простых структурах данных или данных, в некоторой
степени отсортированных. В алгоритме выполняются
последовательные перемещения соседних элементов. Во
время каждого перемещения элементы сравниваются и
меняются местами, если они расположены не в желаемом
порядке. В результате после каждого перемещения
максимальный элемент будет стоять на последней
позиции («всплыл» первый «пузырек»). Отсортированные
элементы не нуждаются в сравнении при последующих
перемещениях, поэтому второй проход перемещений
выполняется до предпоследнего элемента и т.д. Всего
для массива размерности n требуется (n-1) проход.

37.

38.

39.

40.

Алгоритм: последовательно сравниваем каждую пару
соседних чисел и в зависимости от результата
сравнения их переставляем или оставляем на месте.
За один просмотр наибольшее число переместится в
конец, но результата не достигнем, поэтому повторяем
процесс. Алгоритм реализуется с помощью двух
вложенных циклов.
В первом, плохом, варианте и внутренний, и внешний
циклы можно повторить (n -1) раз, где
n – размерность массива.

41.

int main(){
const int n = 10; int i, j;
int x[n] = {37,84,62,91,11,65,57,28,19,49};
for ( i=1; i<n; i++) {
for ( j=0; j<n-i; j++)
if (x[j] > x[j+1]) {
int r=x[j];
x[j]=x[j+1];
x[j+1]=r;}
}
for(j=0; j<n; j++) cout << x[j] << " ";
system("pause");
return 0;}

42.

43.

Сортировка одномерного массива по некоторому
признаку
Рассмотрим сортировку одномерного целочисленного
массива по возрастанию последней цифры значения
элемента.
1.Вначале строим массив параметров (массив D[n]
последних цифр).
2.Сравниваем не сами элементы, а эти параметры. И если
они равны, только тогда сравниваем сами числа.
3.Переставляем не только сами числа, но и параметры,
чтобы они соответствовали тем же числам, что и до
сортировки.

44.

#include <iostream>
#include <time.h>
using namespace std;
int main(){
const int n = 10; int x[n], D[n], i, j;
cout<< "x[i]" << endl;
//заполнение массива х
for (i = 0; i<n; i++) x[i]= rand();
for (i = 0; i<n; i++) cout << x[i] << " ";
cout<< endl;
for ( i=0; i<n; i++) //заполнение массива D
последних цифр
D[i] =x[i] %10;
cout<< "D[i]" << endl;
for (i = 0; i<n; i++) cout << D[i] << " ";
cout<< endl;

45.

int flag = 1, k=n;
while (flag) //сортировка массива «пузырьком»
{ k--;
flag=0;
for ( j=0; j<k; j++)
if((D[j]>D[j+1])||(D[j]==D[j+1]&&x[j]>x[j+1]))
{int r=x[j]; int r1=D[j];
x[j]=x[j+1]; D[j]=D[j+1];
x[j+1]=r; D[j+1] = r1;
flag=1;}}
cout << endl;
for (i = 0; i<n; i++) cout << x[i] << " ";
cout << endl; // для отладки вывод массива D
for (i = 0; i<n; i++) cout << D[i] << " ";
system("pause"); return 0; }

46.

47.

Сортировка вставкой
Массив разделяется на две части: отсортированную и
неотсортированную. Элементы из неотсортированной
части поочередно выбираются и вставляются в
отсортированную часть так, чтобы не нарушить в ней
упорядоченность элементов. В начале работы алгоритма
в качестве отсортированной части массива принимают
только один первый элемент, а в качестве
неотсортированной – все остальные элементы.

48.

Алгоритм будет состоять из (n-1)-го прохода (n –
размерность массива), каждый из которых будет
включать четыре действия:
• взятие очередного i-го неотсортированного элемента
и сохранение его в дополнительной переменной;
• поиск позиции j в отсортированной части массива, в
которой присутствие взятого элемента не нарушит
упорядоченности элементов;
• сдвиг элементов массива от (i-1)-го до j-го вправо,
чтобы освободить найденную позицию вставки;
• вставка взятого элемента в найденную позицию.

49.

int main()
{const int n =10; int x[n];
for (int i=0; i<n; i++) x[i] =n-i;
for (int i=1; i< n; i++) //считаем, что до i
элементы отсортированы
{ int temp = x[i]; //берем очередной элемент
int j = i-1;
while ((temp < x[j]) && (j>=0)) // цикл поиска
позиции вставки
{ x[j+1] = x[j]; // сдвиг элементов
j--;}
x[j+1] = temp;
}
system("pause");
return 0;
}

50.

Сортировка выбором
Выбираем (находим) в массиве элемент с
минимальным значением от первого (0-го)
элемента до последнего ( (n-1)-го) и меняем его
местами с первым элементом. На втором шаге
находим элемент с минимальным значением на
интервале от 2-го до последнего элемента и
меняем его местами со вторым элементом. И так
далее для всех элементов до (n-1)-го.

51.

int main(){
const int n =10; int x[n]; int i, j;
for (i=0; i<n; i++) x[i] = n-i;
for (i=0; i<n-1; i++){
int min = x[i]; //выбор минимального элемента
int i_min = i ; // и запоминание его номера
// поиск минимального элемента в оставшейся части массива
for (j=i+1; j< n; j++)
if (x[j] < min)
{min = x[j]; i_min = j;}
x[i_min] = x[i]; //замена элементов
x[i] = min;
}
for (i=0;i<n;i++) cout<<" " << x[i]; //вывод
отсортированного массива
system("pause");return 0;}

52.

Поиск в массиве максимального элемента и его номера
#include <iostream>
#include <time.h>
using namespace std;
int main(){
const int n=20; static int mas[n], ar[n];
int i, max,imax=0;
srand (time(0));//для получения разных
//псевдослучайных последвательностей
for (i=0; i<n; i++) ar[i]=mas[i] =rand()%15;
//заполнение массива случайными числами от 0 до 14
for (i=0; i<n; i++) cout<<"
cout<<endl;
for (i=0; i<n; i++) cout<<"
cout<<endl;
"<< mas[i];
"<< ar[i];

53.

//первый способ
max=mas[0];imax=0;
for (int i=1; i<n; i++)
if (max < mas[i]) { max = mas[i]; imax=i;}
//максим.элемент и его номер
cout<<"max ="<<max<<"imax="<< imax+1 <<endl;
//второй способ
imax=0;
for (int i=1; i<n; i++) //поиск номера максим.элемента
imax = ar[imax] < ar[i] ? i : imax;
max = ar[imax];
cout<<"max = "<< max <<" imax= "<< imax+1 <<endl;
system("pause");
return 0;
}

54.

Нахождение суммы элементов вещественного массива,
расположенных правее последнего отрицательного элемента
#include <iostream>
#include <time.h>
using namespace std;
int main(){
int n; int i,ineg=0;
cout << "n=?"; cin >>n;
new double [n];
double sum, *a =new double [n];
for (i= 0; i<n;i++){
cout << "a[i]= ?"; cin >> a[i];
}
for (i= 0; i<n;i++) cout << a[i] << " ";

55.

for (i= 0; i<n;i++) if (a[i] < 0) ineg = i;
for (sum = 0, i=ineg+1; i < n; i++) sum+=a[i];
cout << "\nsum:" << sum<<endl;
delete[] a;
system("pause");
return 0;
}