Андрей Богатырев. Хрестоматия по программированию на Си в Unix

© Copyright Андрей Богатырев. 1992-95
Email: abs@opentech.olvit.ru
Txt version is located at
0. Напутствие в качестве вступления.
1. Простые программы и алгоритмы. Сюрпризы, советы.
1.11. Треугольник из звездочек.
1.34. Простые числа.
1.36. Целочисленный квадратный корень.
1.39. Вычисление интеграла по Симпсону.
1.49. Сортировка Шелла.
1.50. Быстрая сортировка.
1.67. Функция чтения строки.
1.88. Перестановки элементов.
1.117. Схема Горнера.
1.137. Системная функция qsort - формат вызова.
1.146. Процесс компиляции программ.
2. Массивы, строки, указатели.
2.58. Функция bcopy.
2.59. Функция strdup.
2.61. Упрощенный аналог функции printf.
3. Мобильность и машинная зависимость программ. Проблемы с русскими буквами.
3.9. _ctype[]
3.12. Программа транслитерации: tr.
3.16. Функция записи трассировки (отладочных выдач) в файл.
3.18. Условная компиляция: #ifdef
4. Работа с файлами.
4.39. Быстрый доступ к строкам файла.
4.45. Эмуляция основ библиотеки STDIO, по мотивам 4.2 BSD.
5. Структуры данных.
5.12. Отсортированный список слов.
5.16. Структуры с полями переменного размера.
5.17. Список со "старением".
6. Системные вызовы и взаимодействие с UNIX.
6.1. Файлы и каталоги.
6.1.1. Определение типа файла.
6.1.3. Выдача неотсортированного содержимого каталога (ls).
6.1.5. Рекурсивный обход каталогов и подкаталогов.
6.2. Время в UNIX.
6.2.9. Функция задержки в микросекундах.
6.3. Свободное место на диске.
6.4. Сигналы.
6.4.3. Функция sleep.
6.5. Жизнь процессов.
6.6. Трубы и FIFO-файлы.
6.7. Нелокальный переход.
6.8. Хозяин файла, процесса, и проверка привелегий.
6.9. Блокировка доступа к файлам.
6.10. Файлы устройств.
6.10.1. Определение текущего каталога: функция getwd.
6.10.2. Канонизация полного имени файла. 6.11. Мультиплексирование ввода-вывода
6.11.1. Мультиплексирование ввода из нескольких файлов.
6.11.2. Программа script.
6.12. Простой интерпретатор команд.
7. Текстовая обработка.
7.12. Программа uniq.
7.14. Расширение табуляций в пробелы, функция untab.
7.15. Функция tabify.
7.25. Поиск методом половинного деления.
7.31. Программа печати в две полосы.
7.33. Инвертирование порядка строк в файле.
7.34. Перенос неразбиваемых блоков текста.
7.36. Двоичная сортировка строк при помощи дерева.
7.41. Функция match.
7.43. Функция контекстной замены по регулярному выражению.
7.44. Алгоритм быстрого поиска подстроки в строке.
7.52. Коррекция правописания.
7.67. Калькулятор-1.
7.68. Калькулятор-2.
8. Экранные библиотеки и работа с видеопамятью.
8.1. Осыпающиеся буквы.
8.13. Использование библиотеки termcap.
8.17. Разбор ESC-последовательностей с клавиатуры.
9. Приложения.
9.1. Таблица приоритетов операций языка C++
9.2. Правила преобразований типов.
9.3. Таблица шестнадцатеричных чисел (HEX).
9.4. Таблица степеней двойки.
9.5. Двоичный код: внутреннее представление целых чисел.
10. Примеры.
Пример 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. Форматирование текста Си-программы.

11. Список литературы.

  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.

Напутствие в качестве вступления.

                                    Ум подобен желудку.
                                    Важно не то, сколько ты в него вложишь,
                                    а то, сколько он сможет переварить.

