Обработка массивов. Лекция №7

1.

Лекция №7
Обработка массивов.

2.

Классы памяти
Класс памяти определяет область действия переменной и
продолжительность ее существования в памяти. Устанавливается
при описании переменной при помощи соответствующего
ключевого слова.
Переменные, определенные вне функции,
внешними и имеют глобальную область действия.
являются
Переменные, определенные внутри функции, являются
автоматическими и локальными, если только не используются
другие ключевые слова

3.

Автоматический класс памяти
Переменные, описанные внутри функции, являются
автоматическими. Это может быть подчеркнуто явно с
помощью ключевого слова auto.
auto int sum;
Локальные
или
автоматические
переменные
определяются внутри блока кода (например, внутри функции) и
существуют только в рамках этого блока.
При входе в блок для этих переменных выделяется
память (которую еще называют автоматическая память), а после
завершения работы этого блока, выделенная память
освобождается, а объекты удаляются.

4.

Внешний класс памяти
Переменная, описанная вне функции, является внешней.
Внешняя переменная также может быть еще раз описана и внутри
функции, которая ее использует, с использованием ключевого
слова extern.
Внешние переменные еще называют глобальными.
Глобальные переменные определены в файле программы
вне любой из функций и могут использоваться любой функцией.
При этом любая функция может изменить ее значение.
Они существуют, пока работает программа, и так как эти
переменные доступны в любой функции, они не исчезнут, если
какая-нибудь одна функция закончит свою работу.

5.

Добавление ключевого слова extern позволяет функции
использовать внешнюю переменную, даже если она
определяется позже в этом или другом файле.

6.

7.

Автоматические переменные, определенные внутри блока кода,
могут скрывать внешние переменные с тем же именем

8.

Статический класс памяти
Статические переменные определяются
функций с помощью ключевого слово static.
на
уровне
Если автоматические переменные определяются и
инициализируются при каждом входе в функцию, то
статические переменные инициализируются только один раз, а
при последующих вызовах функции используется старое
значение статической переменной

9.

10.

11.

Понятие массива.
Массив - это структурированный тип данных,
представляющий собой последовательность однотипных
элементов, имеющих общее имя и снабженных индексами
(порядковыми номерами).
Массивы удобно использовать для хранения однородной по
своей природе информации, например, таблиц и списков.
Например, в виде одномерного массива строк можно
задать список студентов:
( ‘Иванов’, ‘Петров’, ‘Сидоров’, ’Песков’,
’Петренко’),
А в виде массива вещественных чисел – рост этих
студентов (в см):
(178,2 172,3 200,5 185,2 169)

12.

Элементы массива располагаются в памяти подряд друг за
другом.
Адрес массива – адрес начального элемента массива.
Индекс - это выражение целого типа (integer, byte),
определяющее положение элемента в массиве.
Размер массива - это количество элементов в массиве.
Каждый элемент занимает столько памяти, сколько отводится
под соответствующий тип данных.

13.

Массив — это непрерывный участок памяти, содержащий
последовательность объектов одинакового типа, обозначаемый
одним именем.
Элемент массива в языке C обозначается следующим образом:
имя массива [индекс].
Здесь <имя массива> - правильный идентификатор.
Например, x[3] - третий элемент массива x.
Массивы бывают одномерные (с одним индексом) и
многомерные (два и более индексов). Будем рассматривать
сначала одномерные массивы.

14.

Перед использованием массив должен быть объявлен.
Память под него выделяется на этапе компиляции программы.
Количество элементов массива задается при объявлении и
в дальнейшем не изменяется.
В одномерном массиве полный размер массива в байтах
вычисляется следующим образом:
общее число байт = sizeof (базовый тип) *число элементов

15.

Объявление и инициализация массивов
При объявлении массива указывается тип элемента, затем
имя массива и в квадратных скобках – число элементов.
[класс памяти] тип_данных имя_массива[количество_элементов];
Число элементов – это целочисленное константное
значение. Это может быть целочисленный литерал, константа или
выражение, значением которого является константа.
Т.е. на этапе компиляции число элементов массива должно быть
однозначно известно.
Имя массива – это фактически адрес начала массива
(адрес нулевого элемента).
Т.е. для массива a значение a и &a[0] – одинаковые.

