книги / Практикум по программированию на языке Си
..pdfВ.В. Подбельский
Практикум
по программированию на языке Си
Допущено Министерством образования Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлениям "Прикладная математика и информатика", "Информатика и вычислительная техника"
и специальности "Прикладная математика и информатика"
Москва “Финансы и статистика” 2004
УДК 004.438(076.5) ББК 32.973.26-018.1я73
П44
РЕЦЕНЗЕНТЫ:
Кафедра системного программирования
факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова;
П.А. Андросенко,
доктор физико-математических наук, профессор, заведующий кафедрой информационно-компьютерных дисциплин
Обнинского государственного технического университета атомной энергетики
Подбельский В.В.
П44 Практикум по программированию на языке Си (+CD).: Учеб. пособие.– М.: Финансы и статистика, 2004. – 576 с.:ил.
ISBN 5-279-02289-6
Практикум содержит более 200 задач с решениями в виде программ (вместе с функциями их около 400) на языке Си. Сформулированы условия экспериментов, которые можно проделать с программами. Задачи, программы и эксперименты иллюстрируют средства языка Си и приемы современного программирования. Задачи подобраны и распределены по главам так, что объем средств языка, используемых для их решения, постепенно расширяется. На CD размещены тексты программ и компилятор DJGPP.
Для студентов и преподавателей вузов, учащихся специализированных средних учебных заведений, а также для читателей, желающих изучить профессиональное программирование на языке Си.
|
2404000000− 171 |
|
УДК 004.438(076.5) |
|
|
|
ББК 32.973.26-018.1я73 |
||
П |
|
383 |
− 2004 |
|
|
||||
|
010(01) − 2004 |
|
|
|
ISBM 5-279-02289-6 |
|
Подбельский В.В., 2004 |
ПРЕДИСЛОВИЕ
В 2002 г. языку Си исполнилось 30 лет. Как латинский язык явился основой многих европейских языков, так и язык Си стал родоначальником языков Cи++, Java, Perl, С#, PHP, JavaScript и т.д.. В отличие от мертвой латыни язык Си не только живой язык, но и наиболее распространенный и эффективный из универсальных языков программирования. Программы на языке Си исполняются почти на всех компьютерах, он работает со средой программирования UNIX, и сама операционная система UNIX написана на нем. На Си написано множество библиотечных функций и утилит. Сотни тысяч программистов знают язык Си, он неотделим от общечеловеческой культуры программирования. Любой программист должен владеть языком Си, чтобы профессионально работать в области информационных технологий и понимать своих коллег. В учебных программах и стандартах высших и средних специальных учебных заведений для большинства естественно-научных специальностей предусмотрено изучение программирования на языке Си.
Уже много лет издаются монографии и учебные пособия, где подробно рассмотрены синтаксис и семантика языка Си. Однако невозможно профессионально овладеть языком программирования, только читая учебник, необходимо писать свои программы и изучать тексты написанных программ. Предлагаемый Практикум содержит задания для разработки программ, объяснения алгоритмов и прокомментированные тексты программ. Цель Практикума – помочь читателю усовершенствовать свои знания языка Си и освоить рациональные приемы
3
составления программ на этом классическом языке. При этом выбор тем и изложение материала таковы, что читатель освоит:
!синтаксис, семантику и выразительные возможности языка Си;
!основные приемы работы с конкретным компилятором;
!принципы структурного программирования на языке Си;
!макрообработку средствами препроцессора;
!особенности реализации на языке Си классических алгоритмов обработки данных;
!возможности модульного подхода к разработке программ.
Таким образом, назначение Практикума состоит не
только в обучении языку Си, но и в том, чтобы научить читателя эффективно применять средства языка Си для решения конкретных задач.
Всовокупности задачи и соответствующие им программы иллюстрируют все механизмы языка Си и способы их применения при решении типовых проблем, возникающих в практике программирования.
Структура книги. Материал Практикума разбит на темы. Каждая из них начинается с перечня вопросов, ответы на которые будут получены при разработке алгоритмов, выбираемых для решения задач, при описании их программной реализации и обсуждении результатов выполнения программ с разными исходными данными.
Темы включают по нескольку разделов. Содержание каждого раздела составляют "задачи", "задания" и "эксперименты". Каждая задача решена автором, и результат
ввиде текста программы с необходимыми объяснениями приведен в книге. После текстов программ помещены результаты их выполнения при выбранных исходных данных. Для ряда программ показано, как они будут "себя вести" при ошибках в исходных данных.
Всвязи с тем что при решении задач программирования результат (в виде программы) обычно не может быть единственным, задачу сопровождают задания. В
4
них предлагается изменить либо условие задачи, либо предложенный автором вариант ее решения. Для нового варианта задачи (или программы) решение не всегда приведено в тексте книги. В большинстве случаев программа, соответствующая заданию, приведена в электронной поддержке1 Практикума. Учащемуся предлагается самостоятельно "поработать" на компьютере с имеющимся текстом программы либо написать свой вариант выполнения задания.
Эксперименты, роль которых особенно велика в начальных темах Практикума, еще в большей степени рассчитаны на самостоятельную работу читателя. Часто цель эксперимента – привести имеющуюся программу к аварийному завершению. Именно здесь автор следует поговорке "На ошибках учимся".
Материал тем расположен по возрастанию сложности. Если в первых темах требуется, например, напечатать значение выражения, то в последующих читатель знакомится с макросами, рекурсией, бинарными деревьями, регулярными выражениями, хешированием и другими профессиональными средствами и приемами разработки программ.
Последовательное постепенное усложнение материала связано с тем, что по мере продвижения по темам у читателя накапливается "багаж" знаний о все большем количестве средств языка и появляется возможность их активного одновременного применения. При этом автор никогда не ставил целью сформулировать и решить как можно более сложную задачу. Наоборот, часто из нескольких алгоритмов выбирался наиболее наглядный и простой, чтобы трудности разбора алгоритма не заслоняли особенностей изучаемых средств языка.
В завершение каждой темы в рубрике "Коротко о важном" приводятся выводы, практические советы и
1 Тексты программ доступны в Интернете на Web-страницах сайта http:www.finstat.ru/files.html и на прилагаемом к книге CDROM.
5
рекомендации по изученным в теме средствам языка Си и особенностям их применения.
Кому предназначена книга. Материал Практикума адресован как начинающим программистам, так и специалистам, знакомым с языком Си. Для начинающих программистов (это учащиеся и студенты средних и высших учебных заведений) Практикум послужит путеводителем при написании своих программ. Предполагается, что необходимые знания по синтаксису и семантике языка Си можно получить из какого-либо руководства по языку, например, из учебного пособия "Программирование на языке Си" (авторы В.В. Подбельский, С.С.Фомин). Практикум может служить как самоучителем, так и пособием для занятий в учебных группах. При использовании Практикума в качестве самоучителя наилучшая форма освоения материала – последовательное чтение книги, сопровождаемое выполнением на компьютере задач, заданий и экспериментов. Именно при таком изучении будет происходить постепенное накапливание знаний и повышение квалификации обучаемого. Тексты программ в электронном виде становятся особенно незаменимыми при планировании экспериментов с программами, когда в заданиях Практикума приводятся рекомендации по таким модификациям программы, которые сделают ее ошибочной, заставят компилятор выдавать диагностические сообщения и тем самым позволят обучаемому активно воспринимать излагаемый материал, суть которого иллюстрирует программа. При занятиях в учебных группах тексты программ служат образцами для решения задач, предлагаемых преподавателем на семинарах, или при выполнении практических работ на компьютере.
Выводы по темам "Коротко о важном" сформулированы в виде "рецептов", определений и предупреждений. Они могут оказать пользу при подготовке к экзамену и незаменимы при необходимости быстро разобраться в тонкостях того или иного средства языка, незнание которых мешает разработке конкретных программ.
6
Программисты, знающие Си, могут использовать Практикум как справочник, как "книгу для чтения" и как сборник типовых решений. В нем есть ответы на многие вопросы, задаваемые не только начинающими программистами. Вот некоторые из них:
!Как создать динамически растущий массив?
!Как при чтении данных, вводимых с клавиатуры, воспользоваться EOF?
!Чем отличается ввод данных функцией gets() от ввода данных функцией scanf() со спецификацией "%s"?
!Как защитить фрагмент текста от непредусмотренного повторного включения в программу?
!Чем отличается результат применения функции gets() от результата fgets()?
!Как написать макрос для удобного ввода значений переменных?
!Как сортировать разноименные однотипные объекты?
!Как написать функцию, возвращающую в виде символьного массива очередную строку из входного потока?
!Как вывести в окно MS-DOS-приложений текст на русском языке из программы, подготовленной в ко-
дах MS Windows?
!Как использовать регулярные выражения?
!Как и когда полезно применять хеширование?
И т.д.
Ответы на перечисленные и подобные им вопросы можно найти, прочитав краткие выводы по темам (разделы "Коротко о важном"). Затем можно обратиться к указанным в выводах задачам и программам.
Благодарности. Подготовке рукописи Практикума предшествовала многолетняя преподавательская работа автора на факультете прикладной математики Московского института электроники и математики. В течение этого времени на его взгляды и методику преподавания оказали влияние многие специалисты. Автор признателен своим коллегам-программистам старшего поколения Л.И. Шатровскому, З.Н. Мамотко, В.Н. Лебедеву,
7
В.И. Сердобольскому. Среди тех, с кем обсуждались особенности языка Си и ставились соответствующие учебные курсы, автор с благодарностью называет имена С.М. Лавренова, Н.Н. Ионцева, Е.В. Полякова, Т.Л. Федосеевой, С.Г. Чернацкого, В.Г. Воросколевской. Особую роль в подготовке Практикума сыграл С.С. Фомин, в соавторстве с которым ранее были написаны пособия по программированию на Си. Многочисленные продолжительные беседы с С.С. Фоминым предшествовали и началу работы над рукописью Практикума. Именно в результате этих бесед были продуманы концепции и цели ее первоначального проекта.
Автор глубоко признателен рецензентам за проявленное внимание и содержательную конструктивную критику, способствовавшую улучшению рукописи.
Тема 1
Базовые сведения о программе на Си
Сомневаться во всем, верить всему – два решения, одинаково удобные: и то и другое избавляет нас от необходимости размышлять.
А. Пуанкаре. Наука и Гипотеза
Основные вопросы темы
!Структура простейшей программы на языке Си.
!Представление исходного текста программы в электронном виде.
!Общие требования стандарта ANSI/ISO к обработке программ на языке Си.
!Этапы формирования исполнимого модуля программы (исходный текст – единица трансляции – исполнимый модуль).
!Отношение единицы трансляции и библиотечных функций.
!Трансляция и выполнение программы из командной строки ОС.
!Роль прототипов функций и назначение заголовочных файлов.
!Источник данных при исполнении программы.
!Диагностические сообщения компилятора.
!Формат препроцессорной директивы #include.
!Размещение прототипа вызываемой функции.
!Комментарии в тексте программы на Си.
!Особенности функции puts().
!Управляющие символы в выводимой строке.
1.1. Исходный текст программ
Программа на языке Си может состоять из одного или нескольких текстовых файлов, содержащих описания и определения объектов и функций. Эти исходные файлы могут транслироваться либо совместно, либо отдельно друг от друга, а затем на этапе компоновки (linkage) результаты трансляции объединяются в исполнимую про-
9
грамму (executable program). Почти обязательно в эту исполнимую программу компоновщик (linker) включает коды заранее оттранслированных библиотечных функций, вызов которых предусмотрен в исходном тексте программы.
Текст в каждом файле программы на языке Си – это конечная последовательность знаков (character – знак, символ, буква, литера). При электронном представлении программы для обработки на ЭВМ каждый знак представляется соответствующим кодом. (Вопрос о выборе того или иного кода пока оставим в стороне. Сейчас будет достаточно, если читатель понимает, что при нажатии на клавишу клавиатуры компьютер получает некоторый код, а при выводе символа на экран дисплея коду внутри ЭВМ соответствует изображение на экране.) Подготовка программы к обработке на ЭВМ состоит в оформлении ее текста в виде файла (source file - исходный файл) с помощью того или иного текстового редактора. В указанный исходный файл заносятся коды всех знаков текста программы (в том числе и коды пробелов) и вспомогательные (служебные) коды, обеспечивающие правильное форматирование ее текста при печати и/или отображении на экране дисплея. Тот факт, что программа – это конечная последовательность кодов ее знаков, достаточно привычен и мало кого может удивить. Но роль, влияние и значение вспомогательных кодов, включаемых текстовым редактором в файл программы при наборе ее текста, часто остаются непонятными.
Например, до ознакомления с влиянием вспомогательных кодов невозможно правильно и обоснованно ответить на следующий вопрос: "Можно ли исходный текст программы на языке Си записать в виде единственной (может быть, очень длинной) строки, т.е. не добавлять в код ее текста переходов на новые строки?" Существуют и другие вопросы, затрагивающие роль вспомогательных кодов в тексте программы на Си, но рассмотрим сами вспомогательные коды.
В исходный текст программы на Си стандартом предусмотрено включение следующих вспомогательных кодов, называемых управ-
ляющими символами (control characters):
! |
горизонтальная табуляция |
(horizontal tab); |
! |
вертикальная табуляция |
(vertical tab); |
! |
перевод страницы |
(form feed); |
! |
индикация конца строки |
(end-of-line indicator); |
! звуковой или световой сигнал |
(alert); |
|
! возврат на одну позицию |
(backspace); |
10