Тема Управляющие конструкции языка С (продолжение) Лекция 27.09.11г. 1

ассоциирование операций
Преобразование (приведение) типов
Тема «Управляющие конструкции языка С»
Простые операторы и

блоки
Операторы простого выбора
Вложенные операторы выбора
Оператор множественного выбора switch
Операторы повторения (цикла): с предусловием, оператор for, с постусловием

и «досрочно» выйти за пределы цикла. Это можно сделать, разместив

в теле цикла оператор break. Это оператор вызывает «безусловный переход» в точку программы, расположенную непосредственно за циклом. Оператор break может использоваться в любом операторе цикла, а также в операторе множественного выбора switch.
Пример: программа удаляет «незначащие» символы в конце строки s.

#include
#include
int main() {
int n;
char s[] = "qwerty \t\t \n\n";
printf("before:\n");
printf("number of characters(%s) = %d\n", s, strlen(s));
for (n = strlen(s)-1; n >= 0; n--)
if (s[n] != ' ' && s[n] != '\t' && s[n] != '\n') break;
s[n+1] = '\0';
printf("after:\n");
printf("number of characters(%s) = %d\n", s, strlen(s));
system("PAUSE");
return 0;
}

от break, досрочно прекращает выполнение текущей итерации цикла, а не

всего оператора цикла. Для циклов while и do это означает переход к проверке условия, а для цикла for – вычисление выражения3, а уже затем переход к проверке условия.
Пример: подсчитать количество положительных элементов массива и найти их среднее арифметическое.

#include
#include
int main() {
int x[] = {-1, 4, 0, -3, -7, 5, 11, -2}, i, n;
double s;
for(i = 0, n = 0, s = 0.0; i < sizeof(x) / sizeof(x[0]); i++) {
if(x[i] <= 0) continue;
s += x[i]; n++;
}
if(n) s /= n;
printf("number of positive elements = %d\n", n);
printf("mean value = %f\n", s);
system("PAUSE");
return 0;
}

переход к оператору (в той же самой функции) перед которым

записана метка (обычное имя, заканчивающееся символом : - двоеточие).
Пример: проверить, имеют ли два массива хотя бы один общий элемент.

#include
#include
int main() {
int a[] = {-1, 4, 0, -3, -7, 5, 11, -2}, i;
int b[] = {7, -12, 8, 9, 11, -2}, j;
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (a[i] == b[j]) goto found;
printf("no common elements\n");
goto final;
found:
printf("common elements: a[%d] == b[%d]\n", i, j);
final: system("PAUSE");
return 0;
}

логическую структуру программы, однако бывают ситуации, когда программа без goto

получается более громоздкой, чем с goto.
Пример: предыдущая программа без goto.

#include
#include
int main() {
int a[] = {-1, 4, 0, -3, -7, 5, 11, -2}, i;
int b[] = {7, -12, 8, 9, 11, -2}, j, found = 0;
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
for (i = 0; i < n && !found; i++)
for (j = 0; j < m && !found; j++)
if (a[i] == b[j]) found = 1;
if (found)
printf("common elements: a[%d] == b[%d]\n", i, j);
else
printf("no common elements\n");
system("PAUSE");
return 0;
}

согласно которому программное средство - ПС (программа, библиотека, web-приложение и

др.) разделяется на отдельные сущности, называемые модулями. Модульность позволяет упростить задачи проектирования ПС и распределения процесса разработки ПС между группами разработчиков, а также позволяет реализовать методологию повторного использования кода.
При разбиении ПС на модули для каждого модуля указывается реализуемая им функциональность, а также связи с другими модулями. Роль модулей могут играть структуры данных, библиотеки функций, классы, сервисы и др. программные единицы, реализующие некоторую функциональность и предоставляющие интерфейс к ней.
В языке С модульность поддерживается функциями, препроцессоными командами, многофайловой структурой программы и заголовочными файлами.

более мелкие и позволяют инкапсулировать («упрятать» в оболочку) детали реализации

некоторой функциональности, предоставив пользователям («клиентам») формат обращения к этой функциональности (интерфейс). Это делает программу в целом более ясной и облегчает внесение в нее изменений.
Пример: функция, преобразующая символьное изображение числа, записанное в строке, в само число.