16.

int temp[365];
/* внешний массив из 365 целых чисел*/
void main(void)
{
float rain[365];
/*автоматический массив из 365
вещественных чисел */
static char code[12]; /* статический массив из 12 символов */
extern int temp[];
/* внешний массив, размер указан выше */
…
}

17.

Для задания размерности массива можно также использовать
константу, описанную директивой препроцессора #define:
Использование констант при объявлении массива
является признаком хорошего стиля программирования. В этом
случае при необходимости изменить количество элементов
массива не нужно просматривать и изменять всю программу,
достаточно изменить значение константы в одном месте.
При объявлении
элементы массива.
можно
сразу
инициализировать

18.

Инициализация представляет собой набор начальных
значений элементов массива, указанных в фигурных скобках, и
разделенных запятыми.
тип_данных имя_массива[количество элементов]={значение1,
значение2, …
значение n};
int a[10] = { 10, 1, -2, 3, 14, 5, 6, -7, 8, 9 }; // массив a
//из 10 целых чисел
Если количество инициализирующих значений, указанных
в фигурных скобках, меньше, чем количество элементов массива,
указанное в квадратных скобках, то все оставшиеся элементы в
массиве (для которых не хватило инициализирующих значений)
будут равны нулю.
int b[10] = {0};//массив b из 10 элементов, инициализированных 0

19.

При создании с инициализацией количество элементов можно не
указывать.
Компилятор сам определит размер массива исходя из числа
элементов в списке инициализации
int a[] = { 5, 4, 3, 2, 1 }; // массив a содержит 5 элементов
Если инициализирующих значений больше, чем указанная
размерность массива, то возникнет ошибка на этапе компиляции:
double arr[3]={0.5,0.3,-0.4,0.5}; //ошибка
Можно инициализировать или изменять элементы массива,
обращаясь к ним по индексу.
double x[3];
x[2] = 5;
x[4] = 5;//ошибка во время выполнения

20.

Ввод одномерного массива
Ввод n
Пусть n – реальный размер массива;
i=1
x - исходный массив;
нет
i n
да
Ввод x[i]
i=i+1
i - номер текущего элемента массива.

21.

Пример. Если x - массив целых чисел, то в программе для ввода
используем следующие фрагменты:
#define MAX_SIZE 20 //максимальный размер массива

22.

Чтобы нумерация в массиве была привычна
пользователя, а не для программиста, лучше писать
printf("arr[%2d]=", i+1);
для

23.

Заполнение массива случайными числами

24.

Вывод одномерного массива.
i=1
i size
да
Вывод arr[i]
i=i+1
нет

25.

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

26.

Сумма элементов массива
sum =0
i =0
нет
i ≤ size
да
sum = sum +arr[i]
i =i+1

27.

Вычисление количества элементов массива, удовлетворяющих
заданному условию.
Реализация в программе:
K =0
i =<нач. знач.>
нет
i ≤ size
да
да
условие
K=K+1
i =i+<шаг.>
нет
for (int i = нач.зн; i < size;i++)
{
if (условие) k++;
}

28.

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

29.

Вычисление суммы элементов массива, удовлетворяющих
заданному условию.
S =0
Реализация в программе:
i =<нач. знач.>
нет
i ≤ size
да
да
условие
S=S+arr[i]
i=i+<шаг.>
нет
int sum = 0;
for (int i = нз; i < size;i+=шаг)
{
if(условие)
sum = sum + arr[i];
}

30.

Вычисление произведения элементов массива, удовлетворяющих
заданному условию
P =1
i =<нач. знач.>
нет
i ≤ size
да
да
условие
P=P*arr[i]
i=i+<шаг.>
нет

31.

