Многомерные массивы
Одномерный массив.
Тема 5. Статические и динамические массивы.
Конспект лекций. 3 часть.
Массив – это сложная переменная, которая обозначает упорядоченный набор данных одного типа.
Т.е. массив - это контейнер, в котором можно располагать, извлекать данные (объекты). Объявление и инициализация одномерные массивы:
int А[5] = {1,2,3,4,5}; double B[3] = {2.2, 3.3, 4,4};
Квадратные скобки - это обязательный элемент в объявлении массива. В них указывается его размер, т.е. количество элементов, которые в нем содержатся. Кстати, этот параметр является необязательным, т.е. если мы при объявлении массива, сразу его инициализируем, то можно опустить значение в скобках, т.к. наш компилятор сам посчитает количество элементов:
int a[] = {1,2,3,4,5}; double b[] = {2.2, 3.3, 4,4};
Объявление и ввод массива.
Пример:
int a[5];
for (int i =0; i < 5;i++)
scanf ("%d", &a[i]);
Обращение к элементам массива происходит по его индексу. В С/C++ индексы всегда начинаются с нуля. Имя массива является указателем на первый элемент. Поэтому при передаче массива в функцию, не будет проблемы с изменением значений.
Рассмотрим пример:
void PrintArr (int arr[], int len)
{ for (int i = 0; i < len; i++){ printf ("%d", arr[i]); }
}
Эта функция выведет одномерный массив, который мы заполнили чуток выше. Кстати, вместе с массивом мы передаем его длину, чтобы не выйти за его пределы. Во многих компиляторах, уход за пределы массива оканчивается ошибкой, а некоторые компиляторы продолжают выполнение программы, выводя жуткие результаты. Поэтому будьте осторожны и определяйте длину массива функцией sizeof(), во избежание ошибок.
Вызов этой функции:
PrintArr(a, 5);
Т.е. мы передаем адрес массива, поэтому копии ни какой не создается и все отраззится в главной функции main.
Многомерные массивы так же часто используются, как и одномерные. Многомерные массивы - это массивы массивов. Т.е. каждый индексный номер содержит массив.
Пример:
int i[2][4] = {{1,2,3,4}, {5,6,7,8}};
Задаем двумерный массив размером 2х4. Т.е. 2 строчки по 4 элемента каждая.
Ввод/вывод элементов:
#include <conio.h>
#include <stdio.h>
int main()
{ int arr[2][4];
for (int i = 0; i < 2; i++)
{ for (int j = 0; j < 4;j++ )
{ scanf ("%d", &arr[i][j]); }
}
for (int i = 0; i < 2; i++){
for (int j = 0; j < 4; j++ ) { printf ("%d ", arr[i][j]); }
printf ("\n");
}
getch();
return 0;
}
Все очень похоже на одномерный массив. Только в многомерном массиве создаем двойной цикл, первый - это проход по столбцу, а второй - это проход по элементам массива (идем по строке).
Во всех моих примерах при изменении размера многомерного массива, например вместо arr[2][4], хотим сделать arr[7][6]. Так вот, что бы сделать такое изменения придется изменять абсолютно все циклы, так как они ориентируются по старым данным. Но есть способ исправить эту проблему.
Для этого в языке С/C++ есть директива предпроцессора define.
Рассмотрим пример:
#include <conio.h>
#include <stdio.h>
#define SIZE_A 2
#define SIZE_B 2
int main()
{ int arr[SIZE_A][SIZE_B];
for (int i = 0; i < SIZE_A; i++)
{ for (int j = 0; j < SIZE_B;j++ )
{ scanf ("%d", &arr[i][j]); }
}
for (int i = 0; i < SIZE_A; i++)
{ for (int j = 0; j < SIZE_B;j++ )
{ printf ("%d ", arr[i][j]); }
printf ("\n");
}
getch();
return 0;
}
Для массивов часто применимы следующие алгоритмы обработки: суммирование, нахождение максимума (минимума), поиск элементов, сортировка.
Примеры:
1) Нахождение различных сумм в одномерном массиве.
#include <conio.h>
#include <stdio.h>
int main() {
// Ввод массива
____________________________________
for (s=0,i=0; i<n; i++) // Сумма элементов массива
s+=A[i];
_________________________________________________
// Вывод массива
getch();
return 0; }
Можно предложить такие варианты суммирования:
for (s=0,i=0; i<n && A[i]>=0; i++) // Сумма элементов массива до первого
s+=A[i]; // отрицательного
_________________________________________________________________________
for (s=0,i=0; i<n; i++) // Сумма положительных элементов
if (A[i]>0) s+=A[i]; // массива
2) Дан двухмерный массив. Необходимо, сделать ввод/вывод двумерного массива. Найти максимальный элемент двумерного массива.
#include <iostream>
#include <conio.h>
const int n = 3; //объявляем константу для массива
const int n = 3; //объявляем константу для массива
void main () {
int X[n][n]; int i,j;
int max = 0;
for (i = 0; i < n ; i++)
for (j = 0; j < n ; j++){
cout<<"X["<<i<<","<<j<<"] = "; //На экран выводится 'X[i][j] = '
cin>>X[i][j]; //вводим с клавиатуры целые числа
}
cout<<"\n"; //Переход на следующую строку
for (i = 0; i < n ; i++){ //цикл вывода массива
cout<<"\n"; //Переход на следующую строку
for (j = 0; j < n ; j++){
cout<<"X["<<i<<"]"<<"["<<j<<"] = "<<X[i][j]<<"\t"; //На экран выводится результат нашего ввода
}
}
max = X[0][0]; //Пусть максимальное число - это первое число массива
for (i = 1; i < n ; i++){ //цикл нахождение максимального элемента массива
cout<<"\n"; //Переход на следующую строку
for (j = 0; j < n ; j++){
if (X[i][j]> max) max = X[i][j]; //если есть число большее, чем max
//тогда max принимает значение этого числа
}
}
cout<<"\n";
cout<<"Max = "<<max<< endl; //На экран монитора выводится максимальное число
getch();
}
3) Задача поиска.
Двоичный поиск в упорядоченных данных. Алгоритм двоичного или бинарного поиска основан на делении пополам текущего интервала поиска. В основе его лежит тот факт, что при однократном сравнении искомого элемента и некоторого элемента массива мы можем определить, справа или слева от текущего следует искать. Проще всего выбирать элемент на середине интервала, в котором производится поиск. Алгоритм:
· искомый интервал поиска делится пополам и по значению элемента массива в точке деления определяется, в какой части следует искать значение на следующем шаге цикла;
· для выбранного интервала поиск повторяется;
· при «сжатии» интервала в 0 поиск прекращается;
· в качестве начального интервала выбирается весь массив.
//------Двоичный поиск в упорядоченном массиве
int binary(int c[], int n, int val){ // Возвращает индекс найденного
int a,b,m; // Левая, правая границы и
for(a=0,b=n-1; a <= b;) { // середина
m = (a + b)/2; // Середина интервала
if (c[m] == val) // Значение найдено -
return m; // вернуть индекс найденного
if (c[m] > val)
b = m-1; // Выбрать левую половину
else
a = m+1; // Выбрать правую половину
}
return -1; } // Значение не найдено
4) Сортировка. Сортировки различаются применимыми методами выполнимых операций.
Известны следующие методы: выбором и вставками, обменные, на основе разделения/слияния.
Примры:
//------ Простая сортировка
void sort(int A[], int n){
for (int i=0; i<n; i++)
for (int j=i; j<n; j++)
if (A[i]>A[j]){
int c=A[i]; A[i]=A[j]; A[j]=c;}
}
Необходимо переставлять элементы массива, если они нарушают порядок, количество таких перестановок должно соответствовать количеству возможных пар элементов, а это дает цикл в цикле.
//------Обменная сортировка "пузырьком"
Это самое прямолинейное решение проблемы: если в упорядоченной последовательности все пары соседних элементов упорядочены, то нужно достаточно долго переставлять «неправильные» пары, пока порядок не установится. Первая оптимизация состоит в том, что сортировку можно прекратить, если при просмотре всех пар от начала да конца перестановок не будет.
void sort(int A[], int n){
int i,found; // Количество обменов
do { // Повторять просмотр...
found =0;
for (i=0; i<n-1; i++)
if (A[i] > A[i+1]) { // Сравнить соседей
int cc = A[i]; A[i]=A[i+1]; A[i+1]=cc;
found++; // Переставить соседей
}
} while(found !=0); } //...пока есть перестановки