#include
int atoi_ (char s[]) {
int i, n, sign;
for (i = 0; isspace(s[i]); i++) ;
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '+' || s[i] == '-')
i++;
for (n = 0; isdigit(s[i]); i++)
n = 10 * n + (s[i] - '0');
return sign * n;
}

#include
#include
int atoi_ (char[]);
int main() {
int n = atoi_(" -347ab");
printf("n = %d\n", n);
system("PAUSE");
return 0;
}

интерфейс

реализация

описать её интерфейс (т.е. объяснить, как функцией можно воспользоваться) и

привести программный код, раскрывающий, как функция работает (т.е. записать реализацию функции на языке программирования).
Определение любой функции имеет следующую форму:
тип_возвращ_знач имя_функции(список_объявлений_арг) {
объявления и операторы
}
Различные части этого определения могут отсутствовать, но обязательными являются: имя_функции, пара круглых скобок и пара фигурных скобок, т.е. «минимальная» функция определяется так: fun(){} Это – «пустышка», которая не принимает никаких аргументов и ничего не делает (имеет пустое «тело»). Подобные функции могут использоваться в качестве «заглушек» при разработке программ.

Если при объявлении функции не указан тип возвращаемого значения, то по умолчанию подразумевается тип int.

и
функций.
Функции обмениваются данными посредством передачи аргументов и возвращения

значений, а также через внешние переменные.
Функции могут следовать друг за другом в файле исходного кода в любом порядке, и текст программы можно разбивать на любое количество файлов, но при этом запрещается разбивать текст функции между файлами.
Функция не может быть определена внутри другой функции
В результате своей работы функция может возвратить в вызывающую ее функцию результат – некоторое значение, тип которого объявлен перед именем функции. Для этого в теле функции должен присутствовать хотя бы один оператор возврата вида: return выражение; Вызывающая функция может игнорировать (т.е. не использовать) возвращаемое значение.
Существует еще одна форма оператора возврата: return; В этом случае в вызывающую функцию ничего не передается, а при определении функции в качестве типа возвращаемого значения указывается void.
Тело функции может не содержать оператора возврата return ; при этом возврат из функции происходит при достижении конца блока (закрывающей скобки } ).

т.е. функция получает значения своих аргументов в виде временных переменных,

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

#include
#include
void swap(int a, int b) {
int c = a;
a = b; b = c;
}
int main() {
int x = 5, y = 7;
printf("x = %d, y = %d\n",x,y);
swap(x, y);
printf("x = %d, y = %d\n",x,y);
system("PAUSE");
return 0;
}

#include
#include
void swap(int *a, int *b) {
int c = *a;
*a = *b; *b = c;
}
int main() {
int x = 5, y = 7;
printf("x = %d, y = %d\n",x,y);
swap(&x, &y);
printf("x = %d, y = %d\n",x,y);
system("PAUSE");
return 0;
}

условии: в любой программе обязательно должна присутствовать в точности одна

функция с именем main («главная» функция), т.к. запуск программы на выполнение операционной системой производится всегда через эту функцию (т.е. main начинает выполняться первой).
Функция main всегда имеет тип возвращаемого значения int, через это значение ОС уведомляется об успешности или не успешности завершения программы (т.н. «код завершения»). А т.к. int подразумевается «по умолчанию», то тип возвращаемого значения для main часто не указывают.
Существует две формы main:
без аргументов – main() и
с аргументами – main(int argc, char *argv[])
Вторая форма main позволяет при вызове программы из командной строки передать в нее произвольное количество строковых аргументов (об этом позже).

уравнений с двумя неизвестными:
ax + by = c ,

где - a, b, c, x, y – целые числа ; a и b - не нули.
К подобному уравнению сводится решение известной олимпиадной задачи: «Предположительно известно, что некоторый ценный предмет (золотой самородок) весит 20 граммов. Требуется убедиться в этом, взвесив его на обычных рычажных весах, но в нашем распоряжении имеются только гири двух типов – на 2 и на 7 граммов, по 5 штук каждого типа. Можно ли в этих условиях произвести взвешивание? Сколько гирь одного и другого типа нужно взять? Сколько существует вариантов взвешивания?»
Очевидно, что для получения ответа нужно, как минимум, решить уравнение:
2x + 7y = 20
Точнее говоря, найти множество решений …

