Жанр: Учеба
Хрестоматия по программированию на Си в Unix
Андрей Богатырев. Хрестоматия по программированию на Си в Unix
T Copyright Андрей Богатырев. 1992-95
Email: abs@opentech.olvit.ru
Txt version is located at
---------------------------------------------------------------------------
А. Богатырев, 1992-95 - 1 - Си в UNIX
0. Напутствие в качестве вступления.
Ум подобен желудку.
Важно не то, сколько ты в него вложишь,
а то, сколько он сможет переварить.
В этой книге вы найдете ряд задач, примеров, алгоритмов, советов и стилистических
замечаний по использованию языка программирования "C" (Си) в среде операционной
системы UNIX. Здесь собраны этюды разной сложности и "штрихи к портрету" языка Си.
Также описаны различные "подводные камни" на которых нередко терпят крушение новички
в Си. В этом смысле эту книгу можно местами назвать "Как не надо программировать на
Си".
В большинстве случаев в качестве платформы используется персональный компьютер
IBM PC с какой-либо системой UNIX, либо SPARCstation 20 с системой Solaris 2 (тоже
UNIX svr4), но многие примеры без каких-либо изменений (либо с минимумом таковых)
могут быть перенесены в среду MS DOS[**], либо на другой тип машины с системой UNIX.
Это ваша ВТОРАЯ книга по Си. Эта книга не учебник, а хрестоматия к учебнику.
Она не является ни систематическим курсом по Си, ни справочником по нему, и предназначена
не для одноразового последовательного прочтения, а для чтения в несколько проходов
на разных этапах вашей "зрелости". Поэтому читать ее следует вместе с "настоящим"
учебником по Си, среди которых наиболее известна книга Кернигана и Ритчи.
Эта книга - не ПОСЛЕДНЯЯ ваша книга по Си. Во-первых потому, что кое-что в языке
все же меняется со временем, хотя и настал час, когда стандарт на язык Си наконец
принят... Но появился язык C++, который развивается довольно динамично. Еще есть
Objective-C. Во-вторых потому, что есть библиотеки и системные вызовы, которые развиваются
вслед за развитием UNIX и других операционных систем. Следующими вашими
(настольными) книгами должны стать "Справочное руководство": man2 (по системным вызовам),
man3 (по библиотечным функциям).
Мощь языка Си - в существующем многообразии библиотек.
Прошу вас с первых же шагов следить за стилем оформления своих программ. Делайте
отступы, пишите комментарии, используйте осмысленные имена переменных и функций,
отделяйте логические части программы друг от друга пустыми строками. Помните, что
"лишние" пробелы и пустые строки в Си допустимы везде, кроме изображений констант и
имен. Программы на Си, набитые в одну колонку (как на FORTRAN-e) очень тяжело читать
и понимать. Из-за этого бывает трудно находить потерянные скобки { и }, потерянные
символы `;' и другие ошибки.
Существует несколько "школ" оформления программ - приглядитесь к примерам в этой
книге и в других источниках - и выберите любую! Ничего страшного, если вы будете
смешивать эти стили. Но - ПОДАЛЬШЕ ОТ FORTRAN-а !!!
Программу можно автоматически сформатировать к "каноническому" виду при помощи,
например, программы cb.
cb " НашФайл.c " /tmp/$$
mv /tmp/$$ НашФайл.c
но лучше сразу оформлять программу правильно.
Выделяйте логически самостоятельные ("замкнутые") части программы в функции
(даже если они будут вызываться единственный раз). Функции - не просто средство
избежать повторения одних и тех же операторов в тексте программы, но и средство
структурирования процесса программирования, делающее программу более понятной. Вопервых,
вы можете в другой программе использовать текст уже написанной вами ранее
функции вместо того, чтобы писать ее заново. Во-вторых, операцию, оформленную в виде
функции, можно рассматривать как неделимый примитив (от довольно простого по смыслу,
вроде strcmp, strcpy, до довольно сложного - qsort, malloc, gets) и забыть о его
внутреннем устройстве (это хорошо - надо меньше помнить).
____________________
[**] MS DOS - торговый знак фирмы Microsoft Corporation. (читается "Майкрософт");
DOS - дисковая операционная система.
А. Богатырев, 1992-95 - 2 - Си в UNIX
Не гонитесь за краткостью в ущерб ясности. Си позволяет порой писать такие выражения,
над которыми можно полчаса ломать голову. Если же их записать менее мудрено,
но чуть длиннее - они самоочевидны (и этим более защищены от ошибок).
В системе UNIX вы можете посмотреть описание любой команды системы или функции
Си, набрав команду
man названиеФункции
(man - от слова manual, "руководство").
Еще одно напутствие: учите английский язык! Практически все языки программирования
используют английские слова (в качестве ключевых слов, терминов, имен переменных
и функций). Поэтому лучше понимать значение этих слов (хотя и восприятие их как
просто неких символов тоже имеет определенные достоинства). Обратно - программирование
на Си поможет вам выучить английский.
По различным причинам на территории России сейчас используется много разных
восьмибитных русских кодировок. Среди них:
КОИ-8
Исторически принятая на русских UNIX системах - самая ранняя из появившихся.
Отличается тем свойством, что если у нее обрезан восьмой бит: c & 0177 - то она
все же читаема с терминала как транслитерация латинских букв. Именно этой коди-
ровкой пользуется автор этой книги (как и большинство UNIX-sites сети RelCom).
ISO 8859/5
Это американский стандарт на русскую кодировку. А русские программисты к ее
разработке не имеют никакого отношения. Ею пользуется большинство коммерческих
баз данных.
Microsoft 1251
Это та кодировка, которой пользуется Microsoft Windows. Возможно, что именно к
этой кодировке придут и UNIX системы (гипотеза 1994 года).
Альтернативная кодировка для MS DOS
Русская кодировка с псевдографикой, использовавшаяся в MS DOS.
Кодировка для Macintosh
Это великое "разнообразие" причиняет массу неудобств. Но, господа, это Россия - что
значит - широта души и абсолютный бардак. Relax and enjoy.
Многие примеры в данной книге даны вместе с ответами - как образцами для подражания.
Однако мы надеемся, что Вы удержитесь от искушения и сначала проверите свои
силы, а лишь потом посмотрите в ответ! Итак, читая примеры - делайте по аналогии.
А. Богатырев, 1992-95 - 3 - Си в UNIX
1. Простые программы и алгоритмы. Сюрпризы, советы.
1.1. Составьте программу приветствия с использованием функции printf. По традиции
принято печатать фразу "Hello, world !" ("Здравствуй, мир !").
1.2. Найдите ошибку в программе
#include "stdio.h"
main(){
printf("Hello, world\n");
}
Ответ: раз не объявлено иначе, функция main считается возвращающей целое значение
(int). Но функция main не возвращает ничего - в ней просто нет оператора return.
Корректно было бы так:
#include "stdio.h"
main(){
printf("Hello, world\n");
return 0;
}
или
#include "stdio.h"
void main(){
printf("Hello, world\n");
exit(0);
}
а уж совсем корректно - так:
#include "stdio.h"
int main(int argc, char *argv[]){
printf("Hello, world\n");
return 0;
}
1.3. Найдите ошибки в программе
#include studio.h
main
{
int i
i := 43
print ('В году i недель')
}
1.4. Что будет напечатано в приведенном примере, который является частью полной
программы:
int n;
n = 2;
printf ("%d + %d = %d\n", n, n, n + n);
1.5. В чем состоят ошибки?
А. Богатырев, 1992-95 - 4 - Си в UNIX
if( x " 2 )
then x = 2;
if x " 1
x = 1;
Ответ: в Си нет ключевого слова then, условия в операторах if, while должны браться в
()-скобки.
1.6. Напишите программу, печатающую ваше имя, место работы и адрес. В первом варианте
программы используйте библиотечную функцию printf, а во втором - puts.
1.7. Составьте программу с использованием следующих постфиксных и префиксных операций:
a = b = 5
a + b
a++ + b
++a + b
--a + b
a-- + b
Распечатайте полученные значения и проанализируйте результат.
1.8.
Цикл for
________________________________________________________________________________
for(INIT; CONDITION; INCR)
BODY
________________________________________________________________________________
INIT;
repeat:
if(CONDITION){
BODY;
cont:
INCR;
goto repeat;
}
out: ;
Цикл while
________________________________________________________________________________
while(COND)
BODY
________________________________________________________________________________
cont:
repeat:
if(CONDITION){
BODY;
goto repeat;
}
out: ;
А. Богатырев, 1992-95 - 5 - Си в UNIX
Цикл do
________________________________________________________________________________
do
BODY
while(CONDITION)
________________________________________________________________________________
cont:
repeat:
BODY;
if(CONDITION) goto repeat;
out: ;
В операторах цикла внутри тела цикла BODY могут присутствовать операторы break и
continue; которые означают на наших схемах следующее:
#define break goto out
#define continue goto cont
1.9. Составьте программу печати прямоугольного треугольника из звездочек
*
**
****
*****
используя цикл for. Введите переменную, значением которой является размер катета треугольника.
1.10. Напишите операторы Си, которые выдают строку длины WIDTH, в которой сначала
содержится x0 символов '-', затем w символов '*', и до конца строки - вновь символы
'-'. Ответ:
int x;
for(x=0; x " x0; ++x) putchar('-');
for( ; x " x0 + w; x++) putchar('*');
for( ; x " WIDTH ; ++x) putchar('-');
putchar('\n');
либо
for(x=0; x " WIDTH; x++)
putchar( x " x0 ? '-' :
x " x0 + w ? '*' :
'-' );
putchar('\n');
1.11. Напишите программу с циклами, которая рисует треугольник:
*
*****
*******
*********
А. Богатырев, 1992-95 - 6 - Си в UNIX
Ответ:
/* Треугольник из звездочек */
#include "stdio.h"
/* Печать n символов c */
printn(c, n){
while( --n "= 0 )
putchar©;
}
int lines = 10; /* число строк треугольника */
void main(argc, argv) char *argv[];
{
register int nline; /* номер строки */
register int naster; /* количество звездочек в строке */
register int i;
if( argc " 1 )
lines = atoi( argv[1] );
for( nline=0; nline " lines ; nline++ ){
naster = 1 + 2 * nline;
/* лидирующие пробелы */
printn(' ', lines-1 - nline);
/* звездочки */
printn('*', naster);
/* перевод строки */
putchar( '\n' );
}
exit(0); /* завершение программы */
}
1.12. В чем состоит ошибка?
main(){ /* печать фразы 10 раз */
int i;
while(i " 10){
printf("%d-ый раз\n", i+1);
i++;
}
}
Ответ: автоматическая переменная i не была проинициализирована и содержит не 0, а
какое-то произвольное значение. Цикл может выполниться не 10, а любое число раз (в
том числе и 0 по случайности). Не забывайте инициализировать переменные, возьмите
описание с инициализацией за правило!
int i = 0;
Если бы переменная i была статической, она бы имела начальное значение 0.
В данном примере было бы еще лучше использовать цикл for, в котором все операции
над индексом цикла собраны в одном месте - в заголовке цикла:
for(i=0; i " 10; i++) printf(...);
А. Богатырев, 1992-95 - 7 - Си в UNIX
1.13. Вспомогательные переменные, не несущие смысловой нагрузки (вроде счетчика повторений
цикла, не используемого в самом теле цикла) принято по традиции обозначать
однобуквенными именами, вроде i, j. Более того, возможны даже такие курьезы:
main(){
int _ ;
for( _ = 0; _ " 10; _++) printf("%d\n", _ );
}
основанные на том, что подчерк в идентификаторах - полноправная буква.
1.14. Найдите 2 ошибки в программе:
main(){
int x = 12;
printf( "x=%d\n" );
int y;
y = 2 * x;
printf( "y=%d\n", y );
}
Комментарий: в теле функции все описания должны идти перед всеми выполняемыми операторами
(кроме операторов, входящих в состав описаний с инициализацией). Очень часто
после внесения правок в программу некоторые описания оказываются после выполняемых
операторов. Именно поэтому рекомендуется отделять строки описания переменных от
выполняемых операторов пустыми строками (в этой книге это часто не делается для экономии
места).
1.15. Найдите ошибку:
int n;
n = 12;
main(){
int y;
y = n+2;
printf( "%d\n", y );
}
Ответ: выполняемый оператор n=12 находится вне тела какой-либо функции. Следует
внести его в main() после описания переменной y, либо переписать объявление перед
main() в виде
int n = 12;
В последнем случае присваивание переменной n значения 12 выполнит компилятор еще во
время компиляции программы, а не сама программа при своем запуске. Точно так же происходит
со всеми статическими данными (описанными как static, либо расположенными вне
всех функций); причем если их начальное значение не указано явно - то подразумевается
0 ('\0', NULL, ""). Однако нулевые значения не хранятся в скомпилированном выполняемом
файле, а требуемая "чистая" память расписывается при старте программы.
1.16. По поводу описания переменной с инициализацией:
TYPE x = выражение;
является (почти) эквивалентом для
TYPE x; /* описание */
x = выражение; /* вычисление начального значения */
А. Богатырев, 1992-95 - 8 - Си в UNIX
Рассмотрим пример:
#include "stdio.h"
extern double sqrt(); /* квадратный корень */
double x = 1.17;
double s12 = sqrt(12.0); /* #1 */
double y = x * 2.0; /* #2 */
FILE *fp = fopen("out.out", "w"); /* #3 */
main(){
double ss = sqrt(25.0) + x; /* #4 */
}
Строки с метками #1, #2 и #3 ошибочны. Почему?
Ответ: при инициализации статических данных (а s12, y и fp таковыми и являются,
так как описаны вне какой-либо функции) выражение должно содержать только константы,
поскольку оно вычисляется КОМПИЛЯТОРОМ. Поэтому ни использование значений переменных,
ни вызовы функций здесь недопустимы (но можно брать адреса от переменных).
В строке #4 мы инициализируем автоматическую переменную ss, т.е. она отводится
уже во время выполнения программы. Поэтому выражение для инициализации вычисляется
уже не компилятором, а самой программой, что дает нам право использовать переменные,
вызовы функций и.т.п., то есть выражения языка Си без ограничений.
1.17. Напишите программу, реализующую эхо-печать вводимых символов. Программа
должна завершать работу при получении признака EOF. В UNIX при вводе с клавиатуры
признак EOF обычно обозначается одновременным нажатием клавиш CTRL и D (CTRL чуть
раньше), что в дальнейшем будет обозначаться CTRL/D; а в MS DOS - клавиш CTRL/Z.
Используйте getchar() для ввода буквы и putchar() для вывода.
1.18. Напишите программу, подсчитывающую число символов поступающих со стандартного
ввода. Какие достоинства и недостатки у следующей реализации:
#include "stdio.h"
main(){ double cnt = 0.0;
while (getchar() != EOF) ++cnt;
printf("%.0f\n", cnt );
}
Ответ: и достоинство и недостаток в том, что счетчик имеет тип double. Достоинство -
можно подсчитать очень большое число символов; недостаток - операции с double обычно
выполняются гораздо медленнее, чем с int и long (до десяти раз), программа будет
работать дольше. В повседневных задачах вам вряд ли понадобится иметь счетчик,
отличный от long cnt; (печатать его надо по формату "%ld").
1.19. Составьте программу перекодировки вводимых символов со стандартного ввода по
следующему правилу:
a -" b
b -" c
c -" d
z -" a
другой символ -" *
Коды строчных латинских букв расположены подряд по возрастанию.
1.20. Составьте программу перекодировки вводимых символов со стандартного ввода по
следующему правилу:
А. Богатырев, 1992-95 - 9 - Си в UNIX
B -" A
C -" B
Z -" Y
другой символ -" *
Коды прописных латинских букв также расположены по возрастанию.
1.21. Напишите программу, печатающую номер и код введенного символа в восьмеричном и
шестнадцатеричном виде. Заметьте, что если вы наберете на вводе строку символов и
нажмете клавишу ENTER, то программа напечатает вам на один символ больше, чем вы набрали.
Дело в том, что код клавиши ENTER, завершившей ввод строки - символ '\n' -
тоже попадает в вашу программу (на экране он отображается как перевод курсора в
начало следующей строки!).
1.22. Разберитесь, в чем состоит разница между символами '0' (цифра нуль) и '\0'
(нулевой байт). Напечатайте
printf( "%d %d %c\n", '\0', '0', '0' );
Поставьте опыт: что печатает программа?
main(){
int c = 060; /* код символа '0' */
printf( "%c %d %o\n", c, c, c);
}
Почему печатается 0 48 60? Теперь напишите вместо
int c = 060;
строчку
char c = '0';
1.23. Что напечатает программа?
#include "stdio.h"
void main(){
printf("ab\0cd\nxyz");
putchar('\n');
}
Запомните, что '\0' служит признаком конца строки в памяти, а '\n' - в файле. Что в
строке "abcd\n" на конце неявно уже расположен нулевой байт:
'a','b','c','d','\n','\0'
Что строка "ab\0cd\nxyz" - это
'a','b','\0','c','d','\n','x','y',z','\0'
Что строка "abcd\0" - избыточна, поскольку будет иметь на конце два нулевых байта
(что не вредно, но зачем?). Что printf печатает строку до нулевого байта, а не до
закрывающей кавычки.
Программа эта напечатает ab и перевод строки.
Вопрос: чему равен sizeof("ab\0cd\nxyz")? Ответ: 10.
1.24. Напишите программу, печатающую целые числа от 0 до 100.
1.25. Напишите программу, печатающую квадраты и кубы целых чисел.
А. Богатырев, 1992-95 - 10 - Си в UNIX
1.26. Напишите программу, печатающую сумму квадратов первых n целых чисел.
1.27. Напишите программу, которая переводит секунды в дни, часы, минуты и секунды.
1.28. Напишите программу, переводящую скорость из километров в час в метры в секундах.
1.29. Напишите программу, шифрующую текст файла путем замены значения символа (например,
значение символа C заменяется на C+1 или на ~C ).
1.30. Напишите программу, которая при введении с клавиатуры буквы печатает на терминале
ключевое слово, начинающееся с данной буквы. Например, при введении буквы 'b'
печатает "break".
1.31. Напишите программу, отгадывающую задуманное вами число в пределах от 1 до 200,
пользуясь подсказкой с клавиатуры "=" (равно), """ (меньше) и """ (больше). Для угадывания
числа используйте метод деления пополам.
1.32. Напишите программу, печатающую степени двойки
1, 2, 4, 8, ...
Заметьте, что, начиная с некоторого n, результат становится отрицательным из-за переполнения
целого.
1.33. Напишите подпрограмму вычисления квадратного корня с использованием метода
касательных (Ньютона):
x(0) = a
1 a
x(n+1) = - * ( ---- + x(n))
2 x(n)
Итерировать, пока не будет | x(n+1) - x(n) | " 0.001
Внимание! В данной задаче массив не нужен. Достаточно хранить текущее и предыдущее
значения x и обновлять их после каждой итерации.
1.34. Напишите программу, распечатывающую простые числа до 1000.
1, 2, 3, 5, 7, 11, 13, 17, ...
А. Богатырев, 1992-95 - 11 - Си в UNIX
/*#!/bin/cc primes.c -o primes -lm
* Простые числа.
*/
#include "stdio.h"
#include "math.h"
int debug = 0;
/* Корень квадратный из числа по методу Ньютона */
#define eps 0.0001
double sqrt (x) double x;
{
double sq, sqold, EPS;
if (x " 0.0)
return -1.0;
if (x == 0.0)
return 0.0; /* может привести к делению на 0 */
EPS = x * eps;
sq = x;
sqold = x + 30.0; /* != sq */
while (fabs (sq * sq - x) "= EPS) {
/* fabs( sq - sqold )"= EPS */
sqold = sq;
sq = 0.5 * (sq + x / sq);
}
return sq;
}
/* таблица простых чисел */
int is_prime (t) register int t; {
register int i, up;
int not_div;
if (t == 2 || t == 3 || t == 5 || t == 7)
return 1; /* prime */
if (t % 2 == 0 || t == 1)
return 0; /* composite */
up = ceil (sqrt ((double) t)) + 1;
i = 3;
not_div = 1;
while (i "= up && not_div) {
if (t % i == 0) {
if (debug)
fprintf (stderr, "%d поделилось на %d\n",
t, i);
not_div = 0;
break;
}
i += 2; /*
* Нет смысла проверять четные,
* потому что если делится на 2*n,
* то делится и на 2,
* а этот случай уже обработан выше.
*/
}
return not_div;
}
А. Богатырев, 1992-95 - 12 - Си в UNIX
#define COL 6
int n;
main (argc, argv) char **argv;
{
int i,
j;
int n;
if( argc " 2 ){
fprintf( stderr, "Вызов: %s число [-]\n", argv[0] );
exit(1);
}
i = atoi (argv[1]); /* строка -" целое, ею изображаемое */
if( argc " 2 ) debug = 1;
printf ("\t*** Таблица простых чисел от 2 до %d ***\n", i);
n = 0;
for (j = 1; j "= i; j++)
if (is_prime (j)){
/* распечатка в COL колонок */
printf ("%3d%s", j, n == COL-1 ? "\n" : "\t");
if( n == COL-1 ) n = 0;
else n++;
}
printf( "\n---\n" );
exit (0);
}
1.35. Составьте программу ввода двух комплексных чисел в виде A + B * I (каждое на
отдельной строке) и печати их произведения в том же виде. Используйте scanf и printf.
Перед тем, как использовать scanf, проверьте себя: что неверно в нижеприведенном операторе?
int x;
scanf( "%d", x );
Ответ: должно быть написано "АДРЕС от x", то есть scanf( "%d", &x );
1.36. Напишите подпрограмму вычисления корня уравнения f(x)=0 методом деления
отрезка пополам. Приведем реализацию этого алгоритма для поиска целочисленного квадратного
корня из целого числа (этот алгоритм может использоваться, например, в машинной
графике при рисовании дуг):
/* Максимальное unsigned long число */
#define MAXINT (~0L)
/* Определим имя-синоним для типа unsigned long */
typedef unsigned long ulong;
/* Функция, корень которой мы ищем: */
#define FUNC(x, arg) ((x) * (x) - (arg))
/* тогда x*x - arg = 0 означает x*x = arg, то есть
* x = корень_квадратный(arg) */
/* Начальный интервал. Должен выбираться исходя из
* особенностей функции FUNC */
#define LEFT_X(arg) 0
#define RIGHT_X(arg) (arg " MAXINT)? MAXINT : (arg/2)+1;
/* КОРЕНЬ КВАДРАТНЫЙ, округленный вниз до целого.
* Решается по методу деления отрезка пополам:
* FUNC(x, arg) = 0; x = ?
А. Богатырев, 1992-95 - 13 - Си в UNIX
*/
ulong i_sqrt( ulong arg ) {
register ulong mid, /* середина интервала */
rgt, /* правый край интервала */
lft; /* левый край интервала */
lft = LEFT_X(arg); rgt = RIGHT_X(arg);
do{ mid = (lft + rgt + 1 )/2;
/* +1 для ошибок округления при целочисленном делении */
if( FUNC(mid, arg) " 0 ){
if( rgt == mid ) mid--;
rgt = mid ; /* приблизить правый край */
} else lft = mid ; /* приблизить левый край */
} while( lft " rgt );
return mid;
}
void main(){ ulong i;
for(i=0; i "= 100; i++)
printf("%ld -" %lu\n", i, i_sqrt(i));
}
Использованное нами при объявлении переменных ключевое слово register означает, что
переменная является ЧАСТО ИСПОЛЬЗУЕМОЙ, и компилятор должен попытаться разместить ее
на регистре процессора, а не в стеке (за счет чего увеличится скорость обращения к
этой переменной). Это слово используется как
register тип переменная;
register переменная; /* подразумевается тип int */
От регистровых переменных нельзя брать адрес: &переменная ошибочно.
1.37. Напишите программу, вычисляющую числа треугольника Паскаля и печатающую их в
виде треугольника.
C(0,n) = C(n,n) = 1 n = 0...
C(k,n+1) = C(k-1,n) + C(k,n) k = 1..n
n - номер строки
В разных вариантах используйте циклы, рекурсию.
1.38. Напишите функцию вычисления определенного интеграла методом Монте-Карло. Для
этого вам придется написать генератор случайных чисел. Си предоставляет стандартный
датчик ЦЕЛЫХ равномерно распределенных псевдослучайных чисел: если вы хотите получить
целое число из интервала [A..B], используйте
int x = A + rand() % (B+1-A);
Чтобы получать разные последовательности следует задавать некий начальный параметр
последовательности (это называется "рандомизация") при помощи
srand( число ); /* лучше нечетное */
Чтобы повторить одну и ту же последовательность случайных чисел несколько раз, вы
должны поступать так:
srand(NBEG); x=rand(); ... ; x=rand();
/* и повторить вс
...Закладка в соц.сетях