Пример вычисления суммы, произведения,
количества элементов массива
В заданном массиве найти среднее арифметическое
отрицательных элементов, стоящих на местах, кратных 3;
вычислить произведение элементов, не принадлежащих
интервалу (A , B].
Например, пусть задан массив
x = (-2 3 -3 1 4 -5 -1 0 2 8
-3 -7)
Заданный интервал (-3, 3].
Тогда среднее арифметическое отрицательных элементов с
номерами, кратными 3, должно получиться равным
(-3 + -5 + -7) / 3= -5
Произведение элементов, не принадлежащих интервалу (-3 , 3]:
-3* 4*(-5)*8*(-3)*(-7) = 10080

32.

Введем следующие обозначения:
n - размерность массива;
x - исходный массив;
i - номер текущего элемента массива;
A, B - границы заданного интервала;
S -сумма отрицательных элементов, стоящих на местах, кратных 3;
k -количество отрицательных элементов, стоящих на местах,
кратных 3;
Sa -среднее арифметическое отрицательных элементов, стоящих на
местах, кратных 3;
P -произведение элементов, не принадлежащих интервалу (A , B];
k1 -произведение элементов, не принадлежащих интервалу (A , B];

33.

0
начало
1
Ввод x,n,A,B
2
S=0
3
k=0
4
i=2
5
да
6
x[i] < 0
да
7
8
i n
S=S+ x[i]
k=k+ 1
9
i=i+3
нет
нет

34.

да
10
k>0
11
нет
13
Sa=S/k
12
Вывод Sa
Вывод
сообщения

35.

14
P=1
15
k1=0
16
i=1
17
i n
да
да
18 x[i] A
x[i] >B
19
P=P* x[i]
20
k1=k1+ 1
21
i=i+1
нет
нет

36.

да
22
k1>0
23
нет
24
Вывод P
Вывод
сообщения
конец

37.

38.

39.

Для проверки работы программы понадобятся два набора
исходных данных:
1. для проверки работы в случае, когда в массиве нет элементов,
удовлетворяющих условию задачи.
Например,
x = (-2 3 3 1 2 2 -1
Заданный интервал (-3, 3].
0 2
2
-2
1)
Результатом должны быть сообщения
'Нет элементов, не принадл. интервалу'
'В массиве нет отрицательных чисел с номерами, кр. 3 '

40.

41.

Поиск максимального и
минимального элементов массива.
Введем следующие обозначения:
n - размерность массива;
x - исходный массив;
i - номер текущего элемента массива;
Max - значение максимального элемента;
Nm - номер максимального элемента;

42.

max=x[нач. знач. ном.]
nm= нач. знач. ном
i= нач. знач. +шаг
нет
i<n
да
да
x[i] > max
нет
max= x[i]
nm= i
i=i+шаг
Алгоритм поиска минимального элемента аналогичен.

43.

Пример. Найти самый правый максимальный элемент (если
их несколько) массива.
max=x[0]
nm= 0
i= 1
i<n
да
да
x[i] > =max
max= x[i]
nm= i
i=i+1
нет
нет

44.

45.

Можно обойтись и без переменной max. Можно искать только
индекс максимального элемента.

46.

Изменение цвета в консоли
Чтобы
изменить
фон,
можно
использовать
функцию system, в которую передается строка следующего вида:
"color <A><B>",
где <A> и <B> — шестнадцатеричные цифры — первая задает
цвет фона, а вторая — цвет шрифта.
Например,
system("color F0"); // Установка белого фона и черного текста
0 — черный
1 — синий
2 — зеленый
3 — голубой
4 — красный
5 — лиловый
6 — желтый
7 — белый
8 — серый
9 — свело-синий
A — светло-зеленый
B — светло-голубой
С — светло-красный
E — светло-желтый
F — ярко-белый

47.