a, b, c (a и b - не нули). Требуется

найти два целых числа x и y таких, что ax + by = c .
D1. [Нахождение наибольшего общего делителя a и b.] Пользуясь алгоритмом Евклида, найти g - наибольший общий делитель a и b.
D2. [Проверка существования решения.] Если с % g ≠ 0, то решения не существует и выполнение алгоритма прекращается.
DЗ. [Решение вспомогательного уравнения au + bv = g.] Пользуясь расширенным алгоритмом Евклида, найти u и v .
D4. [Получение результата.] Результатом решения исходного уравнения будут множества значений:
x = u*(c/g) – (b/g)*t,
y = v*(c/g) + (a/g)*t,
где t=0, ±1, ±2, …♦

Алгоритм Евклида был рассмотрен ранее. Рассмотрим расширенный алгоритм Евклида (алгоритм EE).

b (a и b - не нули). Требуется найти два

целых числа x и y таких, что ax + by = g (где g - наибольший общий делитель a и b).
EE1. [Установка начальных значений.] Положить x1=0, x2=1, y1=1, y2=0.
EE2. [Цикл с предусловием.] Если b = 0, то решение найдено и перейти к EE4.
EEЗ. [Тело цикла.] Вычислить: q=a/b, r=a-q*b, a=b, b=r, x=x2-q*x1, y=y2-q*y1, x2=x1, x1=x, y2=y1, y1=y . Перейти к шагу EE2.
EE4. [Получение результата.] Положить g=a, x=x2, y=y2 ♦

#include
#include
int main() {
int a, b, q, r, x1 = 0, x2 = 1, y1 = 1, y2 = 0;
int a0, b0, x, y, g;
printf("Input a: "); scanf("%d", &a); a0 = a;
printf("Input b: "); scanf("%d", &b); b0 = b;
while (b) {q = a / b;
r=a-q*b; a=b; b=r; x=x2-q*x1; y=y2-q*y1;
x2=x1; x1=x; y2=y1; y1=y;
}
g=a; x=x2; y=y2;
printf("Result: %d*(%d)+%d*(%d)=%d\n", a0,x,b0,y,g);
system("PAUSE");
return 0;
}

в виде функций языка С.
Алгоритм Е (модифицированный):
int euclid(int a, int

b) {
while (a && b)
if(a>=b) a%=b; else b%=a;
return a + b;
}

Алгоритм ЕЕ:

extern int x, y;
int e_euclid(int a, int b) {
int q, r, x1 = 0, x2 = 1, y1 = 1, y2 = 0;
while (b) {
q = a / b;
r=a-q*b; a=b; b=r;
x=x2-q*x1; y=y2-q*y1;
x2=x1; x1=x; y2=y1; y1=y;
}
x=x2; y=y2;
return a;
}

Замечание по поводу использования внешних переменных x и y.

в отдельные файлы и компилировать независимо. В этом случае основная

программа, которая и решает поставленную задачу, также размещается в отдельном файле и уже не содержит определений функций euclid(a,b) и e_euclid(a,b), а только лишь их объявления.

Более того, объявления функций, используемых в основной программе, можно поместить в самостоятельный заголовочный файл, который подключается к программе с помощью препроцессорной директивы #include.

y;
int euclid(int, int);
int e_euclid(int, int);
int main() {
int a,

b, c, g, u, v, t;
int x_max, y_max;
printf("Input a, b, c: "); scanf("%d%d%d", &a, &b, &c);
printf("Input x_max, y_max: "); scanf("%d%d", &x_max, &y_max);
if (c % euclid(a, b)) printf("***no solution\n");
else {
g = e_euclid(a, b);
for(t = -25; t <= 25; t++) {
if (fabs(u = x*(c/g) - t*(b/g)) > x_max) continue;
if (fabs(v = y*(c/g) + t*(a/g)) > y_max) continue;
printf("result: %d*(%d)+%d*(%d)=%d\n", a, u, b, v, c);
}
}
system("PAUSE");
return 0;
}

