Структурированные типы данных. программирование алгоритмов обработки массивов

Массив – это упорядоченная последовательность данных одного типа, имеющих одно имя. Массив описывается следующим образом:

<тип> <имя массива> [n1] [n2]…

где n1, n2 – размер массива по данному измерению.

Элемент массива представляет собой индексированную переменную, индекс которой указывается в квадратных скобках. Индекс может быть целой константой, целой переменной или выражением целого типа. Все массивы индексируются с нуля.

Массивы подобно переменным могут быть инициализированы начальными значениями, например.

float a[3]={1.2, 3.4, -0.1};

где a[0]=1.2, a[1]=3.4, a[2]=-0.1.

Имя массива является константой указателем на адрес первого элемента массива. Начальный адрес массива определяется компилятором в момент описания массива и не может быть переопределен.

Наиболее серьезная и распространенная ошибка при работе с массивами – выход за границу массива, т.е. когда предпринимается попытка записать или прочитать значение по адресу памяти, который не был описан в программе.

Массивы хранятся в памяти как сплошные последовательности компонентов, причем быстрее изменяется дальний правый индекс.

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

<имя>[<индекс>]

В данном типе определена единственная операция присваивания. Можно присваивать массив лишь массиву, например: А=С. Операции сравнения производиться только поэлементно.

При работе с массивами выделяют следующие типовые операции:

1. Заполнение массива возможно либо с помощью генератора случайных чисел (random()), либо с клавиатуры, либо по определенному правилу.

Пример.

for (i=0; i<n; i++)

for (j=0; j<n; j++)

cin>> a [i][j];

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

структурированные типы данных. программирование алгоритмов обработки массивов - student2.ru

Рис. 5. Принятое деление матрицы на четверти.

Условия нахождения элементов в каждой из частей матрицы следующие:

1. I: (i<j) && (i+j<n-1)

2. II: (i<j) && (i+j>n-1)

3. III: (i>j) && (i+j>n-1)

4. IV: (i>j) && (i+j<n-1)

5. на главной диагонали: i = = j

6. на побочной диагонали: i+j = = n-1

где i – номер строки, j – номер столбца, в которых находится элемент матрицы, n – размерность квадратной матрицы.

2. Вычисление суммы, произведения, среднего арифметического, среднего геометрического, количества элементов, удовлетворяющих некоторому условию.

Пример. Вычислить сумму положительных элементов матрицы и количество отрицательных элементов.

for (i=0; i<n; i++)

for (j=0; j<n; j++)

{if a[i][j]>0 s+=a[i][j];

else k++;

}

3. Сортировка массива

Идея метода сортировки выбором состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.

Шаги алгоритма:

1. находим минимальное значение в текущем списке;

2. производим обмен этого значения со значением на первой позиции;

3. сортируем хвост списка, исключив из рассмотрения уже отсортированный первый элемент.

Будем строить выходную последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная с нулевого и заканчивая (n-1)-м.

На i-м шаге выбираем наименьший из элементов x[i] ... x[n] и меняем его местами с x[i]. Последовательность шагов при n=5 изображена на рис. 6.

структурированные типы данных. программирование алгоритмов обработки массивов - student2.ru

Рис. 6. Сортировка выбором.

Вне зависимости от номера текущего шага i, последовательность x[0]...x[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме x[n], оказывается отсортированной, а x[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

Пример программной реализации.

for (i = 0; i < n-1; i++) { min = i; for (j = i+1; j < n; j++) { if (x[min] > x[j]) { // сортировка по убыванию min = j; } } temp = x[i]; x[i] = x[min]; x[min] = temp;}

4. Вставка и удаление элементов массива

Удаление одного элемента из массива происходит по следующей схеме:

- указывается или ищется порядковый номер элемента, который необходимо удалить из массива;

- все элементы, стоящие за удаляемым элементом, сдвигаются на одну позицию влево;

- количество элементов уменьшается на единицу.

for (i=0; i<n; i++) // n – номер удаляемого элемента

a[j]=a[j+1];

k-=1; // количество элементов

Пример.Найти значение и номер наименьшего элемента в массиве.

Алгоритм решения задачи показан на рис.7.

#include <stdio.h> // библиотека, содержащая описание

// операторов ввода/вывода

# include <conio.h> // библиотека, содержащая описание

// операторов для работы с экраном

# include <stdlib.h> // библиотека, содержащая описание

// генератора случайных чисел

void main() // заголовок главной функции программы

{int a*, i, min, n; // описание целых переменных

clrscr(); // очистка экрана

cout<<”Input size of array”; // вывод информационного сообщения

cin>>n; // ввод размерности массива

randomize(); // генератор случайных чисел, инициализация

// первого элемента ряда

for(i=0;i<n;i++) // заполнение массива

{

a[i]=random(100);

cout<<” ”<<a[i]; // вывод содержимого массива на экран

}

min=a[0];

for (i=0;i<n;i++) // поиск минимального элемента

if (a[i]<min)

{ min=a[i];

k=i;

}

cout<<endl<<”min=”<<min<<” k=”<<k; // вывод результатов

getch();

}

структурированные типы данных. программирование алгоритмов обработки массивов - student2.ru структурированные типы данных. программирование алгоритмов обработки массивов - student2.ru
   

Рис.8

Пример. Вычислить сумму элементов в столбцах двумерного числового массива а размером [3][4].

Алгоритм показан на рисунке 9.

#include <stdio.h> // библиотека, содержащая описание

// операторов ввода/вывода

# include <conio.h> // библиотека, содержащая описание

// операторов для работы с экраном

# include <stdlib.h> // библиотека, содержащая описание

// генератора случайных чисел

void main() // заголовок главной функции программы

{int a[3][4], i, j, sum[4]; // описание переменных

clrscr(); // очистка экрана

randomize(); // генератор случайных чисел, инициализация

// первого элемента ряда

for(i=0;i<3;i++) // заполнение массива

{for(j=0;j<4;j++)

{

a[i][j]=random(100);

cout<<” ”<<a[i][j]; // вывод матрицы на экран

}

cout<<endl;

}

cout<<endl<<”summa”<<endl;

for(j=0;j<4;j++)

{

sum[j]=0;

for (i=0;i<3;i++) // поиск минимального элемента

{sum[j]+=a[i][j];

cout<<sum[j]; // вывод результатов

}

getch();

}

структурированные типы данных. программирование алгоритмов обработки массивов - student2.ru

Лабораторная работа 5

Наши рекомендации