American National Standards Institute, разработавший стандарт на язык Си и его окружение. А. Богатырев, 1992-95 - 20 - Си в UNIX #include <stdio.h> main(){ int max, min, x, n; for( n=0; scanf("%d", &x) != EOF; n++) if( n == 0 ) min = max = x; else{ if( x > max ) max = x; if( x < min ) min = x; } printf( "Ввели %d чисел: min=%d max=%d\n", n, min, max); } Напишите аналогичную программу для поиска максимума и минимума среди элементов мас- сива, изначально min=max=array[0]; 1.49. Напишите программу, которая сортирует массив заданных чисел по возрастанию (убыванию) методом пузырьковой сортировки. Когда вы станете более опытны в Си, напи- шите сортировку методом Шелла. /* * Сортировка по методу Шелла. * Сортировке подвергается массив указателей на данные типа obj. * v------.-------.------.-------.------0 * ! ! ! ! * * * * * * элементы типа obj * Программа взята из книги Кернигана и Ритчи. */ #include <stdio.h> #include <string.h> #include <locale.h> #define obj char static shsort (v,n,compare) int n; /* длина массива */ obj *v[]; /* массив указателей */ int (*compare)(); /* функция сравнения соседних элементов */ { int g, /* расстояние, на котором происходит сравнение */ i,j; /* индексы сравниваемых элементов */ obj *temp; for( g = n/2 ; g > 0 ; g /= 2 ) for( i = g ; i < n ; i++ ) for( j = i-g ; j >= 0 ; j -= g ) { if((*compare)(v[j],v[j+g]) <= 0) break; /* уже в правильном порядке */ /* обменять указатели */ temp = v[j]; v[j] = v[j+g]; v[j+g] = temp; /* В качестве упражнения можете написать * при помощи curses-а программу, * визуализирующую процесс сортировки: * например, изображающую эту перестановку * элементов массива */ } } А. Богатырев, 1992-95 - 21 - Си в UNIX /* сортировка строк */ ssort(v) obj **v; { extern less(); /* функция сравнения строк */ int len; /* подсчет числа строк */ len=0; while(v[len]) len++; shsort(v,len,less); } /* Функция сравнения строк. * Вернуть целое меньше нуля, если a < b * ноль, если a == b * больше нуля, если a > b */ less(a,b) obj *a,*b; { return strcoll(a,b); /* strcoll - аналог strcmp, * но с учетом алфавитного порядка букв. */ } char *strings[] = { "Яша", "Федя", "Коля", "Гриша", "Сережа", "Миша", "Андрей Иванович", "Васька", NULL }; int main(){ char **next; setlocale(LC_ALL, ""); ssort( strings ); /* распечатка */ for( next = strings ; *next ; next++ ) printf( "%s\n", *next ); return 0; } 1.50. Реализуйте алгоритм быстрой сортировки. А. Богатырев, 1992-95 - 22 - Си в UNIX /* Алгоритм быстрой сортировки. Работа алгоритма "анимируется" * (animate-оживлять) при помощи библиотеки curses. * cc -o qsort qsort.c -lcurses -ltermcap */ #include "curses.h" #define N 10 /* длина массива */ /* массив, подлежащий сортировке */ int target [N] = { 7, 6, 10, 4, 2, 9, 3, 8, 5, 1 }; int maxim; /* максимальный элемент массива */ /* quick sort */ qsort (a, from, to) int a[]; /* сортируемый массив */ int from; /* левый начальный индекс */ int to; /* правый конечный индекс */ { register i, j, x, tmp; if( from >= to ) return; /* число элементов <= 1 */ i = from; j = to; x = a[ (i+j) / 2 ]; /* значение из середины */ do{ /* сужение вправо */ while( a[i] < x ) i++ ; /* сужение влево */ while( x < a[j] ) j--; if( i <= j ){ /* обменять */ tmp = a[i]; a[i] = a[j] ; a[j] = tmp; i++; j--; demochanges(); /* визуализация */ } } while( i <= j ); /* Теперь обе части сошлись в одной точке. * Длина левой части = j - from + 1 * правой = to - i + 1 * Все числа в левой части меньше всех чисел в правой. * Теперь надо просто отсортировать каждую часть в отдельности. * Сначала сортируем более короткую (для экономии памяти * в стеке ). Рекурсия: */ if( (j - from) < (to - i) ){ qsort( a, from, j ); qsort( a, i, to ); } else { qsort( a, i, to ); qsort( a, from, j ); } } А. Богатырев, 1992-95 - 23 - Си в UNIX int main (){ register i; initscr(); /* запуск curses-а */ /* поиск максимального числа в массиве */ for( maxim = target[0], i = 1 ; i < N ; i++ ) if( target[i] > maxim ) maxim = target[i]; demochanges(); qsort( target, 0, N-1 ); demochanges(); mvcur( -1, -1, LINES-1, 0); /* курсор в левый нижний угол */ endwin(); /* завершить работу с curses-ом */ return 0; } #define GAPY 2 #define GAPX 20 /* нарисовать картинку */ demochanges(){ register i, j; int h = LINES - 3 * GAPY - N; int height; erase(); /* зачистить окно */ attron( A_REVERSE ); /* рисуем матрицу упорядоченности */ for( i=0 ; i < N ; i++ ) for( j = 0; j < N ; j++ ){ move( GAPY + i , GAPX + j * 2 ); addch( target[i] >= target[j] ? '*' : '.' ); addch( ' ' ); /* Рисовать '*' если элементы * идут в неправильном порядке. * Возможен вариант проверки target[i] > target[j] */ } attroff( A_REVERSE ); /* массив */ for( i = 0 ; i < N ; i++ ){ move( GAPY + i , 5 ); printw( "%4d", target[i] ); height = (long) h * target[i] / maxim ; for( j = 2 * GAPY + N + (h - height) ; j < LINES - GAPY; j++ ){ move( j, GAPX + i * 2 ); addch( '|' ); } } refresh(); /* проявить картинку */ sleep(1); } А. Богатырев, 1992-95 - 24 - Си в UNIX 1.51. Реализуйте приведенный фрагмент программы без использования оператора goto и без меток. if ( i > 10 ) goto M1; goto M2; M1: j = j + i; flag = 2; goto M3; M2: j = j - i; flag = 1; M3: ; Заметьте, что помечать можно только оператор (может быть пустой); поэтому не может встретиться фрагмент { ..... Label: } а только { ..... Label: ; } 1.52. В каком случае оправдано использование оператора goto? Ответ: при выходе из вложенных циклов, т.к. оператор break позволяет выйти только из самого внутреннего цикла (на один уровень). 1.53. К какому if-у относится else? if(...) ... if(...) ... else ... Ответ: ко второму (к ближайшему предшествующему, для которого нет другого else). Вообще же лучше явно расставлять скобки (для ясности): if(...){ ... if(...) ... else ... } if(...){ ... if(...) ... } else ... 1.54. Макроопределение, чье тело представляет собой последовательность операторов в {...} скобках (блок), может вызвать проблемы при использовании его в условном опера- торе if с else-частью: #define MACRO { x=1; y=2; } if(z) MACRO; else .......; Мы получим после макрорасширения if(z) { x=1; y=2; } /* конец if-а */ ; else .......; /* else ни к чему не относится */ то есть синтаксически ошибочный фрагмент, так как должно быть либо if(...) один_оператор; else ..... либо if(...){ последовательность; ...; операторов; } else ..... где точка-с-запятой после } не нужна. С этим явлением борются, оформляя блок {...} в виде do{...}while(0) #define MACRO do{ x=1; y=2; }while(0) Тело такого "цикла" выполняется единственный раз, при этом мы получаем правильный текст: А. Богатырев, 1992-95 - 25 - Си в UNIX if(z) do{ x=1; y=2; }while(0); else .......; 1.55. В чем ошибка (для знающих язык "Паскаль")? int x = 12; if( x < 20 and x > 10 ) printf( "O'K\n"); else if( x > 100 or x < 0 ) printf( "Bad x\n"); else printf( "x=%d\n", x); Напишите #define and && #define or || 1.56. Почему программа зацикливается? Мы хотим подсчитать число пробелов и табуля- ций в начале строки: int i = 0; char *s = " 3 spaces"; while(*s == ' ' || *s++ == '\t') printf( "Пробел %d\n", ++i); Ответ: логические операции || и && выполняются слева направо; как только какое-то условие в || оказывается истинным (а в && ложным) - дальнейшие условия просто не вычисляются. В нашем случае условие *s==' ' сразу же верно, и операция s++ из второго условия не выполняется! Мы должны были написать хотя бы так: while(*s == ' ' || *s == '\t'){ printf( "Пробел %d\n", ++i); s++; } С другой стороны, это свойство || и && черезвычайно полезно, например: if( x != 0.0 && y/x < 1.0 ) ... ; Если бы мы не вставили проверку на 0, мы могли бы получить деление на 0. В данном же случае при x==0 деление просто не будет вычисляться. Вот еще пример: int a[5], i; for(i=0; i < 5 && a[i] != 0; ++i) ...; Если i выйдет за границу массива, то сравнение a[i] с нулем уже не будет вычисляться, т.е. попытки прочесть элемент не входящий в массив не произойдет. Это свойство && позволяет писать довольно неочевидные конструкции, вроде if((cond) && f()); что оказывается эквивалентным if( cond ) f(); Вообще же if(C1 && C2 && C3) DO; эквивалентно if(C1) if(C2) if(C3) DO; и для "или" А. Богатырев, 1992-95 - 26 - Си в UNIX if(C1 || C2 || C3) DO; эквивалентно if(C1) goto ok; else if(C2) goto ok; else if(C3){ ok: DO; } Вот еще пример, пользующийся этим свойством || #include <stdio.h> main(argc, argv) int argc; char *argv[]; { FILE *fp; if(argc < 2 || (fp=fopen(argv[1], "r")) == NULL){ fprintf(stderr, "Плохое имя файла\n"); exit(1); /* завершить программу */ } ... } Если argc==1, то argv[1] не определено, однако в этом случае попытки открыть файл с именем argv[1] просто не будет предпринято! Ниже приведен еще один содержательный пример, представляющий собой одну из воз- можных схем написания "двуязычных" программ, т.е. выдающих сообщения на одном из двух языков по вашему желанию. Проверяется переменная окружения MSG (или LANG): ЯЗЫК: 1) "MSG=engl" английский 2) MSG нет в окружении английский 3) "MSG=rus" русский Про окружение и функцию getenv() смотри в главе "Взаимодействие с UNIX", про strchr() - в главе "Массивы и строки". #include <stdio.h> int _ediag = 0; /* язык диагностик: 1-русский */ extern char *getenv(), *strchr(); #define ediag(e,r) (_ediag?(r):(e)) main(){ char *s; _ediag = ((s=getenv("MSG")) != NULL && strchr("rRрР", *s) != NULL); printf(ediag("%d:english\n", "%d:русский\n"), _ediag); } Если переменная MSG не определена, то s==NULL и функция strchr(s,...) не вызывается (ее первый фргумент не должен быть NULL-ом). Здесь ее можно было бы упрощенно заме- нить на *s=='r'; тогда если s равно NULL, то обращение *s было бы незаконно (обраще- ние по указателю NULL дает непредсказуемые результаты и, скорее всего, вызовет крах программы). 1.57. Иногда логическое условие можно сделать более понятным, используя правила де- Моргана: a && b = ! ( !a || !b ) a || b = ! ( !a && !b ) а также учитывая, что ! !a = a ! (a == b) = (a != b) Например: А. Богатырев, 1992-95 - 27 - Си в UNIX if( c != 'a' && c != 'b' && c != 'c' )...; превращается в if( !(c == 'a' || c == 'b' || c == 'c')) ...; 1.58. Пример, в котором используются побочные эффекты вычисления выражений. Обычно значение выражения присваивается некоторой переменной, но это не необходимо. Поэтому можно использовать свойства вычисления && и || в выражениях (хотя это не есть самый понятный способ написания программ, скорее некоторый род извращения). Ограничение тут таково: все части выражения должны возвращать значения. #include <stdio.h> extern int errno; /* код системной ошибки */ FILE *fp; int openFile(){ errno = 0; fp = fopen("/etc/inittab", "r"); printf("fp=%x\n", fp); return(fp == NULL ? 0 : 1); } int closeFile(){ printf("closeFile\n"); if(fp) fclose(fp); return 0; } int die(int code){ printf("exit(%d)\n", code); exit(code); return 0; } void main(){ char buf[2048]; if( !openFile()) die(errno); closeFile(); openFile() || die(errno); closeFile(); /* если файл открылся, то die() не вычисляется */ openFile() ? 0 : die(errno); closeFile(); if(openFile()) closeFile(); openFile() && closeFile(); /* вычислить closeFile() только если openFile() удалось */ openFile() && (printf("%s", fgets(buf, sizeof buf, fp)), closeFile()); } В последней строке использован оператор "запятая": (a,b,c) возвращает значение выра- жения c. 1.59. Напишите функцию, вычисляющую сумму массива заданных чисел. 1.60. Напишите функцию, вычисляющую среднее значение массива заданных чисел. 1.61. Что будет напечатано в результате работы следующего цикла? for ( i = 36; i > 0; i /= 2 ) printf ( "%d%s", i, i==1 ? ".\n":", "); А. Богатырев, 1992-95 - 28 - Си в UNIX Ответ: 36, 18, 9, 4, 2, 1. 1.62. Найдите ошибки в следующей программе: main { int i, j, k(10); for ( i = 0, i <= 10, i++ ){ k[i] = 2 * i + 3; for ( j = 0, j <= i, j++ ) printf ("%i\n", k[j]); } } Обратите внимание на формат %i, существует ли такой формат? Есть ли это тот формат, по которому следует печатать значения типа int? 1.63. Напишите программу, которая распечатывает элементы массива. Напишите прог- рамму, которая распечатывает элементы массива по 5 чисел в строке. 1.64. Составьте программу считывания строк символов из стандартного ввода и печати номера введенной строки, адреса строки в памяти ЭВМ, значения строки, длины строки. 1.65. Стилистическое замечание: в операторе return возвращаемое выражение не обяза- тельно должно быть в ()-скобках. Дело в том, что return - не функция, а оператор. return выражение; return (выражение); Однако если вы вызываете функцию (например, exit) - то аргументы должны быть в круг- лых скобках: exit(1); но не exit 1; 1.66. Избегайте ситуации, когда функция в разных ветвях вычисления то возвращает некоторое значение, то не возвращает ничего: int func (int x) { if( x > 10 ) return x*2; if( x == 10 ) return (10); /* а здесь - неявный return; без значения */ } при x < 10 функция вернет непредсказуемое значение! Многие компиляторы распознают такие ситуации и выдают предупреждение. 1.67. Напишите программу, запрашивающую ваше имя и "приветствующую" вас. Напишите функцию чтения строки. Используйте getchar() и printf(). Ответ: #include <stdio.h> /* standard input/output */ main(){ char buffer[81]; int i; printf( "Введите ваше имя:" ); while((i = getstr( buffer, sizeof buffer )) != EOF){ printf( "Здравствуй, %s\n", buffer ); printf( "Введите ваше имя:" ); } } getstr( s, maxlen ) char *s; /* куда поместить строку */ int maxlen; /* длина буфера: А. Богатырев, 1992-95 - 29 - Си в UNIX макс. длина строки = maxlen-1 */ { int c; /* не char! (почему ?) */ register int i = 0; maxlen--; /* резервируем байт под конечный '\0' */ while(i < maxlen && (c = getchar()) != '\n' && c != EOF ) s[i++] = c; /* обратите внимание, что сам символ '\n' * в строку не попадет */ s[i] = '\0'; /* признак конца строки */ return (i == 0 && c == EOF) ? EOF : i; /* вернем длину строки */ } Вот еще один вариант функции чтения строки: в нашем примере ее следует вызывать как fgetstr(buffer,sizeof(buffer),stdin); Это подправленный вариант стандартной функции fgets (в ней строки @1 и @2 обменяны местами). char *fgetstr(char *s, int maxlen, register FILE *fp){ register c; register char *cs = s; while(--maxlen > 0 && (c = getc(fp)) != EOF){ if(c == '\n') break; /* @1 */ *cs++ = c; /* @2 */ } if(c == EOF && cs == s) return NULL; /* Заметьте, что при EOF строка s не меняется! */ *cs = '\0'; return s; } Исследуйте поведение этих функций, когда входная строка слишком длинная (длиннее max- len). Замечание: вместо нашей "рукописной" функции getstr() мы могли бы использовать стандартную библиотечную функцию gets(buffer). 1.68. Объясните, почему d стало отрицательным и почему %X печатает больше F, чем в исходном числе? Пример выполнялся на 32-х битной машине. main(){ unsigned short u = 65535; /* 16 бит: 0xFFFF */ short d = u; /* 15 бит + знаковый бит */ printf( "%X %d\n", d, d); /* FFFFFFFF -1 */ } Указание: рассмотрите двоичное представление чисел (смотри приложение). Какие приве- дения типов здесь происходят? 1.69. Почему 128 превратилось в отрицательное число? main() { /*signed*/ char c = 128; /* биты: 10000000 */ unsigned char uc = 128; int d = c; /* используется 32-х битный int */ printf( "%d %d %x\n", c, d, d ); /* -128 -128 ffffff80 */ d = uc; printf( "%d %d %x\n", uc, d, d ); /* 128 128 80 */ } А. Богатырев, 1992-95 - 30 - Си в UNIX Ответ: при приведении char к int расширился знаковый бит (7-ой), заняв всю старшую часть слова. Знаковый бит int-а стал равен 1, что является признаком отрицательного числа. То же будет происходить со всеми значениями c из диапазона 128..255 (содержа- щими бит 0200). При приведении unsigned char к int знаковый бит не расширяется. Можно было поступить еще и так: printf( "%d\n", c & 0377 ); Здесь c приводится к типу int (потому что при использовании в аргументах функции тип char ВСЕГДА приводится к типу int), затем &0377 занулит старший байт полученного целого числа (состоящий из битов 1), снова превратив число в положительное. 1.70. Почему printf("%d\n", '\377' == 0377 ); printf("%d\n", '\xFF' == 0xFF ); печатает 0 (ложь)? Ответ: по той же причине, по которой printf("%d %d\n", '\377', 0377); печатает -1 255, а именно: char '\377' приводится в выражениях к целому расширением знакового бита (а 0377 - уже целое). 1.71. Рассмотрим программу #include <stdio.h> int main(int ac, char **av){ int c; while((c = getchar()) != EOF) switch(c){ case 'ы': printf("Буква ы\n"); break; case 'й': printf("Буква й\n"); break; default: printf("Буква с кодом %d\n", c); break; } return 0; } Она работает так: % a.out йфыв Буква с кодом 202 Буква с кодом 198 Буква с кодом 217 Буква с кодом 215 Буква с кодом 10 ^D % Выполняется всегда default, почему не выполняются case 'ы' и case 'й'? Ответ: русские буквы имеют восьмой бит (левый) равный 1. В case такой байт при- водится к типу int расширением знакового бита. В итоге получается отрицательное число. Пример: void main(void){ int c = 'й'; printf("%d\n", c); } печатает -54 А. Богатырев, 1992-95 - 31 - Си в UNIX Решением служит подавление расширения знакового бита: #include <stdio.h> /* Одно из двух */ #define U(c) ((c) & 0xFF) #define UC(c) ((unsigned char) (c)) int main(int ac, char **av){ int c; while((c = getchar()) != EOF) switch(c){ case U('ы'): printf("Буква ы\n"); break; case UC('й'): printf("Буква й\n"); break; default: printf("Буква с кодом %d\n", c); break; } return 0; } Она работает правильно: % a.out йфыв Буква й Буква с кодом 198 Буква ы Буква с кодом 215 Буква с кодом 10 ^D % Возможно также использование кодов букв: case 0312: но это гораздо менее наглядно. Подавление знакового бита необходимо также и в опера- торах if: int c; ... if(c == 'й') ... следует заменить на if(c == UC('й')) ... Слева здесь - signed int, правую часть компилятор тоже приводит к signed int. Прихо- дится явно говорить, что справа - unsigned. 1.72. Рассмотрим программу, которая должна напечатать числа от 0 до 255. Для этих чисел в качестве счетчика достаточен один байт: int main(int ac, char *av[]){ unsigned char ch; for(ch=0; ch < 256; ch++) printf("%d\n", ch); return 0; } Однако эта программа зацикливается, поскольку в момент, когда ch==255, это значение меньше 256. Следующим шагом выполняется ch++, и ch становится равно 0, ибо для char А. Богатырев, 1992-95 - 32 - Си в UNIX вычисления ведутся по модулю 256 (2 в 8 степени). То есть в данном случае 255+1=0 Решений существует два: первое - превратить unsigned char в int. Второе - вста- вить явную проверку на последнее значение диапазона. int main(int ac, char *av[]){ unsigned char ch; for(ch=0; ; ch++){ printf("%d\n", ch); if(ch == 255) break; } return 0; } 1.73. Подумайте, почему для unsigned a, b, c; a < b + c не эквивалентно a - b < c (первое - более корректно). Намек в виде примера (он выполнялся на 32-битной машине): a = 1; b = 3; c = 2; printf( "%u\n", a - b ); /* 4294967294, хотя в нормальной арифметике 1 - 3 = -2 */ printf( "%d\n", a < b + c ); /* 1 */ printf( "%d\n", a - b < c ); /* 0 */ Могут ли unsigned числа быть отрицательными? 1.74. Дан текст: short x = 40000; printf("%d\n", x); Печатается -25536. Объясните эффект. Указание: каково наибольшее представимое корот- кое целое (16 битное)? Что на самом деле оказалось в x? (лишние слева биты - обруба- ются). 1.75. Почему в примере double x = 5 / 2; printf( "%g\n", x ); значение x равно 2 а не 2.5 ? Ответ: производится целочисленное деление, затем в присваивании целое число 2 приводится к типу double. Чтобы получился ответ 2.5, надо писать одним из следующих способов: double x = 5.0 / 2; x = 5 / 2.0; x = (double) 5 / 2; x = 5 / (double) 2; x = 5.0 / 2.0; то есть в выражении должен быть хоть один операнд типа double. Объясните, почему следующие три оператора выдают такие значения: А. Богатырев, 1992-95 - 33 - Си в UNIX double g = 9.0; int t = 3; double dist = g * t * t / 2; /* 40.5 */ dist = g * (t * t / 2); /* 36.0 */ dist = g * (t * t / 2.0); /* 40.5 */ В каких случаях деление целочисленное, в каких - вещественное? Почему? 1.76. Странслируйте пример на машине с длиной слова int равной 16 бит: long n = 1024 * 1024; long nn = 512 * 512; printf( "%ld %ld\n", n, nn ); Почему печатается 0 0 а не 1048576 262144? Ответ: результат умножения (2**20 и 2**18) - это целое число; однако оно слишком велико для сохранения в 16 битах, поэтому старшие биты обрубаются. Получается 0. Затем в присваивании это уже обрубленное значение приводится к типу long (32 бита) - это все равно будет 0. Чтобы получить корректный результат, надо чтобы выражение справа от = уже имело тип long и сразу сохранялось в 32 битах. Для этого оно должно иметь хоть один операнд типа long: long n = (long) 1024 * 1024; long nn = 512 * 512L; 1.77. Найдите ошибку в операторе: x - = 4; /* вычесть из x число 4 */ Ответ: между `-' и `=' не должно быть пробела. Операция вида x @= expr; означает x = x @ expr; (где @ - одна из операций + - * / % ^ >> << & |), причем x здесь вычисляется единст- венный раз (т.е. такая форма не только короче и понятнее, но и экономичнее). Однако имеется тонкое отличие a=a+n от a+=n; оно заключается в том, сколько раз вычисляется a. В случае a+=n единожды; в случае a=a+n два раза. А. Богатырев, 1992-95 - 34 - Си в UNIX #include <stdio.h> static int x = 0; int *iaddr(char *msg){ printf("iaddr(%s) for x=%d evaluated\n", msg, x); return &x; } int main(){ static int a[4]; int *p, i; printf( "1: "); x = 0; (*iaddr("a"))++; printf( "2: "); x = 0; *iaddr("b") += 1; printf( "3: "); x = 0; *iaddr("c") = *iaddr("d") + 1; for(i=0, p = a; i < sizeof(a)/sizeof(*a); i++) a[i] = 0; *p++ += 1; for(i=0; i < sizeof(a)/sizeof(*a); i++) printf("a[%d]=%d ", i, a[i]); printf("offset=%d\n", p - a); for(i=0, p = a; i < sizeof(a)/sizeof(*a); i++) a[i] = 0; *p++ = *p++ + 1; for(i=0; i < sizeof(a)/sizeof(*a); i++) printf("a[%d]=%d ", i, a[i]); printf("offset=%d\n", p - a); return 0; } Выдача: 1: iaddr(a) for x=0 evaluated 2: iaddr(b) for x=0 evaluated 3: iaddr(d) for x=0 evaluated iaddr(c) for x=0 evaluated a[0]=1 a[1]=0 a[2]=0 a[3]=0 offset=1 a[0]=1 a[1]=0 a[2]=0 a[3]=0 offset=2 Заметьте также, что a[i++] += z; это a[i] = a[i] + z; i++; а вовсе не a[i++] = a[i++] + z; 1.78. Операция y = ++x; эквивалентна y = (x = x+1, x); а операция y = x++; эквивалентна y = (tmp = x, x = x+1, tmp); или y = (x += 1) - 1; где tmp - временная псевдопеременная того же типа, что и x. Операция `,' выдает А. Богатырев, 1992-95 - 35 - Си в UNIX значение последнего выражения из перечисленных (подробнее см. ниже). Пусть x=1. Какие значения будут присвоены x и y после выполнения оператора y = ++x + ++x + ++x; 1.79. Пусть i=4. Какие значения будут присвоены x и i после выполнения оператора x = --i + --i + --i; 1.80. Пусть x=1. Какие значения будут присвоены x и y после выполнения оператора y = x++ + x++ + x++; 1.81. Пусть i=4. Какие значения будут присвоены i и y после выполнения оператора y = i-- + i-- + i--; 1.82. Корректны ли операторы char *p = "Jabberwocky"; char s[] = "0123456789?"; int i = 0; s[i] = p[i++]; или *p = *++p; или s[i] = i++; или даже *p++ = f( *p ); Ответ: нет, стандарт не предусматривает, какая из частей присваивания вычисляется первой: левая или правая. Поэтому все может работать так, как мы и подразумевали, но может и иначе! Какое i используется в s[i]: 0 или уже 1 (++ уже сделан или нет), то есть int i = 0; s[i] = i++; это s[0] = 0; или же s[1] = 0; ? Какое p будет использовано в левой части *p: уже продвинутое или старое? Еще более эта идея драматизирована в s[i++] = p[i++]; Заметим еще, что в int i=0, j=0; s[i++] = p[j++]; такой проблемы не возникает, поскольку индексы обоих в частях присваивания незави- симы. Зато аналогичная проблема встает в if( a[i++] < b[i] )...; Порядок вычисления операндов не определен, поэтому неясно, что будет сделано прежде: взято значение b[i] или значение a[i++] (тогда будет взято b[i+1] ). Надо писать так, чтобы не полагаться на особенности вашего компилятора: if( a[i] < b[i+1] )...; или *p = *(p+1); i++; ++p; А. Богатырев, 1992-95 - 36 - Си в UNIX Твердо усвойте, что i++ и ++i не только выдают значения i и i+1 соответственно, но и изменяют значение i. Поэтому эти операторы НЕ НАДО использовать там, где по смыслу требуется i+1, а не i=i+1. Так для сравнения соседних элементов массива if( a[i] < a[i+1] ) ... ; /* верно */ if( a[i] < a[++i] ) ... ; /* неверно */ 1.83. Порядок вычисления операндов в бинарных выражениях не определен (что раньше вычисляется - левый операнд или же правый ?). Так пример int f(x,s) int x; char *s; { printf( "%s:%d ", s, x ); return x; } main(){ int x = 1; int y = f(x++, "f1") + f(x+=2, "f2"); printf("%d\n", y); } может печатать либо f1:1 f2:4 5 либо f2:3 f1:3 6 в зависимости от особенностей поведения вашего компилятора (какая из двух f() выпол- нится первой: левая или правая?). Еще пример: int y = 2; int x = ((y = 4) * y ); printf( "%d\n", x ); Может быть напечатано либо 16, либо 8 в зависимости от поведения компилятора, т.е. данный оператор немобилен. Следует написать y = 4; x = y * y; 1.84. Законен ли оператор f(x++, x++); или f(x, x++); Ответ: Нет, порядок вычисления аргументов функций не определен. По той же причине мы не можем писать f( c = getchar(), c ); а должны писать c = getchar(); f(c, c); (если мы именно это имели в виду). Вот еще пример: ... case '+': push(pop()+pop()); break; case '-': push(pop()-pop()); break; ... А. Богатырев, 1992-95 - 37 - Си в UNIX следует заменить на ... case '+': push(pop()+pop()); break; case '-': { int x = pop(); int y = pop(); push(y - x); break; } ... И еще пример: int x = 0; printf( "%d %d\n", x = 2, x ); /* 2 0 либо 2 2 */ Нельзя также struct pnt{ int x; int y; }arr[20]; int i=0; ... scanf( "%d%d", & arr[i].x, & arr[i++].y ); поскольку i++ может сделаться раньше, чем чтение в x. Еще пример: main(){ int i = 3; printf( "%d %d %d\n", i += 7, i++, i++ ); } который показывает, что на IBM PC |- и PDP-11 |= аргументы функций вычисляются справа налево (пример печатает 12 4 3). Впрочем, другие компиляторы могут вычислять их слева направо (как и подсказывает нам здравый смысл). 1.85. Программа печатает либо x=1 либо x=0 в зависимости от КОМПИЛЯТОРА - вычисля- ется ли раньше правая или левая часть оператора вычитания: #include <stdio.h> void main(){ int c = 1; int x = c - c++; printf( "x=%d c=%d\n", x, c ); exit(0); } Что вы имели в виду ? left = c; right = c++; x = left - right; или right = c++; left = c; x = left - right; А если компилятор еще и распараллелит вычисление left и right - то одна программа в разные моменты времени сможет давать разные результаты. ____________________ |- IBM ("Ай-би-эм") - International Buisiness Machines Corporation. Персональные компьютеры IBM PC построены на базе микропроцессоров фирмы Intel. |= PDP-11 - (Programmed Data Processor) - компьютер фирмы DEC (Digital Equipment Corporation), у нас известный как СМ-1420. Эта же фирма выпускает машину VAX. А. Богатырев, 1992-95 - 38 - Си в UNIX Вот еще достойная задачка: x = c-- - --c; /* c-----c */ 1.86. Напишите программу, которая устанавливает в 1 бит 3 и сбрасывает в 0 бит 6. Биты в слове нумеруются с нуля справа налево. Ответ: int x = 0xF0; x |= (1 << 3); x &= ~(1 << 6); В программах часто используют битовые маски как флаги некоторых параметров (признак - есть или нет). Например: #define A 0x08 /* вход свободен */ #define B 0x40 /* выход свободен */ установка флагов : x |= A|B; сброс флагов : x &= ~(A|B); проверка флага A : if( x & A ) ...; проверка, что оба флага есть: if((x & (A|B)) == (A|B))...; проверка, что обоих нет : if((x & (A|B)) == 0 )...; проверка, что есть хоть один: if( x & (A|B))...; проверка, что есть только A : if((x & (A|B)) == A)...; проверка, в каких флагах различаются x и y : diff = x ^ y; 1.87. В программах иногда требуется использовать "множество": каждый допустимый эле- мент множества имеет номер и может либо присутствовать в множестве, либо отсутство- вать. Число вхождений не учитывается. Множества принято моделировать при помощи битовых шкал: #define SET(n,a) (a[(n)/BITS] |= (1L <<((n)%BITS))) #define CLR(n,a) (a[(n)/BITS] &= ~(1L <<((n)%BITS))) #define ISSET(n,a) (a[(n)/BITS] & (1L <<((n)%BITS))) #define BITS 8 /* bits per char (битов в байте) */ /* Перечислимый тип */ enum fruit { APPLE, PEAR, ORANGE=113, GRAPES, RAPE=125, CHERRY}; /* шкала: n из интервала 0..(25*BITS)-1 */ static char fr[25]; main(){ SET(GRAPES, fr); /* добавить в множество */ if(ISSET(GRAPES, fr)) printf("here\n"); CLR(GRAPES, fr); /* удалить из множества */ } 1.88. Напишите программу, распечатывающую все возможные перестановки массива из N элементов. Алгоритм будет рекурсивным, например таким: в качестве первого элемента перестановки взять i-ый элемент массива. Из оставшихся элементов массива (если такие есть) составить все перестановки порядка N-1. Выдать все перестановки порядка N, получающиеся склейкой i-ого элемента и всех (по очереди) перестановок порядка N-1. Взять следующее i и все повторить. Главная проблема здесь - организовать оставшиеся после извлечения i-ого элемента элементы массива в удобную структуру данных (чтобы постоянно не копировать массив). Можно использовать, например, битовую шкалу уже выбранных элементов. Воспользуемся для этого макросами из предыдущего параграфа: А. Богатырев, 1992-95 - 39 - Си в UNIX /* ГЕНЕРАТОР ПЕРЕСТАНОВОК ИЗ n ЭЛЕМЕНТОВ ПО m */ extern void *calloc(unsigned nelem, unsigned elsize); /* Динамический выделитель памяти, зачищенной нулями. * Это стандартная библиотечная функция. * Обратная к ней - free(); */ extern void free(char *ptr); static int N, M, number; static char *scale; /* шкала выбранных элементов */ int *res; /* результат */ /* ... текст определений SET, CLR, ISSET, BITS ... */ static void choose(int ind){ if(ind == M){ /* распечатать перестановку */ register i; printf("Расстановка #%04d", ++number); for(i=0; i < M; i++) printf(" %2d", res[i]); putchar('\n'); return; } else /* Выбрать очередной ind-тый элемент перестановки * из числа еще не выбранных элементов. */ for(res[ind] = 0; res[ind] < N; ++res[ind]) if( !ISSET(res[ind], scale)) { /* элемент еще не был выбран */ SET(res[ind], scale); /* выбрать */ choose(ind+1); CLR(res[ind], scale); /* освободить */ } } void arrange(int n, int m){ res = (int *) calloc(m, sizeof(int)); scale = (char *) calloc((n+BITS-1)/BITS, 1); M = m; N = n; number = 0; if( N >= M ) choose(0); free((char *) res); free((char *) scale); } void main(int ac, char **av){ if(ac != 3){ printf("Arg count\n"); exit(1); } arrange(atoi(av[1]), atoi(av[2])); } Программа должна выдать n!/(n-m)! расстановок, где x! = 1*2*...*x - функция "факто- риал". По определению 0! = 1. Попробуйте переделать эту программу так, чтобы оче- редная перестановка печаталась по запросу: res = init_iterator(n, m); /* печатать варианты, пока о