объявления функций

внешние переменные

вызовы функций

a, int b, int *x, int *y) {
int q,

r, x1 = 0, x2 = 1, y1 = 1, y2 = 0;
while (b) {
q = a / b;
r = a-q*b; a = b; b = r;
*x = x2-q*x1; *y = y2-q*y1;
x2=x1; x1=*x; y2=y1; y1=*y;
}
*x = x2; *y = y2;
return a;
}

b, c, g, u, v, t;
int x, y, x_max,

y_max;
int euclid(int, int), e_euclid(int, int, int*, int*);
printf("Input a, b, c: "); scanf("%d%d%d", &a, &b, &c);
printf("Input x_max, y_max: "); scanf("%d%d", &x_max, &y_max);
if (c % euclid(a, b)) printf("***no solution\n");
else {
g = e_euclid(a, b, &x, &y);
for(t = -25; t <= 25; t++) {
if (fabs(u = x*(c/g) - t*(b/g)) > x_max) continue;
if (fabs(v = y*(c/g) + t*(a/g)) > y_max) continue;
printf("result: %d*(%d)+%d*(%d)=%d\n", a, u, b, v, c);
}
}
system("PAUSE");
return 0;
}

объявления функций
можно поместить внутри main

вызовы функций

{
int a, b, c, g, u, v, t;
int

x, y, x_max, y_max;
printf("Input a, b, c: "); scanf("%d%d%d", &a, &b, &c);
printf("Input x_max, y_max: "); scanf("%d%d", &x_max, &y_max);
if (c % euclid(a, b)) printf("***no solution\n");
else {
g = e_euclid(a, b, &x, &y);
for(t = -T; t <= T; t++) {
if (fabs(u = x*(c/g) - t*(b/g)) > x_max) continue;
if (fabs(v = y*(c/g) + t*(a/g)) > y_max) continue;
printf("result: %d*(%d)+%d*(%d)=%d\n", a, u, b, v, c);
}
}
system("PAUSE");
return 0;
}

#define T 25
int euclid(int, int);
int e_euclid(int, int, int*, int*);

строка для компиляции такой программы:
gcc euclid.c e_euclid.c diophant.c -o diophant

вызывать саму себя прямо или косвенно.
Классический пример рекурсии – вычисление

факториала целого числа:

#include
#include
int fact(int n) {
return n ? n * fact(n-1) : 1;
}
main() {
int n;
for(n = 0; n < 10; n++)
printf("%2d! = %10d\n", n, fact(n));
system("PAUSE");
return 0;
}

разработанный английским учёным Чарльзом Энтони Ричардом Хоаром (C.A.R. Hoare) в

1962 г. Этот алгоритм на сегодняшний день является наиболее популярным алгоритмом сортировки.
Суть алгоритма: в сортируемом массиве берется произвольный элемент x и все остальные элементы разбиваются на два подмножества: элементы, меньшие x и элементы, большие или равные x. При этом x помещается на такую позицию массива, что слева от него располагаются элементы первого подмножества, а справа – второго. Затем процедура сортировки применяется рекурсивно к каждому из двух подмножеств. Если в подмножестве меньше двух элементов, сортировка ему не требуется и рекурсия на этом прекращается.

i, int j) {
int temp;
temp = v[i]; v[i]

= v[j]; v[j] = temp;
}
void qsort_(int v[], int left, int right) {
int i, last;
if (left >= right) return;
swap(v, left, (left + right)/2); last = left;
for (i = left + 1; i <= right; i++)
if (v[i] < v[left]) swap(v, ++last, i);
swap(v, left, last);
qsort_(v, left, last-1); qsort_(v, last+1, right);
}
main() {
int x[] = {8, 2, 6, 5, 4, 3, 7, 1};
int i, n = sizeof(x)/sizeof(x[0]);
printf("before: "); for (i = 0; i qsort_(x, 0, n-1);
printf("\nafter: "); for (i = 0; i system("PAUSE");
return 0;
}