Программирование на языке Си Часть II 1.МассивыМассивы 2.Максимальный элемент массиваМаксимальный элемент массива 3.Обработка массивовОбработка массивов. - презентация

1 Программирование на языке Си Часть II 1.МассивыМассивы 2.Максимальный элемент массиваМаксимальный элемент массива 3.Обработка массивовОбработка массивов 4.Сортировка массивовСортировка массивов 5.Поиск в массивеПоиск в массиве 6.Массивы в процедурах и функцияхМассивы в процедурах и функциях © К.Ю. Поляков, Практикум (моделирование)Практикум (моделирование) 8.Символьные строкиСимвольные строки 9.Рекурсивный переборРекурсивный перебор 10.МатрицыМатрицы 11.ФайлыФайлы

2 Программирование на языке Си Часть II Тема 1. Массивы © К.Ю. Поляков,

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

4 4 Массивы A A массив НОМЕР элемента массива (ИНДЕКС) НОМЕР элемента массива (ИНДЕКС) A[0] A[1] A[2] A[3] A[4] ЗНАЧЕНИЕ элемента массива A[2] НОМЕР (ИНДЕКС) элемента массива: 2 ЗНАЧЕНИЕ элемента массива: 15 НУЛЯ Нумерация элементов массива в Си начинается с НУЛЯ! !

5 5 Объявление массивов Зачем объявлять? определить имя массива определить тип массива определить число элементов выделить место в памяти Пример: Размер через константу: имя размер массива (количество элементов) тип элементов тип элементов int A [ ]; const int N = 5; N int A [ 5 ];

6 6 Объявление массивов Еще примеры: int X[10], Y[10]; float zz, A[20]; char s[80]; int X[10], Y[10]; float zz, A[20]; char s[80]; С присвоением начальных значений: int A[4] = { 8, -3, 4, 6 }; float B[2] = { 1. }; char C[3] = { 'A', '1', 'Ю' }; int A[4] = { 8, -3, 4, 6 }; float B[2] = { 1. }; char C[3] = { 'A', '1', 'Ю' }; остальные нулевые! Если начальные значения не заданы, в ячейках находится «мусор»! !

7 7 Что неправильно? int N = 10; float A[N]; int N = 10; float A[N]; const int int X[4.5]; int A[10]; A[10] = 0; int A[10]; A[10] = 0; float X[5]; int n = 1; X[n-2] = 4.5; X[n+8] = 12.; float X[5]; int n = 1; X[n-2] = 4.5; X[n+8] = 12.; выход за границы массива (стираются данные в памяти) выход за границы массива (стираются данные в памяти) int X[4]; X[2] = 4.5; int X[4]; X[2] = 4.5; дробная часть отбрасывается (ошибки нет) дробная часть отбрасывается (ошибки нет) float B[2] = { 1., 3.8, 5.5 }; int A[2] = { 1, 3.8 }; float

8 8 Массивы Объявление: Ввод с клавиатуры: Поэлементные операции: Вывод на экран: const int N = 5; int A[N], i; const int N = 5; int A[N], i; printf("Введите 5 элементов массива:\n"); for( i=0; i < N; i++ ) { printf ("A[%d] = ", i ); scanf ("%d", & A[i] ); } printf("Введите 5 элементов массива:\n"); for( i=0; i < N; i++ ) { printf ("A[%d] = ", i ); scanf ("%d", & A[i] ); } A[0] = A[1] = A[2] = A[3] = A[4] = for( i=0; i < N; i++ ) A[i] = A[i]*2; printf("Результат:\n"); for( i=0; i < N; i++ ) printf("%4d", A[i]); printf("Результат:\n"); for( i=0; i < N; i++ ) printf("%4d", A[i]); Результат:

9 9 Программа #include main() { const int N = 5; int A[N], i; // ввод элементов массива // обработка массива // вывод результата getch(); } #include main() { const int N = 5; int A[N], i; // ввод элементов массива // обработка массива // вывод результата getch(); } Задача: ввести с клавиатуры массив из 5 элементов, умножить все элементы на 2 и вывести полученный массив на экран. на предыдущих слайдах

10 10 Задания «4»: Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое всех элементов массива. Пример: Введите пять чисел: среднее арифметическое «5»: Ввести c клавиатуры массив из 5 элементов, найти минимальный из них. Пример: Введите пять чисел: минимальный элемент 3 При изменении константы N остальная программа не должна изменяться! !

11 Программирование на языке Си Часть II Тема 2. Максимальный элемент массива © К.Ю. Поляков,

12 12 Максимальный элемент Задача: найти в массиве максимальный элемент. Алгоритм: Псевдокод: // считаем, что элемент A[0] – максимальный for ( i=1; i < N; i++ ) if ( A[i] > максимального ) // запомнить новый максимальный элемент A[i] // считаем, что элемент A[0] – максимальный for ( i=1; i < N; i++ ) if ( A[i] > максимального ) // запомнить новый максимальный элемент A[i] Почему цикл от i=1 ? ?

13 13 Максимальный элемент max = A[0]; // пока A[0]– максимальный iMax = 0; for ( i=1; i < N; i++ ) // проверяем остальные if ( A[i] > max ) { // нашли новый max = A[i]; // запомнить A[i] iMax = i; // запомнить i } max = A[0]; // пока A[0]– максимальный iMax = 0; for ( i=1; i < N; i++ ) // проверяем остальные if ( A[i] > max ) { // нашли новый max = A[i]; // запомнить A[i] iMax = i; // запомнить i } Дополнение: как найти номер максимального элемента? Как упростить? ? По номеру элемента iMax всегда можно найти его значение A[iMax]. Поэтому везде меняем max на A[iMax] и убираем переменную max. A[iMax]

14 14 Заполнение случайными числами RAND_MAX – максимальное случайное целое число (обычно RAND_MAX = 32767) Случайное целое число в интервале [0,RAND_MAX] x = rand(); // первое число x = rand(); // уже другое число Установить начальное значение последовательности: srand ( 345 ); // начнем с 345 #include // случайные числа

15 15 Целые числа в заданном интервале Целые числа в интервале [0,N-1] : Примеры: Целые числа в интервале [a,b] : int random(int N) { return rand()% N; } int random(int N) { return rand()% N; } x = random ( 100 ); // интервал [0,99] x = random ( z ); // интервал [0,z-1] 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] x = random ( z ) + a; // интервал [a,z-1+a] x = random (b – a + 1) + a; // интервал [a,b]

16 16 Заполнение случайными числами #include main() { const int N = 10; int A[N], i; printf("Исходный массив:\n"); for (i = 0; i < N; i++ ) { A[i] = random(100) + 50; printf("%4d", A[i]); }... } #include main() { const int N = 10; int A[N], i; printf("Исходный массив:\n"); for (i = 0; i < N; i++ ) { A[i] = random(100) + 50; printf("%4d", A[i]); }... } int random(int N) { return rand() % N; } int random(int N) { return rand() % N; } функция выдает случайное число от 0 до N-1 Какой интервал? ?

17 17 Программа #include main() { const int N = 5; int A[N], i, iMax; // заполнить случайными числами [100,150] // найти максимальный элемент и его номер printf("\nМаксимальный элемент A[%d] = %d", iMax, A[iMax]); getch(); } на предыдущих слайдах const Что дает const ? ?

18 18 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и найти в нем максимальный и минимальный элементы и их номера. Пример: Исходный массив: максимальный a[4]=10 минимальный a[8]=-10 «5»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и найти в нем два максимальных элемента и их номера. Пример: Исходный массив: максимальные a[4]=10, a[7]=8

19 Программирование на языке Си Часть II Тема 3. Обработка массивов © К.Ю. Поляков,

20 20 Реверс массива Задача: переставить элементы массива в обратном порядке (выполнить инверсию). Алгоритм: поменять местами A[0] и A[N-1], A[1] и A[N-2], … Псевдокод: 35…97 79…53 01…N-2N-1 01…N-2N-1 for ( i = 0; i < N; i++ ) // поменять местами A[i] и A[N-1-i] for ( i = 0; i < N; i++ ) // поменять местами A[i] и A[N-1-i] сумма индексов N-1 Что неверно? ? ; i++ ) N / 2N / 2

