Программирование на языке Си Массивы
2 Массивы Массив – это группа однотипных элементов, имеющих общее имя и расположенных в памяти рядом. Особенности: все элементы имеют один тип весь массив имеет одно имя все элементы расположены в памяти рядом Примеры: список учеников в классе квартиры в доме школы в городе данные о температуре воздуха за год
3 Массивы 5 10 15 20 25 0 1 2 3 4 A массив 2 15 НОМЕР элемента массива ( ИНДЕКС ) A[ 0 ] A[ 1 ] A[ 2 ] A[ 3 ] A[ 4 ] ЗНАЧЕНИЕ элемента массива A[2] НОМЕР (ИНДЕКС) элемента массива : 2 ЗНАЧЕНИЕ элемента массива : 1 5 Нумерация элементов массива в Си начинается с НУЛЯ ! !
4 Объявление массивов определить имя массива определить тип массива определить число элементов Пример: int A [ 5 ] ; выделить место в памяти Зачем объявлять? int A [ ] ; const int N = 5; N Размер через константу: тип элементов Имя массива размер массива (количество элементов)
5 Объявление массивов Еще примеры: 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', ' Ю ' }; остальные нулевые! Если начальные значения не заданы, в ячейках находится «мусор»! !
6 Что неправильно? int N = 10; float A[N]; const int int X[4.5]; int A[10]; A[10] = 0; 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
7 Массивы Вывод на экран: 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] ); } 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]); Результат : 1 0 24 68 112 26 Объявление: Ввод с клавиатуры: Поэлементные операции:
8 Программа #include < stdio.h > #include < conio.h > main() { const int N = 5; int A[N], i ; // ввод элементов массива // обработка массива // вывод результата getch (); } Задача: ввести с клавиатуры массив из 5 элементов, умножить все элементы на 2 и вывести полученный массив на экран. на предыдущих слайдах
9 Задания «4»: Ввести c клавиатуры массив из 5 элементов, найти сумму всех элементов. Пример:ех Введите пять чисел: 4 15 3 10 14 Summa=46 «5»: Ввести c клавиатуры массив из 5 элементов и найти произведение. Пример: Введите пять чисел: 4 15 3 10 14 product = 25200 При изменении константы N остальная программа не должна изменяться! !
10 Задания « 6 »: Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое всех элементов массива. Пример: Введите пять чисел: 4 15 3 10 14 ср _ ар = 9.200 int n=5; int mas[n],i; float summa=0; for (i=0; i<n; i++) { printf("mas[%d]=",i); scanf("%d",&mas[i]); } for (i=0; i<n; i++) summa=summa+mas[i]; printf("cp.ap.=%.2f",summa/n); getch();
«7»: Заполнить массив константами: 4, 7, 13, 8, 54, 33 Найти сумму четных чисел и выдать их индексы. { int mas[6]={4,7,13,8,54,33}; int i,min, max,summa=0; for (i=0; i<6; i++) if (mas[i]%2==0) { summa=summa+mas[i]; printf("index=%d\n",i);} printf("summa=%d",summa); getch(); } Задания
12 Максимальный элемент Задача: найти в массиве максимальный элемент. Алгоритм: Псевдокод: // считаем, что элемент A[0] – максимальный for ( i=1; i < N; i++ ) if ( A[i] > максимального ) // запомнить новый максимальный элемент A[i] Почему цикл от i=1 ? ?
«8»: Ввести c клавиатуры массив из 5 элементов, найти максимальный из них. Пример: Введите пять чисел: 4 15 3 10 14 min= 3 { int n=5; int mas[n],i, max ; for (i=0; i<n; i++) { printf("mas[%d]=",i); scanf("%d",&mas[i]); } max =mas[0]; for (i=1; i<n; i++) if (mas[i] > max ) max =mas[i]; printf("min=%d",min); getch(); } Задания
14 Максимальный элемент 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]
«9»: Найти минимальный и максимальный элементы массива и их сумму Пример: Введите пять чисел: 4 15 3 10 14 min= 3 max=15 summa=18 int n=5; int mas[n], i, imin, imax, summa; for (i=0; i<n; i++) { printf("mas[%d]=",i); scanf("%d",&mas[i]); } imin=0; imax=0; for (i=1; i<n; i++) { if (mas[i]<mas[imin]) imin=i; if (mas[i]>mas[imax]) imax=i; }; summa=mas[imin]+mas[imax]; printf("min=%d max=%d summa=%d",mas[imin],mas[imax],summa); getch(); Задания
16 Заполнение случайными числами Случайное целое число в интервале [0,RAND_MAX] x = rand(); // первое число y = rand(); // уже другое число #include <stdlib.h> // случайные числа #include <stdio.h> #include <conio.h> #include <stdlib.h> main() { int x,y,z,nzn; x=RAND_MAX; y=rand(); z=rand(); printf("rand_max=%d y=%d z=%d",x,y); getch(); } RAND_MAX – максимальное случайное целое числ (обычно RAND_MAX = 32767 )
17 Заполнение случайными числами Указание интервала интервал [0,99] x = rand()%100; интервал [0,z-1] x = rand()%z; интервал [a,z-1+a] x = rand()%z + a; Примеры: for (i=0; i<n; i++) { mas[i]=rand()%100; printf("mas[%d]=%d\n", i,mas[i]);} for (i=0; i<n; i++) { mas[i]=rand()%10+30; printf("mas[%d]=%d\n", i,mas[i]);} for (i=0; i<n; i++) { mas[i]=rand()%40-20; printf("mas[%d]=%d\n", i,mas[i]);} for (i=0; i<n; i++) { mas[i]=rand()%30+20; printf("mas[%d]=%d\n", i,mas[i]);} [0,99] [30,39] [-20,19] [20, 4 9] Определить интервалы
18 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ -10.. 10 ] и найти в нем максимальный и минимальный элементы и их номера. int n=10; int mas[n],i,imin,imax; for (i=0; i<n; i++) { mas[i]=rand()%20-10; printf("mas[%d]=%d\n", i,mas[i]);} imin=0; imax=0; for (i=1; i<n; i++) {if (mas[i]<mas[imin]) imin=i; if (mas[i]>mas[imax]) imax=i;}; printf("min=%d max=%d",mas[imin],mas[imax]) ;
19 Задания «5»: Заполнить массив из 10 элементов случайными числами в интервале [ -10.. 10 ] и найти в нем два максимальных элемента и их номера. int n=10; int mas[n],i,imax,imax2; for (i=0; i<n; i++) { mas[i]=rand()%20-10; printf("mas[%d]=%d\n", i,mas[i]);} imax=0; for (i=1; i<n; i++) if (mas[i]>mas[imax]) imax=i; imax2=0; for (i=1; i<n; i++) if (mas[i]>mas[imax2] && mas[i]!=mas[imax]) imax2=i; printf("max2[%d]=%d max[%d]=%d\n",imax2,mas[imax2],imax,mas[imax]); getch();
20 Реверс массива Задача: переставить элементы массива в обратном порядке ( выполнить инверсию). Алгоритм: поменять местами A[0] и A[N-1], A[1] и A[N-2], … Псевдокод: 3 5 … 9 7 7 9 … 5 3 0 1 … N-2 N-1 0 1 … N-2 N-1 for ( i = 0; i < N; i++ ) // поменять местами A[i] и A[N-1-i] сумма индексов N-1 Что неверно ? ? ; i++ ) N / 2
21 Как переставить элементы? 2 3 1 Задача: поменять местами содержимое двух чашек. Задача: поменять местами содержимое двух ячеек памяти. 4 6 ? 4 6 4 x y c c = x; x = y; y = c ; x = y; y = x; 3 2 1
22 Программа main() { const int N = 10; int A[N], i, c; // заполнить массив числами от 0 до 99 // вывести исходный массив for ( i = 0; i < N/2; i++ ) { c = A[i]; A[i] = A[N-1-i]; A[N-1-i] = c; } // вывести полученный массив }
23 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ -10.. 10 ] и выполнить инверсию отдельно для 1-ой и 2-ой половин массива. Пример: Исходный массив: 4 -5 3 10 -4 -6 8 -10 1 0 Результат: - 4 10 3 -5 4 0 1 -10 8 -6 «5»: Заполнить массив из 12 элементов случайными числами в интервале [ -12.. 12 ] и выполнить инверсию для каждой трети массива. Пример: Исходный массив: 4 -5 3 10 -4 -6 8 -10 1 0 5 7 Результат: 10 3 -5 4 -10 8 -6 -4 7 5 0 1
24 Циклический сдвиг Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент становится на место последнего. Алгоритм: A[0]=A[1]; A[1]=A[2];… A[N-2]=A[N-1]; Цикл: 3 5 8 1 … 9 7 0 1 2 3 … N-2 N-1 5 8 1 … 9 7 3 for ( i = 0; i < N-1; i ++) A[i] = A[i+1]; Что неверно ? ? почему не N ?
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 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ -10.. 10 ] и выполнить циклический сдвиг ВПРАВО. Пример: Исходный массив: 4 -5 3 10 -4 -6 8 -10 1 0 Результат: 0 4 -5 3 10 -4 -6 8 -10 1 «5»: Заполнить массив из 12 элементов случайными числами в интервале [ -12.. 12 ] и выполнить циклический сдвиг ВПРАВО на 4 элемента. Пример: Исходный массив: 4 -5 3 10 -4 -6 8 -10 1 0 5 7 Результат: -4 -6 8 -10 1 0 5 7 4 -5 3 10
Тема 4. Сортировка массивов © К.Ю. Поляков, 2007-2009
28 Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Задача: переставить элементы массива в порядке возрастания. Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора сложные, но эффективные «быстрая сортировка» ( Quick Sort ) сортировка «кучей» ( Heap Sort ) сортировка слиянием пирамидальная сортировка сложность O( N 2 ) сложность O( N · log N ) время N O( N 2 ) O( N · log N )
29 Метод пузырька Идея – пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий») элемент перемещается вверх («всплывает»). 5 2 1 3 5 2 1 3 5 1 2 3 1 5 2 3 начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место 1 5 2 3 1 5 2 3 1 2 5 3 1-ый проход 2-ой проход 3-ий проход 1 2 5 3 1 2 3 5 Для сортировки массива из N элементов нужен N -1 проход (достаточно поставить на свои места N-1 элементов).
30 Программа (1-ый проход) 5 2 … 6 3 0 1 … 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; } 0
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; } 1 ( i+1 ) -ый проход for ( j = N-2; j >= i ; j-- ) ... i 1 5 … 3 6 0 1 … N- 2 N -1
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 Метод пузырька с флажком Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны. Реализация: переменная-флаг, показывающая, был ли обмен ; если она равна 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; 2 1 4 3 1 2 3 4 Как улучшить ? ?
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; i i ++;
35 Метод выбора Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[0] ) из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[ 1 ] ), и т.д. 4 3 1 2 1 3 4 2 1 2 4 3 1 2 3 4
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 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ 0.. 100 ] и отсортировать его по последней цифре. Пример: Исходный массив: 14 25 13 30 76 58 32 11 41 97 Результат: 30 11 41 32 13 14 25 76 97 58 «5»: Заполнить массив из 10 элементов случайными числами в интервале [ 0.. 100 ] и отсортировать первую половину по возрастанию, а вторую – по убыванию. Пример: Исходный массив: 14 25 13 30 76 58 32 11 41 97 Результат: 13 14 25 30 76 97 58 41 32 11
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]; 1 -5 3 -2 5 ? ? ? ? ? A B -2 - 5 выбранные элементы не рядом, не в начале массива непонятно, как с ними работать 0 1 2 3 4
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]); 1 -5 3 -2 5 ? ? ? ? ? A B -2 - 5 count 0 1 2 3 4
40 Задания «4»: Заполнить массив случайными числами и отобрать в другой массив все числа, у которых вторая с конца цифра (число десятков) – ноль. Пример: Исходный массив: 40 105 203 1 14 Результат: 105 203 1 «5»: Заполнить массив случайными числами и выделить в другой массив все числа, которые встречаются более одного раза. Пример: Исходный массив: 4 1 2 1 11 2 34 Результат: 1 2
Тема 5. Поиск в массиве © К.Ю. Поляков, 2007-2009
42 Поиск в массиве Задача – найти в массиве элемент, равный X, или установить, что его нет. Решение: для произвольного массива: линейный поиск ( перебор ) недостаток: низкая скорость Как ускорить? – заранее подготовить массив для поиска как именно подготовить? как использовать «подготовленный» массив?
43 Линейный поиск 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 Двоичный поиск 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 X = 7 X < 8 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 4 X > 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 6 X > 6 Выбрать средний элемент A[c] и сравнить с X. Если X = A[c], нашли (выход). Если X < A[c], искать дальше в первой половине. Если X > A[c], искать дальше во второй половине.
45 Двоичный поиск Почему нельзя while ( R > L ) { … } ? ? 0 L c R 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 Сравнение методов поиска Линейный Двоичный подготовка нет отсортировать число шагов N = 2 2 2 N = 16 16 5 N = 1024 1024 11 N= 1048576 1048576 21 N ≤ N ≤ log 2 N+1
47 Задания «4»: Написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в нем элемент, равный X ( это число вводится с клавиатуры ). Использовать двоичный поиск. «5»: Написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. Для поиска использовать 1000 случайных чисел в этом же интервале.
Тема 6. Массивы в процедурах и функциях © К.Ю. Поляков, 2007-2009
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; } } int A[] параметр-массив размер массива
50 Массивы как параметры процедур Особенности: при описании параметра-массива в заголовке функции его размер не указывается (функция работает с массивами любого размера ) размер массива надо передавать как отдельный параметр в процедура передается адрес исходного массива: все изменения, сделанные в процедуре влияют на массив в основной программе Почему здесь размер не обязателен ? ?
51 Массивы в процедурах 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 Задания «4»: Написать процедуру, которая сортирует массив по возрастанию, и показать пример ее использования. «5»: Написать процедуру, которая ставит в начало массива все четные элементы, а конец – все нечетные.
53 Массивы в функциях Задача: составить функцию, которая находит сумму элементов массива. int Sum ( int A[], int N ) { int i, sum = 0 ; for ( i = 0; i < N; i ++ ) sum += A[i]; return sum ; } результат – целое число int A[] параметр-массив размер массива
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 ); // вторая половина ... }
55 Задания «4»: Написать функцию, которая находит максимальный элемент в массиве. «5»: Написать логическую функцию, которая определяет, верно ли, что среди элементов массива есть два одинаковых. Если ответ «да», функция возвращает 1; если ответ «нет», то 0. Подсказка : для отладки удобно использовать массив из 5 элементов, задаваемых вручную: const int N = 5; int A[N] = { 1, 2, 3, 3, 4 };
Тема 7. Практикум (моделирование) © К.Ю. Поляков, 2007-2009
57 Моделирование кипения воды Задача: Построить компьютерную модель кипения воды. Хранение данных: координаты (центров) пузырьков хранятся в массивах X и Y : X[i], Y[i] – координаты центра пузырька с номером i.
58 Структура программы #include <graphics.h> #include <conio.h> #include <stdlib.h> const int N = 100; int X[N], Y[N], r = 3; void Init (); // начальное положение void Draw ( int color ); // рисуем, стираем void Sdvig ( int dy ); // летят вверх void Zamena (); // ушли, пришли main () { init window ( 600, 400 ); ... // основная часть программы closegraph(); } ... // здесь сами процедуры глобальные константы и переменные объявления процедур
59 Основная программа Init(); // начальная расстановка while ( 1 ) // зацикливание ??? { Draw ( YELLOW ); // рисуем все пузырьки delay ( 10 ); // ждем 10 мс Draw ( BLACK ); // стираем все пузырьки Sdvig ( 4 ); // вверх на 4 пикселя Zamena(); // если за пределами экрана… } if ( kbhit() ) if ( getch() == 27 ) break; выход по Esc (код 27)
60 Процедура Init void Init() { int i; for ( i = 0; i < N; i ++ ) { X[i] = random(6 0 0 - 2*r) + r; Y[i] = random(4 0 0 - 2*r) + r; } } Начальная случайная расстановка: 6 0 0 r Интервал для x : [r, 600-r] 400 Интервал для y : [r, 400-r] X[ i ] = random (640 - 2* r ) + r ; Y[i] = random(4 0 0 - 2*r) + r;
61 Процедуры Draw, Sdvig Рисование и стирание: 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; }
62 Процедура Zamena Замена вышедших за границы экрана: 400 void Zamena () { int i; for ( i = 0; i < N; i ++ ) if ( Y[i] < r ) { X[i] = random(600 - 2*r) + r; Y[i] = 400 - r; } } Y[i]< r Y[i] = 400 - r Условие выхода: Перебросить вниз: if ( Y[i] < r ) {... } X [i] = random( 600 - 2*r) + r; Y[i] = 400 – r;
63 Задания «4»: Моделирование кипения воды в стакане (синий фон, рамка): «5»: Моделирование двустороннего потока: часть частиц двигаются влево, часть – вправо.
Тема 8. Символьные строки © К.Ю. Поляков, 2007-2009
65 Чем плох массив символов? char A[4] = { 'A', '3', '[', ' Ж '}; char B[10]; Это массивы символов: Для массива: каждый символ – отдельный объект; массив имеет длину N, которая задана при объявлении Что нужно: обрабатывать последовательность символов как единое целое строка должна иметь переменную длину
66 Символьные строки П р и в е т ! \0 ¤ ¤ … ¤ ¤ ¤ 0 79 рабочая часть s[0] s[1] s[2] s[3] char s[80]; признак окончания строки: символ с кодом 0 Символ '\0' имеет код 0 символ '0' имеет код 48 ! Символьная строка – это последовательность символов, которая заканчивается символом '\0'.
67 Объявление символьных строк Объявить строку = выделить ей место в памяти и присвоить имя. char s[80]; char s1[80] = "abc"; char qqq[] = " Вася "; выделяется 80 байт, в строке – «мусор» (если она глобальная, то нули '\0‘ ) выделяется 80 байт, занято 4 байта (с учетом '\0' ) выделяется 5 байт (с учетом '\0' ) При выделении памяти надо учитывать место для символа '\0'. В строку нельзя записывать больше символов, чем выделено памяти. !
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] %s – формат для ввода и вывода символьных строк (выводится только часть до '\0' "%s" пока не дошли до конца строки переход к следующему символу начали с q[0]
69 Ввод одного слова: Ввод строки с пробелами: char q[80]; printf (" Введите текст:\ n"); scanf ( "%s", q ); printf (" Введено:\ n%s", q ); Ввод символьных строк Введите текст: Вася пошел гулять Введено: Вася char q[80]; printf(" Введите текст:\ n"); gets ( q ); printf(" Введено:\ n%s", q ); Введите текст: Вася пошел гулять Введено: Вася пошел гулять gets ( q );
70 Универсальный способ: Только для одной строки: printf ( " Результат: %s", q ); Вывод символьных строк puts ( q ); можно выводить сразу и другую информацию: надписи, значения переменных, … вывод только одной строки после вывода – переход на новую строку printf ( "%s\n", q );
71 Задания «4»: Ввести символьную строку и заменить все буквы "а" на буквы "б" и наоборот, как заглавные, так и строчные. Пример: Введите строку: ааббссААББСС Результат: ббаассББААСС «5»: Ввести символьную строку и проверить, является ли она палиндромом (палиндром читается одинаково в обоих направлениях). Пример: Пример: Введите строку: Введите строку: АБВГДЕ КАЗАК Результат: Результат: Не палиндром. Палиндром.
72 Функции для работы со строками Длина строки : strlen ( string length ) Подключение библиотеки: #include <string.h> char q[80] = "qwerty"; int n; n = strlen ( q ); n = 6 При определении длины символ '\0' не учитывается! !
73 Сравнение строк char q1[80], q2[80]; int n; gets ( q1 ); gets ( q2 ); n = strcmp ( q1, q2 ); strcmp ( string comparison ) : q1 q2 n "AA" "AA" 0 "AB" "AA" 1 "AA" "AB" – 1 "AA" "A" 65 Функция вычисляет разность между кодами первых двух отличающихся символов! !
74 Пример решения задачи Задача: ввести строку и определить, сколько в ней слов. Программа должна работать только при вводе правильного пароля. Идея решения: проверка пароля – через strcmp количество слов = количеству первых букв слова первая буква: пробел и за ним «не пробел» исключение: предложение начинается со слова (а не с пробела) В а с я п о ш е л г у л я т ь \0 ¤ ¤ ¤ ¤ ¤
75 Проверка пароля #include <string.h> main() { char secret[] = "123", pass[20]; printf ( " Введите пароль \n" ); gets ( pass ); if ( strcmp ( pass, secret ) != 0 ) { printf ( " Пароль неверный " ); getch (); return 1; } ... } если пароль неверный... сообщить об ошибке и выйти из программы аварийное завершение, код ошибки 1
76 Основная часть программы #include <stdio.h> #include <string.h> main() { char q[80]; i n t 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 Подсказка: для вывода одного символа используйте функцию putchar ( символ ). Например: Задания (везде – с паролем!) «4»: Ввести предложение и определить, сколько слов заканчиваются на букву ' а '. Пример: Введите предложение: Введите предложение: Мама мыла раму Декан пропил бутан Найдено слов: 2 Нет таких слов «5»: Ввести предложение и разобрать его на отдельные слова: Пример: Введите предложение: Мама мыла раму Результат: Мама мыла раму putchar(q[i]); putchar('\n'); // переход на новую строку
78 Копирование строк strcpy ( string copy ) char q1[10] = "qwerty", q2[ 1 0] = "01234"; strcpy ( q1, q2 ); куда откуда Старое значение q1 стирается! ! копирование «хвоста» строки char q1[10] = "qwerty", q2[ 1 0] = "01234"; strcpy ( q1, q2 +2 ); q w e r t y \0 ¤ ¤ ¤ 0 1 2 3 4 \0 ¤ ¤ ¤ ¤ q2 q1 q2 = &q2[0] q2+2 = &q2[2] 2 3 4 \0
79 Копирование строк копирование в середину строки char q1[10] = "qwerty", q2[ 1 0] = "01234"; strcpy ( q1 +2, q2 ); q w e r t y \0 ¤ ¤ ¤ 0 1 2 3 4 \0 ¤ ¤ ¤ ¤ q2 q1 q1+2 = &q1[2] 0 1 2 3 4 \0 char q1[10] = "qwerty", q2[ 1 0] = "01234"; strcpy ( q1 +2, q2 +3 ); q w e r t y \0 ¤ ¤ ¤ 0 1 2 3 4 \0 ¤ ¤ ¤ ¤ q2 q1 3 4 \0 q2+ 3 = &q2[ 3 ] q 1 + 2 = &q 1 [ 2 ]
80 Копирование строк str n cpy – копирование нескольких символов char q1[10] = "qwerty", q2[ 1 0] = "01234"; str n cpy ( q1 +2, q2, 2 ); q w e r t y \0 ¤ ¤ ¤ 0 1 2 3 4 \0 ¤ ¤ ¤ ¤ q2 q1 q1+2 = &q1[2] 0 1 Функция str n cpy не добавляет символ '\0' в конце строки! !
81 Копирование строк копирование строки-константы char q1[10] = "qwerty"; strcpy ( q1 + 1, "ABCD"); q w e r t y \0 ¤ ¤ ¤ A B C D \0 q1 A B C D \0 char q1[10] = "qwerty"; strcpy ( "ABCD", q1 +2 ); Первым параметром может быть константа! ! НЕ
82 Копирование строк копирование внутри одной строки char q[10] = "012345"; strcpy ( q, q+2 ); 0 1 2 3 4 5 \0 ¤ ¤ ¤ q 2 3 4 5 \0 char q[10] = "012345"; strcpy ( q+2, q ); 0 1 2 3 4 5 \0 ¤ ¤ ¤ q 0 1 0 1 0 1 Зацикливание и зависание компьютера!
83 Объединение строк strcat ( string concatenation ) = копирование второй строки в конец первой char q1[10] = "qwe", q2[ 1 0] = "0123"; strcat ( q1, q2 ); q w e \0 ¤ ¤ ¤ ¤ ¤ ¤ 0 1 2 3 \0 ¤ ¤ ¤ ¤ ¤ q2 q1 0 1 2 3 \0 char q1[10] = "qwe", q2[ 1 0] = "0123"; strcat ( q1, q2+2 ); q w e \0 ¤ ¤ ¤ ¤ ¤ ¤ 0 1 2 3 \0 ¤ ¤ ¤ ¤ ¤ q2 q1 2 3 \0
84 что-то другое Проблемы при копировании строк Транслятор не сообщает об этих ошибках! ! char q1[] = "qwer", q2[ 1 0] = "01234"; strcpy ( q1 +2, q2 ); не хватает места для строки-результата q w e r \0 0 1 2 3 \0 ¤ ¤ ¤ ¤ ¤ q2 q1 0 1 2 3 \0 зацикливание при копировании в ту же строку «слева направо» char q[ 10 ] = "01234"; strcpy ( q +2, q );
85 Пример решения задачи Задача : ввести имя файла (без пути) и поменять его расширение на ".exe". Пример: Введите имя файла: Введите имя файла: vasya.html vasya Результат: Результат: vasya.exe vasya.exe Алгоритм: найти точку в имени файла если она есть, скопировать в это место строку-константу ".exe " если точки нет, добавить в конец строки ".exe "
86 Программа main () { char fName [80]; int i ; printf("Введите имя файла \n "); g ets ( fName ); i = 0; while ( fName [ i ] != '.' ) { if ( fName [ i ] = = '\0' ) break; i ++; } if ( fName [ i ] == '.' ) strcpy ( fName + i, ".exe " ); else strcat ( fName, ".exe " ); p uts ( "Результат:" ); puts ( fName ); } поиск точки дошли до конца строки меняем или добавляем расширение
87 Задания «4»: Ввести полный адрес файла (возможно, без расширения) и изменить его расширение на «.exe ». Пример: Введите имя файла: Введите имя файла: C:\DOC.TXT\qqq C:\DOC.TXT\qqq.com Результат: Результат: C:\DOC.TXT\qqq.exe C:\DOC.TXT\qqq.exe «5»: Ввести в одной строке фамилию, имя и отчество. Вывести приветствие, где останутся имя и фамилия (см. пример). Пример: Введите ФИО: Пупкин Василий Иванович Результат: Привет, Василий Пупкин!
88 Поиск в символьных строках Задача : найти заданный символ или сочетание символов ( подстроку ) в символьной строке. Функции поиска в Си возвращают адрес найденного символа или подстроки! Если образец не найден, возвращается NULL ( нулевой адрес ). ! Указатель – это переменная в которую можно записать адрес другой переменной заданного типа.
89 Указатели 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); Адрес: 6 BCD:000C, значение 3 pointer – указатель
90 Указатели и символьные строки char str[10] = "0123456"; 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 Поиск символа strchr : найти первый заданный символ c начала строки str r chr : найти последний заданный символ в строке char q[10] = "abcdabcd"; char *p; int nomer; p = strchr(q, 'b'); if ( p == NULL ) printf ( " Не нашли... " ); else { nomer = p – q; printf ( " Номер символа %d", nomer ); } a b c d a b c d \0 ¤ 0 1 2 3 4 5 6 7 8 9 q q+1 q+5 p reverse
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 ); } a b c d a b c d \0 ¤ 0 1 2 3 4 5 6 7 8 9 q q+1 q+5 p
93 Пример решения задачи Задача: ввести предложение и определить, сколько раз в нем встречается имя «Вася». Проблема: функция strstr ищет только с начала строки. Алгоритм: Записать адрес начала строки в указатель start. Искать подстроку «Вася», начиная с адреса start. Если не нашли, выход из цикла. Увеличить счетчик найденных слов. Переставить start на адрес после найденного слова. Перейти к шагу 2. В а с я и В а с я В а с я ! ! ! \0 start p p = strstr( start, " Вася ");
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 Задания «4»: Ввести предложение и заменить все имена «Вася» на «Юра». Пример: Введите предложение: Вася, Вася, Вася и Вася!!! Результат: Юра, Юра, Юра и Юра!!! «5»: Ввести предложение и заменить все имена «Юра» на «Вася». Пример: Введите предложение: Юра, Юра, Юра и Юра!!! Результат: Вася, Вася, Вася и Вася!!!
96 Строки в процедурах и функциях строки передаются в функции и процедуры так же, как и массивы; функции и процедуры могут изменять строки –параметры. ! Задача: составить процедуру, которая переставляет символы строки в обратном порядке. Алгоритм: определить длину строки len; все символы первой половины переставить с соответствующими символами второй половины: c = s[i]; s[i] = s[len-i-1]; s[len-1-i] = c; s[i] s[len-1-i]
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[] = "1234567890"; Reverse ( s ); puts ( s ); Reverse ( s + 5 ); puts ( s ); } 0987654321 0987612345 Как сделать инверсию любой части строки? ? длину строки определяем на месте
98 Задания «4»: Разработать процедуру, которая переставляет пары соседних символов. Пример: Введите предложение: Вася пошел гулять! Результат: аВясп шолег лутя!ь «5»: Разработать процедуру, которая удаляет все лишние пробелы (в начале предложения и сдвоенные пробелы). Пример: Введите предложение: Вася пошел гулять! Результат: Вася пошел гулять!
99 Символьные строки в функциях Задача: составить функцию, которая находит количество цифр в строке. int NumDigits ( char s[] ) { int i, count = 0; for ( i = 0; i < strlen(s); i ++ ) if( strchr ( "0123456789", s[i] ) ) count ++; return count; } if ( strchr ( "0123456789", s[i] ) != NULL ) или if ( '0' <= s[i] && s[i] <= '9' )
100 Символьные строки в функциях Основная программа int NumDigits ( char s[] ) { ... } main() { char s[80]; int n; printf ( " Введите строку \n" ); gets ( s ); n = NumDigits ( s ); printf ( " Нашли %d цифр.", s ); }
101 Задания «4»: Разработать функцию, которая определяет, верно ли, что слово – палиндром. Пример: Введите слово: Введите слово: казак кунак Результат: Результат: Это палиндром. Не палиндром. «5»: Разработать функцию, которая определяет, верно ли, что предложение (с пробелами) – палиндром. Пример: Введите предложение: а роза упала на лапу азора Результат: Это палиндром.
Тема 9. Рекурсивный перебор © К.Ю. Поляков, 2007-2009
103 Рекурсивный перебор Задача: Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ и О. Вывести на экран все слова из К букв, которые можно составить в этом языке, и подсчитать их количество. Число K вводится с клавиатуры. 0 K-1 в каждой ячейке может быть любая из 4-х букв 4 варианта 4 варианта 4 варианта 4 варианта Количество вариантов:
104 Рекурсивный перебор Ы 0 K-1 Рекурсия: Решения задачи для слов из К букв сводится к 4-м задачам для слов из K -1 букв. Щ 0 K-1 О 0 K-1 Ц 0 K-1 перебрать все варианты перебрать все варианты перебрать все варианты перебрать все варианты
105 Процедура ● ● ● ? ? ? ? 0 K-1 p Глобальные переменные: 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 символов уже на своих местах
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 ); } все буквы цикл по всем буквам локальная переменная
107 Программа char s [80] ; int K, count = 0 ; main() { printf ( " Введите длину слов: \n" ); scanf ( "%d", &K ); Rec ( 0 ); printf ( " Всего %d слов.", count ); } void Rec ( int p ) { ... } процедура глобальные переменные ( обнуляются ) count; Как определяется конец строки ? Как обойтись без глобальных переменных? ?
108 Задания Алфавит языка племени "тумба-юмба" состоит из букв Ы, Ц, Щ и О. Число K вводится с клавиатуры. «4»: Вывести на экран все слова из К букв, в которых буква Ы встречается более 1 раза, и подсчитать их количество. «5»: Вывести на экран все слова из К букв, в которых есть одинаковые буквы, стоящие рядом (например, ЫЩЩО ), и подсчитать их количество. Без глобальных переменных! !
Тема 10. Матрицы © К.Ю. Поляков, 2007-2009
110 Матрицы Задача: запомнить положение фигур на шахматной доске. 1 2 3 4 5 6 a b c d e f g h 8 7 6 5 4 3 2 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 c6 A[ 5 ][ 2 ]
111 Матрицы Матрица – это прямоугольная таблица однотипных элементов. Матрица – это массив, в котором каждый элемент имеет два индекса (номер строки и номер столбца). 1 4 7 3 6 2 -5 0 15 1 0 8 9 11 12 20 0 1 2 0 1 2 3 4 A 7 0 11 2 -5 0 15 1 0 1 2 строка 1 столбец 2 ячейка A[ 2 ][ 3 ]
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' }; Ввод с клавиатуры: 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 j for ( j = 0; j < M; j ++ ) for ( i = 0; i < N; i ++ ) {
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 ++ ) printf("%5d", A[i,j]); printf("\n"); } перейти на новую строку for ( j = 0; j < M; j ++ ) printf("%5d", A[i][j]); вывод строки 12 25 1 13 156 1 12 447 1 456 222 23 Если переставить циклы ? ? в той же строке
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); } for ( i = 0; i < N; i ++ ) for ( j = 0; j < M; j ++ ) S += A[i][j];
115 Задания Заполнить матрицу из 8 строк и 5 столбцов случайными числами в интервале [-10,10] и вывести ее на экран. «4»: Найти минимальный и максимальный элементы в матрице их номера. Формат вывода: Минимальный элемент A[3][4]=-6 Максимальный элемент A[ 2 ][ 2 ]= 10 «5»: Вывести на экран строку, сумма элементов которой максимальна. Формат вывода: Строка 2: 3 5 8 9 8
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] ); Задача 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 ]); N-1-i
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 <= i; j ++ ) S += A[i][j]; цикл по всем строкам for ( j = 0; j <= i; j ++ ) S += A[i][j]; складываем нужные элементы строки i
118 Операции с матрицами Задача 4. Перестановка строк или столбцов. В матрице из N строк и M столбцов переставить 1 -ую и 3 -ю строки. 1 2 5 2 1 7 3 1 3 7 1 3 j A[1][j] A[3][j] for ( j = 0; j <= M; j ++ ) { c = A[1][j]; A[1][j] = A[3][j]; A[3][j] = c; } Задача 5. К третьему столбцу добавить шестой. for ( i = 0; i < N; i ++ ) A[i][3] += A[i][6];
119 Задания Заполнить матрицу из 7 строк и 7 столбцов случайными числами в интервале [-10,10] и вывести ее на экран. Обнулить элементы, отмеченные зеленым фоном, и вывести полученную матрицу на экран. «4»: «5»:
Тема 11. Файлы © К.Ю. Поляков, 2007-2009
121 Файлы Файл – это область на диске, имеющая имя. Файлы только текст без оформления, не содержат управляющих символов (с кодами < 32), кроме перевода строки ACSII (1 байт на символ) UNICODE ( 2 байта на символ) *.txt, *.log, *.htm, *.html могут содержать любые символы кодовой таблицы *.doc, *.exe, *.bmp, *.jpg, *.wav, *.mp3, *.avi, *.mpg Текстовые Двоичные Папки (каталоги)
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 Работа с файлами Особенности: имя файла упоминается только в команде fopen, обращение к файлу идет через указатель f ; файл, который открывается на чтение, должен существовать если файл, который открывается на запись, существует, старое содержимое уничтожается данные ( этим способом ) записываются в файл в текстовом виде когда программа заканчивает работу, все файлы закрываются автоматически после закрытия файла переменную f можно использовать еще раз для работы с другим файлом
124 Последовательный доступ при открытии файла курсор устанавливается в начало чтение выполняется с той позиции, где стоит курсор после чтения курсор сдвигается на первый непрочитанный символ 12 5 45 67 56 ● конец файла ( end of file, EOF ) 12 5 45 67 56 ● f = fopen("qq.dat", "r"); fscanf ( f, "%d", &x ); Как вернуться назад ? ?
125 Ошибки при открытии файла 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; } NULL неверное имя файла файл «только для чтения» файл заблокирован другой программой
126 Пример Задача: в файле input.txt записаны числа ( в столбик ), сколько их – неизвестно. Записать в файл output.txt их сумму. Алгоритм: Открыть файл input.txt для чтения. S = 0; Прочитать очередное число в переменную x. Если не удалось, перейти к шагу 7. S + = x; Перейти к шагу 3. Закрыть файл input.txt. Открыть файл output.txt для записи. Записать в файл значение S. Закрыть файл output.txt. Можно ли обойтись без массива ? ? цикл с условием « пока есть данные»
127 Как определить, что числа кончились? FILE *f; int n, x; f = fopen("input.txt", "r") ; ... n = fscanf ( f, "%d", &x ); if ( n ! = 1 ) puts ( " Не удалось прочитать число " ); Функция fscanf возвращает количество удачно прочитанных чисел ; 0, если была ошибка при чтении; – 1, если достигли конца файла. ! дошли до конца файла встретили «не число»
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 Задания В файле input.txt записаны числа, сколько их – неизвестно. «4»: Найти среднее арифметическое всех чисел и записать его в файл output.txt. «5»: Найти минимальное и максимальное числа и записать их в файл output.txt.
130 Обработка массивов Задача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно, но не более 100. Переставить их в порядке возрастания и записать в файл output.txt. Проблемы: для сортировки надо удерживать в памяти все числа сразу (массив); сколько чисел – неизвестно. Решение: выделяем в памяти массив из 100 элементов; записываем прочитанные числа в массив и считаем их в переменной N ; сортируем первые N элементов массива; записываем их в файл. Можно ли обойтись без массива ? ?
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 ): массив заканчиваем цикл если не удалось прочитать … имя файла предел … или заполнили весь массив
132 Программа main() { int A[100], N, i; FILE *f; N = ReadArray ( A, "input.txt", 100 ) ; ... // сортировка первых N элементов f = fopen ( " output. tx t ", "w" ); for ( i = 0; i < N; i ++) fprintf ( f, "%d\n", A[i] ); f close ( f ); } int ReadArray (int A[], char fName[], int MAX) { ... } вывод отсортированного массива в файл
133 Задания В файле input.txt записаны числа (в столбик), известно, что их не более 100. «4»: Отсортировать массив по убыванию последней цифры и записать его в файл output.txt. «5»: Отсортировать массив по возрастанию суммы цифр и записать его в файл output.txt.
134 Обработка текстовых данных Задача: в файле input.txt записаны строки, в которых есть слово-паразит " короче ". Очистить текст от мусора и записать в файл output.txt. Файл input.txt : Мама, короче, мыла, короче, раму. Декан, короче, пропил, короче, бутан. А роза, короче, упала на лапу, короче, Азора. Каждый, короче, охотник желает, короче, знать, где... Результат – файл output.txt : Мама мыла раму. Декан пропил бутан. А роза упала на лапу Азора. Каждый охотник желает знать, где сидит фазан.
135 Обработка текстовых данных Особенность: надо одновременно держать открытыми два файла (один в режиме чтения, второй – в режиме записи). Алгоритм: Открыть оба файла. Прочитать строку. Удалить все сочетания ", короче, ". Записать строку во второй файл. Перейти к шагу 2. Закрыть оба файла. пока не кончились данные
136 Работа с файлами main() { char s[80], *p; int i; FILE * fIn, * fOut; fIn = fopen(" in put.txt ", "r" ); f Out = fopen("output.txt ", "w" ); ... // обработать файл f close(fIn); f close(fOut); } файловые указатели открыть файл для чтения открыть файл для записи указатель для поиска закрыть файлы
137 Обработка текстовых данных Чтение строки s : 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); Обработка строки s : строка длина файл
138 #include <string.h> Полный цикл обработки файла 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 Задания В файле input.txt записаны строки, сколько их – неизвестно. «4»: Заменить во всем тексте «в общем» на «короче» и записать результат в файл output.txt. «5»: Заменить во всем тексте «короче» на «в общем» и записать результат в файл output.txt.
140 Двоичные файлы Особенности: данные хранятся во внутреннем машинном формате (в текстовом редакторе не прочитать) можно читать и записывать любой кусок памяти (просто биты…) принцип сэндвича (открыть – работать – закрыть) обращение к файлу через указатель Файловые указатели FILE *fp;
141 Открытие и закрытие двоичных файлов Открытие файла fp = fopen ( "input.dat", "rb" ); "rb" = read binary ( чтение) "wb" = write binary ( запись) "ab" = append binary ( добавление) Ошибки при открытии if ( fp == NULL ) { printf(" Файл открыть не удалось. "); } Закрытие файла fclose ( fp );
142 Чтение по блокам Чтение в начало массива int A[100]; n = fread ( A, sizeof(int), 100, fp ); адрес области памяти («куда»): A &A[0] размер одного блока размер переменной целого типа количество блоков указатель на файл прочитано фактически Чтение в середину массива int A[100]; n = fread ( A +5, sizeof(int), 2, fp ); читается 2 целых числа: A[ 5 ], A[ 6 ]
143 Запись по блокам Запись с начала массива int A[100]; n = fwrite( A, sizeof(int), 100, fp ); адрес области памяти («откуда»): A &A[0] размер одного блока размер переменной целого типа количество блоков указатель на файл записано фактически Запись отдельных элементов массива int A[100]; n = fwrite( A +5, sizeof(int), 2, fp ); записывается 2 целых числа: A[ 5 ], A[ 6 ]
144 Работа с матрицами Хранение в памяти: по строкам (Си, Паскаль) 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 Запись матрицы int A[ 3 ][3]; FILE *fp = fopen("output.dat", "wb"); ... // здесь заполняем матрицу n = fwrite( A, sizeof(int), 9, fp );
145 Пример Задача: прочитать массив из файла input.dat, умножить все элементы на 2 и вывести в файл output.dat. Структура программы: #include <stdio.h> 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 Работа с файлами 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 ); Запись данных: критическая ошибка некритическая ошибка сколько прочитали
147 Задания «4»: В текстовом файле input.txt записан массив целых чисел. Отсортировать его и записать в двоичный файл output.dat. «5»: В текстовых файлах input 1.txt и input 2.txt записаны два массива. Объединить их в один массив, отсортировать и записать результат в двоичный файл output.dat.
148 Конец фильма
