Программирование на языке Си Часть II

массиве
Массивы в процедурах и функциях
© К.Ю. Поляков, 2007-2009
Практикум (моделирование)
Символьные строки
Рекурсивный

расположенных в памяти рядом.
Особенности:
все элементы имеют один тип
весь массив имеет

массива: 15

место в памяти
Пример:


Размер через константу:
имя
размер массива (количество элементов)
тип
элементов

int

const int N = 5;

N

int A [ 5 ];

присвоением начальных значений:
int A[4] = { 8, -3, 4,

остальные нулевые!

float A[N];
const int
int X[4.5];
int A[10];
A[10]

float X[5];
int n = 1;
X[n-2] = 4.5;
X[n+8] = 12.;

выход за границы массива
(стираются данные в памяти)

int X[4];
X[2] = 4.5;

дробная часть отбрасывается
(ошибки нет)

float B[2] = { 1., 3.8, 5.5 };

int A[2] = { 1, 3.8 };

float

int A[N], i;
printf("Введите 5 элементов массива:\n");
for( i=0; i < N;

A[0] =
A[1] =
A[2] =
A[3] =
A[4] =

5
12
34
56
13

for( i=0; i < N; i++ ) A[i] = A[i]*2;

printf("Результат:\n");
for( i=0; i < N; i++ ) printf("%4d", A[i]);

Результат:
10 24 68 112 26

ввод элементов массива
// обработка массива
// вывод результата
getch();
}
Задача: ввести

на предыдущих слайдах

арифметическое всех элементов массива.
Пример:
Введите пять чисел:
4

элемент массива
© К.Ю.

элемент A[0] – максимальный
for ( i=1; i < N; i++

0;
for ( i=1; i < N; i++ ) // проверяем

Дополнение: как найти номер максимального элемента?

По номеру элемента iMax всегда можно найти его значение A[iMax]. Поэтому везде меняем max на A[iMax] и убираем переменную max.

A[iMax]

(обычно

#include // случайные числа

Целые числа в интервале [a,b]:
int random(int N) {

x = random ( 100 ); // интервал [0,99]
x = random ( z ); // интервал [0,z-1]

x = random ( z ) + a; // интервал [a,z-1+a]
x = random (b – a + 1) + a; // интервал [a,b]

i;
printf("Исходный массив:\n");
for (i = 0; i < N; i++ )

int random(int N)
{ return rand() % N; }

функция выдает случайное число от 0 до N-1

// заполнить случайными числами [100,150]
// найти максимальный элемент и

на предыдущих слайдах

[-10..10] и найти в нем максимальный и минимальный элементы и

Поляков, 2007-2009

местами A[0] и A[N-1], A[1] и A[N-2], …
Псевдокод:
for ( i

сумма индексов N-1

содержимое двух ячеек памяти.
4
6
?
4
6
4
x
y
c
c = x;
x = y;
y = c;
x

3

2

1

// заполнить массив
// вывести исходный массив
for (

[-10..10] и выполнить инверсию отдельно для 1-ой и 2-ой половин

элемент становится на место последнего.
Алгоритм:
A[0]=A[1]; A[1]=A[2];… A[N-2]=A[N-1];
Цикл:
for ( i =

почему не N?

// заполнить массив
// вывести исходный массив
c = A[0];

[-10..10] и выполнить циклический сдвиг ВПРАВО.
Пример:
Исходный массив:

Поляков, 2007-2009

возрастанию, убыванию, последней цифре, сумме делителей, …).
Задача: переставить элементы

сложность O(N2)

сложность O(N·logN)

дна вверх.
Для массивов – самый маленький («легкий») элемент перемещается

начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место

1-ый проход

2-ой проход

3-ий проход

Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

A[N-2]
…
A[0] и A[1]
A[j] и A[j+1]
for( j =

0

1 ; j-- )
if ( A[j] > A[j+1] )

1

(i+1)-ый проход

for ( j = N-2; j >= i ; j-- )
...

i

c;
// заполнить массив
// вывести исходный массив

элементы выше A[i] уже поставлены

i

меняем A[j] и A[j+1]

не было обменов, массив уже отсортирован и остальные проходы не

do {
flag = 0; // сбросить флаг
for (j = N-2; j >= 0; j --)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
flag = 1; // поднять флаг
}
}
while ( flag ); // выход при flag = 0

flag = 0;

flag = 1;

( flag );

int flag;

// сбросить флаг
for ( j = N-2; j >=

i = 0;

i

i ++;

местами с A[0])
из оставшихся найти минимальный элемент и поставить на

++ ) {
nMin = i ;
for ( j

N-1

нужно N-1 проходов

поиск минимального от A[i] до A[N-1]

если нужно, переставляем

i+1

i

[0..100] и отсортировать его по последней цифре.
Пример:
Исходный

некоторому условию (например, отрицательные), и скопировать их в другой массив.

Примитивное решение:

const int N = 5;
int A[N], B[N];
// здесь заполнить массив A
for( i = 0; i < N; i ++ )
if( A[i] < 0 ) B[i] = A[i];

A

B

выбранные элементы не рядом, не в начале массива
непонятно, как с ними работать

элемент ставится на место B[count].
int A[N], B[N], count = 0;
//

A

B

count

все числа, у которых вторая с конца цифра (число десятков)

К.Ю. Поляков, 2007-2009

или установить, что его нет.
Решение: для произвольного массива: линейный

N; i ++)
if ( A[i] == X )

Улучшение: после того, как нашли X, выходим из цикла.

break;

nX = -1; // пока не нашли ...
for ( i = 0; i < N; i ++) // цикл по всем элементам
if ( A[i] == X ) // если нашли, то ...
nX = i; // ... запомнили номер
if (nX < 0) printf("Не нашли...")
else printf("A[%d]=%d", nX, X);

nX – номер нужного элемента в массиве

средний элемент A[c] и сравнить с X.
Если X = A[c],

= N-1; // границы: ищем от A[0] до A[N-1]
while

номер среднего элемента

если нашли …

выйти из цикла

сдвигаем границы

>

в нем элемент, равный X (это число вводится с клавиатуры).

функциях
© К.Ю. Поляков, 2007-2009

обратном порядке.
void Reverse ( int A[] , int N

int A[]

параметр-массив

размер массива

размер не указывается (функция работает с массивами любого размера)


размер массива

int A[10];
// здесь надо заполнить массив
Reverse

A или &A[0]

это адрес начала массива в памяти

A+5 или &A[5]

пример ее использования.

«5»: Написать процедуру, которая ставит в начало массива

int Sum ( int A[], int N )
{
int i, sum

результат – целое число

int A[]

параметр-массив

размер массива

N )
{
...
}
main()
{
int A[10], sum, sum1, sum2;
// заполнить

логическую функцию, которая определяет, верно ли, что среди элементов массива

const int N = 5;
int A[N] = { 1, 2, 3, 3, 4 };