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

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

Тема 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); } //...пока есть перестановки

Дата добавления: 2014-01-06