21 21 Как переставить элементы? Задача: поменять местами содержимое двух чашек. Задача: поменять местами содержимое двух ячеек памяти ? ? x y c c = x; x = y; y = c; c = x; x = y; y = c; x = y; y = x; x = y; y = x; Можно ли обойтись без c ? ?

22 22 Программа main() { const int N = 10; int A[N], i, c; // заполнить массив // вывести исходный массив for ( i = 0; i < N/2; i++ ) { c = A[i]; A[i] = A[N-1-i]; A[N-1-i] = c; } // вывести полученный массив }

23 23 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и выполнить инверсию отдельно для 1-ой и 2-ой половин массива. Пример: Исходный массив: Результат: «5»: Заполнить массив из 12 элементов случайными числами в интервале [ ] и выполнить инверсию для каждой трети массива. Пример: Исходный массив: Результат:

24 24 Циклический сдвиг Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент становится на место последнего. Алгоритм: A[0]=A[1]; A[1]=A[2];… A[N-2]=A[N-1]; Цикл: 3581… …N-2N-1 581…973 for ( i = 0; i < N-1; i ++) A[i] = A[i+1]; Что неверно? ? почему не N ?

25 25 Программа main() { const int N = 10; int A[N], i, c; // заполнить массив // вывести исходный массив c = A[0]; for ( i = 0; i < N-1; i ++) A[i] = A[i+1]; A[N-1] = c; // вывести полученный массив }

26 26 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и выполнить циклический сдвиг ВПРАВО. Пример: Исходный массив: Результат: «5»: Заполнить массив из 12 элементов случайными числами в интервале [ ] и выполнить циклический сдвиг ВПРАВО на 4 элемента. Пример: Исходный массив: Результат:

27 Программирование на языке Си Часть II Тема 4. Сортировка массивов © К.Ю. Поляков,

28 28 Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Задача: переставить элементы массива в порядке возрастания. Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора сложные, но эффективные «быстрая сортировка» (Quick Sort) сортировка «кучей» (Heap Sort) сортировка слиянием пирамидальная сортировка сложность O(N 2 ) сложность O(N·logN) время N O(N 2 ) O(N·logN)

29 29 Метод пузырька Идея – пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий») элемент перемещается вверх («всплывает») начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место ый проход 2-ой проход 3-ий проход Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

30 30 Программа (1-ый проход) 5 2 … … N-2 N-1 сравниваются пары A[N-2] и A[N-1], A[N-3] и A[N-2] … A[0] и A[1] A[j] и A[j+1] for( j = N-2; j >= 0 ; j-- ) if ( A[j] > A[j+1] ) { c = A[j]; A[j] = A[j+1]; A[j+1] = c; } for( j = N-2; j >= 0 ; j-- ) if ( A[j] > A[j+1] ) { c = A[j]; A[j] = A[j+1]; A[j+1] = c; } 0

31 31 Программа (следующие проходы) 2-ой проход A[0] уже на своем месте! ! for ( j = N-2; j >= 1 ; j-- ) if ( A[j] > A[j+1] ) { c = A[j]; A[j] = A[j+1]; A[j+1] = c; } for ( j = N-2; j >= 1 ; j-- ) if ( A[j] > A[j+1] ) { c = A[j]; A[j] = A[j+1]; A[j+1] = c; } 1 (i+1) -ый проход for ( j = N-2; j >= i ; j-- )... for ( j = N-2; j >= i ; j-- )... i 1 5 … … N-2 N-1

32 32 Программа main() { const int N = 10; int A[N], i, j, c; // заполнить массив // вывести исходный массив for (i = 0; i < N-1; i ++){ for (j = N-2; j >= i ; j --) if ( A[j] > A[j+1] ) { с = A[j]; A[j] = A[j+1]; A[j+1] = с; } } // вывести полученный массив } Почему цикл для i < N-1, а не i < N ? ? элементы выше A[i] уже поставлены i меняем A[j] и A[j+1]

33 33 Метод пузырька с флажком Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны. Реализация: переменная-флаг, показывающая, был ли обмен; если она равна 0, то выход. 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 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; Как улучшить? ?

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

35 35 Метод выбора Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[0] ) из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[1] ), и т.д

36 36 Метод выбора N for( i = 0; i < N-1 ; i ++ ) { nMin = i ; for ( j = i+1; j < N; j ++) if( A[j] < A[nMin] ) nMin = j; if( nMin != i ) { c = A[i]; A[i] = A[nMin]; A[nMin] = c; } } N-1 нужно N-1 проходов поиск минимального от A[i] до A[N-1] если нужно, переставляем Можно ли убрать if ? ? i+1 i

37 37 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать его по последней цифре. Пример: Исходный массив: Результат: «5»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию. Пример: Исходный массив: Результат:

38 38 Формирование массива по условию Задача – найти в массиве элементы, удовлетворяющие некоторому условию (например, отрицательные), и скопировать их в другой массив. Примитивное решение: const int N = 5; int A[N], B[N]; // здесь заполнить массив A for( i = 0; i < N; i ++ ) if( A[i] < 0 ) B[i] = A[i]; 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 -5-5 выбранные элементы не рядом, не в начале массива непонятно, как с ними работать

39 39 Формирование массива по условию Решение: ввести счетчик найденных элементов count, очередной элемент ставится на место B[count]. int A[N], B[N], count = 0; // здесь заполнить массив A for( i = 0; i < N; i ++ ) if( A[i] < 0 ) { B[count] = A[i]; count ++; } // вывод массива B for( i = 0; i < count; i ++ ) printf("%d\n", B[i]); int A[N], B[N], count = 0; // здесь заполнить массив A for( i = 0; i < N; i ++ ) if( A[i] < 0 ) { B[count] = A[i]; count ++; } // вывод массива B for( i = 0; i < count; i ++ ) printf("%d\n", B[i]); ? ? ? ? ? A B -5-5 count

40 40 Задания «4»: Заполнить массив случайными числами и отобрать в другой массив все числа, у которых вторая с конца цифра (число десятков) – ноль. Пример: Исходный массив: Результат: «5»: Заполнить массив случайными числами и выделить в другой массив все числа, которые встречаются более одного раза. Пример: Исходный массив: Результат: 1 2

41 Программирование на языке Си Часть II Тема 5. Поиск в массиве © К.Ю. Поляков,

42 42 Поиск в массиве Задача – найти в массиве элемент, равный X, или установить, что его нет. Решение: для произвольного массива: линейный поиск (перебор) недостаток: низкая скорость Как ускорить? – заранее подготовить массив для поиска как именно подготовить? как использовать «подготовленный» массив?

