Страница:
чтобы график выглядел непрерывным; не забывайте приводить double к int, т.к. коорди-
наты пикселов|- - целые числа.
8.22. Напишите функцию, которая заполняет в массиве байт count бит подряд, начиная с
x-ого бита от левого края массива:
байт 0 | байт 1
7 6 5 4 3 2 1 0 | 7 6 5 4 3 2 1 0 : биты в байте
0 1 2 3 4 5 6 7 | 8 9 10 11 12 13 14 15 : x
==========================
x=2, count=11
Такой алгоритм используется в растровой машинной графике для рисования горизонтальных
прямых линий (тогда массив - это видеопамять компьютера, каждый бит соответствует
пикселу на экране).
Ответ (причем мы заполняем биты не просто единицами, а "узором" pattern):
void horizLine(char *addr,int x,int count,char pattern){
static char masks[8] = {
0xFF, 0x7F, 0x3F, 0x1F, 0x0F, 0x07, 0x03, 0x01 };
/* индекс в этом массиве равен числу 0-битов слева */
____________________
|- Пиксел (pixel, pel) - picture element, в машинной графике - точка растра на эк-
ране.
А. Богатырев, 1992-95 - 388 - Си в UNIX
register i;
char mask;
short lbits, rbits; /* число битов слева и справа */
short onebyte; /* единственный байт ? */
addr += x/8; /* в байте 8 бит */
mask = masks[ lbits = x & 7 ]; /* x % 8 */
if( count >= (rbits = 8 - lbits)){
count -= rbits; onebyte = 0;
}else{
mask &= ~masks[ lbits = (x+count) & 7 ];
onebyte = 1;
}
/* Первый байт */
*addr = (*addr & ~mask) | (pattern & mask);
addr++;
/* Для pattern==0xFF можно просто
* *addr++ |= mask;
* поскольку (a &~m)|(0xFF & m) = (a &~m) | m =
* (a|m) & (~m|m) = (a|m) & 0xFF = a | m
* Почему здесь нельзя написать *addr++ = (*addr...) ?
* Потому, что ++ может быть сделан ДО вычисления
* правой части присваивания!
*/
if(onebyte) return;
/* Средние байты */
for(i = count/8; i > 0; --i)
*addr++ = pattern; /* mask==0xFF */
/* Последний байт */
if((lbits = count & 7) == 0) return;
/* последний байт был полным */
mask = ~masks[lbits];
*addr = (*addr & ~mask) | (pattern & mask);
}
Заметим, что для быстродействия подобные алгоритмы обычно пишутся на ассемблере.
8.23. Напишите при помощи curses-а "электронные часы", отображающие текущее время
большими цифрами (например, размером 8x8 обычных символов) каждые 5 секунд. Исполь-
зуйте alarm(), pause().
8.24. Составьте программу, реализующую простой диалоговый интерфейс, основанный на
меню. Меню хранятся в текстовых файлах вида:
А. Богатырев, 1992-95 - 389 - Си в UNIX
файл menu2_12
-----------------------------------------------
ЗАГОЛОВОК_МЕНЮ
+команда_выполняемая_при_входе_в_меню
-команда_выполняемая_при_выходе_из_меню
альтернатива_1
команда1_1
команда1_2
альтернатива_2
команда2_1
команда2_2 #комментарий
команда2_3
альтернатива_3
>menu2_2 #это переход в другое меню
альтернатива_4
>>menu3_7 #хранимое в файле menu3_7
...
...
-----------------------------------------------
Программа должна обеспечивать: возврат к предыдущему меню по клавише Esc (для этого
следует хранить "историю" вызовов меню друг из друга, например в виде "полного имени
меню":
.rootmenu.menu1_2.menu2_4.menu3_1
где menuI_J - имена файлов с меню), обеспечить выход из программы по клавишам 'q' и
ESC, выдачу подсказки по F1, выдачу полного имени меню по F2. Вызов меню при помощи
> означает замещение текущего меню новым, что соответствует замене последней компо-
ненты в полном имени меню. Вызов >> означает вызов меню как функции, т.е. после
выбора в новом меню и выполнения нужных действий автоматически должно быть выдано то
меню, из которого произошел вызов (такой вызов соответствует удлинению полного имени,
а возврат из вызова - отсечению последней компоненты). Этот вызов может быть показан
на экране как появление нового "выскакивающего" окна поверх окна с предыдущим меню
(окно возникает чуть сдвинутым - скажем, на y=1 и x=-2), а возврат - как исчезновение
этого окна. Заголовок меню должен высвечиваться в верхней строке меню:
|-------------------
|--ЗАГОЛОВОК_МЕНЮ---- |
| альтернатива_1 | |
| альтернатива_2 | |
| *альтернатива_3 | |
| альтернатива_4 |--
---------------------
Сначала реализуйте версию, в которой каждой "альтернативе" соответствует единственная
строка "команда". Команды следует запускать при помощи стандартной функции
system(команда).
Усложните функцию выбора в меню так, чтобы альтернативы можно было выбирать по
первой букве при помощи нажатия кнопки с этой буквой (в любом регистре):
Compile
Edit
Run program
8.25. Напишите на curses-е функцию, реализующую выбор в меню - прямоугольной таб-
лице:
А. Богатырев, 1992-95 - 390 - Си в UNIX
слово1 слово4 слово7
слово2 *слово5 слово8
слово3 слово6
Строки - элементы меню - передаются в функцию выбора в виде массива строк. Число
элементов меню заранее неизвестно и должно подсчитываться внутри функции. Учтите,
что все строки могут не поместиться в таблице, поэтому надо предусмотреть "прокручи-
вание" строк через таблицу при достижении края меню (т.е. таблица служит как бы
"окошком" через которое мы обозреваем таблицу большего размера, возможно перемещая
окно над ней). Предусмотрите также случай, когда таблица оказывается заполненной не
полностью (как на рисунке).
8.26. Используя библиотеку curses, напишите программу, реализующую клеточный автомат
Конвея "Жизнь". Правила: есть прямоугольное поле (вообще говоря бесконечное, но при-
нято в конечной модели замыкать края в кольцо), в котором живут "клетки" некоторого
организма. Каждая имеет 8 соседних полей. Следующее поколение "клеток" образуется по
таким правилам:
- если "клетка" имеет 2 или 3 соседей - она выживает.
- если "клетка" имеет меньше 2 или больше 3 соседей - она погибает.
- в пустом поле, имеющем ровно 3х живых соседей, рождается новая "клетка".
Предусмотрите: редактирование поля, случайное заполнение поля, останов при смерти
всех "клеток", останов при стабилизации колонии.
8.27. При помощи curses-а напишите экранный редактор кодов доступа к файлу (в форме
rwxrwxrwx). Расширьте программу, позволяя редактировать коды доступа у группы фай-
лов, изображая имена файлов и коды доступа в виде таблицы:
НАЗВАНИЕ КОДЫ ДОСТУПА
файл1 rwxrw-r--
файл2 rw-r-xr-x
файл3 rwxrwxr--
Имена файлов задавайте как аргументы для main(). Указание: используйте для получения
текущих кодов доступа системный вызов stat(), а для их изменения - системный вызов
chmod().
А. Богатырев, 1992-95 - 391 - Си в UNIX
Операции, расположенные выше, имеют больший приоритет.
Операторы Ассоциативность
--------------------------------------------------
1. () [] -> :: . Left to right
2. ! ~ + - ++ -- & *
(typecast) sizeof new delete Right to left
3. .* ->* Left to right
4. * / % Left to right
5. + - Left to right
6. << >> Left to right
7. < <= > >= Left to right
8. == != Left to right
9. & Left to right
10. ^ Left to right
11. | Left to right
12. && Left to right
13. || Left to right
14. ?: (условное выражение) Right to left
15. = *= /= %= += -= &=
^= |= <<= >>= Right to left
16. , Left to right
Здесь "*" и "&" в строке 2 - это адресные операции; в строке 2 "+" и "-" - унарные;
"&" в строке 9 - это побитное "и"; "(typecast)" - приведение типа; "new" и "delete" -
операторы управления памятью в C++.
Ассоциативность Left to right (слева направо) означает группировку операторов
таким образом:
A1 @ A2 @ A3 это
((A1 @ A2) @ A3)
Ассоциативность Rigth to left (справа налево) это
A1 @ A2 @ A3 это
(A1 @ (A2 @ A3))
9.2.1. В выражениях.
1. Если операнд имеет тип не int и не double, то сначала приводится:
signed char --> int расширением знакового бита (7)
unsigned char --> int дополнением нулями слева
short --> int расширением знакового бита (15)
unsigned short --> unsigned int дополнением нулями слева
enum --> int порядковый номер в перечислимом типе
float --> double дробная часть дополняется нулями
2. Если любой операнд имеет тип double, то и другой операнд приводится к типу dou-
ble. Результат: типа double. Запишем все дальнейшие преобразования в виде схемы:
А. Богатырев, 1992-95 - 392 - Си в UNIX
если есть то другой результат
операнд типа приводится к типу имеет тип
if(double) -->double double
else if(unsigned long) -->unsigned long unsigned long
else if(long) -->long long
else if(unsigned int) -->unsigned int unsigned int
else оба операнда имеют тип int int
При вызове функций их аргументы - тоже выражения, поэтому в них приводятся char,short
к int и float к double. Это говорит о том, что аргументы (формальные параметры) функ-
ций можно всегда объявлять как int и double вместо char,short и float соответственно.
Зато спецификатор unsigned является существенным.
9.2.2. В присваиваниях.
op = expr;
Тип выражения expr приводится к типу левой части - op. При этом возможны приведения
более "длинного" типа к более "короткому" при помощи усечения, вроде:
int --> char обрубается старший байт.
long --> int обрубается старшее слово.
float --> int отброс дробной части
double --> int и обрубание мантиссы, если не лезет.
double --> float округление дробной части.
Вот еще некоторые приведения типов:
signed --> unsigned виртуально (просто знаковый бит
unsigned --> signed считается значащим или наоборот).
unsigned int --> long добавление нулей слева.
int --> long расширение знакового бита.
float --> int преобразование внутреннего
int --> float представления: машинно зависимо.
Некоторые преобразования могут идти в несколько стадий, например:
char --> long это
char --> int --> long
char --> unsigned long это
char --> int --> unsigned long
%d %o %X побитно
--------------------------------
0 0 0x0 0000
1 1 0x1 0001
2 2 0x2 0010
3 3 0x3 0011
4 4 0x4 0100
5 5 0x5 0101
6 6 0x6 0110
7 7 0x7 0111
А. Богатырев, 1992-95 - 393 - Си в UNIX
--------------------------------
8 010 0x8 1000
9 011 0x9 1001
10 012 0xA 1010
11 013 0xB 1011
12 014 0xC 1100
13 015 0xD 1101
14 016 0xE 1110
15 017 0xF 1111
16 020 0x10 10000
n 2**n | n 2**n
--------------|---------------
0 1 | 8 256
1 2 | 9 512
2 4 | 10 1024
3 8 | 11 2048
4 16 | 12 4096
5 32 | 13 8192
6 64 | 14 16384
7 128 | 15 32768
| 16 65536
Целые числа в большинстве современных компьютеров представлены в виде двоичного
кода. Пусть машинное слово состоит из 16 бит. Биты нумеруются справа налево начиная
с 0. Обозначим условно бит номер i через b[i]. Значением его может быть либо 0, либо
1.
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 0| 0| 0| 1| 0| 1| 1| 0| 1| 1| 0| 1| 1| 0| 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Тогда unsigned число, записанное в слове, равно
d = 2**15 * b[15] +
2**14 * b[14] +
...
2**1 * b[1] +
b[0];
(2**n - это 2 в степени n). Такое разложение числа d единственно. При сложении двух
чисел биты складываются по правилам:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 и перенос 1 в разряд слева
Числа со знаком интерпретируются чуть иначе. Бит b[15] считается знаковым: 0 - число
положительно или равно нулю, 1 - отрицательно. Отрицательные числа хранятся в виде
дополнительного кода:
-a = ~a + 1
Например:
А. Богатырев, 1992-95 - 394 - Си в UNIX
2 = 0000000000000010
~2 = 1111111111111101
~2+1 = 1111111111111110 = -2
-1 = 1111111111111111
-2 = 1111111111111110
-3 = 1111111111111101
-4 = 1111111111111100
-5 = 1111111111111011
Такое представление выбрано исходя из правила
a + (-a) = 0
знак|
2 = 0|000000000000010 сложим их
-2 = 1|111111111111110
---------|---------------
сумма: 10|000000000000000
Как видим, произошел перенос 1 в бит номер 16. Но слово содержит лишь биты 0..15 и
бит b[16] просто игнорируется. Получается, что сумма равна
0000000000000000 = 0
что и требовалось. В двоичном коде вычитание реализуется по схеме
a - b = a + (-b) = a + (~b + 1)
Восьмеричные числа соответствуют разбиению двоичного числа на группы по 3 бита и
записи каждой группы в виде соответствующей восьмеричной цифры (смотри таблицу выше).
Шестнадцатеричные числа соответствуют разбиению на группы по 4 бита (nibble):
x = 0010011111011001
число: 0010 0111 1101 1001
16-ричное: 0x 2 7 D 9 = 0x27D9
число: 0 010 011 111 011 001
8-ричное: 0 0 2 3 7 3 1 = 023731
В данном приложении приводится несколько содержательных и достаточно больших
примеров, которые иллюстрируют как сам язык Си, так и некоторые возможности системы
UNIX, а также некоторые программистские приемы решения задач при помощи Си. Многие
из этих примеров содержат в качестве своих частей ответы на некоторые из задач.
Некоторые примеры позаимствованы из других книг, но дополнены и исправлены. Все при-
меры проверены в действии. Смысл некоторых функций в примерах может оказаться вам
неизвестен; однако в силу того, что данная книга не является учебником, мы отсылаем
вас за подробностями к "Оперативному руководству" (man) по операционной системе UNIX
и к документации по системе.
И в заключение - несколько слов о путях развития языка "C". Чистый язык "C" уже
отстал от современных технологий программирования. Такие методы как модули (языки
"Modula-2", "Ada", "CLU"), родовые пакеты ("Ada", "CLU"), объектно-ориентированное
программирование ("Smalltalk", "CLU") требуют новых средств. Поэтому в настоящее
время "C" постепенно вытесняется более мощным и интеллектуальным языком "C++" |-,
обладающим средствами для объектно-ориентированного программирования и родовых
____________________
|- C++ как и C разработан в AT&T; произносится "Си плас-плас"
А. Богатырев, 1992-95 - 395 - Си в UNIX
классов. Существуют также расширения стандартного "C" объектно-ориентированными воз-
можностями ("Objective-C"). Большой простор предоставляет также сборка программ из
частей, написанных на разных языках программирования (например, "C", "Pascal", "Pro-
log").
____________________
|=|=|= Автор благодарит авторов программ и книг по Си и UNIX, по которым некогда
учился я сам; коллег из ИПК Минавтопрома/Демоса; программистов из сетей Usenet и Rel-
com, давших материалы для задач и рассуждений; слушателей курсов по Си за многочис-
ленный материал для книги.
А.Богатырев.
Ученью не один мы посвятили год,
Потом других учить пришел и нам черед.
Какие ж выводы из этой всей науки?
Из праха мы пришли, нас ветер унесет.
Омар Хайям
Оглавление.
0. Напутствие в качестве вступления. .......................................... 1
1. Простые программы и алгоритмы. Сюрпризы, советы. ........................... 3
2. Массивы, строки, указатели. ................................................ 81
3. Мобильность и машинная зависимость программ. Проблемы с русскими буквами.
........................................................................... 122
4. Работа с файлами. .......................................................... 137
5. Структуры данных. .......................................................... 172
6. Системные вызовы и взаимодействие с UNIX. .................................. 186
6.1. Файлы и каталоги. ........................................................ 189
6.2. Время в UNIX. ............................................................ 198
6.3. Свободное место на диске. ................................................ 207
6.4. Сигналы. ................................................................. 212
6.5. Жизнь процессов. ......................................................... 219
6.6. Трубы и FIFO-файлы. ...................................................... 230
6.7. Нелокальный переход. ..................................................... 233
6.8. Хозяин файла, процесса, и проверка привелегий. ........................... 235
6.9. Блокировка доступа к файлам. ............................................. 240
6.10. Файлы устройств. ........................................................ 244
6.11. Мультиплексирование ввода-вывода ......................................... 259
6.12. Простой интерпретатор команд. ........................................... 271
7. Текстовая обработка. ....................................................... 283
8. Экранные библиотеки и работа с видеопамятью. ............................... 348
9. Приложения. ................................................................ 391
9.1. Таблица приоритетов операций языка C++ .................................... 391
9.2. Правила преобразований типов. ............................................ 391
9.3. Таблица шестнадцатеричных чисел (HEX). ................................... 392
9.4. Таблица степеней двойки. ................................................. 393
9.5. Двоичный код: внутреннее представление целых чисел. ...................... 393
10. Примеры. .................................................................. 394
Пример 1. Размен монет. ......................................................
Пример 2. Подсчет букв в файле. ..............................................
Пример 3. Центрирование строк. ...............................................
Пример 4. Разметка текста для nroff. .........................................
Пример 5. Инвертирование порядка слов в строках. .............................
Пример 6. Пузырьковая сортировка. ............................................
Пример 7. Хэш-таблица. .......................................................
Пример 8. Простая база данных. ...............................................
Пример 9. Вставка/удаление строк в файл. .....................................
Пример 10. Безопасный free, позволяющий обращения к автоматическим перемен-
ным. .....................................................................
Пример 11. Поимка ошибок при работе с динамической памятью. ..................
Пример 12. Копирование/перемещение файла. ....................................
Пример 13. Обход поддерева каталогов в MS DOS при помощи chdir. ..............
Пример 14. Работа с сигналами. ...............................................
Пример 15. Управление скоростью обмена через линию. ..........................
Пример 16. Просмотр файлов в окнах. ..........................................
Пример 17. Работа с иерархией окон в curses. Часть проекта uxcom. ............
Пример 18. Поддержка содержимого каталога. Часть проекта uxcom. ..............
Пример 19. Роллируемое меню. Часть проекта uxcom. ............................
Пример 20. Выбор в строке-меню. Часть проекта uxcom. .........................
Пример 21. Редактор строки. Часть проекта uxcom. .............................
Пример 22. Выбор в прямоугольной таблице. Часть проекта uxcom. ...............
Пример 23. UNIX commander - простой визуальный Шелл. Головной модуль проекта
uxcom. ...................................................................
Пример 24. Общение двух процессов через "трубу". .............................
Пример 25. Общение процессов через FIFO-файл. ................................
Пример 26. Общение процессов через общую память и семафоры. ..................
Пример 27. Протоколирование работы программы при помощи псевдотерминала и
процессов. ...............................................................
Пример 28. Оценка фрагментированности файловой системы. ......................
Пример 29. Восстановление удаленного файла в BSD-2.9. ........................
Пример 30. Копирование файлов из MS DOS в UNIX. ..............................
Пример 31. Программа, печатающая свой собственный текст. .....................
Пример 32. Форматирование текста Си-программы. ...............................
1.11. Треугольник из звездочек. ............................................... 6
1.34. Простые числа. .......................................................... 10
1.36. Целочисленный квадратный корень. ........................................ 12
1.39. Вычисление интеграла по Симпсону. ....................................... 14
1.49. Сортировка Шелла. ....................................................... 20
1.50. Быстрая сортировка. ..................................................... 21
1.67. Функция чтения строки. .................................................. 28
1.88. Перестановки элементов. ................................................. 38
1.117. Схема Горнера. ......................................................... 58
1.137. Системная функция qsort - формат вызова. ............................... 67
1.146. Процесс компиляции программ. ........................................... 76
2.58. Функция bcopy. .......................................................... 108
2.59. Функция strdup. ......................................................... 111
2.61. Упрощенный аналог функции printf. ....................................... 112
3.9. _ctype[] .................................................................. 126
3.12. Программа транслитерации: tr. ........................................... 129
3.16. Функция записи трассировки (отладочных выдач) в файл. ................... 132
3.18. Условная компиляция: #ifdef .............................................. 132
4.39. Быстрый доступ к строкам файла. ......................................... 161
4.45. Эмуляция основ библиотеки STDIO, по мотивам 4.2 BSD. .................... 165
5.12. Отсортированный список слов. ............................................ 180
5.16. Структуры с полями переменного размера. ................................. 183
5.17. Список со "старением". .................................................. 184
6.1.1. Определение типа файла. ................................................ 189
6.1.3. Выдача неотсортированного содержимого каталога (ls). ................... 191
6.1.5. Рекурсивный обход каталогов и подкаталогов. ............................ 192
6.2.9. Функция задержки в микросекундах. ...................................... 201
6.4.3. Функция sleep. ......................................................... 217
6.10.1. Определение текущего каталога: функция getwd. ......................... 252
6.10.2. Канонизация полного имени файла. ...................................... 257
6.11.1. Мультиплексирование ввода из нескольких файлов. ....................... 259
6.11.2. Программа script. ..................................................... 261
7.12. Программа uniq. ......................................................... 285
7.14. Расширение табуляций в пробелы, функция untab. .......................... 285
7.15. Функция tabify. ......................................................... 285
7.25. Поиск методом половинного деления. ...................................... 288
7.31. Программа печати в две полосы. .......................................... 292
7.33. Инвертирование порядка строк в файле. ................................... 296
7.34. Перенос неразбиваемых блоков текста. .................................... 298
7.36. Двоичная сортировка строк при помощи дерева. ............................ 300
7.41. Функция match. .......................................................... 309
7.43. Функция контекстной замены по регулярному выражению. .................... 313
7.44. Алгоритм быстрого поиска подстроки в строке. ............................ 316
7.52. Коррекция правописания. ................................................. 321
7.67. Калькулятор-1. .......................................................... 330
7.68. Калькулятор-2. .......................................................... 336
8.1. Осыпающиеся буквы. ....................................................... 350
8.13. Использование библиотеки termcap. ....................................... 359
8.17. Разбор ESC-последовательностей с клавиатуры. ............................ 371
1) Б.Керниган, Д.Ритчи, А.Фьюер. Язык программирования Си. Задачи по языку Си. -
М.: Финансы и статистика, 1985.
2) М.Уэйт, С.Прата, Д.Мартин. Язык Си. Руководство для начинающих. - М.: Мир,
1988.
3) М.Болски. Язык программирования Си. Справочник. - М.: Радио и связь, 1988.
4) Л.Хэнкок, М.Кригер. Введение в программирование на языке Си. - М.: Радио и
связь, 1986.
5) М.Дансмур, Г.Дейвис. ОС UNIX и программирование на языке Си. - М.: Радио и
связь, 1989.
6) Р.Берри, Б.Микинз. Язык Си. Введение для программистов. - М.: Финансы и ста-
тистика, 1988.
7) М.Беляков, А.Ливеровский, В.Семик, В.Шяудкулис. Инструментальная мобильная опе-
рационная система ИНМОС. - М.: Финансы и статистика, 1985.
8) К.Кристиан. Введение в операционную систему UNIX. - М.: Финансы и статистика,
1985.
9) Р.Готье. Руководство по операционной системе UNIX. - М.: Финансы и статистика,
1986.
10) М.Банахан, Э.Раттер. Введение в операционную систему UNIX. - М.: Радио и
связь, 1986.
11) С.Баурн. Операционная система UNIX. - М.: Мир, 1986.
12) П.Браун. Введение в операционную систему UNIX. - М.: Мир, 1987.
13) M.Bach. The design of the UNIX operating system. - Prentice Hall, Englewood
Cliffs, N.J., 1986.
14) S.Dewhurst, K.Stark. Programming in C++. - Prentice Hall, 1989.
15) M.Ellis, B.Stroustrup. The annotated C++ Reference Manual. - Addison-Wesley,
1990.
/* Пример 1 */
/* Задача о размене монеты:
* Поиск всех возможных коэффициентов a0 .. an разложения числа S
* в виде
* S = a0 * c0 + a1 * c1 + ... + an * cn
* где веса c0 .. cn заданы заранее и упорядочены.
* Веса и коэффициенты неотрицательны (ai >= 0, ci >= 0).
*/
#include <stdio.h>
/* Достоинства разменных монет (веса ci) */
int cost[] = {
1, 2, 3, 5, 10, 15, 20, 50, 100, 300, 500 /* копеек */
};
#define N (sizeof cost / sizeof(int))
int count[ N ]; /* число монет данного типа (коэффициенты ai) */
long nvar; /* число вариантов */
main( ac, av ) char *av[];
{
int coin;
if( ac == 1 ){
fprintf( stderr, "Укажите, какую монету разменивать: %s число\n",
av[0] );
exit(1);
}
coin = atoi( av[1] );
printf( " Таблица разменов монеты %d коп.\n", coin );
printf( " Каждый столбец содержит количество монет указанного достоинства.\n" );
printf( "-------------------------------------------------------------------\n" );
printf( "| 5р. | 3р. | 1р. | 50к.| 20к.| 15к.| 10к.| 5к.| 3к.| 2к.| 1к.|\n" );
printf( "-------------------------------------------------------------------\n" );
change( N-1, coin );
printf( "-------------------------------------------------------------------\n" );
printf( "Всего %ld вариантов\n", nvar );
}
/* рекурсивный размен */
change( maxcoin, sum )
int sum; /* монета, которую меняем */
int maxcoin; /* индекс по массиву cost[] монеты максимального
* достоинства, допустимой в данном размене.
*/
{
register i;
if( sum == 0 ){ /* вся сумма разменяна */
/* распечатать очередной вариант */
putchar( '|' );
for( i = N-1 ; i >= 0 ; i-- )
if( count[i] )
printf(" %3d |", count[ i ] );
else
printf(" |" );
putchar( '\n' );
nvar++;
return;
}
if( sum >= cost [ maxcoin ] ){
/* если можно выдать монету достоинством cost[maxcoin] ,
* то выдать ее:
*/
count[ maxcoin ] ++; /* посчитали выданную монету */
/* размениваем остаток суммы :
* Первый аргумент - может быть можно дать еще одну такую монету ?
* Второй аргумент - общая сумма убавилась на одну монету cost[maxcoin].
*/
change( maxcoin, sum - cost[maxcoin] );
count[ maxcoin ] --; /* ... Теперь попробуем иной вариант ... */
}
/* попробовать размен более мелкими монетами */
if( maxcoin )
change( maxcoin-1, sum );
}
/* Пример 2 */
/* Подсчет количества вхождений каждой из букв алфавита в файл.
* Выдача таблицы.
* Подсчет частоты использования битов в байтах файла.
*/
#include <stdio.h>
#include <ctype.h>
long bcnt[8];
char masks[8] = { /* маски битов */
1, 2, 4, 8, 16, 32, 64, 128 };
long cnt[256]; /* счетчики для каждой из 256 букв */
/* распечатка букв в стиле языка СИ */
char *pr( c ){
static char buf[ 20 ];
switch( c ){
case '\n': return " \\n " ;
case '\r': return " \\r " ;
case '\t': return " \\t " ;
case '\b': return " \\b " ;
case '\f': return " \\f " ;
case '\033': return " ESC" ;
case '\0': return " \\0 " ;
case 0177: return " ^? " ;
}
if( c < ' ' ){
sprintf( buf, " ^%c ", c + 'A' - 1 );
}else if( isspace(c)){
наты пикселов|- - целые числа.
8.22. Напишите функцию, которая заполняет в массиве байт count бит подряд, начиная с
x-ого бита от левого края массива:
байт 0 | байт 1
7 6 5 4 3 2 1 0 | 7 6 5 4 3 2 1 0 : биты в байте
0 1 2 3 4 5 6 7 | 8 9 10 11 12 13 14 15 : x
==========================
x=2, count=11
Такой алгоритм используется в растровой машинной графике для рисования горизонтальных
прямых линий (тогда массив - это видеопамять компьютера, каждый бит соответствует
пикселу на экране).
Ответ (причем мы заполняем биты не просто единицами, а "узором" pattern):
void horizLine(char *addr,int x,int count,char pattern){
static char masks[8] = {
0xFF, 0x7F, 0x3F, 0x1F, 0x0F, 0x07, 0x03, 0x01 };
/* индекс в этом массиве равен числу 0-битов слева */
____________________
|- Пиксел (pixel, pel) - picture element, в машинной графике - точка растра на эк-
ране.
А. Богатырев, 1992-95 - 388 - Си в UNIX
register i;
char mask;
short lbits, rbits; /* число битов слева и справа */
short onebyte; /* единственный байт ? */
addr += x/8; /* в байте 8 бит */
mask = masks[ lbits = x & 7 ]; /* x % 8 */
if( count >= (rbits = 8 - lbits)){
count -= rbits; onebyte = 0;
}else{
mask &= ~masks[ lbits = (x+count) & 7 ];
onebyte = 1;
}
/* Первый байт */
*addr = (*addr & ~mask) | (pattern & mask);
addr++;
/* Для pattern==0xFF можно просто
* *addr++ |= mask;
* поскольку (a &~m)|(0xFF & m) = (a &~m) | m =
* (a|m) & (~m|m) = (a|m) & 0xFF = a | m
* Почему здесь нельзя написать *addr++ = (*addr...) ?
* Потому, что ++ может быть сделан ДО вычисления
* правой части присваивания!
*/
if(onebyte) return;
/* Средние байты */
for(i = count/8; i > 0; --i)
*addr++ = pattern; /* mask==0xFF */
/* Последний байт */
if((lbits = count & 7) == 0) return;
/* последний байт был полным */
mask = ~masks[lbits];
*addr = (*addr & ~mask) | (pattern & mask);
}
Заметим, что для быстродействия подобные алгоритмы обычно пишутся на ассемблере.
8.23. Напишите при помощи curses-а "электронные часы", отображающие текущее время
большими цифрами (например, размером 8x8 обычных символов) каждые 5 секунд. Исполь-
зуйте alarm(), pause().
8.24. Составьте программу, реализующую простой диалоговый интерфейс, основанный на
меню. Меню хранятся в текстовых файлах вида:
А. Богатырев, 1992-95 - 389 - Си в UNIX
файл menu2_12
-----------------------------------------------
ЗАГОЛОВОК_МЕНЮ
+команда_выполняемая_при_входе_в_меню
-команда_выполняемая_при_выходе_из_меню
альтернатива_1
команда1_1
команда1_2
альтернатива_2
команда2_1
команда2_2 #комментарий
команда2_3
альтернатива_3
>menu2_2 #это переход в другое меню
альтернатива_4
>>menu3_7 #хранимое в файле menu3_7
...
...
-----------------------------------------------
Программа должна обеспечивать: возврат к предыдущему меню по клавише Esc (для этого
следует хранить "историю" вызовов меню друг из друга, например в виде "полного имени
меню":
.rootmenu.menu1_2.menu2_4.menu3_1
где menuI_J - имена файлов с меню), обеспечить выход из программы по клавишам 'q' и
ESC, выдачу подсказки по F1, выдачу полного имени меню по F2. Вызов меню при помощи
> означает замещение текущего меню новым, что соответствует замене последней компо-
ненты в полном имени меню. Вызов >> означает вызов меню как функции, т.е. после
выбора в новом меню и выполнения нужных действий автоматически должно быть выдано то
меню, из которого произошел вызов (такой вызов соответствует удлинению полного имени,
а возврат из вызова - отсечению последней компоненты). Этот вызов может быть показан
на экране как появление нового "выскакивающего" окна поверх окна с предыдущим меню
(окно возникает чуть сдвинутым - скажем, на y=1 и x=-2), а возврат - как исчезновение
этого окна. Заголовок меню должен высвечиваться в верхней строке меню:
|-------------------
|--ЗАГОЛОВОК_МЕНЮ---- |
| альтернатива_1 | |
| альтернатива_2 | |
| *альтернатива_3 | |
| альтернатива_4 |--
---------------------
Сначала реализуйте версию, в которой каждой "альтернативе" соответствует единственная
строка "команда". Команды следует запускать при помощи стандартной функции
system(команда).
Усложните функцию выбора в меню так, чтобы альтернативы можно было выбирать по
первой букве при помощи нажатия кнопки с этой буквой (в любом регистре):
Compile
Edit
Run program
8.25. Напишите на curses-е функцию, реализующую выбор в меню - прямоугольной таб-
лице:
А. Богатырев, 1992-95 - 390 - Си в UNIX
слово1 слово4 слово7
слово2 *слово5 слово8
слово3 слово6
Строки - элементы меню - передаются в функцию выбора в виде массива строк. Число
элементов меню заранее неизвестно и должно подсчитываться внутри функции. Учтите,
что все строки могут не поместиться в таблице, поэтому надо предусмотреть "прокручи-
вание" строк через таблицу при достижении края меню (т.е. таблица служит как бы
"окошком" через которое мы обозреваем таблицу большего размера, возможно перемещая
окно над ней). Предусмотрите также случай, когда таблица оказывается заполненной не
полностью (как на рисунке).
8.26. Используя библиотеку curses, напишите программу, реализующую клеточный автомат
Конвея "Жизнь". Правила: есть прямоугольное поле (вообще говоря бесконечное, но при-
нято в конечной модели замыкать края в кольцо), в котором живут "клетки" некоторого
организма. Каждая имеет 8 соседних полей. Следующее поколение "клеток" образуется по
таким правилам:
- если "клетка" имеет 2 или 3 соседей - она выживает.
- если "клетка" имеет меньше 2 или больше 3 соседей - она погибает.
- в пустом поле, имеющем ровно 3х живых соседей, рождается новая "клетка".
Предусмотрите: редактирование поля, случайное заполнение поля, останов при смерти
всех "клеток", останов при стабилизации колонии.
8.27. При помощи curses-а напишите экранный редактор кодов доступа к файлу (в форме
rwxrwxrwx). Расширьте программу, позволяя редактировать коды доступа у группы фай-
лов, изображая имена файлов и коды доступа в виде таблицы:
НАЗВАНИЕ КОДЫ ДОСТУПА
файл1 rwxrw-r--
файл2 rw-r-xr-x
файл3 rwxrwxr--
Имена файлов задавайте как аргументы для main(). Указание: используйте для получения
текущих кодов доступа системный вызов stat(), а для их изменения - системный вызов
chmod().
А. Богатырев, 1992-95 - 391 - Си в UNIX
Операции, расположенные выше, имеют больший приоритет.
Операторы Ассоциативность
--------------------------------------------------
1. () [] -> :: . Left to right
2. ! ~ + - ++ -- & *
(typecast) sizeof new delete Right to left
3. .* ->* Left to right
4. * / % Left to right
5. + - Left to right
6. << >> Left to right
7. < <= > >= Left to right
8. == != Left to right
9. & Left to right
10. ^ Left to right
11. | Left to right
12. && Left to right
13. || Left to right
14. ?: (условное выражение) Right to left
15. = *= /= %= += -= &=
^= |= <<= >>= Right to left
16. , Left to right
Здесь "*" и "&" в строке 2 - это адресные операции; в строке 2 "+" и "-" - унарные;
"&" в строке 9 - это побитное "и"; "(typecast)" - приведение типа; "new" и "delete" -
операторы управления памятью в C++.
Ассоциативность Left to right (слева направо) означает группировку операторов
таким образом:
A1 @ A2 @ A3 это
((A1 @ A2) @ A3)
Ассоциативность Rigth to left (справа налево) это
A1 @ A2 @ A3 это
(A1 @ (A2 @ A3))
9.2.1. В выражениях.
1. Если операнд имеет тип не int и не double, то сначала приводится:
signed char --> int расширением знакового бита (7)
unsigned char --> int дополнением нулями слева
short --> int расширением знакового бита (15)
unsigned short --> unsigned int дополнением нулями слева
enum --> int порядковый номер в перечислимом типе
float --> double дробная часть дополняется нулями
2. Если любой операнд имеет тип double, то и другой операнд приводится к типу dou-
ble. Результат: типа double. Запишем все дальнейшие преобразования в виде схемы:
А. Богатырев, 1992-95 - 392 - Си в UNIX
если есть то другой результат
операнд типа приводится к типу имеет тип
if(double) -->double double
else if(unsigned long) -->unsigned long unsigned long
else if(long) -->long long
else if(unsigned int) -->unsigned int unsigned int
else оба операнда имеют тип int int
При вызове функций их аргументы - тоже выражения, поэтому в них приводятся char,short
к int и float к double. Это говорит о том, что аргументы (формальные параметры) функ-
ций можно всегда объявлять как int и double вместо char,short и float соответственно.
Зато спецификатор unsigned является существенным.
9.2.2. В присваиваниях.
op = expr;
Тип выражения expr приводится к типу левой части - op. При этом возможны приведения
более "длинного" типа к более "короткому" при помощи усечения, вроде:
int --> char обрубается старший байт.
long --> int обрубается старшее слово.
float --> int отброс дробной части
double --> int и обрубание мантиссы, если не лезет.
double --> float округление дробной части.
Вот еще некоторые приведения типов:
signed --> unsigned виртуально (просто знаковый бит
unsigned --> signed считается значащим или наоборот).
unsigned int --> long добавление нулей слева.
int --> long расширение знакового бита.
float --> int преобразование внутреннего
int --> float представления: машинно зависимо.
Некоторые преобразования могут идти в несколько стадий, например:
char --> long это
char --> int --> long
char --> unsigned long это
char --> int --> unsigned long
%d %o %X побитно
--------------------------------
0 0 0x0 0000
1 1 0x1 0001
2 2 0x2 0010
3 3 0x3 0011
4 4 0x4 0100
5 5 0x5 0101
6 6 0x6 0110
7 7 0x7 0111
А. Богатырев, 1992-95 - 393 - Си в UNIX
--------------------------------
8 010 0x8 1000
9 011 0x9 1001
10 012 0xA 1010
11 013 0xB 1011
12 014 0xC 1100
13 015 0xD 1101
14 016 0xE 1110
15 017 0xF 1111
16 020 0x10 10000
n 2**n | n 2**n
--------------|---------------
0 1 | 8 256
1 2 | 9 512
2 4 | 10 1024
3 8 | 11 2048
4 16 | 12 4096
5 32 | 13 8192
6 64 | 14 16384
7 128 | 15 32768
| 16 65536
Целые числа в большинстве современных компьютеров представлены в виде двоичного
кода. Пусть машинное слово состоит из 16 бит. Биты нумеруются справа налево начиная
с 0. Обозначим условно бит номер i через b[i]. Значением его может быть либо 0, либо
1.
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 0| 0| 0| 1| 0| 1| 1| 0| 1| 1| 0| 1| 1| 0| 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Тогда unsigned число, записанное в слове, равно
d = 2**15 * b[15] +
2**14 * b[14] +
...
2**1 * b[1] +
b[0];
(2**n - это 2 в степени n). Такое разложение числа d единственно. При сложении двух
чисел биты складываются по правилам:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 и перенос 1 в разряд слева
Числа со знаком интерпретируются чуть иначе. Бит b[15] считается знаковым: 0 - число
положительно или равно нулю, 1 - отрицательно. Отрицательные числа хранятся в виде
дополнительного кода:
-a = ~a + 1
Например:
А. Богатырев, 1992-95 - 394 - Си в UNIX
2 = 0000000000000010
~2 = 1111111111111101
~2+1 = 1111111111111110 = -2
-1 = 1111111111111111
-2 = 1111111111111110
-3 = 1111111111111101
-4 = 1111111111111100
-5 = 1111111111111011
Такое представление выбрано исходя из правила
a + (-a) = 0
знак|
2 = 0|000000000000010 сложим их
-2 = 1|111111111111110
---------|---------------
сумма: 10|000000000000000
Как видим, произошел перенос 1 в бит номер 16. Но слово содержит лишь биты 0..15 и
бит b[16] просто игнорируется. Получается, что сумма равна
0000000000000000 = 0
что и требовалось. В двоичном коде вычитание реализуется по схеме
a - b = a + (-b) = a + (~b + 1)
Восьмеричные числа соответствуют разбиению двоичного числа на группы по 3 бита и
записи каждой группы в виде соответствующей восьмеричной цифры (смотри таблицу выше).
Шестнадцатеричные числа соответствуют разбиению на группы по 4 бита (nibble):
x = 0010011111011001
число: 0010 0111 1101 1001
16-ричное: 0x 2 7 D 9 = 0x27D9
число: 0 010 011 111 011 001
8-ричное: 0 0 2 3 7 3 1 = 023731
В данном приложении приводится несколько содержательных и достаточно больших
примеров, которые иллюстрируют как сам язык Си, так и некоторые возможности системы
UNIX, а также некоторые программистские приемы решения задач при помощи Си. Многие
из этих примеров содержат в качестве своих частей ответы на некоторые из задач.
Некоторые примеры позаимствованы из других книг, но дополнены и исправлены. Все при-
меры проверены в действии. Смысл некоторых функций в примерах может оказаться вам
неизвестен; однако в силу того, что данная книга не является учебником, мы отсылаем
вас за подробностями к "Оперативному руководству" (man) по операционной системе UNIX
и к документации по системе.
И в заключение - несколько слов о путях развития языка "C". Чистый язык "C" уже
отстал от современных технологий программирования. Такие методы как модули (языки
"Modula-2", "Ada", "CLU"), родовые пакеты ("Ada", "CLU"), объектно-ориентированное
программирование ("Smalltalk", "CLU") требуют новых средств. Поэтому в настоящее
время "C" постепенно вытесняется более мощным и интеллектуальным языком "C++" |-,
обладающим средствами для объектно-ориентированного программирования и родовых
____________________
|- C++ как и C разработан в AT&T; произносится "Си плас-плас"
А. Богатырев, 1992-95 - 395 - Си в UNIX
классов. Существуют также расширения стандартного "C" объектно-ориентированными воз-
можностями ("Objective-C"). Большой простор предоставляет также сборка программ из
частей, написанных на разных языках программирования (например, "C", "Pascal", "Pro-
log").
____________________
|=|=|= Автор благодарит авторов программ и книг по Си и UNIX, по которым некогда
учился я сам; коллег из ИПК Минавтопрома/Демоса; программистов из сетей Usenet и Rel-
com, давших материалы для задач и рассуждений; слушателей курсов по Си за многочис-
ленный материал для книги.
А.Богатырев.
Ученью не один мы посвятили год,
Потом других учить пришел и нам черед.
Какие ж выводы из этой всей науки?
Из праха мы пришли, нас ветер унесет.
Омар Хайям
Оглавление.
0. Напутствие в качестве вступления. .......................................... 1
1. Простые программы и алгоритмы. Сюрпризы, советы. ........................... 3
2. Массивы, строки, указатели. ................................................ 81
3. Мобильность и машинная зависимость программ. Проблемы с русскими буквами.
........................................................................... 122
4. Работа с файлами. .......................................................... 137
5. Структуры данных. .......................................................... 172
6. Системные вызовы и взаимодействие с UNIX. .................................. 186
6.1. Файлы и каталоги. ........................................................ 189
6.2. Время в UNIX. ............................................................ 198
6.3. Свободное место на диске. ................................................ 207
6.4. Сигналы. ................................................................. 212
6.5. Жизнь процессов. ......................................................... 219
6.6. Трубы и FIFO-файлы. ...................................................... 230
6.7. Нелокальный переход. ..................................................... 233
6.8. Хозяин файла, процесса, и проверка привелегий. ........................... 235
6.9. Блокировка доступа к файлам. ............................................. 240
6.10. Файлы устройств. ........................................................ 244
6.11. Мультиплексирование ввода-вывода ......................................... 259
6.12. Простой интерпретатор команд. ........................................... 271
7. Текстовая обработка. ....................................................... 283
8. Экранные библиотеки и работа с видеопамятью. ............................... 348
9. Приложения. ................................................................ 391
9.1. Таблица приоритетов операций языка C++ .................................... 391
9.2. Правила преобразований типов. ............................................ 391
9.3. Таблица шестнадцатеричных чисел (HEX). ................................... 392
9.4. Таблица степеней двойки. ................................................. 393
9.5. Двоичный код: внутреннее представление целых чисел. ...................... 393
10. Примеры. .................................................................. 394
Пример 1. Размен монет. ......................................................
Пример 2. Подсчет букв в файле. ..............................................
Пример 3. Центрирование строк. ...............................................
Пример 4. Разметка текста для nroff. .........................................
Пример 5. Инвертирование порядка слов в строках. .............................
Пример 6. Пузырьковая сортировка. ............................................
Пример 7. Хэш-таблица. .......................................................
Пример 8. Простая база данных. ...............................................
Пример 9. Вставка/удаление строк в файл. .....................................
Пример 10. Безопасный free, позволяющий обращения к автоматическим перемен-
ным. .....................................................................
Пример 11. Поимка ошибок при работе с динамической памятью. ..................
Пример 12. Копирование/перемещение файла. ....................................
Пример 13. Обход поддерева каталогов в MS DOS при помощи chdir. ..............
Пример 14. Работа с сигналами. ...............................................
Пример 15. Управление скоростью обмена через линию. ..........................
Пример 16. Просмотр файлов в окнах. ..........................................
Пример 17. Работа с иерархией окон в curses. Часть проекта uxcom. ............
Пример 18. Поддержка содержимого каталога. Часть проекта uxcom. ..............
Пример 19. Роллируемое меню. Часть проекта uxcom. ............................
Пример 20. Выбор в строке-меню. Часть проекта uxcom. .........................
Пример 21. Редактор строки. Часть проекта uxcom. .............................
Пример 22. Выбор в прямоугольной таблице. Часть проекта uxcom. ...............
Пример 23. UNIX commander - простой визуальный Шелл. Головной модуль проекта
uxcom. ...................................................................
Пример 24. Общение двух процессов через "трубу". .............................
Пример 25. Общение процессов через FIFO-файл. ................................
Пример 26. Общение процессов через общую память и семафоры. ..................
Пример 27. Протоколирование работы программы при помощи псевдотерминала и
процессов. ...............................................................
Пример 28. Оценка фрагментированности файловой системы. ......................
Пример 29. Восстановление удаленного файла в BSD-2.9. ........................
Пример 30. Копирование файлов из MS DOS в UNIX. ..............................
Пример 31. Программа, печатающая свой собственный текст. .....................
Пример 32. Форматирование текста Си-программы. ...............................
1.11. Треугольник из звездочек. ............................................... 6
1.34. Простые числа. .......................................................... 10
1.36. Целочисленный квадратный корень. ........................................ 12
1.39. Вычисление интеграла по Симпсону. ....................................... 14
1.49. Сортировка Шелла. ....................................................... 20
1.50. Быстрая сортировка. ..................................................... 21
1.67. Функция чтения строки. .................................................. 28
1.88. Перестановки элементов. ................................................. 38
1.117. Схема Горнера. ......................................................... 58
1.137. Системная функция qsort - формат вызова. ............................... 67
1.146. Процесс компиляции программ. ........................................... 76
2.58. Функция bcopy. .......................................................... 108
2.59. Функция strdup. ......................................................... 111
2.61. Упрощенный аналог функции printf. ....................................... 112
3.9. _ctype[] .................................................................. 126
3.12. Программа транслитерации: tr. ........................................... 129
3.16. Функция записи трассировки (отладочных выдач) в файл. ................... 132
3.18. Условная компиляция: #ifdef .............................................. 132
4.39. Быстрый доступ к строкам файла. ......................................... 161
4.45. Эмуляция основ библиотеки STDIO, по мотивам 4.2 BSD. .................... 165
5.12. Отсортированный список слов. ............................................ 180
5.16. Структуры с полями переменного размера. ................................. 183
5.17. Список со "старением". .................................................. 184
6.1.1. Определение типа файла. ................................................ 189
6.1.3. Выдача неотсортированного содержимого каталога (ls). ................... 191
6.1.5. Рекурсивный обход каталогов и подкаталогов. ............................ 192
6.2.9. Функция задержки в микросекундах. ...................................... 201
6.4.3. Функция sleep. ......................................................... 217
6.10.1. Определение текущего каталога: функция getwd. ......................... 252
6.10.2. Канонизация полного имени файла. ...................................... 257
6.11.1. Мультиплексирование ввода из нескольких файлов. ....................... 259
6.11.2. Программа script. ..................................................... 261
7.12. Программа uniq. ......................................................... 285
7.14. Расширение табуляций в пробелы, функция untab. .......................... 285
7.15. Функция tabify. ......................................................... 285
7.25. Поиск методом половинного деления. ...................................... 288
7.31. Программа печати в две полосы. .......................................... 292
7.33. Инвертирование порядка строк в файле. ................................... 296
7.34. Перенос неразбиваемых блоков текста. .................................... 298
7.36. Двоичная сортировка строк при помощи дерева. ............................ 300
7.41. Функция match. .......................................................... 309
7.43. Функция контекстной замены по регулярному выражению. .................... 313
7.44. Алгоритм быстрого поиска подстроки в строке. ............................ 316
7.52. Коррекция правописания. ................................................. 321
7.67. Калькулятор-1. .......................................................... 330
7.68. Калькулятор-2. .......................................................... 336
8.1. Осыпающиеся буквы. ....................................................... 350
8.13. Использование библиотеки termcap. ....................................... 359
8.17. Разбор ESC-последовательностей с клавиатуры. ............................ 371
1) Б.Керниган, Д.Ритчи, А.Фьюер. Язык программирования Си. Задачи по языку Си. -
М.: Финансы и статистика, 1985.
2) М.Уэйт, С.Прата, Д.Мартин. Язык Си. Руководство для начинающих. - М.: Мир,
1988.
3) М.Болски. Язык программирования Си. Справочник. - М.: Радио и связь, 1988.
4) Л.Хэнкок, М.Кригер. Введение в программирование на языке Си. - М.: Радио и
связь, 1986.
5) М.Дансмур, Г.Дейвис. ОС UNIX и программирование на языке Си. - М.: Радио и
связь, 1989.
6) Р.Берри, Б.Микинз. Язык Си. Введение для программистов. - М.: Финансы и ста-
тистика, 1988.
7) М.Беляков, А.Ливеровский, В.Семик, В.Шяудкулис. Инструментальная мобильная опе-
рационная система ИНМОС. - М.: Финансы и статистика, 1985.
8) К.Кристиан. Введение в операционную систему UNIX. - М.: Финансы и статистика,
1985.
9) Р.Готье. Руководство по операционной системе UNIX. - М.: Финансы и статистика,
1986.
10) М.Банахан, Э.Раттер. Введение в операционную систему UNIX. - М.: Радио и
связь, 1986.
11) С.Баурн. Операционная система UNIX. - М.: Мир, 1986.
12) П.Браун. Введение в операционную систему UNIX. - М.: Мир, 1987.
13) M.Bach. The design of the UNIX operating system. - Prentice Hall, Englewood
Cliffs, N.J., 1986.
14) S.Dewhurst, K.Stark. Programming in C++. - Prentice Hall, 1989.
15) M.Ellis, B.Stroustrup. The annotated C++ Reference Manual. - Addison-Wesley,
1990.
/* Пример 1 */
/* Задача о размене монеты:
* Поиск всех возможных коэффициентов a0 .. an разложения числа S
* в виде
* S = a0 * c0 + a1 * c1 + ... + an * cn
* где веса c0 .. cn заданы заранее и упорядочены.
* Веса и коэффициенты неотрицательны (ai >= 0, ci >= 0).
*/
#include <stdio.h>
/* Достоинства разменных монет (веса ci) */
int cost[] = {
1, 2, 3, 5, 10, 15, 20, 50, 100, 300, 500 /* копеек */
};
#define N (sizeof cost / sizeof(int))
int count[ N ]; /* число монет данного типа (коэффициенты ai) */
long nvar; /* число вариантов */
main( ac, av ) char *av[];
{
int coin;
if( ac == 1 ){
fprintf( stderr, "Укажите, какую монету разменивать: %s число\n",
av[0] );
exit(1);
}
coin = atoi( av[1] );
printf( " Таблица разменов монеты %d коп.\n", coin );
printf( " Каждый столбец содержит количество монет указанного достоинства.\n" );
printf( "-------------------------------------------------------------------\n" );
printf( "| 5р. | 3р. | 1р. | 50к.| 20к.| 15к.| 10к.| 5к.| 3к.| 2к.| 1к.|\n" );
printf( "-------------------------------------------------------------------\n" );
change( N-1, coin );
printf( "-------------------------------------------------------------------\n" );
printf( "Всего %ld вариантов\n", nvar );
}
/* рекурсивный размен */
change( maxcoin, sum )
int sum; /* монета, которую меняем */
int maxcoin; /* индекс по массиву cost[] монеты максимального
* достоинства, допустимой в данном размене.
*/
{
register i;
if( sum == 0 ){ /* вся сумма разменяна */
/* распечатать очередной вариант */
putchar( '|' );
for( i = N-1 ; i >= 0 ; i-- )
if( count[i] )
printf(" %3d |", count[ i ] );
else
printf(" |" );
putchar( '\n' );
nvar++;
return;
}
if( sum >= cost [ maxcoin ] ){
/* если можно выдать монету достоинством cost[maxcoin] ,
* то выдать ее:
*/
count[ maxcoin ] ++; /* посчитали выданную монету */
/* размениваем остаток суммы :
* Первый аргумент - может быть можно дать еще одну такую монету ?
* Второй аргумент - общая сумма убавилась на одну монету cost[maxcoin].
*/
change( maxcoin, sum - cost[maxcoin] );
count[ maxcoin ] --; /* ... Теперь попробуем иной вариант ... */
}
/* попробовать размен более мелкими монетами */
if( maxcoin )
change( maxcoin-1, sum );
}
/* Пример 2 */
/* Подсчет количества вхождений каждой из букв алфавита в файл.
* Выдача таблицы.
* Подсчет частоты использования битов в байтах файла.
*/
#include <stdio.h>
#include <ctype.h>
long bcnt[8];
char masks[8] = { /* маски битов */
1, 2, 4, 8, 16, 32, 64, 128 };
long cnt[256]; /* счетчики для каждой из 256 букв */
/* распечатка букв в стиле языка СИ */
char *pr( c ){
static char buf[ 20 ];
switch( c ){
case '\n': return " \\n " ;
case '\r': return " \\r " ;
case '\t': return " \\t " ;
case '\b': return " \\b " ;
case '\f': return " \\f " ;
case '\033': return " ESC" ;
case '\0': return " \\0 " ;
case 0177: return " ^? " ;
}
if( c < ' ' ){
sprintf( buf, " ^%c ", c + 'A' - 1 );
}else if( isspace(c)){