В этой книге вы найдете ряд задач, примеров, алгоритмов, советов и стилистических замечаний по использованию языка программирования "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) и забыть о его внутреннем устройстве (это хорошо - надо меньше помнить).

Не гонитесь за краткостью в ущерб ясности. Си позволяет порой писать такие выражения, над которыми можно полчаса ломать голову. Если же их записать менее мудрено, но чуть длиннее - они самоочевидны (и этим более защищены от ошибок).

В системе UNIX вы можете посмотреть описание любой команды системы или функции Си, набрав команду

            man названиеФункции
(man - от слова manual, "руководство").

Еще одно напутствие: учите английский язык! Практически все языки программирования используют английские слова (в качестве ключевых слов, терминов, имен переменных и функций). Поэтому лучше понимать значение этих слов (хотя и восприятие их как просто неких символов тоже имеет определенные достоинства). Обратно - программирование на Си поможет вам выучить английский.

По различным причинам на территории России сейчас используется много разных восьмибитных русских кодировок. Среди них:

  1. КОИ-8 Исторически принятая на русских UNIX системах - самая ранняя из появившихся. Отличается тем свойством, что если у нее обрезан восьмой бит: c & 0177 - то она все же читаема с терминала как транслитерация латинских букв. Именно этой кодировкой пользуется автор этой книги (как и большинство UNIX-sites сети RelCom).
  2. ISO 8859/5 Это американский стандарт на русскую кодировку. А русские программисты к ее разработке не имеют никакого отношения. Ею пользуется большинство коммерческих баз данных.
  3. Microsoft 1251 Это та кодировка, которой пользуется Microsoft Windows. Возможно, что именно к этой кодировке придут и UNIX системы (гипотеза 1994 года).
  4. Альтернативная кодировка для MS DOS Русская кодировка с псевдографикой, использовавшаяся в MS DOS.
  5. Кодировка для Macintosh
Это великое "разнообразие" причиняет массу неудобств. Но, господа, это Россия - что значит - широта души и абсолютный бардак. Relax and enjoy.

Многие примеры в данной книге даны вместе с ответами - как образцами для подра- жания. Однако мы надеемся, что Вы удержитесь от искушения и сначала проверите свои силы, а лишь потом посмотрите в ответ! Итак, читая примеры - делайте по аналогии.

Примеры.

В данном приложении приводится несколько содержательных и достаточно больших примеров, которые иллюстрируют как сам язык Си, так и некоторые возможности системы UNIX, а также некоторые программистские приемы решения задач при помощи Си. Многие из этих примеров содержат в качестве своих частей ответы на некоторые из задач. Некоторые примеры позаимствованы из других книг, но дополнены и исправлены. Все примеры проверены в действии. Смысл некоторых функций в примерах может оказаться вам неизвестен; однако в силу того, что данная книга не является учебником, мы отсылаем вас за подробностями к "Оперативному руководству" (man) по операционной системе UNIX и к документации по системе.

И в заключение - несколько слов о путях развития языка "C". Чистый язык "C" уже отстал от современных технологий программирования. Такие методы как модули (языки "Modula-2", "Ada", "CLU"), родовые пакеты ("Ada", "CLU"), объектно-ориентированное программирование ("Smalltalk", "CLU") требуют новых средств. Поэтому в настоящее время "C" постепенно вытесняется более мощным и интеллектуальным языком "C++", обладающим средствами для объектно-ориентированного программирования и родовых классов. Существуют также расширения стандартного "C" объектно-ориентированными возможностями ("Objective-C"). Большой простор предоставляет также сборка программ из частей, написанных на разных языках программирования (например, "C", "Pascal", "Pro- log").

        Ученью не один мы посвятили год,
        Потом других учить пришел и нам черед.
        Какие ж выводы из этой всей науки?
        Из праха мы пришли, нас ветер унесет.
                                Омар Хайям