43 43 Линейный поиск nX = -1; for ( i = 0; i < N; i ++) if ( A[i] == X ) { nX = i; break; //выход из цикла } nX = -1; for ( i = 0; i < N; i ++) if ( A[i] == X ) { nX = i; break; //выход из цикла } Что можно улучшить? ? Улучшение: после того, как нашли 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 – номер нужного элемента в массиве

44 44 Двоичный поиск X = 7X = 7 X < 8X < X > 4X > X > 6 1.Выбрать средний элемент A[c] и сравнить с X. 2.Если X = A[c], нашли (выход). 3.Если X < A[c], искать дальше в первой половине. 4.Если X > A[c], искать дальше во второй половине.

45 45 Двоичный поиск Почему нельзя while ( R > L ) { … } ? ? 0LcR N-1 nX = -1; L = 0; R = N-1; // границы: ищем от A[0] до A[N-1] while ( R >= L ){ c = (R + L) / 2; if (X = = A[c]) { nX = c; break; } if (X < A[c]) R = c - 1; if (X > A[c]) L = c + 1; } if (nX < 0) printf("Не нашли..."); else printf("A[%d]=%d", nX, X); номер среднего элемента если нашли … выйти из цикла сдвигаем границы > ">

46 46 Сравнение методов поиска ЛинейныйДвоичный подготовканетотсортировать число шагов N = 222 N = N = N= N N log 2 N+1

47 47 Задания «4»: Написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в нем элемент, равный X (это число вводится с клавиатуры). Использовать двоичный поиск. «5»: Написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. Для поиска использовать 1000 случайных чисел в этом же интервале.

48 Программирование на языке Си Часть II Тема 6. Массивы в процедурах и функциях © К.Ю. Поляков,

49 49 Массивы в процедурах Задача: составить процедуру, которая переставляет элементы массива в обратном порядке. void Reverse ( int A[], int N ) { int i, c; for ( i = 0; i < N/2; i ++ ) { c = A[i]; A[i] = A[N-1-i]; A[N-1-i] = c; } void Reverse ( int A[], int N ) { int i, c; for ( i = 0; i < N/2; i ++ ) { c = A[i]; A[i] = A[N-1-i]; A[N-1-i] = c; } } int A[] параметр- массив размер массива

50 50 Массивы как параметры процедур Особенности: при описании параметра-массива в заголовке функции его размер не указывается (функция работает с массивами любого размера) размер массива надо передавать как отдельный параметр в процедура передается адрес исходного массива: все изменения, сделанные в процедуре влияют на массив в основной программе Почему здесь размер не обязателен? ?

51 51 Массивы в процедурах void Reverse ( int A[], int N ) {... } main() { int A[10]; // здесь надо заполнить массив Reverse ( A, 10 ); // весь массив // Reverse ( A, 5 ); // первая половина // Reverse ( A+5, 5 ); // вторая половина } void Reverse ( int A[], int N ) {... } main() { int A[10]; // здесь надо заполнить массив Reverse ( A, 10 ); // весь массив // Reverse ( A, 5 ); // первая половина // Reverse ( A+5, 5 ); // вторая половина } A или &A[0] это адрес начала массива в памяти A+5 или &A[5]

52 52 Задания «4»: Написать процедуру, которая сортирует массив по возрастанию, и показать пример ее использования. «5»: Написать процедуру, которая ставит в начало массива все четные элементы, а конец – все нечетные.

53 53 Массивы в функциях Задача: составить функцию, которая находит сумму элементов массива. int Sum ( int A[], int N ) { int i, sum = 0; for ( i = 0; i < N; i ++ ) sum += A[i]; return sum; } int Sum ( int A[], int N ) { int i, sum = 0; for ( i = 0; i < N; i ++ ) sum += A[i]; return sum; } результат – целое число int A[] параметр- массив размер массива

54 54 Массивы в процедурах и функциях int Sum ( int A[], int N ) {... } main() { int A[10], sum, sum1, sum2; // заполнить массив sum = Sum ( A, 10 ); // весь массив sum1 = Sum ( A, 5 ); // первая половина sum2 = Sum ( A+5, 5 ); // вторая половина... } int Sum ( int A[], int N ) {... } main() { int A[10], sum, sum1, sum2; // заполнить массив sum = Sum ( A, 10 ); // весь массив sum1 = Sum ( A, 5 ); // первая половина sum2 = Sum ( A+5, 5 ); // вторая половина... }

55 55 Задания «4»: Написать функцию, которая находит максимальный элемент в массиве. «5»: Написать логическую функцию, которая определяет, верно ли, что среди элементов массива есть два одинаковых. Если ответ «да», функция возвращает 1; если ответ «нет», то 0. Подсказка: для отладки удобно использовать массив из 5 элементов, задаваемых вручную: const int N = 5; int A[N] = { 1, 2, 3, 3, 4 }; const int N = 5; int A[N] = { 1, 2, 3, 3, 4 };

56 Программирование на языке Си Часть II Тема 7. Практикум (моделирование) © К.Ю. Поляков,

57 57 Моделирование кипения воды Задача: Построить компьютерную модель кипения воды. Хранение данных: координаты (центров) пузырьков хранятся в массивах X и Y : X[i], Y[i] – координаты центра пузырька с номером i.

58 58 Структура программы #include const int N = 100; int X[N], Y[N], r = 3; void Init (); // начальное положение void Draw ( int color ); // рисуем, стираем void Sdvig ( int dy ); // летят вверх void Zamena (); // ушли, пришли main() { initwindow (600, 400);... // основная часть программы closegraph(); }... // здесь сами процедуры глобальные константы и переменные объявления процедур

59 59 Основная программа Init(); // начальная расстановка while ( 1 ) // зацикливание ??? { Draw ( YELLOW ); // рисуем все пузырьки delay ( 10 ); // ждем 10 мс Draw ( BLACK ); // стираем все пузырьки Sdvig ( 4 ); // вверх на 4 пикселя Zamena(); // если за пределами экрана… } Init(); // начальная расстановка while ( 1 ) // зацикливание ??? { Draw ( YELLOW ); // рисуем все пузырьки delay ( 10 ); // ждем 10 мс Draw ( BLACK ); // стираем все пузырьки Sdvig ( 4 ); // вверх на 4 пикселя Zamena(); // если за пределами экрана… } if ( kbhit() ) if ( getch() == 27 ) break; if ( kbhit() ) if ( getch() == 27 ) break; выход по Esc (код 27)

60 60 Процедура Init void Init() { int i; for ( i = 0; i < N; i ++ ) { X[i] = random( *r) + r; Y[i] = random( *r) + r; } void Init() { int i; for ( i = 0; i < N; i ++ ) { X[i] = random( *r) + r; Y[i] = random( *r) + r; } Начальная случайная расстановка: r Интервал для x: [r, 600-r] 400 Интервал для y: [r, 400-r] X[i] = random( *r) + r; Y[i] = random( *r) + r;

61 61 Процедуры Draw, Sdvig Рисование и стирание: void Draw ( int color ) { int i; setcolor ( color ); for ( i = 0; i < N; i ++ ) circle ( X[i], Y[i], r ); } void Draw ( int color ) { int i; setcolor ( color ); for ( i = 0; i < N; i ++ ) circle ( X[i], Y[i], r ); } Сдвиг вверх: void Sdvig ( int dy ) { int i; for ( i = 0; i < N; i ++ ) Y[i] -= dy; } void Sdvig ( int dy ) { int i; for ( i = 0; i < N; i ++ ) Y[i] -= dy; }

62 62 Процедура Zamena Замена вышедших за границы экрана: 400 void Zamena () { int i; for ( i = 0; i < N; i ++ ) if ( Y[i] < r ) { X[i] = random( *r) + r; Y[i] = r; } void Zamena () { int i; for ( i = 0; i < N; i ++ ) if ( Y[i] < r ) { X[i] = random( *r) + r; Y[i] = r; } Y[i]< r Y[i] = r Условие выхода: Перебросить вниз: if ( Y[i] < r ) {... } X[i] = random( *r) + r; Y[i] = 400 – r; X[i] = random( *r) + r; Y[i] = 400 – r;

63 63 Задания «4»: Моделирование кипения воды в стакане (синий фон, рамка): «5»: Моделирование двустороннего потока: часть частиц двигаются влево, часть – вправо.

64 Программирование на языке Си Часть II Тема 8. Символьные строки © К.Ю. Поляков,

65 65 Чем плох массив символов? char A[4] = { 'A', '3', '[', 'Ж'}; char B[10]; char A[4] = { 'A', '3', '[', 'Ж'}; char B[10]; Это массивы символов: Для массива: каждый символ – отдельный объект; массив имеет длину N, которая задана при объявлении Что нужно: обрабатывать последовательность символов как единое целое строка должна иметь переменную длину

66 66 Символьные строки Привет!\0¤¤…¤¤¤ 0 79 рабочая часть s[0] s[1] s[2] s[3] char s[80]; признак окончания строки: символ с кодом 0 Символ '\0' имеет код 0 символ '0' имеет код 48 ! Символьная строка – это последовательность символов, которая заканчивается символом '\0'.

67 67 Объявление символьных строк Объявить строку = выделить ей место в памяти и присвоить имя. char s[80]; char s1[80] = "abc"; char qqq[] = "Вася"; char s[80]; char s1[80] = "abc"; char qqq[] = "Вася"; выделяется 80 байт, в строке – «мусор» (если она глобальная, то нули '\0) выделяется 80 байт, занято 4 байта (с учетом '\0') выделяется 5 байт (с учетом '\0') выделяется 5 байт (с учетом '\0') При выделении памяти надо учитывать место для символа '\0'. В строку нельзя записывать больше символов, чем выделено памяти. !

68 68 Ввод и вывод символьных строк Задача: ввести слово с клавиатуры и заменить все буквы «а» на буквы «б». main() { char q[80]; int i; printf("Введите строку\n"); scanf( "%s", q); i = 0; while ( q[i] != '\0' ) { if ( q[i] == 'а' ) q[i] = 'б'; i ++; } printf ( "Результат: %s ", q ); } %s не надо ставить &: q &q[0] не надо ставить &: q &q[0] %s – формат для ввода и вывода символьных строк (выводится только часть до '\0' "%s" пока не дошли до конца строки переход к следующему символу начали с q[0]

69 69 Ввод одного слова: Ввод строки с пробелами: char q[80]; printf ("Введите текст:\n"); scanf ( "%s", q ); printf ("Введено:\n%s", q ); char q[80]; printf ("Введите текст:\n"); scanf ( "%s", q ); printf ("Введено:\n%s", q ); Ввод символьных строк Введите текст: Вася пошел гулять Введено: Вася Введите текст: Вася пошел гулять Введено: Вася char q[80]; printf("Введите текст:\n"); gets ( q ); printf("Введено:\n%s", q ); char q[80]; printf("Введите текст:\n"); gets ( q ); printf("Введено:\n%s", q ); Введите текст: Вася пошел гулять Введено: Вася пошел гулять Введите текст: Вася пошел гулять Введено: Вася пошел гулять gets ( q );

70 70 Универсальный способ: Только для одной строки: printf ( "Результат: %s", q ); Вывод символьных строк puts ( q ); можно выводить сразу и другую информацию: надписи, значения переменных, … вывод только одной строки после вывода – переход на новую строку printf ( "%s\n", q );

71 71 Задания «4»: Ввести символьную строку и заменить все буквы "а" на буквы "б" и наоборот, как заглавные, так и строчные. Пример: Введите строку: ааббссААББСС Результат: ббаассББААСС «5»: Ввести символьную строку и проверить, является ли она палиндромом (палиндром читается одинаково в обоих направлениях). Пример: Пример: Введите строку: Введите строку: АБВГДЕ КАЗАК Результат: Результат: Не палиндром. Палиндром.

72 72 Функции для работы со строками Длина строки: strlen (string length) Подключение библиотеки: #include char q[80] = "qwerty"; int n; n = strlen ( q ); char q[80] = "qwerty"; int n; n = strlen ( q ); n = 6n = 6 n = 6n = 6 При определении длины символ '\0' не учитывается! !

73 73 Сравнение строк char q1[80], q2[80]; int n; gets ( q1 ); gets ( q2 ); n = strcmp ( q1, q2 ); char q1[80], q2[80]; int n; gets ( q1 ); gets ( q2 ); n = strcmp ( q1, q2 ); strcmp (string comparison): q1q2n "AA" 0 "AB""AA"1 "AB"– 1 "AA""A"65 Функция вычисляет разность между кодами первых двух отличающихся символов! !

74 74 Пример решения задачи Задача: ввести строку и определить, сколько в ней слов. Программа должна работать только при вводе правильного пароля. Идея решения: проверка пароля – через strcmp количество слов = количеству первых букв слова первая буква: пробел и за ним «не пробел» исключение: предложение начинается со слова (а не с пробела) Васяпошелгулять\0¤¤¤¤¤

75 75 Проверка пароля #include main() { char secret[] = "123", pass[20]; printf ( "Введите пароль\n" ); gets ( pass ); if ( strcmp ( pass, secret ) != 0 ) { printf ( "Пароль неверный" ); getch (); return 1; }... } если пароль неверный... сообщить об ошибке и выйти из программы аварийное завершение, код ошибки 1

76 76 Основная часть программы #include main() { char q[80]; int i, len, count = 0;... // проверка пароля printf ("Введите предложение\n"); gets ( q ); len = strlen( q ); if ( q[0] != ' ') count++; for ( i = 0; i < len - 1; i ++ ) if ( q[i] == ' ' && q[i+1] != ' ' ) count ++; printf ( "Найдено %d слов", count ); } особый случай если нашли пробел, а за ним не пробел… предыдущий слайд

77 77 Подсказка: для вывода одного символа используйте функцию putchar(символ). Например: Задания (везде – с паролем!) «4»: Ввести предложение и определить, сколько слов заканчиваются на букву 'а'. Пример: Введите предложение: Введите предложение: Мама мыла раму Декан пропил бутан Найдено слов: 2 Нет таких слов «5»: Ввести предложение и разобрать его на отдельные слова: Пример: Введите предложение: Мама мыла раму Результат: Мама мыла раму putchar(q[i]); putchar('\n'); // переход на новую строку putchar(q[i]); putchar('\n'); // переход на новую строку

78 78 Копирование строк strcpy (string copy) char q1[10] = "qwerty", q2[10] = "01234"; strcpy ( q1, q2 ); char q1[10] = "qwerty", q2[10] = "01234"; strcpy ( q1, q2 ); куда откуда Старое значение q1 стирается! ! копирование «хвоста» строки char q1[10] = "qwerty", q2[10] = "01234"; strcpy ( q1, q2+2 ); char q1[10] = "qwerty", q2[10] = "01234"; strcpy ( q1, q2+2 ); qwerty\0¤¤¤ ¤¤¤¤ q2 q1 q2 = &q2[0] q2+2 = &q2[2] 234\0 79 79 Копирование строк копирование в середину строки char q1[10] = "qwerty", q2[10] = "01234"; strcpy ( q1+2, q2 ); char q1[10] = "qwerty", q2[10] = "01234"; strcpy ( q1+2, q2 ); qwerty\0¤¤¤ ¤¤¤¤ q2 q1 q1+2 = &q1[2] 01234\0 char q1[10] = "qwerty", q2[10] = "01234"; strcpy ( q1+2, q2+3 ); char q1[10] = "qwerty", q2[10] = "01234"; strcpy ( q1+2, q2+3 ); qwerty\0¤¤¤ ¤¤¤¤ q2 q1 34\0 q2+3 = &q2[3] q1+2 = &q1[2]

80 80 Копирование строк strncpy – копирование нескольких символов char q1[10] = "qwerty", q2[10] = "01234"; strncpy ( q1+2, q2, 2 ); char q1[10] = "qwerty", q2[10] = "01234"; strncpy ( q1+2, q2, 2 ); qwerty\0¤¤¤ ¤¤¤¤ q2 q1 q1+2 = &q1[2] 01 Функция strncpy не добавляет символ '\0' в конце строки! !

81 81 Копирование строк копирование строки-константы char q1[10] = "qwerty"; strcpy ( q1+1, "ABCD"); char q1[10] = "qwerty"; strcpy ( q1+1, "ABCD"); qwerty\0¤¤¤ ABCD q1 ABCD\0 char q1[10] = "qwerty"; strcpy ( "ABCD", q1+2 ); char q1[10] = "qwerty"; strcpy ( "ABCD", q1+2 ); Первым параметром может быть константа! ! НЕ

82 82 Копирование строк копирование внутри одной строки char q[10] = "012345"; strcpy ( q, q+2 ); char q[10] = "012345"; strcpy ( q, q+2 ); \0¤¤¤ q 2345 char q[10] = "012345"; strcpy ( q+2, q ); char q[10] = "012345"; strcpy ( q+2, q ); \0¤¤¤ q Зацикливание и зависание компьютера!

83 83 Объединение строк strcat (string concatenation) = копирование второй строки в конец первой char q1[10] = "qwe", q2[10] = "0123"; strcat ( q1, q2 ); char q1[10] = "qwe", q2[10] = "0123"; strcat ( q1, q2 ); qwe\0¤¤¤¤¤¤ 0123 ¤¤¤¤¤ q2 q1 0123\0 char q1[10] = "qwe", q2[10] = "0123"; strcat ( q1, q2+2 ); char q1[10] = "qwe", q2[10] = "0123"; strcat ( q1, q2+2 ); qwe\0¤¤¤¤¤¤ 0123 ¤¤¤¤¤ q2 q1 23\0

84 84 что-то другое Проблемы Проблемы при копировании строк Транслятор не сообщает об этих ошибках! ! char q1[] = "qwer", q2[10] = "01234"; strcpy ( q1+2, q2 ); char q1[] = "qwer", q2[10] = "01234"; strcpy ( q1+2, q2 ); не хватает места для строки-результата qwer\ ¤¤¤¤¤ q2 q1 0123\0 зацикливание при копировании в ту же строку «слева направо» char q[10] = "01234"; strcpy ( q+2, q ); char q[10] = "01234"; strcpy ( q+2, q );

85 85 Пример решения задачи Задача: ввести имя файла (без пути) и поменять его расширение на ".exe". Пример: Введите имя файла: Введите имя файла: vasya.html vasya Результат: Результат: vasya.exe vasya.exe Алгоритм: найти точку в имени файла если она есть, скопировать в это место строку- константу ".exe" если точки нет, добавить в конец строки ".exe"

86 86 Программа main() { charfName[80]; int i; printf("Введите имя файла\n"); gets ( fName ); i = 0; while ( fName[i] != '.' ) { if ( fName[i] == '\0' ) break; i ++; } if ( fName[i] == '.' ) strcpy ( fName+i, ".exe" ); else strcat ( fName, ".exe" ); puts ( "Результат:" ); puts ( fName ); } поиск точки дошли до конца строки меняем или добавляем расширение

87 87 Задания «4»: Ввести полный адрес файла (возможно, без расширения) и изменить его расширение на «.exe ». Пример: Введите имя файла: Введите имя файла: C:\DOC.TXT\qqq C:\DOC.TXT\qqq.com Результат: Результат: C:\DOC.TXT\qqq.exe C:\DOC.TXT\qqq.exe «5»: Ввести в одной строке фамилию, имя и отчество. Вывести приветствие, где останутся имя и фамилия (см. пример). Пример: Введите ФИО: Пупкин Василий Иванович Результат: Привет, Василий Пупкин!

88 88 Поиск в символьных строках Задача: найти заданный символ или сочетание символов (подстроку) в символьной строке. Функции поиска в Си возвращают адрес найденного символа или подстроки! Если образец не найден, возвращается NULL (нулевой адрес). ! Указатель – это переменная в которую можно записать адрес другой переменной заданного типа.

89 89 Указатели char *p; // адрес любого символа или строки int *pI; // адрес целого числа float *pF; // адрес вещественного числа char *p; // адрес любого символа или строки int *pI; // адрес целого числа float *pF; // адрес вещественного числа Объявление: Целые переменные и массивы: int n = 6, A[5] = {0, 1, 2, 3, 4}; int *p; // указатель на целое p = &n; // записать адрес n *p = 20; // n = 20 p = A + 2; // записать адрес A[2] (&A[2]) *p = 99; // изменить A[2] p ++; // перейти к A[3] printf("Адрес: %p, число %d", p, *p); int n = 6, A[5] = {0, 1, 2, 3, 4}; int *p; // указатель на целое p = &n; // записать адрес n *p = 20; // n = 20 p = A + 2; // записать адрес A[2] (&A[2]) *p = 99; // изменить A[2] p ++; // перейти к A[3] printf("Адрес: %p, число %d", p, *p); Адрес: 6BCD:000C, значение 3 pointer – указатель

90 90 Указатели и символьные строки char str[10] = " "; char *p; p = str; *p = 'A'; p ++; *p = 'B'; p ++; strcpy ( p, "CD" ); strcat ( p, "qqq" ); puts ( p ); char str[10] = " "; char *p; p = str; *p = 'A'; p ++; *p = 'B'; p ++; strcpy ( p, "CD" ); strcat ( p, "qqq" ); puts ( p ); // указатель на символ // или & str[0] // "A12345" // перейти к str[1] // "AB2345 // перейти к str[2] // "ABCD" // "ABCDqqq"

91 91 Поиск символа strchr: найти первый заданный символ c начала строки strrchr: найти последний заданный символ в строке char q[10] = "abcdabcd"; char *p; int nomer; p = strchr(q, 'b'); if ( p == NULL ) printf ( "Не нашли..." ); else { nomer = p – q; printf ( "Номер символа %d", nomer ); } char q[10] = "abcdabcd"; char *p; int nomer; p = strchr(q, 'b'); if ( p == NULL ) printf ( "Не нашли..." ); else { nomer = p – q; printf ( "Номер символа %d", nomer ); } abcdabcd\0¤ q q q+1 q+5 p p reverse

92 92 Поиск подстроки strstr: найти первую подстроку c начала строки char q[10] = "abcdabcd"; char *p; int nomer; p = strstr(q, "bcd"); if ( p == NULL ) printf ( "Не нашли..." ); else { nomer = p – q; printf ( "Номер первого символа %d", nomer ); } char q[10] = "abcdabcd"; char *p; int nomer; p = strstr(q, "bcd"); if ( p == NULL ) printf ( "Не нашли..." ); else { nomer = p – q; printf ( "Номер первого символа %d", nomer ); } abcdabcd\0¤ q q q+1 q+5 p p

93 93 Пример решения задачи Задача: ввести предложение и определить, сколько раз в нем встречается имя «Вася». Проблема: функция strstr ищет только с начала строки. Алгоритм: 1.Записать адрес начала строки в указатель start. 2.Искать подстроку «Вася», начиная с адреса start. 3.Если не нашли, выход из цикла. 4.Увеличить счетчик найденных слов. 5.Переставить start на адрес после найденного слова. 6.Перейти к шагу 2. Вася иВасяВася!!!\0 start p p = strstr( start, "Вася");

94 94 Программа main() { char q[80], *start, *p; int count = 0; puts ( "Введите предложение" ); gets ( q ); start = q; // ищем с начала строки while ( 1 ) { p = strstr ( start, "Вася" ); if ( p == NULL ) break; count ++; start = p + 4; // отсюда ищем следующее слово } printf ( "Имя 'Вася' встречается %d раз", count ); } начало поиска адрес найденного слова

95 95 Задания «4»: Ввести предложение и заменить все имена «Вася» на «Юра». Пример: Введите предложение: Вася, Вася, Вася и Вася!!! Результат: Юра, Юра, Юра и Юра!!! «5»: Ввести предложение и заменить все имена «Юра» на «Вася». Пример: Введите предложение: Юра, Юра, Юра и Юра!!! Результат: Вася, Вася, Вася и Вася!!!

96 96 Строки в процедурах и функциях строки передаются в функции и процедуры так же, как и массивы; функции и процедуры могут изменять строки – параметры. ! Задача: составить процедуру, которая переставляет символы строки в обратном порядке. Алгоритм: определить длину строки len; все символы первой половины переставить с соответствующими символами второй половины: c = s[i]; s[i] = s[len-i-1]; s[len-1-i] = c; c = s[i]; s[i] = s[len-i-1]; s[len-1-i] = c; s[i]s[len-1-i]

97 97 Программа void Reverse ( char s[] ) { int len = strlen(s); char c; for ( i = 0; i < len/2; i ++ ) { c = s[i]; s[i] = s[len-i-1]; s[len-1-i] = c; } main() { char s[] = " "; Reverse ( s ); puts ( s ); Reverse ( s + 5 ); puts ( s ); } void Reverse ( char s[] ) { int len = strlen(s); char c; for ( i = 0; i < len/2; i ++ ) { c = s[i]; s[i] = s[len-i-1]; s[len-1-i] = c; } } main() { char s[] = " "; Reverse ( s ); puts ( s ); Reverse ( s + 5 ); puts ( s ); } Как сделать инверсию любой части строки? ? длину строки определяем на месте

98 98 Задания «4»: Разработать процедуру, которая переставляет пары соседних символов. Пример: Введите предложение: Вася пошел гулять! Результат: аВясп шолег лутя!ь «5»: Разработать процедуру, которая удаляет все лишние пробелы (в начале предложения и сдвоенные пробелы). Пример: Введите предложение: Вася пошел гулять! Результат: Вася пошел гулять!

99 99 Символьные строки в функциях Задача: составить функцию, которая находит количество цифр в строке. int NumDigits ( char s[] ) { int i, count = 0; for ( i = 0; i < strlen(s); i ++ ) if( strchr ( " ", s[i] ) ) count ++; return count; } int NumDigits ( char s[] ) { int i, count = 0; for ( i = 0; i < strlen(s); i ++ ) if( strchr ( " ", s[i] ) ) count ++; return count; } if ( strchr ( " ", s[i] ) != NULL ) или if ( '0'

100 100 Символьные строки в функциях Основная программа int NumDigits ( char s[] ) {... } main() { char s[80]; int n; printf ( "Введите строку\n" ); gets ( s ); n = NumDigits ( s ); printf ( "Нашли %d цифр.", s ); } int NumDigits ( char s[] ) {... } main() { char s[80]; int n; printf ( "Введите строку\n" ); gets ( s ); n = NumDigits ( s ); printf ( "Нашли %d цифр.", s ); }

101 101 Задания «4»: Разработать функцию, которая определяет, верно ли, что слово – палиндром. Пример: Введите слово: Введите слово: казак кунак Результат:Результат: Это палиндром.Не палиндром. «5»: Разработать функцию, которая определяет, верно ли, что предложение (с пробелами) – палиндром. Пример: Введите предложение: а роза упала на лапу азора Результат: Это палиндром.

102 Программирование на языке Си Часть II Тема 9. Рекурсивный перебор © К.Ю. Поляков,

103 103 Рекурсивный перебор Задача: Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ и О. Вывести на экран все слова из К букв, которые можно составить в этом языке, и подсчитать их количество. Число K вводится с клавиатуры. 0K-1 в каждой ячейке может быть любая из 4-х букв 4 варианта Количество вариантов:

104 104 Рекурсивный перебор Ы 0K-1 Рекурсия: Решения задачи для слов из К букв сводится к 4-м задачам для слов из K-1 букв. Щ 0K-1 О 0 Ц 0 перебрать все варианты

105 105 Процедура ???? 0K-1 p Глобальные переменные: char s[80]; int count, K; Глобальные переменные: char s[80]; int count, K; s p+1 рекурсивные вызовы А если букв много? ? окончание рекурсии void Rec( int p ) { if ( p >= K ) { puts ( s ); count ++; return; } s[p] = 'Ы'; Rec ( p + 1 ); s[p] = 'Ц'; Rec ( p + 1 ); s[p] = 'Щ'; Rec ( p + 1 ); s[p] = 'О'; Rec ( p + 1 ); } p символов уже на своих местах

= K ) { puts ( s ); count ++; return; } for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); } const char letters[] = 'ЫЦЩО'; for ( i = 0; i < str" title="106 Процедура void Rec ( int p ) { const char letters[] = "ЫЦЩО"; int i; if ( p >= K ) { puts ( s ); count ++; return; } for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); } const char letters[] = 'ЫЦЩО'; for ( i = 0; i < str" class="link_thumb"> 106 106 Процедура void Rec ( int p ) { const char letters[] = "ЫЦЩО"; int i; if ( p >= K ) { puts ( s ); count ++; return; } for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); } const char letters[] = 'ЫЦЩО'; for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); } все буквы цикл по всем буквам локальная переменная = K ) { puts ( s ); count ++; return; } for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); } const char letters[] = 'ЫЦЩО'; for ( i = 0; i < str"> = K ) { puts ( s ); count ++; return; } for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); } const char letters[] = 'ЫЦЩО'; for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); } все буквы цикл по всем буквам локальная переменная"> = K ) { puts ( s ); count ++; return; } for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); } const char letters[] = 'ЫЦЩО'; for ( i = 0; i < str" title="106 Процедура void Rec ( int p ) { const char letters[] = "ЫЦЩО"; int i; if ( p >= K ) { puts ( s ); count ++; return; } for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); } const char letters[] = 'ЫЦЩО'; for ( i = 0; i < str">

107 107 Программа char s[80]; int K, count = 0 ; main() { printf ( "Введите длину слов:\n" ); scanf ( "%d", &K ); Rec ( 0 ); printf ( "Всего %d слов.", count ); } char s[80]; int K, count = 0 ; main() { printf ( "Введите длину слов:\n" ); scanf ( "%d", &K ); Rec ( 0 ); printf ( "Всего %d слов.", count ); } void Rec ( int p ) {... } процедура глобальные переменные (обнуляются) глобальные переменные (обнуляются) count; 1. Как определяется конец строки? 2. Как обойтись без глобальных переменных? ?

108 108 Задания Алфавит языка племени "тумба-юмба" состоит из букв Ы, Ц, Щ и О. Число K вводится с клавиатуры. «4»: Вывести на экран все слова из К букв, в которых буква Ы встречается более 1 раза, и подсчитать их количество. «5»: Вывести на экран все слова из К букв, в которых есть одинаковые буквы, стоящие рядом (например, ЫЩЩО), и подсчитать их количество. Без глобальных переменных! !

109 Программирование на языке Си Часть II Тема 10. Матрицы © К.Ю. Поляков,

110 110 Матрицы Задача: запомнить положение фигур на шахматной доске abcdefgh c6 A[5][2]

111 111 Матрицы Матрица – это прямоугольная таблица однотипных элементов. Матрица – это массив, в котором каждый элемент имеет два индекса (номер строки и номер столбца) A строка 1 столбец 2 ячейка A[2][3]

112 112 Матрицы Объявление: const int N = 3, M = 4; int A[N][M]; float a[2][2] = {{3.2, 4.3}, {1.1, 2.2}}; char sym[2][2] = { 'a', 'b', 'c', 'd' }; const int N = 3, M = 4; int A[N][M]; float a[2][2] = {{3.2, 4.3}, {1.1, 2.2}}; char sym[2][2] = { 'a', 'b', 'c', 'd' }; Ввод с клавиатуры: for ( i = 0; i < N; i ++ ) for ( j = 0; j < M; j ++ ) { printf ( "A[%d][%d]=", i, j); scanf ( "%d", &A[i][j] ); } for ( i = 0; i < N; i ++ ) for ( j = 0; j < M; j ++ ) { printf ( "A[%d][%d]=", i, j); scanf ( "%d", &A[i][j] ); } Если переставить циклы? ? A[0][0]=25 A[0][1]=14 A[0][2]=14... A[2][3]=54 i i j j for ( j = 0; j < M; j ++ ) for ( i = 0; i < N; i ++ ) {

113 113 Матрицы Заполнение случайными числами for ( i = 0; i < N; i ++ ) for ( j = 0; j < M; j ++ ) A[i][j] = random(25)- 10; for ( i = 0; i < N; i ++ ) for ( j = 0; j < M; j ++ ) A[i][j] = random(25)- 10; Какой интервал? ? цикл по строкам цикл по столбцам Вывод на экран for ( i = 0; i < N; i ++ ) { for ( j = 0; j < M; j ++ ) printf("%5d", A[i,j]); printf("\n"); } for ( i = 0; i < N; i ++ ) { for ( j = 0; j < M; j ++ ) printf("%5d", A[i,j]); printf("\n"); } перейти на новую строку for ( j = 0; j < M; j ++ ) printf("%5d", A[i][j]); for ( j = 0; j < M; j ++ ) printf("%5d", A[i][j]); вывод строки Если переставить циклы? ? в той же строке

114 114 Обработка всех элементов матрицы Задача: заполнить матрицу из 3 строк и 4 столбцов случайными числами и вывести ее на экран. Найти сумму элементов матрицы. main() { const int N = 3, M = 4; int A[N][M], i, j, S = 0;... // заполнение матрицы и вывод на экран for ( i = 0; i < N; i ++ ) for ( j = 0; j < M; j ++ ) S += A[i][j]; printf("Сумма элементов матрицы S=%d", S); } main() { const int N = 3, M = 4; int A[N][M], i, j, S = 0;... // заполнение матрицы и вывод на экран for ( i = 0; i < N; i ++ ) for ( j = 0; j < M; j ++ ) S += A[i][j]; printf("Сумма элементов матрицы S=%d", S); } for ( i = 0; i < N; i ++ ) for ( j = 0; j < M; j ++ ) S += A[i][j]; for ( i = 0; i < N; i ++ ) for ( j = 0; j < M; j ++ ) S += A[i][j];

115 115 Задания Заполнить матрицу из 8 строк и 5 столбцов случайными числами в интервале [-10,10] и вывести ее на экран. «4»: Найти минимальный и максимальный элементы в матрице их номера. Формат вывода: Минимальный элемент A[3][4]=-6 Максимальный элемент A[2][2]=10 «5»: Вывести на экран строку, сумма элементов которой максимальна. Формат вывода: Строка 2:

116 116 Операции с матрицами Задача 1. Вывести на экран главную диагональ квадратной матрицы из N строк и N столбцов. A[0][N-1] A[1][1] A[2][2] A[N-1][N-1] for ( i = 0; i < N; i ++ ) printf ( "%5d", A[i][i] ); for ( i = 0; i < N; i ++ ) printf ( "%5d", A[i][i] ); Задача 2. Вывести на экран вторую диагональ. A[N-1][0] A[N-2][1] A[1][N-2] сумма номеров строки и столбца N-1 A[0][0] for ( i = 0; i < N; i ++) printf ( "%5d", A[i][ N-1-i ]); for ( i = 0; i < N; i ++) printf ( "%5d", A[i][ N-1-i ]); N-1-i

117 117 Операции с матрицами Задача 3. Найти сумму элементов, стоящих на главной диагонали и ниже ее. Одиночный цикл или вложенный? ? строка 0: A[0][0] строка 1: A[1][0]+A[1][1]... строка i: A[i][0]+A[i][2]+...+A[i][i] S = 0; for ( i = 0; i < N; i ++ ) for ( j = 0; j

118 118 Операции с матрицами Задача 4. Перестановка строк или столбцов. В матрице из N строк и M столбцов переставить 1-ую и 3-ю строки j A[1][j] A[3][j] for ( j = 0; j

119 119 Задания Заполнить матрицу из 7 строк и 7 столбцов случайными числами в интервале [-10,10] и вывести ее на экран. Обнулить элементы, отмеченные зеленым фоном, и вывести полученную матрицу на экран. «4»: «5»:

120 Программирование на языке Си Часть II Тема 11. Файлы © К.Ю. Поляков,

121 121 Файлы Файл – это область на диске, имеющая имя. Файлы только текст без оформления, не содержат управляющих символов (с кодами < 32), кроме перевода строки ACSII (1 байт на символ) UNICODE (2 байта на символ) *.txt, *.log, *.htm, *.html могут содержать любые символы кодовой таблицы *.doc, *.exe, *.bmp, *.jpg, *.wav, *.mp3, *.avi, *.mpg ТекстовыеДвоичные Папки (каталоги)

122 122 Принцип сэндвича I этап. открыть файл (сделать его активным, приготовить к работе) f = fopen("qq.dat", "r"); II этап: работа с файлом III этап: закрыть (освободить) файл fclose ( f ); fscanf ( f, "%d", &n ); // ввести значение n fprintf( f, "n=%d", n ); // записать значение n для чтения ( "r", англ. read) f = fopen("qq.dat", "w"); для записи ( "w", англ. write) f = fopen("qq.dat", "a"); для добавления ( "a", англ. append) Переменная типа «указатель на файл»: FILE *f;

123 123 Работа с файлами Особенности: имя файла упоминается только в команде fopen, обращение к файлу идет через указатель f ; файл, который открывается на чтение, должен существовать если файл, который открывается на запись, существует, старое содержимое уничтожается данные (этим способом) записываются в файл в текстовом виде когда программа заканчивает работу, все файлы закрываются автоматически после закрытия файла переменную f можно использовать еще раз для работы с другим файлом

124 124 Последовательный доступ при открытии файла курсор устанавливается в начало чтение выполняется с той позиции, где стоит курсор после чтения курсор сдвигается на первый непрочитанный символ конец файла (end of file, EOF) конец файла (end of file, EOF) f = fopen("qq.dat", "r"); fscanf ( f, "%d", &x ); Как вернуться назад? ?

125 125 Ошибки при открытии файла FILE *f; f = fopen("qq.dat", "r"); if ( f == NULL ) { puts("Файл на найден."); return; } FILE *f; f = fopen("qq.dat", "r"); if ( f == NULL ) { puts("Файл на найден."); return; } NULL неверное имя файла нет файла файл заблокирован другой программой неверное имя файла нет файла файл заблокирован другой программой Если файл открыть не удалось, функция fopen возвращает NULL (нулевое значение)! ! FILE *f; f = fopen("qq.dat", "w"); if ( f == NULL ) { puts("Не удалось открыть файл."); return; } FILE *f; f = fopen("qq.dat", "w"); if ( f == NULL ) { puts("Не удалось открыть файл."); return; } NULL неверное имя файла файл «только для чтения» файл заблокирован другой программой неверное имя файла файл «только для чтения» файл заблокирован другой программой

126 126 Пример Задача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно. Записать в файл output.txt их сумму. Алгоритм: 1.Открыть файл input.txt для чтения. 2.S = 0; 3.Прочитать очередное число в переменную x. 4.Если не удалось, перейти к шагу 7. 5.S + = x; 6.Перейти к шагу 3. 7.Закрыть файл input.txt. 8.Открыть файл output.txt для записи. 9.Записать в файл значение S. 10.Закрыть файл output.txt. Можно ли обойтись без массива? ? цикл с условием «пока есть данные»

127 127 Как определить, что числа кончились? FILE *f; int n, x; f = fopen("input.txt", "r");... n = fscanf ( f, "%d", &x ); if ( n ! = 1 ) puts ( "Не удалось прочитать число" ); FILE *f; int n, x; f = fopen("input.txt", "r");... n = fscanf ( f, "%d", &x ); if ( n ! = 1 ) puts ( "Не удалось прочитать число" ); Функция fscanf возвращает количество удачно прочитанных чисел; 0, если была ошибка при чтении; – 1, если достигли конца файла. ! дошли до конца файла встретили «не число» дошли до конца файла встретили «не число»

128 128 Программа main() { FILE *f; int n, x, S = 0; f = fopen ( "input.txt", "r" ); if ( f == NULL ) { printf("Файл не найден."); return; } while ( 1 ) { n = fscanf ( f, "%d", &x ); if ( n != 1 ) break; S += x; } fclose ( f ); f = fopen ( "output.txt", "w" ); fprintf ( f, "S = %d", S ); fclose ( f ); } ошибка при открытии файла цикл чтения данных: выход при n 1. запись результата

129 129 Задания В файле input.txt записаны числа, сколько их – неизвестно. «4»: Найти среднее арифметическое всех чисел и записать его в файл output.txt. «5»: Найти минимальное и максимальное числа и записать их в файл output.txt.

130 130 Обработка массивов Задача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно, но не более 100. Переставить их в порядке возрастания и записать в файл output.txt. Проблемы: для сортировки надо удерживать в памяти все числа сразу (массив); сколько чисел – неизвестно. Решение: 1)выделяем в памяти массив из 100 элементов; 2)записываем прочитанные числа в массив и считаем их в переменной N ; 3)сортируем первые N элементов массива; 4)записываем их в файл. Можно ли обойтись без массива? ?

= MAX ) break; } fclose(f); return N; } Функ" title="131 Чтение данных в массив int ReadArray ( int A[], char fName[], int MAX ) { int N = 0, k; FILE *f; f = fopen ( fName, "r" ); while ( 1 ) { k = fscanf ( f, "%d", &A[N]); if ( k != 1 ) break; N ++; if ( N >= MAX ) break; } fclose(f); return N; } Функ" class="link_thumb"> 131 131 Чтение данных в массив int ReadArray ( int A[], char fName[], int MAX ) { int N = 0, k; FILE *f; f = fopen ( fName, "r" ); while ( 1 ) { k = fscanf ( f, "%d", &A[N]); if ( k != 1 ) break; N ++; if ( N >= MAX ) break; } fclose(f); return N; } Функция, которая читает массив из файла, возвращает число прочитанных элементов (не более MAX): массив заканчиваем цикл если не удалось прочитать … имя файла предел … или заполнили весь массив = MAX ) break; } fclose(f); return N; } Функ"> = MAX ) break; } fclose(f); return N; } Функция, которая читает массив из файла, возвращает число прочитанных элементов (не более MAX): массив заканчиваем цикл если не удалось прочитать … имя файла предел … или заполнили весь массив"> = MAX ) break; } fclose(f); return N; } Функ" title="131 Чтение данных в массив int ReadArray ( int A[], char fName[], int MAX ) { int N = 0, k; FILE *f; f = fopen ( fName, "r" ); while ( 1 ) { k = fscanf ( f, "%d", &A[N]); if ( k != 1 ) break; N ++; if ( N >= MAX ) break; } fclose(f); return N; } Функ">

