Цикл do...while
Цикл do...while имеет вид
do действие; while (условие);
Действие лучше всегда обрамлять фигурными скобками, даже когда оно состоит только из одного оператора, например,
do { x *= 2; } while (x < n);
Цикл do...while является циклом с постусловием. Сначала выполняется тело цикла и только после этого проверяется условие продолжения цикла. Если условие истинно, то тело цикла повторяется, и так до бесконечности, пока условие не станет ложным. Таким образом, тело цикла выполняется всегда, даже если условие ложно с самого начала. Это является потенциальным источником ошибок. Лучше всегда использовать цикл с предусловием while (прежде чем прыгнуть, лучше сначала посмотреть, куда прыгаешь!).
Приведем пример ошибочного использования цикла do...while. Пусть переменная n содержит целое положительное число. Надо записать в целочисленную переменную p максимальную степень двойки, не превосходящую n. Ранее этот фрагмент уже был реализован с помощью цикла while (раздел 3.5.5):
int n, p; . . . p = 1; while (2*p <= n) { p *= 2; }
Попытка использовать цикл do...while может привести к ошибке:
int n, p; . . . p = 1; do { p *= 2; } while (2*p <= n);
Программа работает неверно при n = 1 (в переменную p записывается двойка вместо единицы), поскольку тело цикла do...while всегда выполняется один раз независимо от истинности условия, которое проверяется лишь после выполнения тела цикла. Такого рода ошибки в "крайних" ситуациях наиболее опасны в программировании: программа правильно работает почти во всех ситуациях, кроме нескольких исключений. Но известно, что большинство катастроф происходит как раз в результате исключительного стечения обстоятельств!
Цикл for
Популярный в других языках программирования арифметический цикл (см. с. 41) в языке Си реализуется с помощью цикла for. Он выглядит следующим образом:
for (инициализация; условие продолжения; итератор) тело цикла;
Инициализация выполняется один раз перед первой проверкой условия продолжения и первым выполнением тела цикла. Условие продолжения проверяется перед каждым выполнением тела цикла. Если условие истинно, то выполняется тело цикла, иначе цикл завершается. Итератор выполняется после каждого выполнения тела цикла (перед следующей проверкой условия продолжения).
Поскольку условие продолжения проверяется перед выполнением тела цикла, цикл for является, подобно циклу while, циклом с предусловием. Если условие продолжения не выполняется изначально, то тело цикла не выполняется ни разу, а это хорошо как с точки зрения надежности программы, так и с точки зрения простоты и эстетики (поскольку не нужно отдельно рассматривать исключительные случаи).
Рассмотрим пример суммирования массива с использованием цикла for:
double a[100]; // Массив a содержит не более 100 эл-тов int n; // Реальная длина массива a (n <= 100) double sum; // Переменная для суммы эл-тов массива int i; // Переменная цикла . . . sum = 0.0; for (i = 0; i < n; ++i) { sum += a[i]; // Увеличиваем сумму на a[i] }
Здесь целочисленная переменная i используется в качестве переменной цикла. В операторе инициализации переменной i присваивается значение 0. Условием продолжения цикла является условие i<n. Итератор ++i увеличивает переменную i на единицу. Таким образом, переменная i последовательно принимает значения 0, 1, 2,..., n-1. Для каждого значения i выполняется тело цикла.
В большинстве других языков программирования арифметический цикл жестко связан с использованием переменной цикла, которая должна принимать значения из арифметической прогрессии. В Си это не так, здесь инициализация, условие продолжения и итератор могут быть произвольными выражениями, что обеспечивает гораздо большую гибкость программы.
Конструкцию цикла for можно реализовать с помощью цикла while:
for ( инициализация; инициализация; условие; while (условие) { итератор ~ тело цикла; ) { итератор; тело цикла; } }
Например, фрагмент с суммированием массива реализуется с использованием цикла while следующим образом:
i = 0; for (i=0; i < n; ++i) { while (i < n) { sum += a[i]; ~ sum += a[i]; } ++i; }
В принципе, конструкция цикла for не нужна: она реализуется с помощью цикла while, он проще и понятнее. Однако большинство программистов продолжают использовать цикл for. Связано это, скорее всего, с традицией и привычками, поскольку в более ранних языках программирования, например, в первых версиях Фортрана, арифметический цикл был основным, а цикл while приходилось реализовывать с помощью операторов if и goto.
Цикл while
Конструкция цикла "пока" соответствует циклу while в Си:
while (условие) действие;
Цикл while называют циклом с предусловием, поскольку условие проверяется перед выполнением тела цикла.
Цикл while выполняется следующим образом: сначала проверяется условие. Если оно истинно, то выполняется действие. Затем снова проверяется условие; если оно истинно, то снова повторяется действие, и так до бесконечности. Цикл завершается, когда условие становится ложным. Пример:
int n, p; . . . p = 1; while (2*p <= n) p *= 2;
В результате выполнения этого фрагмента в переменной p будет вычислена максимальная степень двойки, не превосходящая целого положительного числа n.
Если условие ложно с самого начала, то действие не выполняется ни разу. Это очень облегчает программирование и делает программу более надежной, поскольку исключительные ситуации автоматически правильно обрабатываются. Так, приведенный выше фрагмент работает корректно при n = 1 (цикл не выполняется ни разу).
При ошибке программирования цикл может никогда не кончиться. Чтобы избежать этого, следует составлять программу таким образом, чтобы некоторая ограниченная величина, от которой прямо или косвенно зависит условие в заголовке цикла, монотонно убывала или возрастала после каждого выполнения тела цикла. Это обеспечивает завершение цикла. В приведенном выше фрагменте такой величиной является значение p, которое возрастает вдвое после каждого выполнения тела цикла.
Тело цикла может состоять из одного или нескольких операторов. В последнем случае их надо заключить в фигурные скобки. Советуем заключать тело цикла в фигурные скобки даже в том случае, когда оно состоит всего из одного оператора, - это делает текст программы более наглядным и облегчает его возможную модификацию. Например, приведенный выше фрагмент лучше было бы записать так:
int n, p; . . . p = 1; while (2*p <= n) { p *= 2; }
Сознательное применение цикла "пока" всегда связано с явной формулировкой инварианта цикла, см. раздел 1.5.2.
Рассмотрим построение цикла "пока" на примере программы вычисления квадратного корня методом деления отрезка пополам.
Динамическая память, или куча
Помимо статической и стековой памяти, существует еще практически неограниченный ресурс памяти, которая называется динамическая, или куча (heap). Программа может захватывать участки динамической памяти нужного размера. После использования ранее захваченный участок динамической памяти следует освободить.
Под динамическую память отводится пространство виртуальной памяти процесса между статической памятью и стеком. (Механизм виртуальной памяти был рассмотрен в разделе 2.6.) Обычно стек располагается в старших адресах виртуальной памяти и растет в сторону уменьшения адресов (см. раздел 2.3). Программа и константные данные размещаются в младших адресах, выше располагаются статические переменные. Пространство выше статических переменных и ниже стека занимает динамическая память:
|
0 4 8 |
код программы и данные, защищенные от изменения | ||
| ... |
статические переменные программы | ||
| динамическая память | |||
|
max. адрес (232-4) | стек ^ |
Структура динамической памяти автоматически поддерживается исполняющей системой языка Си или C++. Динамическая память состоит из захваченных и свободных сегментов, каждому из которых предшествует описатель сегмента. При выполнении запроса на захват памяти исполняющая система производит поиск свободного сегмента достаточного размера и захватывает в нем отрезок требуемой длины. При освобождении сегмента памяти он помечается как свободный, при необходимости несколько подряд идущих свободных сегментов объединяются.
В языке Си для захвата и освобождения динамической памяти применяются стандартные функции malloc и free, описания их прототипов содержатся в стандартном заголовочном файле "stdlib.h". (Имя malloc является сокращением от memory allocate - "захват памяти".) Прототипы этих функций выглядят следующим образом:
void *malloc(size_t n); // Захватить участок памяти // размером в n байт void free(void *p); // Освободить участок // памяти с адресом p
Здесь n - это размер захватываемого участка в байтах, size_t - имя одного из целочисленных типов, определяющих максимальный размер захватываемого участка.
Тип size_t задается в стандартном заголовочном файле "stdlib.h" с помощью оператора typedef (см. c. 117). Это обеспечивает независимость текста Си-программы от используемой архитектуры. В 32- разрядной архитектуре тип size_t определяется как беззнаковое целое число:
typedef unsigned int size_t;
Функция malloc возвращает адрес захваченного участка памяти или ноль в случае неудачи (когда нет свободного участка достаточно большого размера). Функция free освобождает участок памяти с заданным адресом. Для задания адреса используется указатель общего типа void*. После вызова функции malloc его необходимо привести к указателю на конкретный тип, используя операцию приведения типа, см. раздел 3.4.11. Например, в следующем примере захватывается участок динамической памяти размером в 4000 байтов, его адрес присваивается указателю на массив из 1000 целых чисел:
int *a; // Указатель на массив целых чисел . . . a = (int *) malloc(1000 * sizeof(int));
Выражение в аргументе функции malloc равно 4000, поскольку размер целого числа sizeof(int) равен четырем байтам. Для преобразования указателя используется операция приведения типа (int *) от указателя обобщенного типа к указателю на целое число.
Фигурные скобки
Фигурные скобки позволяют объединить несколько элементарных операторов в один составной оператор, или блок. Во всех синтаксических конструкциях составной оператор можно использовать вместо простого.
В Си в начало блока можно помещать описания локальных переменных. Локальные переменные, описанные внутри блока, создаются при входе в блок и уничтожаются при выходе из него.
В C++ локальные переменные можно описывать где угодно, а не только в начале блока. Тем не менее, они, так же как и в Си, автоматически уничтожаются при выходе из блока.
Приведем фрагмент программы, обменивающий значения двух вещественных переменных:
double x, y; . . . { double tmp = x; x = y; y = tmp; }
Здесь, чтобы обменять значения двух переменных x и y, мы сначала запоминаем значение x во вспомогательной переменной tmp. Затем в x записывается значение y, а в y - сохраненное в tmp предыдущее значение x. Поскольку переменная tmp нужна только внутри этого фрагмента, мы заключили его в блок и описали переменную tmp внутри этого блока. По выходу из блока память, занятая переменной tmp, будет освобождена.
Конструкции, которые лучше не использовать
В программировании предпочтительнее избегать решений эстетически красивых, но не очень понятных. На первый план в последнее время вышло требование надежности программы, поэтому из нескольких решений лучше выбирать более простое, по возможности сводящее к минимуму вероятность ошибок. Это предполагает также некоторое самоограничение свободы программиста.
Перечисленные ниже конструкции существуют в языке Си начиная с самых ранних версий. Тем не менее, без них можно обойтись, заменяя их другими конструкциями, которые потенциально более надежны.
Операция "запятая" и цикл for
В цикле for
for (инициализация; условие продолжения; итератор) тело цикла;
в качестве инициализации и итератора можно использовать любые выражения, в частности, операцию присваивания = и операцию увеличения значения переменной на единицу ++. Как быть, если необходимо выполнить несколько действий при инициализации или в итераторе? Можно, конечно, использовать цикл while, но любители цикла for поступают другим образом. Для этого язык Си предоставляет операцию "запятая", которая позволяет объединить несколько выражений в одно. У операции "запятая" два аргумента, которые вычисляются последовательно слева направо. Результатом операции является последнее вычисленное, т.е. правое, значение. Пример:
int x, y, z; x = 5; z = (y = x + 10, ++x); // y = 15, x = 6, z = 6
Здесь при вычислении выражения в скобках сначала вычисляется первое подвыражение y = x+10, в результате которого в y записывается значение 15, значение первого подвыражения также равно 15. Затем вычисляется стоящее после запятой второе подвыражение ++x, в результате чего значение x увеличивается и становится равным 6, значение второго подвыражения также равно 6. Значением операции "запятая" является значение второго подвыражения, т.е. 6. В результате значение 6 присваивается переменной z.
Наличие операции "запятая" отражает эстетскую сторону первоначального варианта языка Cи 70-х годов XX века: в нем почти любая запись имела какой-то смысл. Позже программисты пришли к пониманию того, что надежность программы важнее краткости и изящества, и приняли более строгий ANSI-стандарт языка Си 1989 г., который несколько ограничил свободу творчества в области Си-программ.
Тем не менее, операцию "запятая" по-прежнему можно использовать в заголовке цикла for, когда нужно выполнить несколько действий при инициализации или в итераторе. Например, фрагмент суммирования массива
sum = 0.0; for (i = 0; i < n; ++i) { sum += a[i]; }
можно переписать следующим "эстетским" образом:
for (sum = 0.0, i = 0; i < n; sum += a[i], ++i);
Здесь тело цикла вообще пустое, все действия вынесены в заголовок цикла! Лучше избегать такого стиля программирования: он ничего не добавляет в смысле эффективности готовой программы, но делает текст менее понятным и, таким образом, увеличивает вероятность ошибок.
Оператор if
Оператор if ("если") позволяет организовать ветвление в программе. Он имеет две формы: оператор "если" и оператор "если...иначе". Оператор "если" имеет вид
if (условие) действие;
оператор "если...иначе" имеет вид
if (условие) действие1; else действие2;
В качестве условия можно использовать любое выражение логического или целого типа. Напомним, что при использовании целочисленного выражения значению "истина" соответствует любое ненулевое значение. При выполнении оператора "если" сначала вычисляется условное выражение после if. Если оно истинно, то выполняется действие, если ложно, то ничего не происходит. Например, в следующем фрагменте в переменную m записывается максимальное из значений переменных x и y:
double x, y, m; . . . m = x; if (y > x) m = y;
При выполнении оператора "если...иначе" в случае, когда условие истинно, выполняется действие, записанное после if; в противном случае выполняется действие после else. Например, предыдущий фрагмент переписывается следующим образом:
double x, y, m; . . . if (x > y) m = x; else m = y;
Когда надо выполнить несколько действий в зависимости от истинности условия, следует использовать фигурные скобки, объединяя несколько операторов в блок, например,
double x, y, d; . . . if (d > 1.0) { x /= d; y /= d; }
Здесь переменные x и y делятся на d только в том случае, когда значение d больше единицы.
Фигурные скобки можно использовать даже, когда после if или else стоит только один оператор. Они улучшают структуру текста программы и облегчают ее возможную модификацию. Пример:
double x, y; . . . if (x != 0.0) { y = 1.0; }
Если нужно будет добавить еще одно действие, выполняемое при условии "x отлично от нуля", то мы просто добавим строку внутри фигурных скобок.
Оператор перехода на метку goto
Оператор перехода goto позволяет изменить естественный порядок выполнения программы и осуществить переход на другой участок программы, обозначенный меткой. Переход может осуществляться только внутри функции, т.е. оператор goto не может ни выйти из функции, ни войти внутрь другой функции. Оператор goto выглядит следующим образом:
L: ...; . . . goto L;
В качестве метки можно использовать любое имя, допустимое в Си (т.е. последовательность букв, цифр и знаков подчеркивания "_", начинающуюся не с цифры). Метка может стоять до или после оператора goto. Метка выделяется символом двоеточия ":". Лучше после него сразу ставить точку с запятой ";", помечая таким образом пустой оператор - это общепринятая программистская практика, согласно которой метки ставятся между операторами, а не на операторах.
Не следует увлекаться использованием оператора goto - это всегда запутывает программу. Большинство программистов считают применение оператора goto дурным стилем программирования. Вместо goto при необходимости можно использовать операторы выхода из цикла break и пропуска итерации цикла continue (см. раздел 3.5.7). Единственная ситуация, в которой использование goto оправдано, - это выход из нескольких вложенных друг в друга циклов:
while (...) { . . . while (...) { . . . if (...) { goto LExit; // Выход из двух // вложенных циклов } . . . } } LExit: ;
В объектно-ориентированном языке Java, синтаксис которого построен на основе языка Си, использование оператора goto запрещено. Вместо него для выхода из нескольких вложенных друг в друга циклов применяется форма оператора break с меткой. Меткой помечается цикл, из которого надо выйти:
Loop1: while (...) { . . . while (...) { . . . break Loop1; // Выход из цикла, // помеченного меткой Loop1 . . . } . . . }
Оператор switch (вычисляемый goto)
Оператор switch имеет следующий вид:
switch (выражение) { case значение_1: фрагмент_1; case значение_2: фрагмент_2; case значение_3: фрагмент_3; . . . default: // Необязательный фрагмент фрагмент_N; }
Выражение должно быть дискретного типа (целое число или указатель). Значения должны быть константами того же типа, что и выражение в заголовке. Оператор switch работает следующим образом:
сначала вычисляется значение выражения в заголовке switch; затем осуществляется переход на метку "case L:", где константа L совпадает с вычисленным значением выражения в заголовке; если такого значения нет среди меток внутри тела switch, то если есть метка "default:", то осуществляется переход на нее; если метка "default:" отсутствует, то ничего не происходит.
Подчеркнем, что после перехода на метку "case L:" текст программы выполняется последовательно. Например, при выполнении фрагмента программы
int n, k; n = 2; switch (n) { case 1: k = 2; case 2: k = 4; case 3: k = 8; }
переменной k будет присвоено значение 8, а не 4. Дело в том, что при переходе на метку "case 2:" будут выполнена сначала строка
k = 4;
и затем строка
k = 8;
что делает приведенный фрагмент совершенно бессмысленным (оптимизирующий компилятор вообще исключит строки "k = 2;" и "k = 4;" из кода готовой программы!). Чтобы исправить этот фрагмент, следует использовать оператор
break;
Так же, как и в случае цикла, оператор break приводит к выходу из фигурных скобок, обрамляющих тело оператора switch. Приведенный фрагмент надо переписать следующим образом:
int n, k; n = 2; switch (n) { case 1: k = 2; break; case 2: k = 4; break; case 3: k = 8; break; }
В результате выполнения этого фрагмента переменной k будет присвоено значение 4. Если бы значение n равнялось 1, то k было бы присвоено значение 2, если n равнялось бы 3, то 8. Если n не равно ни 1, ни 2, ни 3, то ничего не происходит.
Оператор switch иногда совершенно необосновано называют оператором выбора. На самом деле, для выбора следует использовать конструкцию if...else if..., см. раздел 3.5.3. Например, приведенный фрагмент лучше реализовать следующим образом:
if (n == 1) { k = 2; } else if (n == 2) { k = 4; } else if (n == 3) { k = 8; }
Оператор switch по сути своей является оператором перехода goto с вычисляемой меткой. Ему присущи многие недостатки goto, например, проблемы с инициализацией локальных переменных при входе в блок. Кроме того, switch не позволяет записывать условия в виде логических выражений, что ограничивает сферу его применения. Рекомендуется никогда не использовать оператор switch: выбор в стиле if...else if... во всех отношениях лучше!
Операторы new и delete языка C++
В языке C++ для захвата и освобождения динамической памяти используются операторы new и delete. Они являются частью языка C++, в отличие от функций malloc и free, входящих в библиотеку стандартных функций Си.
Пусть T - некоторый тип языка Си или C++, p - указатель на объект типа T. Тогда для захвата памяти размером в один элемент типа T используется оператор new:
T *p; p = new T;
Например, для захвата восьми байтов под вещественное число типа double используется фрагмент
double *p; p = new double;
При использовании new, в отличие от malloc, не нужно приводить указатель от типа void* к нужному типу: оператор new возвращает указатель на тип, записанный после слова new. Сравните два эквивалентных фрагмента на Си и C++:
|
double *p; p = (double*) malloc(sizeof(double)); |
double *p; p = new double; |
Конечно, второй фрагмент гораздо короче и нагляднее.
Оператор new удобен еще и тем, что можно присвоить начальное значение объекту, созданному в динамической памяти (т.е. выполнить инициализацию объекта). Для этого начальное значение записывается в круглых скобках после имени типа, следующего за словом new. Например, в приведенной ниже строке захватывается память под вещественное число, которому присваивается начальное значение 1.5:
double *p = new double(1.5);
Этот фрагмент эквивалентен фрагменту
double *p = new double; *p = 1.5;
С помощью оператора new можно захватывать память под массив элементов заданного типа. Для этого в квадратных скобках указывается длина захватываемого массива, которая может представляться любым целочисленным выражением. Например, в следующем фрагменте в динамической создается памяти для хранения вещественной матрицы размера m*n:
double *a; int m = 100, n = 101; a = new double[m * n];
Такую форму оператора new иногда называют векторной.
Оператор delete освобождает память, захваченную ранее с помощью оператора new, например,
double *p = new double(1.5); // Захват и инициализация . . . delete p; // Освобождение памяти
Если память под массив была захвачена с помощью векторной формы оператора new, то для ее освобождения следует использовать векторную форму оператора delete, в которой после слова delete записываются пустые квадратные скобки:
double *a = new double[100]; // Захватываем массив . . . delete[] a; // Освобождаем массив
Для массивов, состоящих из элементов базовых типов Си, при освобождении памяти можно использовать и обычную форму оператора delete. Единственное отличие векторной формы: при освобождении массива элементов класса, в котором определен деструктор, т.е. завершающее действие перед уничтожением объекта, этот деструктор вызывается для каждого элемента уничтожаемого массива. Поскольку для базовых типов деструкторы не определены, векторная и обычная формы оператора delete для них эквивалентны.
Приятная особенность оператора delete состоит в том, что при освобождении нулевого указателя ничего не происходит. Например, следующий фрагмент вполне корректен:
double *a = 0; // Нулевой указатель bool b; . . . if (b) { a = new double[1000]; . . . } . . . delete[] a;
Здесь в указатель a вначале записывается нулевой адрес. Затем, если справедливо некоторое условие, захватывается память под массив. Таким образом, при выполнении оператора delete указатель a содержит либо нулевое значение, либо адрес массива. В первом случае оператор delete ничего не делает, во втором освобождает память, занятую массивом. Такая технология применяется практически всеми программистами на C++: всегда инициализировать указатели на динамическую память нулевыми значениями и в результате не иметь никаких проблем при освобождении памяти.
Попытка освобождения нулевого указателя с помощью стандартной функции free может привести к аварийному завершению программы (это зависит от используемой Си-библиотеки: нормальная работа не гарантируется стандартом ANSI).
Передача параметров функциям
В языке Си функциям передаются значения фактических параметров. При вызове функции значения параметров копируются в аппаратный стек, см. раздел 2.3. Следует четко понимать, что изменение формальных параметров в теле функции не приводит к изменению переменных вызывающей программы, передаваемых функции при ее вызове, - ведь функция работает не с самими этими переменными, а с копиями их значений! Рассмотрим, например, следующий фрагмент программы:
void f(int x); // Описание прототипа функции
int main() { . . . int x = 5; f(x); // Значение x по-прежнему равно 5 . . . }
void f(int x) { . . . x = 0; // Изменение формального параметра . . . // не приводит к изменению фактического // параметра в вызывающей программе }
Здесь в функции main вызывается функция f, которой передается значение переменной x, равное пяти. Несмотря на то, что в теле функции f формальному параметру x присваивается значение 0, значение переменной x в функции main не меняется.
Если необходимо, чтобы функция могла изменить значения переменных вызывающей программы, надо передавать ей указатели на эти переменные. Тогда функция может записать любую информацию по переданным адресам. В Си таким образом реализуются выходные и входно-выходные параметры функций. Подробно этот прием уже рассматривался в разделе 3.5.4, где был дан короткий обзор функций printf и scanf из стандартной библиотеки ввода-вывода языка Си. Напомним, что функции ввода scanf надо передавать адреса вводимых переменных, а не их значения.
печать n первых простых чисел
Рассмотрим пример, использующий захват динамической памяти. Требуется ввести целое цисло n и напечатать n первых простых чисел. (Простое число - это число, у которого нет нетривиальных делителей.) Используем следующий алгоритм: последовательно проверяем все нечетные числа, начиная с тройки (двойку рассматриваем отдельно). Делим очередное число на все простые числа, найденные на предыдущих шагах алгоритма и не превосходящие квадратного корня из проверяемого числа. Если оно не делится ни на одно из этих простых чисел, то само является простым; оно печатается и добавляется в массив найденных простых.
Поскольку требуемое количество простых чисел n до начала работы программы неизвестно, невозможно создать массив для их хранения в статической памяти. Выход состоит в том, чтобы захватывать пространство под массив в динамической памяти уже после ввода числа n. Вот полный текст программы:
#include <stdio.h> #include <stdlib.h> #include <math.h>
int main() { int n; // Требуемое количество простых чисел int k; // Текущее количество найденных простых чисел int *a; // Указатель на массив найденных простых int p; // Очередное проверяемое число int r; // Целая часть квадратного корня из p int i; // Индекс простого делителя bool prime; // Признак простоты
printf("Введите число простых: "); scanf("%d", &n); if (n <= 0) // Некорректное значение => return 1; // завершаем работу с кодом ошибки
// Захватываем память под массив простых чисел a = (int *) malloc(n * sizeof(int));
a[0] = 2; k = 1; // Добавляем двойку в массив printf("%d ", a[0]); // и печатаем ее
p = 3; while (k < n) {
// Проверяем число p на простоту r = (int)( // Целая часть корня sqrt((double) p) + 0.001 ); i = 0; prime = true; while (i < k && a[i] <= r) { if (p % a[i] == 0) { // p делится на a[i] prime = false; // => p не простое, break; // выходим из цикла } ++i; // К следующему простому делителю }
if (prime) { // Если нашли простое число, a[k] = p; // то добавляем его в массив ++k; // Увеличиваем число простых printf("%d ", p); // Печатаем простое число if (k % 5 == 0) { // Переход на новую строку printf("\n"); // после каждых пяти чисел } }
p += 2; // К следующему нечетному числу }
if (k % 5 != 0) { printf("\n"); // Перевести строку }
// Освобождаем динамическую память free(a); return 0; }
Пример работы данной программы:
Введите число простых: 50 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229
расширенный алгоритм Евклида
Вернемся к примеру с расширенным алгоритмом Евклида, подробно рассмотренному в разделе 1.5.2. Напомним, что наибольший общий делитель двух целых чисел выражается в виде их линейной комбинации с целыми коэффициентами. Пусть x и y - два целых числа, хотя бы одно из которых не равно нулю. Тогда их наибольший общий делитель d = НОД(x,y) выражается в виде
d = ux+vy,
где u и v - некоторые целые числа. Алгоритм вычисления чисел d, u, v по заданным x и y называется расширенным алгоритмом Евклида. Мы уже выписывали его на псевдокоде, используя схему построения цикла с помощью инварианта.
Оформим расширенный алгоритм Евклида в виде функции на Си. Назовем ее extGCD (от англ. Extended Greatest Common Divizor). У этой функции два входных аргумента x, y и три выходных аргумента d, u, v. В случае выходных аргументов надо передавать функции указатели на переменные. Итак, функция имеет следующий прототип:
void extGCD(int x, int y, int *d, int *u, int *v);
При вызове функция вычисляет наибольший общий делитель от двух переданных целых значений x и y и коэффициенты его представления через x и y. Ответ записывается по переданным адресам d, u, v.
Приведем полный текст программы. Функция main вводит исходные данные (числа x и y), вызывает функцию extGCD и печатает ответ. Функция extGCD использует схему построения цикла с помощью инварианта для реализации расширенного алгоритма Евклида.
#include <stdio.h> // Описания стандартного ввода-вывода
// Прототип функции extGCD (расш. алгоритм Евклида) void extGCD(int x, int y, int *d, int *u, int *v);
int main() { int x, y, d, u, v; printf("Введите два числа:\n"); scanf("%d%d", &x, &y); if (x == 0 && y == 0) { printf("Должно быть хотя бы одно ненулевое.\n"); return 1; // Вернуть код некорректного завершения }
// Вызываем раширенный алгоритм Евклида extGCD(x, y, &d, &u, &v);
// Печатаем ответ printf("НОД = %d, u = %d, v = %d\n", d, u, v);
return 0; // Вернуть код успешного завершения }
void extGCD( int x, int y, int *d, int *u, int *v) { int a, b, q, r, u1, v1, u2, v2; int t; // вспомогательная переменная
// инициализация a = x; b = y; u1 = 1; v1 = 0; u2 = 0; v2 = 1;
// утверждение: НОД(a, b) == НОД(x, y) && // a == u1 * x + v1 * y && // b == u2 * x + v2 * y;
while (b != 0) { // инвариант: НОД(a, b) == НОД(x, y) && // a == u1 * x + v1 * y && // b == u2 * x + v2 * y; q = a / b; // целая часть частного a / b r = a % b; // остаток от деления a на b a = b; b = r; // заменяем пару (a, b) на (b, r)
// Вычисляем новые значения переменных u1, u2 t = u2; // запоминаем старое значение u2 u2 = u1 - q * u2; // вычисляем новое значение u2 u1 = t; // новое u1 := старое u2
// Аналогично вычисляем новые значения v1, v2 t = v2; v2 = v1 - q * v2; v1 = t; }
// утверждение: b == 0 && // НОД(a, b) == НОД(m, n) && // a == u1 * m + v1 * n;
// Выдаем ответ *d = a; *u = u1; *v = v1; }
Пример работы программы:
Введите два числа: 187 51 НОД = 17, u = -1, v = 4
Здесь первая и третья строка напечатаны компьютером, вторая введена человеком.
рекурсивный обход дерева
В качестве примера использования указателей на структуры приведем фрагмент программы, вычисляющий количество вершин бинарного дерева. Бинарным деревом называется связный граф без циклов, у которого одна вершина отмечена как корневая, а все вершины упорядочены иерархически по длине пути от корня к вершине. У каждой вершины должно быть не больше двух сыновей, причем задан их порядок (левый и правый сыновья).
Вершина дерева описывается структурой TreeNode, которая рассматривалась в предыдущем разделе. Если у вершины один из сыновей отсутствует, то соответствующий указатель содержит нулевой адрес.
Для подсчета числа вершин дерева используем функцию numNodes с прототипом
int numNodes(const struct TreeNode *root);
Ей передается константный указатель на корневую вершину дерева или поддерева. Функция возвращает суммарное число вершин дерева или поддерева. Эта функция легко реализуется с помощью рекурсии: достаточно подсчитать число вершин для каждого из двух поддеревьев, соответствующих левому и правому сыновьям корневой вершины, сложить их и прибавить к сумме единицу. Если левый или правый сын отсутствует, то соответствующее слагаемое равно нулю. Вот фрагмент программы, реализующий функцию numNodes.
// Описание структуры, представляющей вершину дерева struct TreeNode { struct TreeNode *parent; // Указатель на отца, struct TreeNode *left; // на левого сына, struct TreeNode *right; // на правого сына void *value; // Значение в вершине };
// Рекурсивная реализация функции, // вычисляющей число вершин дерева. // Вход: указатель на корень поддерева // Возвращаемое значение: число вершин поддерева int numNodes(const struct TreeNode *root) { int num = 0; if (root == 0) { // Для нулевого указателя на корень return 0; // возвращаем ноль }
if (root->left != 0) { // Есть левый сын => num += numNodes(root->left); // вызываем функцию } // для левого сына
if (root->right != 0) { // Есть правый сын => num += numNodes(root->right); // вызываем ф-цию } // для правого сына
return num + 1; // Возвращаем суммарное число вершин }
Здесь неоднократно применялась операция стрелочка ?> для доступа к полю структуры через указатель на нее.
решение квадратного уравнения
Рассмотрим простой пример, в котором применяется конструкция "если...иначе": требуется решить квадратное уравнение
ax2+bx+c = 0
Программа должна ввести с клавиатуры терминала числа a, b, c и затем напечатать ответ. После ввода надо проверить корректность введенных чисел - коэффициент a должен быть отличен от нуля (иначе уравнение перестает быть квадратным, тогда формула решения квадратного уравнения неприменима). В зависимости от знака дискриминанта уравнение может не иметь решений. Программа должна напечатать либо сообщение об отсутствии решений, либо два корня уравнения (возможно, совпадающие в случае нулевого дискриминанта).
Для печати на экран терминала и ввода информации с клавиатуры используются функции ввода-вывода из стандартной библиотеки Си. Отметим, что функции стандартного ввода-вывода не являются частью языка Си: Си не содержит средств ввода-вывода. Однако любой компилятор обычно предоставляет набор библиотек, в который входит стандартный ввод-вывод. Описания функций ввода-вывода содержатся в заголовочном файле stdio.h, который подключается с помощью строки
#include <stdio.h>
Мы используем две функции: функцию printf вывода по формату и функцию scanf ввода по формату. У обеих этих функций число аргументов переменное, первым аргументом всегда является форматная строка. В случае функции printf обычные символы форматной строки просто выводятся на экран терминала. Например, в рассмотренном ранее примере "Hello, World!" текст выводился на экран с помощью строки прoграммы
printf("Hello, World!\n");
(Здесь '\n' - символ конца строки, т.е. перевода курсора в начало следующей строки.) Единственным аргументом функции printf в данном случае служит форматная строка.
Кроме обычных символов, форматная строка может включать символы формата, которые при выводе заменяются значениями остальных аргументов функции printf, начиная со второго аргумента. Для каждого типа данных Си имеются свои форматы. Формат начинается с символа процента '%'.
После процента идет необязательный числовой аргумент, управляющий представлением данных. Наконец, далее идет одна или несколько букв, задающих тип выводимых на печать данных. Для вывода чисел можно использовать следующие форматы:
%d вывод целого числа типа int (d - от decimal) %lf вывод вещ. числа типа double (lf - от long float)
Например, для печати целого числа n можно использовать строку
printf("n = %d\n", n);
Здесь формат "%d" будет заменен на значение переменной n. Пусть, к примеру, n = 15. Тогда при выполнении функции printf будет напечатана строка
n = 15
При печати вещественного числа компьютер сам решает, сколько знаков после десятичной точки следует напечатать. Если нужно повлиять на представление числа, следует использовать необязательную часть формата. Например, формат
%.3lf
применяется для печати значения вещественного числа в форме с тремя цифрами после десятичной точки. Пусть значение вещественной переменной x равно единице. Тогда при выполнении функции
printf("ответ = %.3lf\n", x);
будет напечатана строка
ответ = 1.000
При вызове функции форматного ввода scanf форматная строка должна содержать только форматы. Этим функция scanf отличается от printf. Вместо значений печатаемых переменных или выражений, как в функции printf, функция scanf должна содержать указатели на вводимые переменные! Для начинающих это постоянный источник ошибок. Необходимо запомнить: функции scanf нужно передавать адреса переменных, в которые надо записать введенные значения. Если вместо адресов переменных передать их значения, то функция scanf все равно проинтерпретирует полученные значения как адреса, что при выполнении вызовет попытку записи по некорректным адресам памяти и, скорее всего, приведет к ошибке типа Segmentation fault. Пример: пусть нужно ввести значения трех вещественных переменных a, b, c. Тогда следует использовать фрагмент
scanf("%lf%lf%lf", &a, &b, &c);
Ошибка, которую часто совершают начинающие: передача функции scanf значений переменных вместо адресов:
scanf("%lf%lf%lf", a, b, c); // Ошибка! Передаются // значения вместо указателей
Помимо стандартной библиотеки ввода-вывода, в Си- программах широко используется стандартная библиотека математических функций. Ее описания содержатся в стандартном заголовочном файле math.h, который подключается строкой
#include <math.h>
Стандартная математическая библиотека содержит математические функции sin, cos, exp, log (натуральный логарифм), fabs (абсолютная величина вещ. числа) и многие другие. Нам необходима функция sqrt, вычисляющая квадратный корень вещественного числа.
Итак, приведем полный текст программы, решающей квадратное уравнение; он содержится в файле "squareEq.cpp".
#include <stdio.h> // Описания стандартного ввода-вывода #include <math.h> // Описания математической библиотеки
int main() { double a, b, c; // Коэффициенты уравнения double d; // Дискриминант double x1, x2; // Корни уравнения
printf("Введите коэффициенты a, b, c:\n"); scanf("%lf%lf%lf", &a, &b, &c);
if (a == 0.0) { printf("Коэффициент a должен быть ненулевым.\n"); return 1; // Возвращаем код некорректного } // завершения
d = b*b - 4.0*a*c; // Вычисляем дискриминант if (d < 0.0) { printf("Решений нет.\n"); } else { d = sqrt(d); // Квадр. корень из дискриминанта x1 = (-b + d) / (2.0 * a); // Первый корень ур-я x2 = (-b - d) / (2.0 * a); // Второй корень ур-я
// Печатаем ответ printf( "Решения уравнения: x1 = %lf, x2 = %lf\n", x1, x2 ); } return 0; // Возвращаем код успешного завершения }
Приведем пример выполнения программы:
Введите коэффициенты a, b, c: 1 2 -3 Решения уравнения: x1 = 1.000000, x2 = -3.000000
Здесь первая и третья строчки напечатаны компьютером, вторая строчка напечатана человеком (ввод чисел заканчивается клавишей перевода строки Enter).
вычисление квадратного корня методом деления отрезка пополам
Метод вычисления корня функции с помощью деления отрезка пополам в общем случае уже был рассмотрен в разделе 1.5.2. Пусть надо найти квадратный корень из неотрицательного вещественного числа a с заданной точностью ?. Задача сводится к нахождению корня функции
y = x2-a
на отрезке [0,b], где b = max(1,a). На этом отрезке функция имеет ровно один корень, поcкольку она монотонно возрастает и на концах отрезка принимает значения разных знаков (или нулевое значение при a = 0 или a = 1).
Идея алгоритма состоит в том, что отрезок делится пополам и выбирается та половина, на которой функция принимает значения разных знаков. Эта операция повторяется до тех пор, пока длина отрезка не станет меньше, чем ?. Концы текущего отрезка содержатся в переменных x0, x1. В данном случае функция монотонно возрастает при x
Приведем полный текст программы:
#include <stdio.h> // Описания стандартного ввода-вывода
int main() { double a; // Число, из которого извлекается корень double x, x0, x1; // [x0, x1] - текущий отрезок double y; // Значение ф-ции в точке x double eps = 0.000001; // Точность вычисления корня
printf("Введите число a:\n"); scanf("%lf", &a);
if (a < 0.0) { printf("Число должно быть неотрицательным.\n"); return 1; // Возвращаем код } // некорректного завершения
// Задаем концы отрезка x0 = 0.0; x1 = a; if (a < 1.0) { x1 = 1.0; }
// Утверждение: x0 * x0 - a <= 0, // x1 * x1 - a >= 0
while (x1 - x0 > eps) { // Инвариант: x0 * x0 - a <= 0, // x1 * x1 - a >= 0 x = (x0 + x1) / 2.0; // середина отрезка [x0,x1] y = x * x - a; // значение ф-ции в точке x
if (y >= 0.0) { x1 = x; // выбираем левую половину отрезка } else { x0 = x; // выбираем правую половину отрезка } }
// Утверждение: x0 * x0 - a <= 0, // x1 * x1 - a >= 0, // x1 - x0 <= eps x = (x0 + x1) / 2.0; // Корень := середина отрезка
// Печатаем ответ printf("Квадратный корень = %lf\n", x);
return 0; // Возвращаем код успешного завершения }
Отметим, что существует более быстрый способ вычисления квадратного корня числа - метод итераций Ньютона, или метод касательных к графику функции, но здесь мы его не рассматриваем.
вычисление наибольшего общего делителя
Программа вводит с клавиатуры терминала два целых числа, затем вычисляет и печатает их наибольший общий делитель. Непосредственно вычисление наибольшего общего делителя реализовано в виде отдельной функции
int gcd(int x, int y);
(gcd - от слов greatest common divizor). Основная функция main лишь вводит исходные данные, вызывает функцию gcd и печатает ответ. Описание прототипа функции gcd располагается в начале текста программы, затем следует функция main и конце - реализация функции gcd. Приведем полный текст программы:
#include <stdio.h> // Описания стандартного ввода-вывода
int gcd(int x, int y); // Описание прототипа функции
int main() { int x, y, d; printf("Введите два числа:\n"); scanf("%d%d", &x, &y); d = gcd(x, y); printf("НОД = %d\n", d); return 0; }
int gcd(int x, int y) { // Реализация функции gcd while (y != 0) { // Инвариант: НОД(x, y) не меняется int r = x % y; // Заменяем пару (x, y) на x = y; // пару (y, r), где r -- y = r; // остаток от деления x на y } // Утверждение: y == 0 return x; // НОД(x, 0) = x }
Стоит отметить, что реализация функции gcd располагается в конце текста программы. Можно было бы расположить реализацию функции в начале текста и при этом сэкономить на описании прототипа. Это, однако, дурной стиль! Лучше всегда, не задумываясь, описывать прототипы всех функций в начале текста, ведь функции могут вызывать друг друга, и правильно упорядочить их (чтобы вызываемая функция была реализована раньше вызывающей) во многих случаях невозможно. К тому же предпочтительнее, чтобы основная функция main, с которой начинается выполнение программы, была бы реализована раньше функций, которые из нее вызываются. Это соответствует технологии "сверху вниз" разработки программы: основная задача решается сразу на первом шаге путем сведения ее к одной или нескольким вспомогательным задачам, которые решаются на следующих шагах.
Прототипы функций
Перед использованием или реализацией функции необходимо описать ее прототип. Прототип функции сообщает информацию об имени функции, типе возвращаемого значения, количестве и типах ее аргументов. Пример:
int gcd(int x, int y);
Описан прототип функции gcd, возвращающей целое значение, с двумя целыми аргументами. Имена аргументов x и y здесь являются лишь комментариями, не несущими никакой информации для компилятора. Их можно опускать, например, описание
int gcd(int, int);
является вполне допустимым.
Описания прототипов функций обычно выносятся в заголовочные файлы, см. раздел 3.1. Для коротких программ, которые помещаются в одном файле, описания прототипов располагают в начале программы. Рассмотрим пример такой короткой программы.
Работа с памятью
В традиционных языках программирования, таких как Си, Фортран, Паскаль, существуют три вида памяти: статическая, стековая и динамическая. Конечно, с физической точки зрения никаких различных видов памяти нет: оперативная память - это массив байтов, каждый байт имеет адрес, начиная с нуля. Когда говорится о видах памяти, имеются в виду способы организации работы с ней, включая выделение и освобождение памяти, а также методы доступа.
Статическая память
Статическая память выделяется еще до начала работы программы, на стадии компиляции и сборки. Статические переменные имеют фиксированный адрес, известный до запуска программы и не изменяющийся в процессе ее работы. Статические переменные создаются и инициализируются до входа в функцию main, с которой начинается выполнение программы.
Существует два типа статических переменных:
глобальные переменные - это переменные, определенные вне функций, в описании которых отсутствует слово static. Обычно описания глобальных переменных, включающие слово extern, выносятся в заголовочные файлы (h-файлы). Слово extern означает, что переменная описывается, но не создается в данной точке программы. Определения глобальных переменных, т.е. описания без слова extern, помещаются в файлы реализации (c-файлы или cpp-файлы). Пример: глобальная переменная maxind описывается дважды: в h-файле с помощью строки
extern int maxind;
это описание сообщает о наличии такой переменной, но не создает эту переменную!
в cpp-файле с помощью строки
int maxind = 1000;
это описание создает переменную maxind и присваивает ей начальное значение 1000. Заметим, что стандарт языка не требует обязательного присвоения начальных значений глобальным переменным, но, тем не менее, это лучше делать всегда, иначе в переменной будет содержаться непредсказуемое значение (мусор, как говорят программисты). Инициализация всех глобальных переменных при их определении - это правило хорошего стиля.
Глобальные переменные называются так потому, что они доступны в любой точке программы во всех ее файлах. Поэтому имена глобальных переменных должны быть достаточно длинными, чтобы избежать случайного совпадения имен двух разных переменных. Например, имена x или n для глобальной переменной не подходят; статические переменные - это переменные, в описании которых присутствует слово static. Как правило, статические переменные описываются вне функций. Такие статические переменные во всем подобны глобальным, с одним исключением: область видимости статической переменной ограничена одним файлом, внутри которого она определена, - и, более того, ее можно использовать только после ее описания, т.е.
ниже по тексту. По этой причине описания статических переменных обычно выносятся в начало файла. В отличие от глобальных переменных, статические переменные никогда не описываются в h-файлах (модификаторы extern и static конфликтуют между собой). Совет: используйте статические переменные, если нужно, чтобы они были доступны только для функций, описанных внутри одного и того же файла. По возможности не применяйте в таких ситуациях глобальные переменные, это позволит избежать конфликтов имен при реализации больших проектов, состоящих из сотен файлов. Статическую переменную можно описать и внутри функции, хотя обычно так никто не делает. Переменная размещается не в стеке, а в статической памяти, т.е. ее нельзя использовать при рекурсии, а ее значение сохраняется между различными входами в функцию. Область видимости такой переменной ограничена телом функции, в которой она определена. В остальном она подобна статической или глобальной переменной. Заметим, что ключевое слово static в языке Си используется для двух различных целей: как указание типа памяти: переменная располагается в статической памяти, а не в стеке; как способ ограничить область видимости переменной рамками одного файла (в случае описания переменной вне функции).
Слово static может присутствовать и в заголовке функции. При этом оно используется только для того, чтобы ограничить область видимости имени функции рамками одного файла. Пример:
static int gcd(int x, int y); // Прототип ф-ции . . . static int gcd(int x, int y) { // Реализация . . . }
Совет: используйте модификатор static в заголовке функции, если известно, что функция будет вызываться лишь внутри одного файла. Слово static должно присутствовать как в описании прототипа функции, так и в заголовке функции при ее реализации.
Стековая, или локальная, память
Локальные, или стековые, переменные - это переменные, описанные внутри функции. Память для таких переменных выделяется в аппаратном стеке, см. раздел 2.3.2. Память выделяется в момент входа в функцию или блок и освобождается в момент выхода из функции или блока. При этом захват и освобождение памяти происходят практически мгновенно, т.к. компьютер только изменяет регистр, содержащий адрес вершины стека.
Локальные переменные можно использовать при рекурсии, поскольку при повторном входе в функцию в стеке создается новый набор локальных переменных, а предыдущий набор не разрушается. По этой же причине локальные переменные безопасны при использовании нитей в параллельном программировании (см. раздел 2.6.2). Программисты называют такое свойство функции реентерабельностью, от англ. re-enter able - возможность повторного входа. Это очень важное качество с точки зрения надежности и безопасности программы! Программа, работающая со статическими переменными, этим свойством не обладает, поэтому для защиты статических переменных приходится использовать механизмы синхронизации (см. 2.6.2), а логика программы резко усложняется. Всегда следует избегать использования глобальных и статических переменных, если можно обойтись локальными.
Недостатки локальных переменных являются продожением их достоинств. Локальные переменные создаются при входе в функцию и исчезают после выхода из нее, поэтому их нельзя использовать в качестве данных, разделяемых между несколькими функциями. К тому же, размер аппаратного стека не бесконечен, стек может в один прекрасный момент переполниться (например, при глубокой рекурсии), что приведет к катастрофическому завершению программы. Поэтому локальные переменные не должны иметь большого размера. В частности, нельзя использовать большие массивы в качестве локальных переменных.
Структуры
Структура — это конструкция, которая позволяет объединить несколько переменных с разными типами и именами в один составной объект. Она позволяет строить новые типы данных языка Си. В других языках программирования структуры называют записями или кортежами.
Описание структуры выглядит следующим образом:
struct имя_структуры { описание полей структуры };
Здесь имя_структуры — это любое имя, соответствующее синтаксису языка Си, описания полей структуры — любая последовательность описаний переменных, имена и типы этих переменных могут быть произвольными. Эти переменные называются полями структуры. Заканчивается описание структуры закрывающей фигурной скобкой. За закрывающей фигурной скобкой в описании структуры обязательно следует точка с запятой, в отличие от конструкции составного оператора, не следует забывать об этом! Для чего здесь нужна точка с запятой, будет объяснено ниже в разделе "Структуры и оператор определения типа typedef".
Рассмотрим пример: опишем вектор в трехмерном пространстве, который задается тремя вещественными координатами x, y, z:
struct R3Vector { double x; double y; double z; };
Таким образом, вводится новый тип "struct R3Vector"; объект этого типа содержит внутри себя три вещественных поля с именами x, y, z. После того как структура определена, можно описывать переменные такого типа, при этом в качестве имени типа следует использовать выражение struct R3Vector. Например, в следующей строке описываются два вещественных вектора в трехмерном пространстве с именами u, v:
struct R3Vector u, v;
С объектами типа структура можно работать как с единым целым, например, копировать эти объекты целиком:
struct R3Vector u, v; . . . u = v; // Копируем вектор как единое целое
В этом примере вектор v копируется в вектор u; копирование структур сводится к переписыванию области памяти. Сравнивать структуры нельзя:
struct R3Vector u, v; . . . if (u == v) { // Ошибка! Сравнивать структуры нельзя . . . }
Имеется также возможность работать с полями структуры.
Для этого используется операция точка ".": пусть s — объект типа структура, f — имя поля структуры. Тогда выражение
s.f
является полем f структуры s, с ним можно работать как с обычной переменной. Например, в следующем фрагменте в вектор w записывается векторное произведение векторов u и v трехмерного пространства: w = u ? v.
struct R3Vector u, v, w; . . . // Вычисляем векторное произведение w = u * v w.x = u.y * v.z - u.z * v.y; w.y = (-u.x) * v.z + u.z * v.x; w.z = u.x * v.y - u.y * v.x;
В приведенных примерах все поля структуры R3Vector имеют один и тот же тип double, однако это совершенно не обязательно. Полями структуры могут быть другие структуры, никаких ограничений нет. Пример: плоскость в трехмерном пространстве задается точкой и вектором нормали, ей соответствует структура R3Plane. Точке трехмерного пространства соответствует структура R3Point, которая определяется аналогично вектору. Полное описание всех трех структур:
struct R3Vector { // Вектор трехмерного пространства double x; double y; double z; }; struct R3Point { // Точка трехмерного пространства double x; double y; double z; }; struct R3Plane { // Плоскость в трехмерном пр-ве struct R3Point origin; // точка в плоскости struct R3Vector normal; // нормаль к плоскости };
Пусть plane — это объект типа плоскость. Для того, чтобы получить координату x точки плоскости, надо два раза применить операцию "точка" доступа к полю структуры:
plane.origin.x
Структуры и оператор определения типа typedef
Синтаксис языка Си позволяет в одном предложении определить структуру и описать несколько переменных структурного типа. Например, строка
struct R2_point { double x; double y; } t, *p;
одновременно определяет структуру R2_point (точка на двумерной плоскости) и описывает две переменные t и p. Первая имеет тип struct R2_point (точка плоскости), вторая — struct R2_point * (указатель на точку плоскости). Таким образом, после закрывающей фигурной скобки может идти необязательный список определяемых переменных, причем можно использовать все конструкции Си для построения сложных типов (указатели, массивы, функции). Список всегда завершается точкой с запятой, поэтому даже при пустом списке точка с запятой после фигурной скобки обязательна.
Возможно анонимное определение структуры, когда имя структуры после ключевого слова struct опускается; в этом случае список описываемых переменных должен быть непустым (иначе такое описание совершенно бессмысленно). Пример:
struct { double x; double y; } t, *p;
Здесь имя структуры отсутствует. Определены две переменные t и p, первая имеет структурный тип с полями x и y типа double, вторая — указатель на данный структурный тип. Такие описания в чистом виде программисты обычно не используют, гораздо чаще анонимное определение структуры комбинируют с оператором определения имени типа typedef (см. c. 117. ). Например, можно определить два типа R2Point (точка вещественной двумерной плоскости) и R2PointPtr (указатель на точку вещественной двумерной плоскости) в одном предложении, комбинируя оператор typedef с анонимным определением структуры:
typedef struct { double x; double y; } R2Point, *R2PointPtr;
Такая технология довольно популярна среди программистов и применяется в большинстве системных h-файлов. Преимущество ее состоит в том, что в дальшейшем при описании переменных структурного типа не нужно использовать ключевое слово struct, например,
R2Point a, b, c; // Описываем три точки a, b, c R2PointPtr p; // Описываем указатель на точку R2Point *q; // Эквивалентно R2PointPtr q;
Сравните с описаниями, использующими приведенное выше определение структуры R2_point:
struct R2_Point a, b, c; struct R2_Point *p; struct R2_Point *q;
Первый способ лаконичнее и нагляднее.
Вовсе не обязательно комбинировать оператор typedef непременно с анонимным определением структуры; можно в одном предложении как определить имя структуры, так и ввести новый тип. Например, предложение
typedef struct R2_point { double x; double y; } R2Point, *R2PointPtr;
определяет структуру R2_point, а также два новых типа R2Point (структура R2_point) и R2PointPtr (указатель на структуру R2_point). К сожалению, имя структуры не должно совпадать с именем типа, именно поэтому здесь в качестве имени структуры приходится использовать несколько вычурное имя R2_point. Впрочем, обычно в дальнейшем оно не нужно.
Все вышесказанное касательно языка Си справедливо и в C++. Кроме того, в C++ считается, что определение структуры S одновременно вводит и новый тип с именем S. Поэтому в случае C++ нет необходимости в использовании оператора typedef при задании структурных типов. Связано это с тем, что структура с точки зрения C++ является классом, а классы и определяемые ими типы — это основа языка C++. Сравните описания Си
struct S { ... }; struct S a, b, c; struct S *p, *q;
и C++:
struct S { ... }; S a, b, c; S *p, *q;
Конечно, описания C++ проще и нагляднее.
Структуры и указатели
Указатели на структуры используются довольно часто. Указатель на структуру S описывается обычным образом, в качестве имени типа фигурирует struct S*. Например, в следующем фрагменте переменная p описана как указатель на структуру S:
struct S { . . . }; // Определение структуры S struct S *p; // Описание указателя на структуру S
Описание структуры может содержать указатель на структуру того же типа в качестве одного из полей. Язык Си допускает использование указателей на структуры, определение которых еще не завершено. Например, рассмотрим структуру TreeNode (вершина дерева), которая используется при определении бинарного дерева (см. раздел 4.5.4). Она содержит указатели на родительский узел и на левого и правого сыновей, которые также имеют тип struct TreeNode:
struct TreeNode { // Вершина дерева struct TreeNode *parent; // Указатель на отца, struct TreeNode *left; // на левого сына, struct TreeNode *right; // на правого сына void *value; // Значение в вершине };
Здесь при описании полей parent, left, right используется тип ``указатель на структуру TreeNode'', определение которой еще не завершено, что допустимо в языке Си. Возможны и более сложные комбинации, например, структура A содержит указатель на структуру B, а структура B — указатель на структуру A. В этом случае можно использовать предварительное описание структуры, например, строка
struct A;
просто сообщает компилятору, что имя A является именем структуры, полное определение которой будет дано ниже. Тогда упомянутое описание двух структур A и B, ссылающихся друг на друга, может выглядеть следующим образом:
struct A; // Предварительное описание структуры A struct B; // Предварительное описание структуры B
struct A { // Определение структуры A . . . struct B *p; // Указатель на структуру B . . . };
struct B { // Определение структуры B . . . struct A *q; // Указатель на структуру A . . . };
Для доступа к полям структуры через указатель на структуру служит операция стрелочка, которая обозначается двумя символами ?> (минус и знак больше), их нужно рассматривать как одну неразрывную лексему (т.е. единый знак, единое слово). Пусть S — имя структуры, f — некоторое поле структуры S, p — указатель на структуру S. Тогда выражение
p?>f
обозначает поле f структуры S (само поле, а не указатель не него!). Это выражение можно записать, используя операцию звездочка (доступ к объекту через указатель),
p?>f ~ (*p).f
но, конечно, первый способ гораздо нагляднее. (Во втором случае круглые скобки вокруг выражения *p обязательны, поскольку приоритет операции точка выше, чем операции звездочка.)
Управляющие конструкции
Управляющие конструкции позволяют организовывать циклы и ветвления в программах. В Си всего несколько конструкций, причем половину из них можно не использовать (они реализуются через остальные).
Выбор из нескольких возможностей: if...else if...
Несколько условных операторов типа "если...иначе" можно записывать последовательно (т.е. действие после else может снова представлять собой условный оператор). В результате реализуется выбор из нескольких возможностей. Конструкция выбора используется в программировании очень часто. Пример: дана вещественная переменная x, требуется записать в вещественную переменную y значение функции sign(x):
sign(x) = -1, при x < 0 sign(x) = 1, при x > 0 sign(x) = 0, при x = 0
Это делается с использованием конструкции выбора:
double x, s; . . . if (x < 0.0) { s = (-1.0); } else if (x > 0.0) { s = 1.0; } else { s = 0.0; }
При выполнении этого фрагмента сперва проверяется условие x < 0.0. Если оно истинно, то выполняется оператор s = (-1.0); иначе проверяется второе условие x < 0.0. В случае его истинности выполняется оператор s = 1.0, иначе выполняется оператор s = 0.0. Фигурные скобки здесь добавлены для улучшения структурности текста программы.
В любом случае, в результате выполнения конструкции выбора исполняется лишь один из операторов (возможно, составных). Условия проверяются последовательно сверху вниз. Как только находится истинное условие, то производится соответствующее действие и выбор заканчивается.
Выход из цикла break, переход на конец цикла continue
Если необходимо прервать выполнение цикла, следует использовать оператор
break;
Оператор break применяется внутри тела цикла, заключенного в фигурные скобки. Пример: требуется найти корень целочисленной функции f(x), определенной для целочисленных аргументов.
int f(int x); // Описание прототипа функции . . . int x; . . . // Ищем корень функции f(x) x = 0; while (true) { if (f(x) == 0) { break; // Нашли корень } // Переходим к следующему целому значению x // в порядке 0, -1, 1, -2, 2, -3, 3, ... if (x >= 0) { x = (-x - 1); } else { x = (-x); } } // Утверждение: f(x) == 0
Здесь используется бесконечный цикл "while (true)". Выход из цикла осуществляется с помощью оператора "break".
Иногда требуется пропустить выполнение тела цикла при каких-либо значениях изменяющихся в цикле переменных, переходя к следующему набору значений и очередной итерации. Для этого используется оператор
continue;
Оператор continue, так же, как и break, используется лишь в том случае, когда тело цикла состоит более чем из одного оператора и заключено в фигурные скобки. Его следует понимать как переход на фигурную скобку, закрывающую тело цикла. Пример: пусть задана n+1 точка на вещественной прямой xi, i = 0, 1,..., n; точки xi будут называться узлами интерполяции. Элементарный интерполяционный многочлен Лагранжа Lk(x) - это многочлен степени n, который принимает нулевые значения во всех узлах xi, кроме xk. В k-ом узле xk многочлен Lk(x) принимает значение 1. Многочлен Lk(x) вычисляется по следующей формуле:
Пусть требуется вычислить значение элементарного интерполяционного многочлена Lk(x) в заданной точке x = t. Это делается с помощью следующего фрагмента программы:
double x[100]; // Узлы интерполяции (не более 100) int n; // Количество узлов интерполяции int k; // Номер узла double t; // Точка, в которой вычисляется значение double L; // Значение многочлена L_k(x) в точке t int i; . . . L = 1.0; // Начальное значение произведения i = 0; while (i <= n) { if (i == k) { ++i; // К следующему узлу continue; // Пропустить k-й множитель }
// Вычисляем произведение L *= (t - x[i]) / (x[k] - x[i]); ++i; // К следующему узлу } // Ответ в переменной L
Здесь оператор continue используется для того, чтобы пропустить вычисление произведения при i = k.
Аргументы командной строки
До сих пор во всех примерах программ использовался ввод исходных данных либо с клавиатуры (т.е. из входного потока), либо из файла. Язык Си предоставляет также возможность указывать аргументы программы в командной строке.
Аргументы командной строки являются параметрами функции main, с которой начинается выполнение Си-программы. До сих пор применялся вариант функции main без параметров, однако, при необходимости доступа к аргументам командной строки можно использовать следующий заголовок функции main:
int main(int argc, char *argv[]) { . . . }
Здесь целая переменная argc равна числу аргументов, т.е. отдельных слов командной строки, а массив argv содержит указатели на строки, каждая из которых равна очередному слову командной строки. Нулевой элемент argv[0] равен имени программы. Таким образом, число аргументов argc всегда не меньше единицы.
Например, при запуске программы testprog с помощью командной строки
testprog -x abcd.txt efgh.txt
значение переменной argc будет равно 4, а массив argv будет содержать 4 строки "testprog", "-x", "abcd.txt" и "efgh.txt".
В операционной системе Unix нулевой элемент массива argv содержит полный путь к файлу с выполняемой программой. В системах MS DOS и MS Windows строка argv[0] может быть равна как полному пути к файлу, так и первому слову командной строки (зависит от используемого командного процессора).
Пример программы, печатающей аргументы своей командной строки:
// Файл "comargs.cpp" // Напечатать аргументы командной строки #include <stdio.h>
int main(int argc, char *argv[]) { int i; printf("Число аргументов ком. строки = %d\n", argc); printf("Аргументы командной строки:\n"); for (i = 0; i < argc; ++i) { printf("%s\n", argv[i]); } return 0; }
Диагностика ошибок: функция perror
Использовать переменную errno для печати кода ошибки не очень удобно, поскольку необходимо иметь под рукой таблицу возможных кодов ошибок и их значений. В стандартной библиотеке Си существует более удобная функция perror, которая печатает системное сообщение о последней ошибке вместо ее кода. Печать производится на английском языке, но есть возможность добавить к системному сообщению любой текст, который указывается в качестве единственного аргумента функции perror. Например, предыдущий фрагмент переписывается следующим образом:
#include <stdio.h> . . .
FILE *f = fopen("filnam.txt", "rt"); if (f == 0) { perror("Не могу открыть файл на чтение"); . . . }
Функция perror печатает сначала пользовательское сообщение об ошибке, затем после двоеточия системное сообщение. Например, при выполнении приведенного фрагмента в случае ошибки из-за отсутствия файла будет напечатано
Не могу открыть файл на чтение: No such file or directory
Другие полезные функции ввода-вывода
Стандартная библиотека ввода-вывода Си содержит ряд других полезных функций ввода-вывода. Отметим некоторые из них.
| int fgetc(FILE *f); | ввести символ из потока f |
| int fputc(int c, FILE *f); | вывести символ в поток f |
| char *fgets(char *line,int size, FILE *f); | ввести строку из потока f |
| char *fputs(char *line, FILE *f); | вывести строку в поток f |
| int fseek(FILE *f, long offset, int whence); | установить текущую позицию в файле f |
| long ftell(FILE *f); | получить текущую позицию в файле f |
| int feof(FILE *f); | проверить,достигнут ли конец файла f |
Функция fgetc возвращает код введенного символа или константу EOF (определенную как минус единицу) в случае конца файла или ошибки чтения. Функция fputc записывает один символ в файл. При ошибке fputc возвращает константу EOF (т.е. отрицательное значение), в случае удачи - код выведенного символа c (неотрицательное значение).
В качестве примера использования функции fgetc перепишем рассмотренную ранее программу wc, подсчитывающую число символов и строк в текстовом файле:
// // Файл "wc1.cpp" // Подсчет числа символов и строк в текстовом файле // с использованием функции чтения символа fgetc // #include <stdio.h> // Описания функций ввода-вывода
int main() { char fileName[256]; // Путь к файлу FILE *f; // Структура, описывающая файл int c; // Код введенного символа int numChars = 0; // Суммарное число символов := 0 int numLines = 0; // Суммарное число строк := 0
printf("Введите имя файла: "); scanf("%s", fileName);
f = fopen(fileName, "rb"); // Открываем файл if (f == 0) { // При ошибке открытия файла // Напечатать сообщение об ошибке perror("Не могу открыть файл для чтения"); return 1; // закончить работу программы с кодом 1 }
while ((c = fgetc(f)) != EOF) { // Читаем символ // Цикл продолжается, пока c != -1 (конец файла)
++numChars; // Увеличиваем число символов
// Подсчитываем число символов перевода строки if (c == '\n') { ++numLines; // Увеличиваем число строк } }
fclose(f);
// Печатаем результат printf("Число символов в файле = %d\n", numChars); printf("Число строк в файле = %d\n", numLines);
return 0; // Возвращаем код успешного завершения }
Пример выполнения программы wc1 в применении к собственному тексту, записанному в файле "wc1.cpp:
Введите имя файла: wc1.cpp Число символов в файле = 1334 Число строк в файле = 44
Функция fgets с прототипом
char *fgets(char *line, int size, FILE *f);
выделяет из файла или входного потока f очередную строку и записывает ее в массив символов line. Второй аргумент size указывает размер массива для записи строки. Максимальная длина строки на единицу меньше, чем size, поскольку всегда в конец считанной строки добавляется нулевой байт. Функция сканирует входной поток до тех пор, пока не встретит симол перевода строки "\n" или пока число введенных символов не станет равным size - 1. Символ перевода строки "\n" также записывается в массив непосредственно перед терминирующим нулевым байтом. Функция возвращает указатель line в случае успеха или нулевой указатель при ошибке или конце файла.
Раньше в стандартную библиотеку Си входила также функция gets с прототипом
char *gets(char *line);
которая считывала очередную строку из стандартного входного потока и помещала ее в массив, адрес которого являлся ее единственным аргументом. Отличие от функции fgets в том, что не указывается размер массива line. В результате, подав на вход функции gets очень длинную строку, можно добиться переполнения массива и стереть или подменить участок памяти, используемый программой. Если программа имеет привилегии суперпользователя, то применение в ней функции gets открывает путь к взлому системы, который использовался хакерами. Поэтому в настоящее время функция gets считается опасной и применение ее не рекомендовано. Вместо gets следует использовать fgets с третьим аргументом stdin.
При выполнении файловых операций исполняющая система поддерживает указатель текущей позиции в файле.
При чтении или записи n байтов указатель текущей позиции увеличивается на n; таким образом, чтение или запись происходят последовательно. Библиотека ввода-вывода Си предоставляет, однако, возможность нарушать эту последовательность путем позиционирования в произвольную точку файла. Для этого используется стандартная функция fseek с прототипом
int fseek(FILE *f, long offset, int whence);
Первый аргумент f функции определяет файл, для которого производится операция позиционирования. Второй аргумент offset задает смещение в байтах, оно может быть как положительным, так и отрицательным. Третий аргумент whence указывает, откуда отсчитывать смещение. Он может принимать одно из трех значений, заданных как целые константы в стандартном заголовочном файле "stdio.h":
| SEEK_CUR | смещение отсчитывается от текущей позиции |
| SEEK_SET | смещение отсчитывается от начала файла |
| SEEK_END | смещение отсчитывается от конца файла |
fseek(f, 0, SEEK_SET);
устанавливает текущую позицию в начало файла. Фрагмент
fseek(f, -4, SEEK_END);
устанавливает текущую позицию в четырех байтах перед концом файла. Наконец, фрагмент
fseek(f, 12, SEEK_CUR);
продвигает текущую позицию на 12 байтов вперед.
Отметим, что смещение может быть положительным даже при использовании константы SEEK_END (т.е. при позиционировании относительно конца файла): в этом случае при следующей записи размер файла соответственно увеличивается.
Функция возвращает нулевое значение в случае успеха и отрицательное значение EOF (равное -1) при неудаче - например, если указанное смещение некорректно при заданной операции или если файл или поток не позволяет выполнять прямое позиционирование.
Узнать текущую позицию относительно начала файла можно с помощью функции ftell с прототипом
long ftell(FILE *f);
Функция ftell возвращает текущую позицию (неотрицательное значение) в случае успеха или отрицательное значение -1 при неудаче (например, если файл не разрешает прямое позиционирование).
Наконец, узнать, находится ли текущая позиция в конце файла, можно с помощью функции feof с прототипом
int feof(FILE *f);
Она возвращает ненулевое значение (т.е. истину), если конец файла достигнут, и нулевое значение (т.е. ложь) в противном случае. Например, в следующем фрагменте в цикле проверяется, достигнут ли конец файла, и, если нет, считывается очередной байт:
FILE *f; . . . while (!feof(f)) { // цикл пока не конец файла int c = fgetc(f); // | прочесть очередной байт . . . // | . . . } // конец цикла
Форматный ввод-вывод: функции fscanf и fprintf
В отличие от функции бинарного ввода fread, которая вводит байты из файла без всякого преобразования непосредственно в память компьютера, функция форматного ввода fscanf предназначена для ввода информации с преобразованием ее из текстового представления в бинарное. Пусть информация записана в текстовом файле в привычном для человека виде (т.е. так, что ее можно прочитать или ввести в файл, используя текстовый редактор). Функция fscanf читает информацию из текстового файла и преобразует ее во внутреннее представление данных в памяти компьютера. Информация о количестве читаемых элементов, их типах и особенностях представления задается с помощью формата. В случае функции ввода формат - это строка, содержащая описания одного или нескольких вводимых элементов. Форматы, используемые функцией fscanf, аналогичны применяемым функцией scanf, они уже неоднократно рассматривались (см. раздел 3.5.4). Каждый элемент формата начинается с символа процента "%". Наиболее часто используемые при вводе форматы приведены в таблице:
| %d | целое десятичное число типа int (d - от decimal) |
| %lf | вещ. число типа double (lf - от long float) |
| %c | один символ типа char |
| %s | ввод строки. Из входного потока выделяется слово, ограниченое пробелами или символами перевода строки '\n'. Слово помещается в массив символов. Конец слова отмечается нулевым байтом. |
Прототип функции fscanf выглядит следующим образом:
int fscanf(FILE *f, const char *format, ...);
Многоточие здесь означает, что функция имеет переменное число аргументов, большее двух, и что количество и типы аргументов, начиная с третьего, произвольны. На самом деле, фактические агрументы, начиная с третьего, должны быть указателями на вводимые переменные. Несколько примеров использования функции fscanf:
int n, m; double a; char c; char str[256]; FILE *f; . . . fscanf(f, "%d", &n); // Ввод целого числа fscanf(f, "%lf", &a); // Ввод вещественного числа fscanf(f, "%c", &c); // Ввод одного символа fscanf(f, "%s", str); // Ввод строки (выделяется очередное // слово из входного потока) fscanf(f, "%d%d", &n, &m); // Ввод двух целых чисел
Функция fscanf возвращает число успешно введенных элементов. Таким образом, возвращаемое значение всегда меньше или равно количеству процентов внутри форматной строки (которое равно числу фактических аргументов минус 2).
Функция fprintf используется для форматного вывода в файл. Данные при выводе преобразуются в их текстовое представление в соответствии с форматной строкой. Ее отличие от форматной строки, используемой в функции ввода fscanf, заключается в том, что она может содержать не только форматы для преобразования данных, но и обычные символы, которые записываются без преобразования в файл. Форматы, как и в случае функции fscanf, начинаются с символа процента "%". Они аналогичны форматам, используемым функцией fscanf. Небольшое отличие заключается в том, что форматы функции fprintf позволяют также управлять представлением данных, например, указывать количество позиций, отводимых под запись числа, или количество цифр после десятичной точки при выводе вещественного числа. Некоторые типичные примеры форматов для вывода приведены в следующей таблице:
| %d | вывод целого десятичного числа |
| %10d | вывод целого десятичного числа, для записи числа отводится 10 позиций, запись при необходимости дополняется пробелами слева |
| %lf | вывод вещественного число типа double в форме с фиксированной десятичной точкой |
| %.3lf | вывод вещественного число типа double с печатью трёх знаков после десятичной точки |
| %12.3lf | вывод вещественного число типа double с тремя знаками после десятичной точки, под число отводится 12 позиций |
| %c | вывод одного символа |
| %s | конец строки, т.е. массива символов. Конец строки задается нулевым байтом |
int fprinf(FILE *f, const char *format, ...);
Многоточие, как и в случае функции fscanf, означает, что функция имеет переменное число аргументов. Количество и типы аргументов, начиная с третьего, должны соответствовать форматной строке. В отличие от функции fscanf, фактические аргументы, начиная с третьего, представляют собой выводимые значения, а не указатели на переменные.
Для примера рассмотрим небольшую программу, выводящую данные в файл "tmp.dat":
#include <stdio.h> // Описания функций ввода вывода #include <math.h> // Описания математических функций #include <string.h> // Описания функций работы со строками
int main() { int n = 4, m = 6; double x = 2.; char str[256] = "Print test"; FILE *f = fopen("tmp.dat", "wt"); // Открыть файл if (f == 0) { // для записи perror("Не могу открыть файл для записи"); return 1; // Завершить программу с кодом ошибки } fprintf(f, "n=%d, m=%d\n", m, n); fprintf(f, "x=%.4lf, sqrt(x)=%.4lf\n", x, sqrt(x)); fprintf( f, "Строка \"%s\" содержит %d символов.\n", str, strlen(str) ); fclose(f); // Закрыть файл return 0; // Успешное завершение программы }
В результате выполнения этой программы в файл "tmp.dat" будет записан следующий текст:
n=6, m=4 x=2.0000, sqrt(x)=1.4142 Строка "Print test" содержит 10 символов.
В последнем примере форматная строка содержит внутри себя двойные апострофы. Это специальные символы, выполняющие роль ограничителей строки, поэтому внутри строки их надо экранировать (т.е. защищать от интерпретации как специальных символов) с помощью обратной косой черты \, которая, напомним, в системе Unix и в языке Си выполняет роль защитного символа. Отметим также, что мы воспользовались стандартной функцией sqrt, вычисляющей квадратный корень числа, и стандартной функцией strlen, вычисляющей длину строки.
Функции бинарного чтения и записи fread и fwrite
После того как файл открыт, можно читать информацию из файла или записывать информацию в файл. Рассмотрим сначала функции бинарного чтения и записи fread и fwrite. Они называются бинарными потому, что не выполняют никакого преобразования информации при вводе или выводе (с одним небольшим исключением при работе с текстовыми файлами, которое будет рассмотрено ниже): информация хранится в файле как последовательность байтов ровно в том виде, в котором она хранится в памяти компьютера.
Функции чтения fread имеет следующий прототип:
size_t fread( char *buffer, // Массив для чтения данных size_t elemSize, // Размер одного элемента size_t numElems, // Число элементов для чтения FILE *f // Указатель на структуру FILE );
Здесь size_t определен как беззнаковый целый тип в системных заголовочных файлах. Функция пытается прочесть numElems элементов из файла, который задается указателем f на структуру FILE, размер каждого элемента равен elemSize. Функция возвращает реальное число прочитанных элементов, которое может быть меньше, чем numElems, в случае конца файла или ошибки чтения. Указатель f должен быть возвращен функцией fopen в результате успешного открытия файла. Пример использования функции fread:
FILE *f; double buff[100]; size_t res;
f = fopen("tmp.dat", "rb"); // Открываем файл if (f == 0) { // При ошибке открытия файла // Напечатать сообщение об ошибке perror("Не могу открыть файл для чтения"); exit(1); // завершить работу с кодом 1 }
// Пытаемся прочесть 100 вещественных чисел из файла res = fread(buff, sizeof(double), 100, f); // res равно реальному количеству прочитанных чисел
В этом примере файл "tmp.dat" открывается на чтение как бинарный, из него читается 100 вещественных чисел размером 8 байт каждое. Функция fread возвращает реальное количество прочитанных чисел, которое меньше или равно, чем 100.
Функция fread читает информацию в виде потока байтов и в неизменном виде помещает ее в память. Следует различать текстовое представление чисел и их бинарное представление! В приведенном выше примере числа в файле должны быть записаны в бинарном виде, а не в виде текста.
Для текстового ввода чисел надо использовать функции ввода по формату, которые будут рассмотрены ниже.
Внимание! Открытие файла как текстового с помощью функции fopen, например,
FILE *f = fopen("tmp.dat", "rt");
вовсе не означает, что числа при вводе с помощью функции fopen будут преобразовываться из текстовой формы в бинарную! Из этого следует только то, что в операционных системах, в которых строки текстовых файлов разделяются парами символами "\r\n" (они имеют названия CR и LF - возврат каретки и продергивание бумаги, Carriage Return и Line Feed), при вводе такие пары символов заменяются на один символ "\n" (продергивание бумаги). Обратно, при выводе символ "\n" заменяется на пару "\r\n". Такими операционными системами являются MS DOS и MS Windows. В системе Unix строки разделяются одним символом "\n" (отсюда проистекает обозначение "\n", которое расшифровывается как new line). Таким образом, внутреннее представление текста всегда соответствует системе Unix, а внешнее - реально используемой операционной системе. Отметим также, что создатели операционной системы компьютеров Apple Macintosh выбрали, чтобы жизнь не казалась скучной, третий, отличный от двух предыдущих, вариант: текстовые строки разделяются одним символом "\r" возврат каретки!
Такое представление текстовых файлов восходит к тем уже далеким временам, когда еще не было компьютерных мониторов и для просмотра текста использовались электрифицированные пишущие машинки или посимвольные принтеры. Текстовый файл фактически представлял собой программу печати на пишущей машинке и, таким образом, содержал команды возврата каретки и продергивания бумаги в конце каждой строки.
Функция бинарной записи в файл fwrite аналогична функции чтения fread. Она имеет следующий прототип:
size_t fwrite( char *buffer, // Массив записываемых данных size_t elemSize, // Размер одного элемента size_t numElems, // Число записываемых элементов FILE *f // Указатель на структуру FILE );
Функция возвращает число реально записанных элементов, которое может быть меньше, чем numElems, если при записи произошла ошибка - например, не хватило свободного пространства на диске. Пример использования функции fwrite:
FILE *f; double buff[100]; size_t num; . . .
f = fopen("tmp.res", "wb"); // Открываем файл "tmp.res" if (f == 0) { // При ошибке открытия файла // Напечатать сообщение об ошибке perror("Не могу открыть файл для записи"); exit(1); // завершить работу программы с кодом 1 }
// Записываем 100 вещественных чисел в файл res = fwrite(buff, sizeof(double), 100, f); // В случае успеха res == 100
Функции scanf и printf ввода и вывода в стандартные потоки
Поскольку ввод из стандартного входного потока, по умолчанию назначенного на клавиатуру, и вывод в стандартный выходной поток, по умолчанию назначенный на экран терминала, используются особенно часто, библиотека функций ввода-вывода Си предоставляет для работы с этими потоками функции scanf и printf. Они отличаются от функций fscanf и fprintf только тем, что у них отсутствует первый аргумент, означающий поток ввода или вывода. Строка
scanf(format, ...); // Ввод из станд. входного потока
эквивалентна строке
fscanf(stdin, format, ...); // Ввод из потока stdin
Аналогично, строка
printf(format, ...); // Вывод в станд. выходной поток
эквивалентна строке
fprintf(stdout, format, ...); // Вывод в поток stdout
Функции текстового преобразования sscanf и sprintf
Стандартная библиотека ввода-вывода Си предоставляет также две замечательные функции sscanf и sprintf ввода и вывода не в файл или поток, а в строку символов (т.е. массив байтов), расположенную в памяти компьютера. Мнемоника названий функций следующая: в названии функции fscanf первая буква f означает файл (file), т.е. ввод производится из файла; соответственно, в названии функции sscanf первая буква s означает строку (string), т.е. ввод производится из текстовой строки. (Последняя буква f в названиях этих функций означает форматный). Первым аргументом функций sscanf и sprintf является строка (т.е. массив символов, ограниченный нулевым байтом), из которой производится ввод или в которую производится вывод. Эта строка как бы стоит на месте файла в функциях fscanf и fprintf.
Фунции sscanf и sprintf удобны для преобразования данных из текстового представления во внутреннее и обратно. Например, в результате выполнения фрагмента
char txt[256] = "-135.76"; double x; sscanf(txt, "%lf", &x);
текстовая запись вещественного числа, содержащаяся в строке txt, преобразуется во внутреннее представление вещественного числа, результат записывается в переменную x. Обратно, при выполнения фрагмента
char txt[256]; int x = 12345; sprintf(txt, "%d", x);
значение целочисленной переменной x будет преобразовано в текстовую форму и записано в строку txt, в результате строка будет содержать текст "12345", ограниченный нулевым байтом.
Для преобразования данных из текстового представления во внутреннее в стандартной библиотеке Си имеются также функции atoi и atof с прототипами
int atoi(const char *txt); // текст => int double atof(const char *txt); // текст => double
Функция atoi преобразует текстовое представление целого числа типа int во внутреннее. Соответственно, функция atof преобразует текстовое представление вещественного числа типа double. Мнемоника имен следующая:
atoi означает "character to integer";atof означает "character to float".
(В последнем случае float следует понимать как плавающее, т.е. вещественное, число, имеющее тип double, а вовсе не float! Тип float является атавизмом и практически не используется.)
Прототипы функций atoi и atof описаны в стандартном заголовочном файле "stdlib.h", а не "stdio.h", поэтому при их использовании надо подключать этот файл:
#include <stdlib.h>
(вообще-то, это можно делать всегда, поскольку "stdlib.h" содержит описания многих полезных функций, например, функции завершения программы exit, генератора случайных чисел rand и др.).
Отметим, что аналогов функции sprintf для обратного преобразования из внутреннего в текстовое представление в стандартной библиотеке Си нет. Компилятор Си фирмы Borland предоставляет функции itoa и ftoa, однако, эти функции не входят в стандарт и другими компиляторами не поддерживаются, поэтому пользоваться ими не следует.
Константа NULL
В приведенном выше примере при открытии файла функция fopen в случае ошибки возвращает нулевой указатель на структуру FILE. Чтобы проверить, произошла ли ошибка, следует сравнить возвращенное значение с нулевым указателем. Для наглядности стандартный заголовочный файл "stdio.h" определяет символическую константу NULL как нулевой указатель на тип void:
#define NULL ((void *) 0)
Сделано это вроде бы с благой целью: чтобы отличить число ноль от нулевого указателя. При этом язык Си, в котором контроль ошибок осуществляется недостаточно строго, позволяет сравнивать указатель общего типа void * с любым другим указателем. Между тем,в Си вместо константы NULL всегда можно использовать просто 0, и вряд ли от этого программа становится менее понятной. Более строгий язык C++ запрещает сравнение разных указателей, поэтому в случае C++ стандартный заголовочный файл определяет константу NULL как обычный ноль:
#define NULL 0
Автор языка C++ Б. Страуструп советует использовать обычный ноль 0 вместо символического обозначения NULL. Тем не менее, по традиции большинство программистов любят константу NULL.
Константа NULL не является частью языка Си или C++, и без подключения одного из стандартных заголовочных файлов, в котором она определяется, использовать ее нельзя. (По этой причине авторы языка Java добавили в язык ключевое слово null, записываемое строчными буквами.) Так что в случае Си или C++ безопаснее следовать совету Б. Страуструпа и использовать обычный ноль 0 вместо символической константы NULL.
Копирование строк
char *strcpy(char *dst, const char *src); копировать строку src в строку dst;
char *strncpy(char *dst, const char *src, size_t maxlen); копировать строку src в dst, не более maxlen символов;
char *strcat(char *dst, const char *src); копировать строку src в конец dst (конкатенация строк).
Определение типов символов
Библиотека Си предоставляет следующие функции для определения типа символов, описанные в стандартном заголовочном файле "ctype.h":
| int isdigit(int c); | символ c - цифра; |
| int isalpha(int c); |
c - латинская буква; |
| int isspace(int c); |
c - пробел, перевод строки и т.п.; |
| int ispunkt(int c); |
c - знак препинания; |
| int isupper(int c); |
c - прописная латинская буква; |
| int islower(int c); |
c - строчная латинская буква; |
| int toupper(int c); | если c -- лат. буква, то преобразовать c к прописной букве; |
| int tolower(int c); | если c -- лат. буква, то преобразовать c к строчной букве. |
Функции, начинающиеся с префикса is, возвращают ненулевое значение (т.е. истину), если символ с кодом c принадлежит указанному классу, и нулевое значение (ложь) в противном случае. Функции toupper и tolower преобразуют латинские буквы к верхнему или нижнему регистру, на остальных символах они действуют тождественно.
В качестве примера использования функции isspace модифицируем программу "wc.cpp", подсчитывающую число строк и символов в текстовом файле. Добавим в нее подсчет слов. Будем считать словами любые связные группы символов, разделенные пробелами, табуляциями или разделителями строк.
// // Файл "wc2.cpp" // Подсчет числа символов, слов и строк в текстовом файле // #include <stdio.h> // Описания функций ввода-вывода #include <ctype.h> // Описания типов символов
int main() { char fileName[256]; // Путь к файлу FILE *f; // Структура, описывающая файл int c; // Код введенного символа int numChars = 0; // Суммарное число символов := 0 int numLines = 0; // Суммарное число строк := 0 int numWords = 0; // Суммарное число слов := 0 bool readingWord = false; // Читаем слово := false
printf("Введите имя файла: "); scanf("%s", fileName);
f = fopen(fileName, "rb"); // Открываем файл if (f == 0) { // При ошибке открытия файла // Напечатать сообщение об ошибке perror("Не могу открыть файл для чтения"); return 1; // закончить работу программы с кодом 1 }
while ((c = fgetc(f)) != EOF) { // Читаем символ // Цикл продолжается, пока c != -1 (конец файла)
++numChars; // Увеличиваем число символов
// Подсчитываем число символов перевода строки if (c == '\n') { ++numLines; // Увеличиваем число строк }
// Подсчитываем число слов if (!isspace(c)) { // если c не пробел if (!readingWord) { // если не читаем слово ++numWords; // увеличить число слов readingWord = true; // читаем слово:=true } // конец если } else { // иначе readingWord = false;// читаем слово:=false } // конец если }
fclose(f);
// Печатаем результат printf("Число символов в файле = %d\n", numChars); printf("Число слов = %d\n", numWords); printf("Число строк = %d\n", numLines);
return 0; // Возвращаем код успешного завершения }
Пример выполнения программы wc2 в применении к собственному тексту, записанному в файле "wc2.cpp":
Введите имя файла: wc2.cpp Число символов в файле = 1998 Число слов = 260 Число строк = 57
Открытие файла: функция fopen
Для доступа к файлу применяется тип данных FILE. Это структурный тип, имя которого задано с помощью оператора typedef в стандартном заголовочном файле "stdio.h". Программисту не нужно знать, как устроена структура типа файл: ее устройство может быть системно зависимым, поэтому в целях переносимости программ обращаться явно к полям струтуры FILE запрещено. Тип данных "указатель на структуру FILE используется в программах как черный ящик: функция открытия файла возвращает этот указатель в случае успеха, и в дальнейшем все файловые функции применяют его для доступа к файлу.
Прототип функции открытия файла выглядит следующим образом:
FILE *fopen(const char *path, const char *mode);
Здесь path - путь к файлу (например, имя файла или абсолютный путь к файлу), mode - режим открытия файла. Строка mode может содержать несколько букв. Буква "r" (от слова read) означает, что файл открывается для чтения (файл должен существовать). Буква "w" (от слова write) означает запись в файл, при этом старое содержимое файла теряется, а в случае отсутствия файла он создается. Буква "a" (от слова append) означает запись в конец существующего файла или создание нового файла, если файл не существует.
В некоторых операционных системах имеются различия в работе с текстовыми и бинарными файлами (к таким системам относятся MS DOS и MS Windows; в системе Unix различий между текстовыми и бинарными файлами нет). В таких системах при открытии бинарного файла к строке mode следует добавлять букву "b" (от слова binary), а при открытии текстового файла -- букву "t" (от слова text). Кроме того, при открытии можно разрешить выполнять как операции чтения, так и записи; для этого используется символ + (плюс). Порядок букв в строке mode следующий: сначала идет одна из букв "r", "w", "a", затем в произвольном порядке могут идти символы "b", "t", "+". Буквы "b" и "t" можно использовать, даже если в операционной системе нет различий между бинарными и текстовыми файлами, в этом случае они просто игнорируются.
Значения символов в строке mode сведены в следующую таблицу:
| r | Открыть существующий файл на чтение |
| w | Открыть файл на запись. Старое содержимое файла теряется, в случае отсутствия файла он создаётся. |
| a | Открыть файл на запись. Если файл существует, то запись производится в его конец. |
| t | Открыть текстовый файл. |
| b | Открыть бинарный файл. |
| + | Разрешить и чтение, и запись. |
FILE *f, *g, *h; . . . // 1. Открыть текстовый файл "abcd.txt" для чтения f = fopen("abcd.txt", "rt");
// 2. Открыть бинарный файл "c:\Windows\Temp\tmp.dat" // для чтения и записи g = fopen("c:/Windows/Temp/tmp.dat", "wb+");
// 3. Открыть текстовый файл "c:\Windows\Temp\abcd.log" // для дописывания в конец файла h = fopen("c:\\Windows\\Temp\\abcd.log", "at");
Обратите внимание, что во втором случае мы используем обычную косую черту / для разделения директорий, хотя в системах MS DOS и MS Windows для этого принято использовать обратную косую черту \. Дело в том, что в операционной системе Unix и в языке Си, который является для нее родным, символ \ используется в качестве экранирующего символа, т.е. для защиты следующего за ним символа от интерпретации как специального. Поэтому во всех строковых константах Си обратную косую черту надо повторять дважды, как это и сделано в третьем примере. Впрочем, стандартная библиотека Си позволяет в именах файлов использовать нормальную косую черту вместо обратной; эта возможность была использована во втором примере.
В случае удачи функция fopen открытия файла возвращает ненулевой указатель на структуру типа FILE, описывающую параметры открытого файла. Этот указатель надо затем использовать во всех файловых операциях. В случае неудачи (например, при попытке открыть на чтение несуществующий файл) возвращается ненулевой указатель. При этом глобальная системная переменная errno, описанная в стандартном заголовочном файле "errno.h, содержит численный код ошибки.В случае неудачи при открытии файла этот код можно распечатать, чтобы получить дополнительную информацию:
#include <stdio.h> #include <errno.h> . . .
FILE *f = fopen("filnam.txt", "rt"); if (f == NULL) { printf( "Ошибка открытия файла с кодом %d\n", errno ); . . . }
Понятие потока ввода или вывода
В операционной системе Unix и в других системах, использующих идеи системы Unix (например, MS DOS и MS Windows), применяется понятие потока ввода или вывода. Поток представляет собой последовательность байтов. Различают потоки ввода и вывода. Программа может читать данные из потока ввода и выводить данные в поток вывода. Программы можно запускать в конвейере, когда поток вывода первой программы является потоком ввода второй программы и т.д. Для запуска двух программ в конвейере используется символ вертикальной черты | между именами программ в командной строке. Например, командная строка
ab | cd | ef
означает, что поток вывода программы ab направляется на вход программе cd, а поток вывода программы cd - на вход программе ef. По умолчанию, потоком ввода для программы является клавиатура, поток вывода назначен на терминал (или, как говорят программисты, на консоль). Потоки можно переправлять в файл или из файла, используя символы больше > и меньше <, которые можно представлять как воронки. Например, командная строка
abcd > tmp.res
перенаправляет выходной поток программы abcd в файл "tmp.res", т.е. данные будут выводиться в файл вместо печати на экране терминала. Соответственно, командная строка
abcd < tmp.dat
заставляет программу abcd читать исходные данные из файла "tmp.dat" вместо ввода с клавиатуры. Командная строка
abcd < tmp.dat > tmp.res
перенаправляет как входной, так и выходной потоки: входной назначается на файл "tmp.dat", выходной -- на файл "tmp.res".
В Си работа с потоком не отличается от работы с файлом. Доступ к потоку осуществляется с помощью переменной типа FILE *. В момент начала работы Си-программы открыты три потока:
stdin -- стандартный входной поток. По умолчанию он назначен на клавиатуру;
stdout -- стандартный выходной поток. По умолчанию он назначен на экран терминала;
stderr -- выходной поток для печати информации об ошибках. Он также назначен по умолчанию на экран терминала.
Переменные stdin, stdout, stderr являются глобальными, они описаны в стандартном заголовочном файле "stdio.h.
Операции файлового ввода- вывода могут использовать эти потоки, например, строка
fscanf(stdin, "%d", &n);
вводит значение целочисленной переменной n из входного потока. Строка
fprintf(stdout, "n = %d\n", n);
выводит значение переменой n в выходной поток. Строка
fprintf(stderr, "Ошибка при открытии файла\n");
выводит указанный текст в поток stderr, используемый обычно для печати сообщений об ошибках. Функция perror также выводит сообщения об ошибках в поток stderr.
По умолчанию, стандартный выходной поток и выходной поток для печати ошибок назначены на экран терминала. Однако операция перенаправления вывода в файл > действует только на стандартный выходной поток. Например, в результате выполнения командной строки
abcd > tmp.res
обычный вывод программы abcd будет записываться в файл "tmp.res", а сообщения об ошибках по-прежнему будут печататься на экране терминала. Для того чтобы перенаправить в файл "tmp.log" стандартный поток печати ошибок, следует использовать командную строку
abcd 2> tmp.log
(между двойкой и символом > не должно быть пробелов!). Двойка здесь означает номер перенаправляемого потока. Стандартный входной поток имеет номер 0, стандартный выходной поток - номер 1, стандартный поток печати ошибок - номер 2. Данная команда перенаправляет только поток stderr, поток stdout по-прежнему будет выводиться на терминал. Можно перенаправить потоки в разные файлы:
abcd 2> tmp.log > tmp.res
Таким образом, существование двух разных потоков вывода позволяет при необходимости отделить мух от котлет, т.е. направить нормальный вывод и вывод информации об ошибках в разные файлы.
Представление матриц и многомерных массивов
Специального типа данных матрица или многомерный массив в Си нет, однако, можно использовать массив элементов типа массив. Например, переменная a представляет матрицу размера 3?3 с вещественными элементами:
double a[3][3];
Элементы матрицы располагаются в памяти последовательно по строкам: сначала идут элементы строки с индексом 0, затем строки с индексом 1, в конце строки с индексом 2 (в программировании отсчет индексов всегда начинается с нуля, а не с единицы!). При этом выражение
a[i]
где i -- целая переменная, представляет собой указатель на начальный элемент i-й строки и имеет тип double*.
Для обращения к элементу матрицы надо записать его индексы в квадратных скобках, например, выражение
a[i][j]
представляет собой элемент матрицы a в строке с индексом i и столбце с индексом j. Элемент матрицы можно использовать в любом выражении как обычную переменную (например, можно читать его значение или присваивать новое).
Такая реализация матрицы удобна и максимально эффективна с точки зрения времени доступа к элементам. У нее только один существенный недостаток: так можно реализовать только матрицу, размер которой известен заранее. Язык Си не позволяет описывать массивы переменного размера, размер массива должен быть известен до начала работы программы еще на стадии компиляции.
Пусть нужна матрица, размер которой определяется во время работы программы. Тогда пространство под нее надо захватывать в динамической памяти с помощью функции malloc языка Си или оператора new языка C++ (см. раздел 3.7.3). При этом в динамической памяти захватывается линейный массив и возвращается указатель на него. Рассмотрим вещественную матрицу размером m строк на n столбцов. Захват памяти выполняется с помощью функции malloc языка Си
double *a; . . . a = (double *) malloc(m * n * sizeof(double));
или с помощью оператора new языка C++:
double *a; int m, n; . . . a = new double[m * n];
При этом считается, что элементы матрицы будут располагаться в массиве следующим образом: сначала идут элементы строки с индексом 0, затем элементы строки с индексом 1 и т.д., последними идут элементы строки с индексом m ? 1.
подсчет числа символов и строк в текстовом файле
В качестве содержательного примера использования рассмотренных выше функций файлового ввода приведем программу, которая подсчитывает число символов и строк в текстовом файле. Программа сначала вводит имя файла с клавиатуры. Для этого используется функция scanf ввода по формату из входного потока, для ввода строки применяется формат "%s. Затем файл открывается на чтение как бинарный (это означает, что при чтении не будет происходить никакого преобразования разделителей строк). Используя в цикле функцию чтения fread, мы считываем содержимое файла порциями по 512 байтов, каждый раз увеличивая суммарное число прочитанных символов. После чтения очередной порции сканируется массив прочитанных символов и подсчитывается число символов "\n" продергивания бумаги, которые записаны в концах строк текстовых файлов как в системе Unix, так и в MS DOS или MS Windows. В конце закрывается файл и печатается результат.
// // Файл "wc.cpp" // Подсчет числа символов и строк в текстовом файле // #include <stdio.h> // Описания функций ввода-вывода #include <stdlib.h> // Описание функции exit
int main() { char fileName[256]; // Путь к файлу FILE *f; // Структура, описывающая файл char buff[512]; // Массив для ввода символов size_t num; // Число прочитанных символов int numChars = 0; // Суммарное число символов := 0 int numLines = 0; // Суммарное число строк := 0 int i; // Переменная цикла
printf("Введите имя файла: "); scanf("%s", fileName);
f = fopen(fileName, "rb"); // Открываем файл на чтение if (f == 0) { // При ошибке открытия файла // Напечатать сообщение об ошибке perror("Не могу открыть файл для чтения"); exit(1); // закончить работу программы с кодом 1 // ошибочного завершения }
while ((num = fread(buff, 1, 512, f)) > 0) { // Читаем // блок из 512 символов. num -- число реально // прочитанных символов. Цикл продолжается, пока // num > 0
numChars += num; // Увеличиваем число символов
// Подсчитываем число символов перевода строки for (i = 0; i < num; ++i) { if (buff[i] == '\n') { ++numLines; // Увеличиваем число строк } } }
fclose(f);
// Печатаем результат printf("Число символов в файле = %d\n", numChars); printf("Число строк в файле = %d\n", numLines);
return 0; // Возвращаем код успешного завершения }
Пример выполнения программы: она применяется к собственному тексту, записанному в файле "wc.cpp.
Введите имя файла: wc.cpp Число символов в файле = 1635 Число строк в файле = 50
приведение матрицы к ступенчатому виду методом Гаусса
В качестве примера работы с матрицами рассмотрим алгоритм Гаусса приведения матрицы к ступенчатому виду. Метод Гаусса - один из основных результатов линейной алгебры и аналитической геометрии, к нему сводятся множество других теорем и методов линейной алгебры (теория и вычисление определителей, решение систем линейных уравнений, вычисление ранга матрицы и обратной матрицы, теория базисов конечномерных векторных пространств и т.д.).
Напомним, что матрица A с элементами aij
называется ступенчатой, если она обладает следующими двумя свойствами:
если в матрице есть нулевая строка, то все строки ниже нее также нулевые;пусть aij
не равное 0 -- первый ненулевой элемент в строке с индексом i, т.е. элементы ail = 0 при l < j. Тогда все элементы в j-м столбце ниже элемента aij
равны нулю, и все элементы левее и ниже aij
также равны нулю: akl = 0 при k > i и l =< j.
Ступенчатая матрица выглядит примерно так:
здесь тёмными квадратиками отмечены первые ненулевые элементы строк матрицы. Белым цветом изображаются нулевые элементы, серым цветом - произвольные элементы.
Алгоритм Гаусса использует элементарные преобразования матрицы двух типов.
Преобразование первого рода: две строки матрицы меняются местами, и при этом знаки всех элементов одной из строк изменяются на противоположные.
Преобразование второго рода: к одной строке матрицы прибавляется другая строка, умноженная на произвольное число.
Элементарные преобразования сохраняют определитель и ранг матрицы, а также множество решений линейной системы. Алгоритм Гаусса приводит произвольную матрицу элементарными преобразованиями к ступенчатому виду. Для ступенчатой квадратной матрицы определитель равен произведению диагональных элементов, а ранг - числу ненулевых строк (рангом по определению называется размерность линейной оболочки строк матрицы).
Метод Гаусса в математическом варианте состоит в следующем:
ищем сначала ненулевой элемент в первом столбце. Если все элементы первого столбца нулевые, то переходим ко второму столбцу, и так далее.
Если нашли ненулевой элемент в k- й строке, то при помощи элементарного преобразования первого рода меняем местами первую и k-ю строки, добиваясь того, чтобы первый элемент первой строки был отличен от нуля; используя элементарные преобразования второго рода, обнуляем все элементы первого столбца, начиная со второго элемента. Для этого от строки с номером k вычитаем первую строку, умноженную на коэффициент ak1/a11
.переходим ко второму столбцу (или j-му, если все элементы первого столбца были нулевыми), и в дальнейшем рассматриваем только часть матрицы, начиная со второй строки и ниже. Снова повторяем пункты 1) и 2) до тех пор, пока не приведем матрицу к ступенчатому виду.
Программистский вариант метода Гаусса имеет три отличия от математического:
индексы строк и столбцов матрицы начинаются с нуля, а не с единицы; недостаточно найти просто ненулевой элемент в столбце. В программировании все действия с вещественными числами производятся приближенно, поэтому можно считать, что точного равенства вещественных чисел вообще не бывает. Некоторые компиляторы даже выдают предупреждения на каждую операцию проверки равенства вещественных чисел. Поэтому вместо проверки на равенство нулю числа aij
следует сравнивать его абсолютную величину ?aij? с очень маленьким числом ? (например, ? = 0.00000001). Если ?aij? =< ?, то следует считать элемент aij
нулевым; при обнулении элементов j-го столбца, начиная со строки i + 1, мы к k-й строке, где k > i, прибавляем i-ю строку, умноженную на коэффициент r = -akj/aij
: r = -akj/aij. ak = ak + r * ai
Такая схема работает нормально только тогда, когда коэффициент r по абсолютной величине не превосходит единицы. В противном случае, ошибки округления умножаются на большой коэффициент и, таким образом, экспоненциально растут. Математики называют это явление неустойчивостью вычислительной схемы. Если вычислительная схема неустойчива, то полученные с ее помощью результаты не имеют никакого отношения к исходной задаче. В нашем случае схема устойчива, когда коэффициент r = -akj/aij
не превосходит по модулю единицы. Для этого должно выполняться неравенство
?aij? >= ?akj? при k > i
Отсюда следует, что при поиске разрешающего элемента в j-м столбце необходимо найти не первый попавшийся ненулевой элемент, а максимальный по абсолютной величине. Если он по модулю не превосходит ?, то считаем, что все элементы столбца нулевые; иначе меняем местами строки, ставя его на вершину столбца, и затем обнуляем столбец элементарными преобразованиями второго рода.
Ниже дан полный текст программы на Си, приводящей вещественную матрицу к ступенчатому виду. Функция, реализующая метод Гаусса, одновременно подсчитывает и ранг матрицы. Программа вводит размеры матрицы и ее элементы с клавиатуры и вызывает функцию приведения к ступенчатому виду. Затем программа печатает ступенчатый вид матрицы и ее ранг. В случае квадратной матрицы также вычисляется и печатается определитель матрицы, равный произведению диагональных элементов ступенчатой матрицы.
При реализации метода Гаусса используется схема построения цикла с помощью инварианта, см. раздел 1.5.2. В цикле меняются две переменные -- индекс строки i, 0 =< i < m - 1, и индекс столбца j, 0 =< j < n - 1. Инвариантом цикла является утверждение о том, что часть матрицы (математики говорят минор) в столбцах 0,1,...j - 1 приведена к ступенчатому виду и что первый ненулевой элемент в строке i - 1 стоит в столбце с индексом меньшим j. В теле цикла рассматривается только минор матрицы в строках i,...,m - 1 и столбцах j,...,n - 1. Сначала ищется максимальный по модулю элемент в j-м столбце. Если он по абсолютной величине не превосходит ?, то j увеличивается на единицу (считается, что столбец нулевой). Иначе перестановкой строк разрешающий элемент ставится на вершину j-го столбца минора, и затем столбец обнуляется элементарными преобразованиями второго рода. После этого оба индекса i и j увеличиваются на единицу. Алгоритм завершается, когда либо i = m, либо j = n. По окончании алгоритма значение переменной i равно числу ненулевых строк ступенчатой матрицы, т.е.
рангу исходной матрицы.
Для вычисления абсолютной величины вещественного числа x типа double мы пользуемся стандарной математической функцией fabs(x), описанной в стандартном заголовочном файле "math.h.
#include <stdio.h> // Описания функций ввода-вывода #include <math.h> // Описания математических функций #include <stdlib.h> // Описания функций malloc и free
// Прототип функции приведения матрицы // к ступенчатому виду. // Функция возвращает ранг матрицы int gaussMethod( int m, // Число строк матрицы int n, // Число столбцов матрицы double *a, // Адрес массива элементов матрицы double eps // Точность вычислений );
int main() { int m, n, i, j, rank; double *a; double eps, det;
printf("Введите размеры матрицы m, n: "); scanf("%d%d", &m, &n);
// Захватываем память под элементы матрицы a = (double *) malloc(m * n * sizeof(double));
printf("Введите элементы матрицы:\n"); for (i = 0; i < m; ++i) { for (j = 0; j < n; ++j) { // Вводим элемент с индексами i, j scanf("%lf", &(a[i*n + j])); } }
printf("Введите точность вычислений eps: "); scanf("%lf", &eps);
// Вызываем метод Гаусса rank = gaussMethod(m, n, a, eps);
// Печатаем ступенчатую матрицу printf("Ступенчатый вид матрицы:\n"); for (i = 0; i < m; ++i) { // Печатаем i-ю строку матрицы for (j = 0; j < n; ++j) { printf( // Формат %10.3lf означает 10 "%10.3lf ", // позиций на печать числа, a[i*n + j] // 3 знака после точки ); } printf("\n"); // Перевести строку }
// Печатаем ранг матрицы printf("Ранг матрицы = %d\n", rank);
if (m == n) { // Для квадратной матрицы вычисляем и печатаем // ее определитель det = 1.0; for (i = 0; i < m; ++i) { det *= a[i*n + i]; } printf("Определитель матрицы = %.3lf\n", det); }
free(a); // Освобождаем память return 0; // Успешное завершение программы }
// Приведение вещественной матрицы // к ступенчатому виду методом Гаусса с выбором // максимального разрешающего элемента в столбце. // Функция возвращает ранг матрицы int gaussMethod( int m, // Число строк матрицы int n, // Число столбцов матрицы double *a, // Адрес массива элементов матрицы double eps // Точность вычислений ) { int i, j, k, l; double r;
i = 0; j = 0; while (i < m && j < n) { // Инвариант: минор матрицы в столбцах 0..j-1 // уже приведен к ступенчатому виду, и строка // с индексом i-1 содержит ненулевой эл-т // в столбце с номером, меньшим чем j
// Ищем максимальный элемент в j-м столбце, // начиная с i-й строки r = 0.0; for (k = i; k < m; ++k) { if (fabs(a[k*n + j]) > r) { l = k; // Запомним номер строки r = fabs(a[k*n + j]); // и макс. эл-т } } if (r <= eps) { // Все элементы j-го столбца по абсолютной // величине не превосходят eps. // Обнулим столбец, начиная с i-й строки for (k = i; k < m; ++k) { a[k*n + j] = 0.0; } ++j; // Увеличим индекс столбца continue; // Переходим к следующей итерации }
if (l != i) { // Меняем местами i-ю и l-ю строки for (k = j; k < n; ++k) { r = a[i*n + k]; a[i*n + k] = a[l*n + k]; a[l*n + k] = (-r); // Меняем знак строки } }
// Утверждение: fabs(a[i*n + k]) > eps
// Обнуляем j- й столбец, начиная со строки i+1, // применяя элем. преобразования второго рода for (k = i+1; k < m; ++k) { r = (-a[k*n + j] / a[i*n + j]);
// К k-й строке прибавляем i-ю, умноженную на r a[k*n + j] = 0.0; for (l = j+1; l < n; ++l) { a[k*n + l] += r * a[i*n + l]; } }
++i; ++j; // Переходим к следующему минору }
return i; // Возвращаем число ненулевых строк }
Приведем два примера работы этой программы. В первом случае вводится вырожденная матрица размера 4 ? 4:
Введите размеры матрицы m, n: 4 4 Введите элементы матрицы: 1 2 3 4 4 3 2 1 5 6 7 8 8 7 6 5 Введите точность вычислений eps: 0.00001 Ступенчатый вид матрицы: 8.000 7.000 6.000 5.000 0.000 1.625 3.250 4.875 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 Ранг матрицы = 2 Определитель матрицы = 0.000
Во втором случае вводится матрица размера 3 ? 4 максимального ранга:
Введите размеры матрицы m, n: 3 4 Введите элементы матрицы: 1 0 2 1 2 1 0 -1 1 0 1 0 Введите точность вычислений eps: 0.00001 Ступенчатый вид матрицы: 2.000 1.000 0.000 -1.000 0.000 0.500 -2.000 -1.500 0.000 0.000 -1.000 -1.000 Ранг матрицы = 3
программа "Записная книжка"
В качестве примера работы с текстовой информацией рассмотрим программу "Записная книжка". Записная книжка хранит имена людей и их телефоны. Под именем понимается полное имя, включающее фамилию, имя, отчество в произвольном формате: имя представляется любой текстовой строкой. Телефон также представляется текстовой строкой (представление с помощью целого числа не подходит, потому что номер может быть очень длинным и содержать специальные символы, например, знак плюс).
Программа позволяет добавлять записи в записную книжку, удалять записи и искать номер телефона по имени. При поиске не обязательно вводить имя полностью, достаточно нескольких первых символов. Можно также распечатать содержимое всей записной книжки. В перерывах между запусками программы информация сохраняется в файле "NoteBook.dat".
Записная книжка соответствует структуре данных нагруженное множество, которая будет рассмотрена в разделе 4.6.1. и для которой имеется ряд реализаций, обеспечивающих быстрый поиск и модификацию. Мы, однако, ограничимся сейчас простейшей реализацией: не упорядочиваем записи по алфавиту и применяем последовательный поиск. Записи хранятся в массиве, его максимальный размер равен 1000 элементов. Новая запись добавляется в конец массива. При удалении записи из книжки последняя запись переписывается на место удаленной.
Для записей используется структурный тип NameRecord, определенный следующим образом:
typedef struct { char *name; char *phone; } NameRecord;
Здесь поле name структуры является указателем на имя абонента, которое представляет собой текстовую строку. Номер телефона также задается строкой, указатель на которую записывается в поле phone. Пространство под строки захватывается в динамической памяти с помощью функции malloc. При удалении записи память освобождается с помощью функции free.
Записи хранятся в массиве records:
const int MAXNAMES = 1000; static NameRecord records[MAXNAMES]; static int numRecords = 0;
Константа MAXNAMES задает максимально возможный размер массива records.
Текущее количество записей (т.е. реальный размер массива) хранится в переменной numRecords.
В начале работы программа вводит содержимое записной книжки из файла "NoteBook.dat, имя которого задается как константный указатель на константную строку:
const char* const NoteBookFile = "NoteBook.dat";
В конце работы содержимое записной книжки сохраняется в файле. Для ввода используется функция loadNoteBook, для сохранения - функция saveNoteBook с прототипами
static bool loadNoteBook(); static bool saveNoteBook();
Каждой записи соответствует пара строк файла. Пусть, например, имя абонента "Иван Петров, телефон - "123-45-67". Этой записи соответствует пара строк
name=Иван Петров phone=123-45-67
Записи в файле разделяются пустыми строками.
Сохранение файла выполняется только в случае, когда содержимое записной книжки изменялось в процессе работы. За это отвечает переменная
static bool modified;
которая принимает значение true, если хотя бы раз была выполнена одна из команд, меняющих содержимое записной книжки.
Работа с записной книжкой происходит в интерактивном режиме. Пользователь вводит команду, программа ее выполняет. При выполнении команды программа просит ввести дополнительную информацию, если это необходимо, и печатает результат выполнения. Команды записываются латинскими буквами, чтобы исключить возможные проблемы с русскими кодировками. После команды может идти имя абонента. Реализованы следующие команды:
add - добавить запись. Программа просит ввести имя абонента, если оно не указано непосредственно после команды, затем его телефон, после этого запись добавляется в записную книжку, или телефон изменяется, если данное имя уже содержится в книжке;
remove - удалить запись. Программа просит ввести имя абонента, если оно не указано непосредственно после команды, и удаляет запись из книжки, если она там присутствует;
find - найти запись. Программа при необходимости просит ввести имя абонента и печатает либо его телефон, либо сообщение, что данного имени в книжке нет;
modify - изменить номер телефона. Программа просит ввести имя абонента, если оно не указано непосредственно после команды. Затем осуществляется поиск записи с данным именем. В случае успеха программа просит ввести новый номер телефона, после этого старый номер заменяется на новый; в противном случае, печатается сообщение, что имя не содержится в книжке;
show - напечатать записи, для которых имена начинаются с данного префикса. Если имя или начало имени не указано непосредственно после команды, то печатается все содержимое записной книжки. Если указано начало имени, то печатаются все записи, для которых начало имени совпадает с заданным;
help - напечатать подсказку;
quit - закончить работу.
Каждой команде соответствует отдельная функция, выполняющая команду. Например, команде add соответствует функция onAdd, команде find - функция onFind и т.д. Начало искомого имени и его длина, если имя указано в командной строке, передаются через статические переменные
static char namePrefix[256]; static int namePrefixLen;
Если имя не указано в командной строке, то для его ввода вызывается функция readName, которая просит пользователя ввести имя с клавиатуры, считывает имя и заполняет переменные namePrefix и namePrefixLen.
Для поиска записи с заданным началом имени используется функция search с прототипом
static int search( const char *namePrefix, // Начало искомого имени int startPosition // Позиция начала поиска );
Ей передается начало искомого имени и индекс элемента массива, с которого начинается поиск. Второй аргумент нужен для того, чтобы последовательно находить имена с одинаковым префиксом (например, имена, начинающиеся с заданной буквы). Функция возвращает индекс найденного элемента в случае успеха или отрицательное значение -1 при неудаче. Применяется последовательный поиск, при котором просматриваются все элементы, начиная со стартовой позиции. Для сравнения имен используется стандартная функция strncmp(s1, s2, n), которая сравнивает n первых символов строк s1 и s2.
При поиске в качестве s1 используется заданное начало имени, в качестве s2 -- очередное имя из записной книжке, n равно длине начала имени.
Для ввода строки с клавиатуры мы используем вспомогательную функцию readLine с прототипом
static bool readLine( char *buffer, int maxlen, int *len );
Функция вводит строку из стандартного входного потока, используя библиотечную функцию fgets. Затем из конца строки удаляются символы-разделители строк "\r" и "\n". Введенная строка помещается в массив buffer с максимальной длиной maxlen. Реальная длина введенной строки записывается в переменную, адрес которой передается через указатель len.
Полный текст программы:
// Файл "NoteBook.cpp" // Программа "Записная книжка" // #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h>
typedef struct { char *name; // Указатель на имя char *phone; // Указатель на телефон } NameRecord;
// Максимальный размер записной книжки const int MAXNAMES = 1000;
// Массив записей static NameRecord records[MAXNAMES];
// Текущее количество записей в книжке static int numRecords = 0;
// Имя файла для сохранения содержимого книжки const char* const NoteBookFile = "NoteBook.dat";
static bool modified; static char namePrefix[256]; // Начало имени, static int namePrefixLen; // его длина static char phone[256]; // Телефон, static int phoneLen; // его длина
// Прототипы функций static bool loadNoteBook(); // Загрузить книжку из файла static bool saveNoteBook(); // Сохранить книжку в файле static bool readLine( // Ввести строку с клавиатуры char *line, int maxlen, int *len ); static bool readName(); // Ввести имя с клавиатуры
static int search( // Поиск имени в массиве const char *namePrefix, // начало искомого имени int startPosition // позиция начала поиска );
static void releaseMemory(); // Освободить память
// Прототипы функций, реализующих команды static void onAdd(); static void onRemove(); static void onFind(); static void onModify(); static void onShow(); static void onHelp();
int main() { char line[256]; // Введенная строка int lineLen; // Длина строки int comBeg, // Индексы начала comEnd; // и за-конца команды int comLen; // Длина команды const char *command; // Указатель на начало команды int nameBeg; // Индекс начала имени int i; // Индекс в массиве line
printf("Программа \"Записная книжка\"\n"); onHelp(); // Напечатать подсказку
loadNoteBook(); // Загрузить содержимое книжки // из файла while (true) { printf(">"); // Приглашение на ввод команды
// Ввести командную строку if (!readLine(line, 256, &lineLen)) { break; // При ошибке завершить программу }
// Разбор командной строки // 1. Пропустить пробелы в начале строки i = 0; while (i < lineLen && isspace(line[i])) { ++i; }
// 2. Выделить команду comBeg = i; while (i < lineLen && isalpha(line[i])) { ++i; } comEnd = i;
command = line + comBeg; // Указ.начала команды comLen = comEnd - comBeg; // ее длина if (comLen <= 0) // Команда пустая => continue; // ввести следующую
// 3. Выделить префикс имени i = comEnd; // Пропустить пробелы перед именем while (i < lineLen && isspace(line[i])) { ++i; } nameBeg = i; if (nameBeg >= lineLen) { // Имя не указано в команде namePrefix[0] = 0; // Запомним, что имя namePrefixLen = 0; // пустое } else { // Имя задано в команде, запомним его. // Указ. на начало имени равен line+nameBeg, // длина имени равна lineLen-nameBeg. strcpy(namePrefix, line + nameBeg); namePrefixLen = lineLen - nameBeg; }
// Разбор строки закончен. // Вызовем функцию, реализующую команду if (strncmp(command, "add", comLen) == 0) { onAdd(); } else if ( strncmp(command, "remove", comLen) == 0 ) { onRemove(); } else if ( strncmp(command, "find", comLen) == 0 ) { onFind(); } else if ( strncmp(command, "modify", comLen) == 0 ) { onModify(); } else if ( strncmp(command, "show", comLen) == 0 ) { onShow(); } else if ( strncmp(command, "help", comLen) == 0 ) { onHelp(); } else if ( strncmp(command, "quit", comLen) == 0 ) { break; // Завершить работу } else { // Неправильная команда => onHelp(); // напечатать подсказку } } // конец цикла while
if (modified) { // Если книжка модифицирована, saveNoteBook(); // то сохранить ее содержимое }
releaseMemory(); // Освободить память return 0; // Завершить программу с кодом успеха }
static bool readLine( // Считать строку с клавиатуры char *line, int maxlen, int *len ) { int size;
*line = 0; *len = 0; // Инициализация пустой строкой if (fgets(line, maxlen, stdin) == 0) return false; // Ошибка ввода
size = strlen(line); // Длина введенной строки
// Удалить разделители строк из конца строки if (size > 0 && line[size - 1] == '\n') { line[size - 1] = 0; --size; } if (size > 0 && line[size - 1] == '\r') { line[size - 1] = 0; --size; }
*len = size; // Выдать длину строки return true; }
static int search( // Поиск имени в массиве const char *namePrefix, // искомый префикс имени int startPosition // позиция начала поиска ) { int i = startPosition; int len = strlen(namePrefix);
if (len == 0) return startPosition;
while (i < numRecords) { if ( strncmp( // Сравнить имя и префикс records[i].name, namePrefix, len ) == 0 ) { return i; // Нашли имя с данным префиксом } ++i; // К следующей записи } return (-1); // Имя не найдено }
static bool readName() { // Ввести имя с клавиатуры int size; printf("Введите имя:\n"); return readLine(namePrefix, 256, &namePrefixLen); }
static void onAdd() { // Добавить или изменить запись int i;
if (namePrefixLen == 0) { // Если имя не задано в if (!readName()) { // команде, то ввести его return; // Ошибка ввода } }
if (namePrefixLen == 0) { return; }
// Ищем имя в книжке i = search(namePrefix, 0); if (i < 0) { // Имя не содержится в книжке, добавим его if (numRecords >= MAXNAMES) { printf("Переполнение книжки.\n"); return; } i = numRecords; ++numRecords;
// Захватим память под имя records[i].name = (char *) malloc(namePrefixLen + 1); // Запишем имя в книжку strcpy(records[i].name, namePrefix); }
printf("Введите телефон:\n"); readLine(phone, 256, &phoneLen);
// Захватим память под телефон records[i].phone = (char *) malloc(phoneLen + 1); // Запишем телефон strcpy(records[i].phone, phone);
modified = true; // Запомним, что содержимое менялось }
static void onRemove() { // Удалить запись int i;
if (namePrefixLen == 0) { // Если имя не задано в if (!readName()) { // команде, то ввести его return; // Ошибка ввода } }
if (namePrefixLen == 0) { return; }
// Ищем имя в книжке i = search(namePrefix, 0); if (i < 0) { // Если имя не содержится в книжке, return; // то ничего не делать }
// Освободим память free(records[i].name); free(records[i].phone);
// Перепишем последнюю запись на место удаляемой if (i >= 2 && i != numRecords - 1) { records[i] = records[numRecords - 1]; } --numRecords; // Уменьшим число записей
modified = true; // Запомним, что содержимое менялось }
static void onFind() { // Найти запись int i; if (namePrefixLen == 0) { if (!readName()) { return; // Ошибка ввода } } i = search(namePrefix, 0); if (i < 0) { printf("Имя не найдено.\n"); } else { printf("Имя: %s\n", records[i].name); printf("Телефон: %s\n", records[i].phone); } }
static void onModify() { // Изменить номер телефона int i; if (namePrefixLen == 0) { if (!readName()) { return; // Ошибка ввода } } if (namePrefixLen == 0) { return; }
// Ищем имя в книжке i = search(namePrefix, 0); if (i < 0) { printf("Имя не найдено.\n"); } else { onAdd(); // Добавление модифицирует телефон, } // когда имя уже в книжке }
// Показать все записи с данным префиксом static void onShow() { int pos = 0; while (pos < numRecords) { if (namePrefixLen > 0) { pos = search(namePrefix, pos); if (pos < 0) { // Имя не найдено => break; // выйти из цикла } } printf("Имя: %s\n", records[pos].name); printf("Телефон: %s\n\n", records[pos].phone); ++pos; } }
static void onHelp() { printf( "Список команд:\n" " add добавить пару (имя, телефон)\n" " remove удалить имя\n" " find найти имя и напечатать телефон\n" " modify изменить телефон\n" " show напечатать записи с данным префиксом\n" " (если префикс пустой, то все записи)\n" " help напечатать этот текст\n" " quit закончить работу\n" ); printf("Введите команду и (не обязательно) имя.\n"); }
static bool loadNoteBook() { // Загрузить книжку из файла char line[256]; // Буфер для ввода строки int i; FILE *f = fopen(NoteBookFile, "rt"); if (f == 0) { return false; } numRecords = 0; while (fgets(line, 256, f) != 0) { int len = strlen(line); char *name; char *phone = 0;
// Удалим разделители строк if (len > 0 && line[len - 1] == '\n') { line[len - 1] = 0; --len; } if (len > 0 && line[len - 1] == '\r') { line[len - 1] = 0; --len; }
if (len < 6 || strncmp(line, "name=", 5) != 0) { continue; // К следующей строке }
// Запомним имя name = (char *) malloc((len - 5) + 1); strcpy(name, line + 5);
// Считаем строку с телефоном if (fgets(line, 256, f) != 0) { len = strlen(line); // Удалим разделители строк if (len > 0 && line[len - 1] == '\n') { line[len - 1] = 0; --len; } if (len > 0 && line[len - 1] == '\r') { line[len - 1] = 0; --len; } if ( len >= 7 && strncmp(line, "phone=", 6) == 0 ) { // Запомним телефон phone = (char *) malloc((len - 6) + 1); strcpy(phone, line + 6); } }
// Заполним новую запись records[numRecords].name = name; if (phone == 0) { phone = (char *) malloc(1); phone[0] = 0; // Пустая строка } records[numRecords].phone = phone; ++numRecords; // Увеличим число записей } return true; }
static bool saveNoteBook() { // Сохранить книжку в файле int i; FILE *f = fopen(NoteBookFile, "wt"); if (f == 0) { return false; } for (i = 0; i < numRecords; ++i) { fprintf(f, "name=%s\n", records[i].name); fprintf(f, "phone=%s\n\n", records[i].phone); } return true; }
static void releaseMemory() { int i; for (i = 0; i < numRecords; ++i) { free(records[i].name); free(records[i].phone); } }
Работа с файлами
Стандартная библиотека Си содержит набор функций для работы с файлами. Эти функции описаны в стандарте ANSI. Отметим, что файловый ввод-вывод не является частью языка Си, и ANSI-функции - не единственное средство ввода-вывода. Так, в операционной системе Unix более популярен другой набор функций ввода-вывода, который можно использовать не только для работы с файлами, но и для обмена по сети. В C++ часто используются библиотеки классов для ввода-вывода. Тем не менее, функции ANSI-библиотеки поддерживаются всеми Си-компиляторами, и потому программы, применяющие их, легко переносятся с одной платформы на другую. Прототипы функций ввода-вывода и используемые для этого типы данных описаны в стандартном заголовочном файле "stdio.h.
Работа с произвольными массивами байтов
void *memmove(void *dst, const void *src, size_t len); копировать область памяти с адресом src размером len байтов в область памяти с адресом dst;
void *memset(void *dst, int value, size_t len); записать значение value в каждый из len байтов, начиная с адреса dst.
Работа с текстами
Стандартная библиотека Си предоставляет набор функций для работы с текстами. К сожалению, большая часть из них ориентирована на представление символов в виде одного байта (во время разработки языка Си кодировка Unicode, в которой на символ отводится два байта, еще не существовала). Функции можно разделить на две группы:
функции, определяющие тип символа, - является ли он буквой, цифрой, пробелом, знаком препинания и т.п. Это функции описаны в стандартном заголовочном файле "ctype.h". Увы, функции, касающиеся букв, работают только для латинского алфавита; функции для работы с текстовыми строками. Строкой в Си считается последовательность байтов, ограниченная в конце нулевым байтом. Функции работы со строками описаны в стандартном заголовочном файле "string.h".
Работа с текстовыми строками
Стандартная библиотека Си предоставляет средства вычисления длины строки, копирования, сравнения, соединения (конкатенации) строк, поиска вхождений одной строки в другую. Функции описаны в стандартном заголовочном файле "string.h". Прототипы наиболее часто используемых функций приведены ниже.
Разработка больших проектов
До сих пор все рассмотренные примеры программ на Си имели небольшой объем (за исключением, возможно, программы Записная книжка). Такие маленькие программы помещаются в один файл. Однако реальные проекты имеют, как правило, значительно больший объем, измеряемый десятками, а чаще сотнями тысяч строк. Реализовать такую программу в виде одного непрерывного текста, помещающегося в одном файле, невозможно. Большой проект разбивается на более или менее независимые модули, которые можно написать и отладить по отдельности. Обычно в один такой модуль выделяется группа функций, работающих над общими глобальными данными и в той или иной мере связанных логически между собой. В простейшем случае каждому модулю соответствуют два файла с исходными текстами: заголовочный, или h-файл, описывающий интерфейс модуля, и файл реализации - c- или cpp-файл. Заголовочный файл содержит прототипы функций модуля, описания констант и глобальных переменных, структур, определения используемых типов и т.п. Файл реализации содержит определения глобальных переменных (т.е. их описания без слова extern), определения статических переменных, которые не экспортируются за пределы данного файла (т.е. описания со словом static), реализацию глобальных функций, а также описания прототипов и реализацию вспомогательных функций, которые не экспортируются за пределы файла.
Технология тестирования и отладки отдельного модуля предполагает использование заглушек вместо функций из других модулей, вызываемых функциями данного модуля, в том случае, когда другие модули еще не реализованы.
Существуют различные подходы к разбиению проекта на модули. Наиболее популярна технология сверху вниз, когда основной модуль реализуется на первом шаге на основе нескольких вспомогательных, интерфейс которых формулируется по мере реализации основного модуля. На следующем шаге реализуются вспомогательные модули, для этого придумываются новые вспомогательные модули более низкого уровня и т.д., пока не дойдем до базовых исполнителей.
Удобнее всего разрабатывать большие проекты в объектно-ориентированных языках (C++, Java, C#, Visual Basic и др.). В них имеются понятия класса и пространства имен, использование которых значительно облегчает создание больших проектов. Класс - это, говоря упрощенно, набор функций, которые работают над общими данными. Функции называются методами класса, а общие данные - членами класса. Объектно-ориентированный язык позволяет создавать объекты класса, т.е. однотипные наборы данных, соответствующие описанию класса. Пространством имен в C++ или пакетом в Java называется набор классов и функций, логически связанных между собой, реализуемых и используемых совместно. Отдельные классы или пространства имен соответствуют модулям, на которые разбивается проект.
Отметим, что, даже не используя объектно-ориентированного языка, можно придерживаться объектно-ориентированного стиля программирования, т.е. выделять группы функций и общие глобальные или статические данные, над которыми эти функции работают. Такие группы, подобно классам, реализуются и отлаживаются как отдельные структурные единицы.
Пример небольшого проекта "Стековый калькулятор" будет рассмотрен в следующей главе, посвященной структурам данных.
Сравнение строк
int strcmp(const char *s1, const char *s2); лексикографическое сравнение строк s1 и s2. Результат нулевой, если строки равны, отрицательный, если первая строка меньше второй, и положительный, если первая строка больше второй;
int strncmp(const char *s1, const char *s2, size_t maxlen); сравнение строк s1 и s2, сравнивается не более maxlen символов;
int memcmp(const void *m1, const void *m2, size_t len); сравнение областей памяти с адресами m1 и m2 размером len каждая.
Закрытие файла: функция fclose
По окончании работы с файлом его надо обязательно закрыть. Система обычно запрещает полный доступ к файлу до тех пор, пока он не закрыт. (Например, в нормальном режиме система запрещает одновременную запись в файл для двух разных программ.) Кроме того, информация реально записывается полностью в файл лишь в момент его закрытия. До этого она может содержаться в оперативной памяти (в так называемой файловой кеш-памяти), что при выполнении многочисленных операций записи и чтения значительно ускоряет работу программы.
Для закрытия файла используется функция fclose с прототипом
int fclose(FILE *f);
В случае успеха функция fclose возвращает ноль, при ошибке -- отрицательное значение (точнее, константу конец файла EOF, определенную в системных заголовочных файлах как минус единица). При ошибке можно воспользоваться функцией perror, чтобы напечатать причину ошибки. Отметим, что ошибка при закрытии файла - явление очень редкое (чего не скажешь в отношении открытия файла), так что анализировать значение, возвращаемое функцией fclose, в общем-то, не обязательно. Пример использования функции fclose:
FILE *f;
f = fopen("tmp.res", "wb"); // Открываем файл "tmp.res" if (f == 0) { // При ошибке открытия файла // Напечатать сообщение об ошибке perror("Не могу открыть файл для записи"); exit(1); // завершить работу программы с кодом 1 }
. . .
// Закрываем файл if (fclose(f) < 0) { // Напечатать сообщение об ошибке perror("Ошибка при закрытии файла"); }