Изменение цвета выводимого текста
Цвет задается с помощью специальных управляющих символов:
\x1B[ - начало форматирования текста (можно \033).
x;y;zm - код цвета (x = код форматирования, y = код цвета текста,
z = код цвета фона). Порядок следования x, y и z не имеет
значения, т.к. код определяется по числовому значению, а не по
его положению.
\x1B[m - конец форматирования текста (необязателен, нужен для
сброса форматирования).

48.

Цвет
Обычный
Яркий
Фон
Яркий фон
Black
30
90
40
100
Red
31
91
41
101
Green
32
92
42
102
Brown/Yello
w
33
93
43
103
Blue
34
94
44
104
Magenta
35
95
45
105
Cyan
36
96
46
106
White
(light
gray) 37
97
47
107
Default color
39
49

49.

printf("%s\n", "\033[34mHello, World!\x1B");
printf("\033[34m%s\033\n", "Hello, World!\x1B");
printf("\033[34mHello, World!\x1B[m\n");
Например, выделим максимальные элементы массива
красным цветом

50.

51.

52.

Перестановка элементов в массиве.
Чтобы поменять местами два элемента массива,
можно применить так называемый метод трех стаканов.
Суть его заключается в следующем: чтобы поменять
местами жидкости в двух стаканах, нужен третий пустой
стакан.
2
чай
сок
1
3

53.

Например, нужно поменять местами 2-й и 5-й элементы
массива.
Пример. Найти значение минимального элемента среди
элементов с четными номерами
int min = x[1];
for (int i = 3; i < n; i+=2)
{
if (x[i] < min)
min = x[i];
}
printf("Минимальный среди элементов "
"с четными номерами = %d\n", min);

54.

Формирование нового массива из элементов исходного,
удовлетворяющих заданному условию
Пусть n - размерность массива; x - исходный массив;
i - номер текущего элемента массива, j - количество элементов нового массива, y –
новый массив.
j=0
i= нач. знач.
нет
i<n
да
да
условие
y[j] = x[i]
j = j+1
i=i+шаг
нет

55.

//массив из положительных элементов исходного
int j = 0;
for (int i = 0; i < n; i++)
{
if (x[i] > 0)
{
y[j] = x[i];
j++;
}
}
puts("полученный массив y:");
for (int i = 0; i < j; i++)
{
printf("%d ", y[i]);
}
printf("\n");

56.

Пример. Заданы два одномерных массива целых чисел.
Сформировать новый массив из элементов первого массива,
превышающих значение минимального элемента второго
массива, и элементов второго массива с четными номерами.
Введем следующие обозначения:
n1 - размерность 1-го массива;
a – 1-й исходный массив;
n2 - размерность 2-го массива;
b – 2-й исходный массив;
i - номер текущего элемента массива;
Min - значение максимального элемента 2-го массива;
j - размерность нового массива;
с – полученный массив;

57.

начало
Ввод n1,a, n2, b
Min=b[0]
i=1
нет
i < n2
да
да
b[i] < Min
Min= b[i]
i=i+1
А
нет

58.

А
j=0
i=0
нет
i<n1
да
да
a[i]>Min
c[j] = a[i]
j = j+1
i = i+1
B
нет

59.

B
i=1
нет
i<n2
да
c[j] = b[i]
j = j+1
i = i+2
C

60.

C
да
j >0
нет
Вывод
сообщения
Вывод c
конец

61.

Поиск элемента, удовлетворяющего заданному условию
Пример. Определить
элемента в массиве.
индекс
первого
положительного

62.

Еще вариант.
int positiveNumber=-1;
for (int i = 0; i < n; i++)
{
if (x[i] > 0)
{
positiveNumber = i;
i = n;
}
}
if(positiveNumber>=0)
printf("Номер первого положительного элемента: %d\n",
positiveNumber);
else
printf("В массиве нет положительных чисел\n");

63.

// найти первый положительный элемент
int i;
for ( i = 0; i < n && x[i] <= 0; i++);
if(i<n)
printf("Номер первого положительного элемента:
else
printf("В массиве нет положительных чисел\n");
%d\n", i);
Пример. Найти последний отрицательный элемент
//найти последний отрицательный
int i;
for (i = n-1; i >=0 && x[i] >= 0 ; i--);
if (i >=0)
printf("Последний отрицательный элемент: %d\n", x[i]);
else
printf("В массиве нет отрицательных чисел\n");

64.

Понятие указателя
Указатели представляют собой переменные, значением
которых служат адреса других объектов (переменных, констант,
указателей) или функций. Используются для управления
памятью в языке Си
Память машины представляет собой массив последовательно
пронумерованных ячеек, с которыми можно работать по
отдельности или связанными кусками.

65.

Значение переменной-указателя - адрес другой переменной.
Указатель связан с определенным типом данных. Для
определения указателя надо указать тип объекта, на
который указывает указатель, и символ звездочки *.
тип* переменная-указатель;
Например (обратите внимание, где может располагаться *)
int* p1;
int * p2;
int *p3;

66.

Для работы
операции:
с
указателями
используются
следующие
& - операция взятия адреса переменной;
* - операция взятия
разыменования).
значения
по
адресу
(операция
Запись вида
ptr_x = &x;
присваивает адрес ячейки, в которой находится переменная x,
переменной ptr_x, которая является переменной указателем. В
этом случае принято говорить:
ptr_x указывает (или ссылается) на x

67.

Адрес
представляет
целочисленное
выраженное в шестнадцатеричном формате.
значение,
int x = 25;
int* p = &x;// указатель получает адрес переменной
printf("%ld %p\n\n", p, p);
Для ввода и вывода значения указателя можно использовать
специальный спецификатор %p
Операция & (взятия адреса) не может применяться к
выражениям и регистровым переменным (с модификатором
register).

68.

Операция разыменования читается как «взять
содержимое по адресу такому-то».
Т.е. *p – это содержимое по адресу, на который
указывает p.
Результатом этой операции является объект, на который
указывает указатель.
Чтобы получить значение переменной по её адресу, следует
написать звёздочку перед именем указателя.
int x = 10;
int* p;
p = &x;
printf("Адрес = %p \n", p);
printf("x = %d \n", *p);

69.

int* p;
double* q;
int x = 3;
p = &x;
double y = 3.5;
q = &y;
При описании переменных-указателей рекомендуется
включать в имена переменных префикс или суффикс ptr
(pointer – указатель). Например: ptrSum, xPtr, ptr_z.
В каких случаях использовать указатели?
Передача в функцию адреса переменной, которая должна
быть изменена;
Работа с массивом (эффективность);
Динамическое выделение и освобождение памяти.

70.

Используя указатель, можно менять значение по адресу,
который хранится в указателе:
int x = 10;
double q = 5;
int* xPtr,* qPtr;
xPtr = &x;
qPtr = &q;
*xPtr = 4; //в ячейку с адресом xPtr записать 4
(*qPtr)++; // ячейку с адресом qPtr увеличить на 1
*qPtr = *xPtr / 2.; //содержимое по адресу xPtr //
// разделить на 2
//и результат записать по адресу qPtr

71.

Операции над указателями
Присваивание
Указателю можно присвоить адрес объекта того же типа,
значение другого указателя или константу NULL (или 0).
NULL – это «пустой указатель», который никуда не
указывает.
Константа NULL определена в заголовочном файле stdio.h
xPtr = NULL;
Указателю можно присвоить значение другого указателя
того же типа. В этом случае они указывают на одну и ту же
переменную.
int* xPtr,* qPtr;
xPtr = &x;
qPtr = xPtr; //оба указателя содержат адрес x

72.

Разыменование указателя (получение значения по адресу )
*имя_указателя позволяет получить объект по адресу,
который хранится в указателе.
Получение адреса указателя –
подобно любым переменным указатель имеет адрес и значение
int a = 10;
int* pa = &a;
printf("Адрес указателя =%p \n", &pa);//адрес указателя
Увеличение (уменьшение) указателя
Указатель можно увеличивать или уменьшать на целое число.
При этом компилятор изменяет адрес в соответствии с
типом, с которым связан данный указатель (т.е. для типа int
приращение на 1 означает на самом деле увеличение адреса на 4
байта, а для типа double – на 8 байт). Т.е., после увеличения на 1
указатель указывает на следующее число соответствующего типа:

73.

int a = 10;
int* aPtr = &a;
printf("a=%d Адрес а = %p \n",a,aPtr);
printf("Число после a = %d Его адрес = %p\n", *(aPtr+1),
aPtr+1);
printf("Число до a = %d Его адрес = %p\n", *(aPtr-1),
aPtr-1);
При этом следует помнить, что унарные операции с
одинаковым приоритетом выполняются справа налево!
++*p и *++p не одно и то же
Функция sizeof(тип_элемента) возвращает количество
байт, которые занимает данный тип данных в оперативной
памяти.
Если мы увеличиваем указатель любого типа на x, то на
самом деле адрес возрастает на x*sizeof(адресуемый_тип)
байт.

74.

Разность между указателями
Можно найти разность двух указателей, если они
указывают на один и тот же тип данных. Результатом будет
количество чисел данного типа, которые можно разместить
между этими указателями.
int b = 3, c = 8;
int* bPtr = &b;
int* cPtr = &c;
printf("Адрес b= %p \n",bPtr);
printf("Адрес c= %p \n", cPtr);
printf("Разность указателей= %d \n", bPtr - cPtr);

75.

Операции сравнения
К
указателям
могут
применяться
операции
сравнения >, >=, <, <=,==, !=.
Операции сравнения применяются только к указателям
одного типа и константе NULL. Для сравнения используются
номера адресов
if (bPtr > cPtr)
printf("bPtr (%p) больше, чем (%p) \n", bPtr, cPtr);
else
printf("bPtr (%p) меньше, чем (%p) \n", bPtr, cPtr);
Указатель типа void применяется в тех случаях, когда
конкретный тип объекта, адрес которого требуется хранить,
не определен (например, данный указатель в разные моменты
времени работы программы будет ссылаться на переменные
разного типа).

76.

Указателю типа void можно присвоить адрес любой
переменной, или значение указателя любого типа.
Чтобы обратиться к участку памяти по указателю типа
void, нужно предварительно явно преобразовать его к
конкретному типу.
int i = 3;
double x = 3.5;
ptr = &i;
printf("Значение целой переменной: %d\n", *(int*)ptr );
ptr = &x;
printf("Значение вещественной переменной:%d\n", *(double*)ptr);

77.

Указатель на константу и константа-указатель
При объявлении указателя можно использовать
модификатор const (константа)/
Если этот модификатор стоит первым, то он относится не к
самому указателю, а к значению, на которое он указывает:
const int* qPtr; //указатель на целую константу
qPtr++; //допустимая операция, т.к. сам указатель
// переменная
Если модификатор const стоит между * и именем указателя, то
он относится к самому указателю, который при этом
обязательно должен быть инициализирован:
int a = 83;
int* const gPtr = &a; //указатель-константа
a++; //допустимая операция, т.к. a - переменная
//gPtr++; //недопустимая операция, т.к. gPtr- константа

78.

Указатели и массивы
Между указателями и массивами существует тесная
связь. Любую операцию, которую можно выполнить с помощью
индексов массива, можно сделать и с помощью указателей. При
этом вариант с указателями выполняется быстрее.
Имя массива в Си является адресом его первого элемента.
Т.е., имя массива – это и есть указатель-константа на начало
массива (на нулевой элемент). Соответственно через операцию
разыменования можно получить значение по этому адресу
int a[N];
int* ptr;
ptr = a; // эквивалентно ptr=&a[0];

79.

После этого к i-му элементу массива можно обращаться
любым из следующих способов:
a[i]
*(a+i)
*(ptr+i)
ptr[i]
ptr – переменная-указатель, а имя массива – это константауказатель. Поэтому изменять ptr можно, а – нельзя!
ptr++; //можно
//a++; // нельзя!
Например, вывод массива с использованием указателей:
int a[N] = {2,4,5,8,-4,2,7,1,5,-1};
int* ptr;
ptr = a;
for (int i = 0; i < N; i++)
{
printf("%d ", *(ptr + i));
}

80.

Этот вариант не даст выигрыша в быстродействии по сравнению с
обращением a[i].
И в том, и в другом случае перед обращением к элементу
массива вычисляется его адрес путем сложения адреса начала
массива и масштабированного количества элементов:
ptr+sizeof(int)*i (или a+ sizeof(int)*i).
Если сделать указатель подвижным, каждый раз
увеличивая его на 1, то код будет работать быстрее, т.к. перед
обращением к очередному элементу выполняется только
сложение: ptr+sizeof(int):
for (int i = 0; i < N; i++)
{
printf("%d ", *ptr);
ptr++;
}
printf("\n");

81.

Пример. В массиве из 10 целых чисел найти первый
отрицательный и последний положительный элементы и поменять
их местами.

82.

83.

84.

Динамическая память
Для управления динамическим выделением памяти
используются следующие функции, которые определены в
заголовочном файле stdlib.h:
Функции динамического распределения памяти:
void* malloc(РазмерВБайтах);
void* calloc(ЧислоЭлементов, РазмерЭлементаВБайтах);
Функции динамического выделения памяти находят в
оперативной памяти непрерывный участок требуемой длины и
возвращают начальный адрес этого участка.
Т.к. обе представленные функции в качестве
возвращаемого значения имеют указатель на пустой тип void,
требуется явное приведение типа возвращаемого значения

85.

Функция освобождения памяти
free(указатель);
«Правилом хорошего тона» в программировании
является освобождение динамически выделенной памяти в
случае отсутствия ее дальнейшего использования. Однако если
динамически выделенная память не освобождается явным
образом, она будет освобождена по завершении выполнения
программы.
Функция перераспределения памяти
void* realloc (void* ptr, size_t size);
ptr - указатель на блок ранее выделенной памяти
функциями malloc(), calloc() или realloc() для перемещения в
новое место. Если этот параметр равен NULL, то выделяется
новый блок, и функция возвращает на него указатель.

86.

size - новый размер, в байтах, выделяемого блока памяти.
Если size = 0, ранее выделенная память освобождается и
функция возвращает нулевой указатель, ptr устанавливается
в NULL.
Динамические массивы
Очень часто возникают задачи обработки массивов данных,
размерность которых заранее неизвестна. В этом случае
возможно использование одного из двух подходов:
выделение памяти под статический массив, содержащий
максимально возможное число элементов, однако в этом
случае память расходуется нерационально;
динамическое выделение памяти для хранение массива
данных.

87.

malloc() не инициализирует выделенную память.
calloc() выделяет память, а также инициализирует выделение
памяти для всех битов 0.
Используйте malloc (), если вы собираетесь установить
все, что вы используете в выделенном пространстве.
Используйте calloc (), если вы собираетесь оставить
части данных неинициализированными, и было бы полезно
обнулить ненастроенные части.
Пример. Организация динамического одномерного массива,
ввод и вывод его элементов.

88.

89.

// Вывод элементов массива
for (i = 0; i < n; i++)
printf("%d ", a[i]);
free(a);
Методы сортировки массива
Пузырьковая сортировка (или сортировка простыми
обменами.).
Алгоритм пузырьковой сортировки является одним из
самых простых в реализации и самых медленных по времени
выполнения.
Его суть сводится к поочередному сравнению соседних
элементов массива.

90.

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

91.

Алгоритм пузырьковой сортировки всегда выполняет
(n2-n)/2
сравнений, где n — количество сортируемых
элементов. Данная формула выведена на том основании, что
внешний цикл выполняется n-1 раз, а внутренний выполняется
в среднем n/2 раз.

92.

93.

Это метод сортировки по возрастанию (неубыванию)
обменом с фиксированным числом просмотров, направленных
слева направо

94.

95.

При сортировке методом пузырька часто встречается
ситуация, когда массив уже отсортирован, а просмотры
продолжаются. Чтобы прекратить процесс сортировки, можно,
например, завести переменную-флаг, которая будет фиксировать
факт перестановки элементов.
Переменной-флагу присваивается значение 0 (false)
перед началом прохода по массиву.
При обмене флаг меняет свое значение на любое другое.
Если по окончании прохода эта переменная осталась 0,
то перестановок не было (массив уже упорядочен). В этом
случае новой итерации цикла проходов уже не нужно.

96.

97.

Еще один сократить число просмотров пузырьковой
сортировки - запомнить индекс последнего обмена при
очередном просмотре. Тогда следующий просмотр может быть
только до этой позиции, так как правее все элементы уже
расположены по порядку.

98.

Шейкерная сортировка (сортировка перемешиванием)
двунаправленная пузырьковая сортировка, пульсирующая
сортировка (ripple sort), трансфертная сортировка (shuttle
sort), сортировка «счастливый час» (happy hour sort)
Массив просматривается поочередно справа налево и
слева направо.
Просмотр массива осуществляется до тех пор, пока все
элементы не встанут в порядке возрастания (убывания).
Шейкерная сортировка работает немного быстрее чем
пузырьковая, поскольку по массиву в нужных направлениях
попеременно мигрируют и максимумы и минимумы.

99.

100.

101.

Сортировка расчёской
Основная идея «расчёски» в том, чтобы первоначально
брать достаточно большое расстояние между сравниваемыми
элементами и по мере упорядочивания массива сужать это
расстояние вплоть до минимального.
Первоначальный
разрыв
между
сравниваемыми
элементами лучше брать с учётом специальной величины
называемой фактором уменьшения, равным примерно 1,247.
Сначала расстояние между элементами равно размеру массива
разделённого на фактор уменьшения . Затем, пройдя массив с
этим шагом, мы снова делим шаг на фактор уменьшения и
проходим по списку вновь. Так продолжается до тех пор, пока
разность индексов не достигнет единицы. В этом случае
массив досортировывается обычным пузырьком.

102.

103.

104.

105.

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

106.

i=0
i<n-1
нет
да
nMin=i
j=i+1
да
j<n
да
a[j]<a[nMin]
nMin=j
j=j+1
temp=a[i]
a[i]=a[nMin]
a[nMin]=temp
i=i+1
нет
нет

107.

108.

Сортировка вставками (Insertion sort, метод включения)
Описание алгоритма
выбираем один из элементов исходного массива
вставляем его на нужную позицию в уже отсортированном
списке,
продолжаем до тех пор, пока набор входных данных не будет
исчерпан.
Метод выбора очередного элемента из исходного
массива произволен; может использоваться практически любой
алгоритм выбора. Обычно элементы вставляются по порядку их
появления во входном массиве. Приведенный ниже алгоритм
использует именно эту стратегию выбора.

109.

i=1
i<n
нет
да
value = a[i]
j=i-1
j≥0 и a[j] > value
да
a[j + 1] = a[j]
j=j-1
a[j + 1] = value
i=i+1
05.12.2022
нет

110.

Сначала считаем, что a[0] – упорядоченный массив из одного
элемента. Включим элемент a[1] так, чтобы массив из двух
элементов также получился упорядоченным. И т.д.

111.

Сортировка слиянием
Сортировки
слиянием
работают
по
такому
принципу:
Ищутся (или формируются) упорядоченные подмассивы
Упорядоченные
подмассивы
соединяются
в
общий
упорядоченный массив.

112.

Пусть даны два упорядоченных массива: a[n] упорядочен
по возрастанию, а b[m] упорядочен по убыванию. Требуется
составить из них упорядоченный по возрастанию массив.
На следующем слайде

113.

114.

115.

Бинарный поиск
Суть алгоритма состоит в том, чтобы найти
позицию (индекс) заданного элемента в отсортированном
массиве за самое короткое время, не анализируя все элементы
в этой коллекции.
Перед применением алгоритма двоичного поиска массив
обязательно должен быть отсортирован.
На первом шаге делим исходный отсортированный массив
пополам и сравниваем ключ поиска со средним значением (по
которому делили массив). Если равны, то ключ поиска
найден, если ключ поиска меньше этого среднего значения, то
продолжим поиск в первой половине массива, в обратном
случае, во второй части.
На следующем шаге выбранную часть массива также делим
пополам и, как и в предыдущем случае, выполняем
сравнение. В случае, если ключ поиска не совпал с
центральным элементом, выбираем нужную часть.
115
05.12.2022
Романькова Т.Л.

116.

Т.е. после каждого сравнения отсекается ровно половина,
сокращая тем самым область поиска.
Так продолжается до тех пор, пока значение
центрального элемента не совпадет с ключом поиска, либо не
исчерпаются все элементы в получаемых частях.