132 132 Программа main() { int A[100], N, i; FILE *f; N = ReadArray ( A, "input.txt", 100 );... // сортировка первых N элементов f = fopen("output.txt", "w"); for ( i = 0; i < N; i ++) fprintf ( f, "%d\n", A[i] ); fclose ( f ); } main() { int A[100], N, i; FILE *f; N = ReadArray ( A, "input.txt", 100 );... // сортировка первых N элементов f = fopen("output.txt", "w"); for ( i = 0; i < N; i ++) fprintf ( f, "%d\n", A[i] ); fclose ( f ); } int ReadArray(int A[], char fName[], int MAX) {... } вывод отсортированного массива в файл

133 133 Задания В файле input.txt записаны числа (в столбик), известно, что их не более 100. «4»: Отсортировать массив по убыванию последней цифры и записать его в файл output.txt. «5»: Отсортировать массив по возрастанию суммы цифр и записать его в файл output.txt.

134 134 Обработка текстовых данных Задача: в файле input.txt записаны строки, в которых есть слово-паразит "короче". Очистить текст от мусора и записать в файл output.txt. Файл input.txt : Мама, короче, мыла, короче, раму. Декан, короче, пропил, короче, бутан. А роза, короче, упала на лапу, короче, Азора. Каждый, короче, охотник желает, короче, знать, где... Результат – файл output.txt : Мама мыла раму. Декан пропил бутан. А роза упала на лапу Азора. Каждый охотник желает знать, где сидит фазан.

135 135 Обработка текстовых данных Особенность: надо одновременно держать открытыми два файла (один в режиме чтения, второй – в режиме записи). Алгоритм: 1. Открыть оба файла. 2. Прочитать строку. 3. Удалить все сочетания ", короче,". 4. Записать строку во второй файл. 5. Перейти к шагу Закрыть оба файла. пока не кончились данные

136 136 Работа с файлами main() { char s[80], *p; int i; FILE *fIn, *fOut; fIn = fopen("input.txt", "r"); fOut = fopen("output.txt", "w");... // обработать файл fclose(fIn); fclose(fOut); } main() { char s[80], *p; int i; FILE *fIn, *fOut; fIn = fopen("input.txt", "r"); fOut = fopen("output.txt", "w");... // обработать файл fclose(fIn); fclose(fOut); } файловые указатели открыть файл для чтения открыть файл для записи указатель для поиска закрыть файлы

137 137 Обработка текстовых данных Чтение строки s : while ( 1 ) { p = strstr ( s, ", короче," ); if ( p == NULL ) break; strcpy ( p, p + 9 ); } while ( 1 ) { p = strstr ( s, ", короче," ); if ( p == NULL ) break; strcpy ( p, p + 9 ); } искать ", короче," удалить 9 символов выйти из цикла, если не нашли char s[80], *p; FILE *fIn;... // здесь надо открыть файл p = fgets ( s, 80, fIn ); if ( p == NULL ) printf("Файл закончился."); else printf("Прочитана строка:\n%s", s); char s[80], *p; FILE *fIn;... // здесь надо открыть файл p = fgets ( s, 80, fIn ); if ( p == NULL ) printf("Файл закончился."); else printf("Прочитана строка:\n%s", s); Обработка строки s : строка длина файл

138 138 #include Полный цикл обработки файла while ( 1 ) { p = fgets ( s, 80, fIn ); if ( p == NULL ) break; while ( 1 ) { p = strstr ( s, ", короче," ); if ( p == NULL ) break; strcpy ( p, p + 9 ); } fputs ( s, fOut ); } while ( 1 ) { p = fgets ( s, 80, fIn ); if ( p == NULL ) break; while ( 1 ) { p = strstr ( s, ", короче," ); if ( p == NULL ) break; strcpy ( p, p + 9 ); } fputs ( s, fOut ); } while ( 1 ) { p = strstr ( s, ", короче," ); if ( p == NULL ) break; strcpy ( p, p + 9 ); } если нет больше строк, выйти из цикла обработка строки запись "очищенной" строки читаем строку

139 139 Задания В файле input.txt записаны строки, сколько их – неизвестно. «4»: Заменить во всем тексте «в общем» на «короче» и записать результат в файл output.txt. «5»: Заменить во всем тексте «короче» на «в общем» и записать результат в файл output.txt.

140 140 Двоичные файлы Особенности: данные хранятся во внутреннем машинном формате (в текстовом редакторе не прочитать) можно читать и записывать любой кусок памяти (просто биты…) принцип сэндвича (открыть – работать – закрыть) обращение к файлу через указатель Файловые указатели FILE *fp;

141 141 Открытие и закрытие двоичных файлов Открытие файла fp = fopen ( "input.dat", "rb" ); "rb" = read binary (чтение) "wb" = write binary (запись) "ab" = append binary (добавление) "rb" = read binary (чтение) "wb" = write binary (запись) "ab" = append binary (добавление) Ошибки при открытии if ( fp == NULL ) { printf("Файл открыть не удалось."); } if ( fp == NULL ) { printf("Файл открыть не удалось."); } Закрытие файла fclose ( fp );

142 142 Чтение по блокам Чтение в начало массива int A[100]; n = fread ( A, sizeof(int), 100, fp ); int A[100]; n = fread ( A, sizeof(int), 100, fp ); адрес области памяти («куда»): A &A[0] адрес области памяти («куда»): A &A[0] размер одного блока размер переменной целого типа количество блоков указатель на файл прочитано фактически Чтение в середину массива int A[100]; n = fread ( A+5, sizeof(int), 2, fp ); int A[100]; n = fread ( A+5, sizeof(int), 2, fp ); читается 2 целых числа: A[5], A[6] читается 2 целых числа: A[5], A[6]

143 143 Запись по блокам Запись с начала массива int A[100]; n = fwrite( A, sizeof(int), 100, fp ); int A[100]; n = fwrite( A, sizeof(int), 100, fp ); адрес области памяти («откуда»): A &A[0] адрес области памяти («откуда»): A &A[0] размер одного блока размер переменной целого типа количество блоков указатель на файл записано фактически Запись отдельных элементов массива int A[100]; n = fwrite( A+5, sizeof(int), 2, fp ); int A[100]; n = fwrite( A+5, sizeof(int), 2, fp ); записывается 2 целых числа: A[5], A[6] записывается 2 целых числа: A[5], A[6]

144 144 Работа с матрицами Хранение в памяти: по строкам (Си, Паскаль) Запись матрицы int A[3][3]; FILE *fp = fopen("output.dat", "wb");... // здесь заполняем матрицу n = fwrite( A, sizeof(int), 9, fp ); int A[3][3]; FILE *fp = fopen("output.dat", "wb");... // здесь заполняем матрицу n = fwrite( A, sizeof(int), 9, fp );

145 145 Пример Задача: прочитать массив из файла input.dat, умножить все элементы на 2 и вывести в файл output.dat. Структура программы: #include main() { const int N = 10; int i, A[N], n; FILE *fp; // чтение данных и файла input.dat for ( i = 0; i < n; i ++ ) A[i] = A[i] * 2; // запись данных в файл output.dat } #include main() { const int N = 10; int i, A[N], n; FILE *fp; // чтение данных и файла input.dat for ( i = 0; i < n; i ++ ) A[i] = A[i] * 2; // запись данных в файл output.dat } прочитано фактически

146 146 Работа с файлами fp = fopen( "input.dat", "rb" ); if ( fp == NULL ) { printf("Файл открыть не удалось."); return; } n = fread ( A, sizeof(int), N, fp ); if ( n < N ) printf("Не хватает данных в файле"); fclose ( fp ); fp = fopen( "input.dat", "rb" ); if ( fp == NULL ) { printf("Файл открыть не удалось."); return; } n = fread ( A, sizeof(int), N, fp ); if ( n < N ) printf("Не хватает данных в файле"); fclose ( fp ); Чтение данных: fp = fopen( "output.dat", "wb" ); fwrite ( A, sizeof(int), n, fp ); fclose ( fp ); fp = fopen( "output.dat", "wb" ); fwrite ( A, sizeof(int), n, fp ); fclose ( fp ); Запись данных: критическая ошибка некритическая ошибка сколько прочитали

147 147 Задания «4»: В текстовом файле input.txt записан массив целых чисел. Отсортировать его и записать в двоичный файл output.dat. «5»: В текстовых файлах input1.txt и input2.txt записаны два массива. Объединить их в один массив, отсортировать и записать результат в двоичный файл output.dat.

148 148 Конец фильма