Обзор современных средств создания компьютерных программ. Основы алгоритмизации задач

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Институт Прикладной математики и компьютерных наук Кафедра Вычислительной техники Савин Н.И. Доцент, кандидат технических наук КОНСПЕКТ ЛЕКЦИЙ учебной дисциплины «Программирование» Уровень профессионального образования: (высшее образование – бакалавриат) Направление подготовки:09.03.01Информатика и вычислительная техника Профиль подготовки: Вычислительные машины, комплексы, системы и сети Профиль подготовки:Автоматизированные системы обработки информации и управления Квалификация выпускника: Академический бакалавр Форма обучения:дистанционная Тула 2017 Содержание 1 Обзор современных средств создания компьютерных программ 3 2 Основы алгоритмизации задач 10 3 Введение в язык С 16 4 Встроенные операции в языке С 21 5 Операторы языка С 28 6 Структурированные данные - массивы 35 7 Указатели 44 8 Функции. 58 9 Производные типы данных – структуры, битовые поля, объединения, перечисления 75 10 Организация операций ввода-вывода 89 11 Файловая система 94 1 Обзор современныхсредств создания компьютерных программ 1.1. 1.2. 1.3. 1.4. 1.5. Введение. Цель и задачи курса, его структура и связь с другими дисциплинами. Назначение ЭВМ. Современный компьютер, перспективы развития. Этапы подготовки задачи к решению на ЭВМ. Общие принципы построения и использования языков программирования Стандарты языков программирования. 1.1 Первые языки программирования В пятидесятые годы двадцатого века с появлением компьютеров на электронных лампах началось бурное развитие языков программирования. Компьютеры, стоившие в то время значительно дороже, чем разработка любой программы, требовали высокоэффективного кода. Такой код разрабатывался вручную на языке Ассемблер. В середине 50-х годов под руководством Джона Бэкуса для фирмы IBM был разработан алгоритмический язык программирования FORTRAN. Несмотря на то, что уже существовали разработки языков, выполняющие преобразование арифметических выражений в машинный код, создание языка FORTRAN (FORmula TRANslator), предоставляющего возможность записи алгоритма вычислений с использованием условных операторов и операторов ввода/вывода, стало точкой отсчета эры алгоритмических языков программирования. К языку FORTRAN предъявлялись требования cоздания высокоэффективного кода. Поэтому многие конструкции языка первоначально разрабатывались с учетом архитектуры IBM 407. Успех разработки этого языка привел к тому, что производители других вычислительных систем стали создавать свои версии трансляторов. С целью некоторой возможной на тот момент унификации языка язык FORTRAN IV, разработанный в 1966 году, стал первым стандартом, именуемым FORTRAN 66. Как альтернатива языку FORTRAN, первоначально ориентированному на архитектуру IBM, под руководством Питера Наура в конце 50-х годов был разработан язык ALGOL (ALGOrithmic Language). Основной целью, преследуемой разработчиками этого языка, была независимость от конкретной архитектуры вычислительной системы. Кроме того, создатели языка ALGOL стремились разработать язык, удобный для описания алгоритмов и применяющий систему обозначений, близкую к той, что принята в математике. Языки FORTRAN и ALGOL были первыми языками, ориентированными на программирование вычислений. Язык PL 1, первые версии которого появились в начале 60-х годов, был первоначально ориентирован на IBM 360 и расширял возможности языка FORTRAN некоторыми средствами языка COBOL, разработанного в эти же годы. Несмотря на определенную популярность языка PL/I у программистов, работавших на компьютерах IBM и машинах серии ЕС, в настоящее время он представляет чисто теоретический интерес. В конце 60-х годов под руководством Найарда и Дала был разработан язык Simula-67, использующий концепцию пользовательских типов данных. Фактически это первый язык, применяющий понятие классов. В середине 70-х годов Вирт предложил язык Pascal, который сразу стал широко использоваться. В это же время по инициативе Министерства обороны США началась работа по созданию языка высокого уровня, получившего название Ada – в честь Ады Лавлейс, программистки и дочери лорда Байрона. Создание языка началось с определения требований и выработки спецификаций. Над проектом работали четыре независимые группы, но все они использовали как основу язык Pascal. В начале 80-х годов был разработан первый промышленный компилятор языка Ada. Универсальный язык программирования С был разработан в середине 70-х годов Денисом Ритчи и Кеном Томпсоном. Этот язык стал популярным языком системного программирования и в свое время использовался для написания ядра операционной системы UNIX. Стандарт языка С начал разрабатываться рабочей группой института стандартов ANSI в 1982 году. Международный стандарт языка С принят в 1990 году. Язык С лег в основу разработки языков программирования C++ и Java. Наряду с алгоритмическими языками параллельно развивались и языки, предназначаемые для обработки деловой информации, а также языки искусственного интеллекта. Кпервымотноситсяязык COBOL (COmmon Business Oriented Language), аковторым – языки LISP (LISt Processing) и Prolog. Язык LISP, разработанный в 60-х годах под руководством Дж. Маккарти, был первым функциональным языком обработки списков, который нашел широкое применение в теории игр. С появлением персональных компьютеров языки стали составными частями интегрированных сред разработки. Появились языки, применяемые в различных офисных программах, например VBA (Visual Basic for Application). В 90-х годах с распространением сети Интернет расширяется возможность распределенной обработки данных, что отражается и на развитии языков программирования. Появляются языки, ориентированные на создание серверных приложений, такие как Java, Perl и PHP, языки описания документов – HTML и XML. Традиционные языки программирования С++ и Pascal также претерпевают изменения: под языком программирования начинает пониматься не только функциональность самого языка, а также библиотеки классов, предоставляемые средой программирования. Акцент со спецификации самих языков программирования переносится на стандартизацию механизмов взаимодействия распределенных приложений. Появляются новые технологии – COM и CORBA, специфицирующие взаимодействие распределенных объектов. 1.2 Области применения языков программирования В настоящее время языки программирования применяются в самых различных областях человеческой деятельности, таких как:  научные вычисления (языки C++, FORTRAN, Java);  системное программирование (языки C++, Java);  обработка информации (языки C++, COBOL, Java);  искусственный интеллект (LISP, Prolog);  издательская деятельность (Postscript, TeX);  удаленная обработка информации (Perl, PHP, Java, C++);  описание документов (HTML, XML). С течением времени одни языки развивались, приобретали новые черты и остались востребованы, другие утратили свою актуальность и сегодня представляют в лучшем случае чисто теоретический интерес. В значительной степени это связано с такими факторами, как:  наличие среды программирования, поддерживающей разработку приложений на конкретном языке программирования;  удобство сопровождения и тестирования программ;  стоимость разработки с применением конкретного языка программирования;  четкость и ортогональность конструкций языка;  применение объектно-ориентированного подхода. 1.3 Парадигмы программирования Синтаксис языка описывает систему правил написания различных языковых конструкций, а семантика языка программирования определяет смысл этих конструкций. Синтаксис языка программирования может быть описан с помощью НБФ-нотаций. Семантика языка взаимосвязана с используемой вычислительной моделью. В настоящее время языки программирования в зависимости от применяемой вычислительной модели делятся на четыре основные группы:  Процедурные языки, которые представляют собой последовательность выполняемых операторов. Если рассматривать состояние ПК как состояние ячеек памяти, то процедурный язык – это последовательность операторов, изменяющих значение одной или нескольких ячеек. К процедурным языкам относятся FORTRAN, C, Ada, Pascal, Smalltalk и некоторые другие. Процедурные языки иногда также называются императивными языками. Код программы на процедурном языке может быть записан следующим образом: оperator1; operator2; operator3;  Аппликативные языки, в основу которых положен функциональный подход. Язык рассматривается с точки зрения нахождения функции, необходимой для перевода памяти ПК из одного состояния в другое. Программа представляет собой набор функций, применяемых к начальным данным, позволяющий получить требуемый результат. К аппликативным языкам относится язык LISP. Код программы на аппликативном языке может быть записан следующим образом: function1(function2(function3(beginning_date)));  Языки системы правил, называемые также языками логического программирования, основываются на определении набора правил, при выполнении которых возможно выполнение определенных действий. Правила могут задаваться в виде утверждений и в виде таблиц решений. К языкам логического программирования относится язык Prolog. Код программы на языке системы правил может быть записан следующим образом: if condition1 then operator1; if condition2 then operator2; if condition3 then operator3;  Объектно-ориентированные языки, основанные на построении объектов как набора данных и операций над ними. Объектно-ориентированные языки объединяют и расширяют возможности, присущие процедурным и аппликативным языкам. К объектно-ориентированным языкам относятся C++, Object Pascal, Java. В настоящий момент наибольшее распространение получили языки, основанные на объектноориентированной модели. Они, реализуя процедурную модель построения языка, поддерживают аппликативность конструкций, позволяя представлять блок-схему выполнения структурированной программы как некоторый набор аппликативных функций. 1.4 Стандартизация языков программирования Концепция языка программирования неотрывно связана с его реализацией. Для того чтобы компиляция одной и той же программы различными компиляторами всегда давала одинаковый результат, разрабатываются стандарты языков программирования. Существует ряд организаций, целенаправленно занимающихся вопросами стандартизации. Это Американский национальный институт стандартов ANSI (American National Standards Institute), Институт инженеров по электротехнике и электронике IEEE (Institute of Electrical and Electronic Engineers), Организация международных стандартов ISO (International Organization for Standardization). Как правило, при создании языка выпускается частный стандарт, определяемый разработчиками языка. Если язык получает широкое распространение, то со временем появляются различные версии компиляторов, которые не точно следуют частному стандарту. В большинстве случаев идет расширение зафиксированных первоначально возможностей языка. Для приведения наиболее популярных реализаций языка в соответствие друг с другом разрабатывается согласительный стандарт. Очень важным фактором стандартизации языка программирования является своевременность появления стандарта – до широкого распространения языка и создания множества несовместимых реализаций. В процессе развития языка могут появляться новые стандарты, отражающие современные нововведения. Так, язык FORTRAN первоначально был стандартизирован в 1966 году. В результате был издан стандарт FORTRAN 66. Далее этот стандарт несколько раз пересматривался (в 1977 году был выпущен FORTRAN 77, затем появился и FORTRAN 90). Язык Java, ставший в последнее время весьма распространенным, постепенно был значительно расширен и модифицирован: новая спецификация получила название Java 2. В процессе развития языка некоторые его конструкции и функции устаревают. Однако с целью обратной совместимости новые версии должны поддерживать и все устаревающие возможности. Это ведет к "разбуханию" компиляторов. В последнее время в реализациях введено понятие не рекомендуемой и устаревшей возможности. В первом случае следующий стандарт еще будет поддерживать не рекомендуемую возможность, но может перевести ее в категорию устаревшей. Во втором случае стандарт может исключить поддержку возможности, объявленной ранее как устаревшая. Введение не рекомендуемых и устаревших возможностей предоставляет разработчикам временной интервал, в течение которого они могут модифицировать код в соответствии с новыми требованиями стандарта. 1.5 Среда проектирования С развитием языков программирования совершенствовались и средства разработки программ – от режима командной строки до интегрированной среды проектирования. Такая среда предоставляет удобный графический интерфейс разработки и большой спектр сервисов, включающих управление версиями хранимых данных, утилиты просмотра и управления информацией, библиотеки классов, мастера создания шаблонов приложений и т.п. Компилятор языка программирования выступает как составная часть среды проектирования. Сама программа наряду с конструкциями, предусмотренными стандартом, как правило, использует библиотечные функции и классы, предоставляемые средой проектирования. Так, интегрированная среда разработки VisualStudio.NET содержит библиотеку классов MFC (Microsoft Foundation Classes), значительно упрощающую процесс разработки приложений, использующих оконный интерфейс. Интегрированная среда проектирования VisualStudio.NET (MicrosoftVisualStudio) позволяет создавать и компилировать приложения на языках C++, C#, Visual Basic и VisualJ. Для разработки приложений на языке С++ предназначается также среда CBuilder (CodeGear). Для проектирования приложений на языке Object Pascal используется интегрированная среда проектирования Delphi (CodeGear). Наиболее удобной средой разработки программ на языке Java является интегрированная среда проектирования JBuilder. 1.6 Модели трансляциипрограмм Трансляторы Программа, написанная на языке высокого уровня, перед исполнением должна быть преобразована в программу на "машинном языке". Такой процесс называется трансляцией. По типу выходных данных различают два основных вида трансляторов:  компилирующие - получают объектный код программы;  интерпретирующие – получают интерпретируемый код, для выполнения которого требуется дополнительное программное обеспечение. Окончательным выполнимым кодом являются приложения, реализованные как EXE-файлы, DLL-библиотеки, COM-компоненты. К интерпретируемому коду можно отнести байт-код JAVA-программ, выполняемый посредством виртуальной машины JVM. Языки, формирующие объектный код, называются компилируемыми языками. К ним относятся языки С, C++, FORTRAN, Pascal. Языки, реализующие интерпретируемый код, называются интерпретируемыми языками. К таким языкам относятся язык Java, LISP, Perl, Python, Бейсик. В большинстве случаев код, получаемый в результате процесса трансляции, формируется из нескольких программных модулей. Программным модулем называется определенным образом оформленный код на языке высокого уровня. Процесс трансляции в этом случае может выполняться как единое целое – компиляция и редактирование связей, или как два отдельных этапа – сначала компиляция объектных модулей, а затем вызов редактора связей, создающего окончательный код. Последний подход более удобен для разработки программ. Он реализован в трансляторах языков С и С++. Объектный код, создаваемый компилятором, представляет собой область данных и область машинных команд, имеющих адреса, которые в дальнейшем "согласуются" редактором связи (иногда называемым загрузчиком). Редактор связи размещает в едином адресном пространстве все по отдельности откомпилированные объектные модули и статически подключаемые библиотеки. Будем называть выполнимой формой программы код, получаемый в результате трансляции исходной программы. Процесс трансляции Программу, написанную на языке программирования высокого уровня, называют исходной программой, а каждую самостоятельную программную единицу, образующую данную программу, - программным модулем. Для преобразования исходной программы в ее выполняемую форму (выполнимый файл) транслятор выполняет некоторую последовательность действий. Эта последовательность зависит как от языка программирования, так и от конкретной реализации самого транслятора. В ходе трансляции важно не просто откомпилировать программу, а получить при этом достаточно эффективный код. В процессе трансляции выполняется анализ исходной программы, а затем синтез выполнимой формы данной программы. В зависимости от числа просмотров исходной программы, выполняемых компилятором, трансляторы разделяются на однопроходные, двухпроходные и трансляторы, использующие более двух проходов. К достоинствам однопроходного компилятора можно отнести высокую скорость компиляции, а к недостаткам - получение, как правило, не самого эффективного кода. Широкое распространение получили двухпроходные компиляторы. Они позволяют при первом проходе выполнить анализ программы и построить информационные таблицы, используемые при втором проходе для формирования объектного кода. На рисунке 2.1 представлены основные этапы, выполняемые в процессе трансляции исходной программы. Рис. 2.1. Основные этапы трансляции программы Фаза анализа программы состоит из:  лексического анализа;  синтаксического анализа;  семантического анализа. При анализе исходной программы транслятор последовательно просматривает текст программы, представимой как набор символов, выполняя разбор структуры программы. На этапе лексического анализа выполняется выделение основных составляющих программы – лексем. Лексемами являются ключевые слова, идентификаторы, символы операций, комментарии, пробелы и разделители. Лексический анализатор не только выделяет лексемы, но и определяет тип каждой лексемы. При этом на этапе лексического анализа составляется таблица символов, в которой каждому идентификатору сопоставлен свой адрес. Это позволяет при дальнейшем анализе вместо конкретного значения (строки символов) использовать его адрес в таблице символов. Процесс выделения лексем достаточно трудоемок и требует применения сложных контекстно-зависимых алгоритмов. На этапе синтаксического анализа выполняется разбор полученных лексем с целью получения семантически понятных синтаксических единиц, которые затем обрабатываются семантическим анализатором. Так, синтаксическими единицами выступают выражения, объявление, оператор языка программирования, вызов функции. На этапе семантического анализа выполняется обработка синтаксических единиц и создание промежуточного кода. В зависимости от наличия или отсутствия фазы оптимизации результатом семантического анализа может быть оптимизируемый далее промежуточный код или готовый объектный модуль. К наиболее общим задачам, решаемым семантическим анализатором, относятся:  обнаружение ошибок времени компиляции;  заполнение таблицы символов, созданной на этапе лексического анализа, конкретными значениями, определяющими дополнительную информацию о каждом элементе таблицы;  замена макросов их определениями;  выполнение директив времени компиляции. Макросом называется некоторый предварительно определенный код, который на этапе компиляции вставляется в программу во всех местах указания вызова данного макроса. На фазе синтеза программы производится:  генерация кода;  редактирование связей. Процесс генерации кода состоит из преобразования промежуточного кода (или оптимизированного кода) в объектный код. При этом в зависимости от языка программирования получаемый объектный код может быть представлен в выполнимой форме или как объектный модуль, подлежащий дальнейшей обработке редактором связей. Так, процесс генерации кода является неотъемлемой частью фазы синтеза программы, а необходимость выполнения редактора связей зависит от конкретного языка программирования. Следует учесть, что на практике термин "генерация кода" часто применяют ко всем действиям фазы синтеза программы, ведущим к получению выполнимой формы программы. Редактор связей приводит в соответствие адреса фрагментов кода, расположенных в отдельных объектных модулях: определяются адреса вызываемых внешних функций, адреса внешних переменных, адреса функций и методов каждого модуля. Для редактирования адресов редактор связей использует специальные, создаваемые на этапе трансляции, таблицы загрузчика. После обработки объектных модулей редактором связей генерируется выполнимая форма программы. 1.7 Формальные грамматики для представления синтаксиса языков программирования НБФ-грамматика Грамматикой называется формальное описание синтаксиса языка программирования. Грамматика определяется набором правил (называемых иногда правилами подстановки), определяющих формирование из лексем достоверных программ. Формальная грамматика использует строгую систему обозначений. Существуют различные типы грамматик. НБФ-грамматика (грамматика Наура-Бэкуса или грамматика Бэкуса-Наура - БНФ-грамматика) является контекстно-свободной грамматикой. Эта грамматика использует НБФ-нотации, предложенные Джоном Бэкусом в конце 50-х годов для описания синтаксиса языка ALGOL. Простая НБФ-нотация позволяет описывать все достоверные конструкции языка программирования, используя следующие символы:  символ ::= имеет значение "определяется как" и предшествует указанию всех допустимых значений описываемой синтаксической единицы;  символ | имеет значение "или" и используется для перечисления альтернативных вариантов;  пара символов <> ограничивает имя синтаксической единицы, называемой также нетерминальным символом или синтаксической категорией. Значения, указываемые вне скобок <>, называются терминальными символами. НБФ-грамматика состоит из набора правил (называемых иногда металингвистическими формулами или продукциями), записываемых при помощи НБФ-нотации. Например: <цифра>::= 0|1|2|3|4|5|6|7|8|9 <целочисленное значение> ::= цифра | цифра < целочисленное значение> В данном примере символы 0, 1, 2, 3 и т.д. являются терминальными символами. При построении грамматики, описывающей язык программирования, выделяется начальный нетерминальный символ, определяющий конструкцию "программа". Существуют порождающие и распознающие грамматики. Порождающая грамматика генерирует множество цепочек терминальных символов из начального символа, а распознающая грамматика используется для построения по цепочке символов дерева грамматического разбора, ведущего к начальному символу. Можно сказать, что грамматика состоит из множества терминальных и нетерминальных символов, начального нетерминального символа и набора правил. В 1959 году Ноам Хомский предложил следующую классификацию грамматик:  регулярные грамматики, используемые для построения лексических анализаторов;  контекстно-свободные грамматики, используемые для построения дерева грамматического разбора. К этому типу относятся НБФ-грамматики;  контекстно-зависимые грамматики, представляемые набором правил типа x->y, в которых х может быть любой цепочкой нетерминальных символов, а y – цепочкой терминальных и нетерминальных символов. Этот тип грамматик намного сложнее контекстно-свободных грамматик и не имеет столь широкого применения при моделировании языков программирования;  грамматики с фразовой структурой, реализуемые набором правил типа x->y, в которых х может быть любой цепочкой нетерминальных символов, а y – цепочкой терминальных и нетерминальных символов (при этом нет никаких ограничений на длину получаемых цепочек символов). Большинство таких грамматик являются неразрешимыми и не имеют практического интереса. Расширенная НБФ-нотация При описании правил НБФ-грамматики с применением стандартной НБФ-нотации синтаксические конструкции, имеющие необязательные или альтернативные элементы, выглядят при всей их простоте достаточно громоздко. Расширенная НБФ-нотация вводит ряд дополнительных элементов, позволяющих значительно улучшить наглядность представления правил НБФ-грамматики. Расширенная НБФ-нотация вводит следующие дополнительные элементы:  необязательные элементы указываются заключенными в квадратные скобки;  альтернативные элементы, указываемые через символ вертикальной черты, также могут являться необязательными элементами, заключаемыми в квадратные скобки;  последовательность нескольких однотипных элементов обозначается заключением элемента в фигурные скобки, за которыми указывается символ звездочка ({<целое>}*). 2 Основыалгоритмизации задач 2.1. Введение в алгоритмизацию задач. Общее понятие алгоритма. Способы описания алгоритма. 2.2. Алгоритмы линейной структуры и структуры выбора, их схемное описание. Алгоритмизация типовых задач. Схемное описание типовых задач. 2.3. Алгоритмы структуры вложенных повторений.Алгоритмизация типовых задач. Схемное описание типовых задач. 2.1 Последовательность этапов проектирования программ 2.1.1 Формирование технического задания Производится совместно с заказчиком программного продукта и включает следующие пункты:  назначение программы;  вычислительную среду для эксплуатации;  функциональные характеристики программы;  область значений программы;  область определения программы;  эксплуатационные характеристики. 2.1.2 Постановка задачи. При постановке задачи на создание программы необходимо учитывать следующее:  назначение программы;  вычислительную среду для эксплуатации;  вычислительную среду для создания программы;  функциональные характеристики программы;  математические и алгоритмические методы решения составных частей общей задачи;  область значений программы;  область определения программы;  эксплуатационные характеристики. Пример постановки задачи. Вычисление площади треугольника по трем сторонам Исходные данные: переменные a, b, c - стороны треугольника. Результат: S - площадь треугольника. Ограничения: Все переменные – положительные вещественные числа. Постановка задачи. Назначение: Функциональная компонента библиотеки математических функций. Среда эксплуатации: Стандартный компьютер архитектуры IBMPC. ОС WindowsXP. Алгоритмический язык, в котором можно использовать программу – С и С++. Производительность системы – не менее 1 миллиона условных команд в секунду. Среда разработки: Стандартный компьютер архитектуры IBMPC. ОС WindowsXP. Программная среда разработки – CodeGearRADStudio. Алгоритмический язык программирования - С Производительность системы – не менее 1 миллиона условных команд в секунду. Функциональные характеристики: Проверка на соответствие чисел треугольнику. Вычисление площади треугольника по формуле Герона. Математические и алгоритмические методы решения составных частей общей задачи: Алгоритм проверки на вырожденность треугольника. Формула Герона вычисления площади треугольника по трем сторонам. {Площадь вычисляется по формуле Герона  S= p( p  a)( p  b)( p  c) где p - полупериметр  a, b, c> 0, если max(a, b, c) = c, то a+ b>c для треугольника. В этом случае p>c должно быть, так как a+ b>c, т.е. a+ b +c> 2c, и (a+ b +c)/2 >c. Примечание. Как правило математические и алгоритмические методы приводятся в специальных разделах документа, при общей постановке только указываются названия методов и алгоритмов.} Область значений программы: Площадь вычисляется в стандартном формате чисел с плавающей точкой, точность представления соответствует выбранному формату чисел. Если площадь вычислить невозможно, то функция возвращает -1. Организация данных. В программе будут использованы следующие скалярные переменные. a, b, c - стороны треугольника d - наибольшая из сторон p - полупериметр S - площадь треугольника, причем p>d, S>0, a>0, b>0, c>0 и все переменные вещественные. Эксплуатационные характеристики: Объем требуемой памяти – 30К. Время выполнения – не более 1 мсек. 2.1.3 Алгоритмизация. Логика работы программы описывается на языке схем алгоритмов, либо в виде словесно-формульной, либо в виде псевдокода. В языке схем алгоритмов используются следующие обозначения. а) последовате льность операторов б) ввод в) выбор A A г) цикл д) начало завершение е) множественный выбор Описание алгоритма в словесной форме: 1. Начало. 2. Задание a, b, c. 3. Вычисление p. 4. Нахождение наибольшей стороны. 5. Если a, b, c - стороны треугольника то- вычислить площадь Sи вывести результат, иначе- вывести, что a, b, c - не стороны треугольника. 6. Конец. Описание алгоритма в виде псевдокода: 1. inta, b, c, d; float p; 2. p=(a+b+c)/2 3. d=ad, то S = sqrt (p*(p-a)*(p-b)*(p-c)) и возвратитьS. Иначе возвратить -1. 6. Конец. 2.1.4 Программирование. Перевод алгоритма решения задачи на необходимый язык программирования с комментариями и контролем вводимых данных. 2.1.5 Тестирование и отладка. После трансляции исправить синтаксические ошибки. Подготовить тестовые примеры, простые, но достаточно полно проверяющие программу по каждой ветви алгоритма. Задать входные данные Результат 3, 4, 5 6. 1, 1, 2 -1. 0, 0, 0 -1. 1, 1, 3 -1. 2, 1, -3 -1. 2.1.6 Документирование При документировании разработки как правило создается технический отчет (в большинстве случаев используется MS Word). В отчет включаются следующие разделы:  Техническое задание;  Постановка задачи;  Математические методы решения задачи;  Структура программы;  Схема данных;  Алгоритмы модулей и функционально законченных блоков программы;  Программные компоненты;  Алгоритмы и методы тестирования программы;  Описание пакета установки;  Инструкция программисту;  Инструкция пользователю;  Библиографический список;  Приложения (в приложения включить коды программных компонент и структур данных, результаты тестирования, а также необходимый иллюстративный материал) 2.2 Методы пректирования программ К методам проектирования программ относят: нисходящее проектирование; восходящее проектирование; структурное проектирование; объектно-ориентированноепрограммирование. Структуры программы формируются по следующим принципам: функциональной(процедурной) декомпозиции; модульному; объектно-ориентированному; комплексному. Последовательность этапов решения задач при нисходящем проектировании. Нисходящее проектирование рассматривается как последовательность шагов, уточняющих проект. Рассмотрим схему нисходящего проектирования программы, изображенную на рисунке. уровень 1 уровень 2 Модуль 1 eehjdtm уровень 3 Модуль А уровень 4 Главная программа Модуль 2 Модуль В Модуль 3 Модуль С Модуль А Модуль D На верхнем уровне иерархии выделяется главная функция, которая реализует поставленную задачу. На следующем, втором, уровне иерархии располагаются функции, использование которых позволяет выполнить главную функцию и т.д. Функции, имеющие самостоятельное значение, называются модулями. Правила построения иерархической схемы. 1. Каждый модуль может быть связан только с одним модулем верхнего уровня и несколькими модулями нижнего уровня. Имеет один вход и один выход на каждый модуль нижнего уровня. 2. Если обращение к одному модулю происходит несколько раз, то его изображают на схеме столько раз и в тех местах, где он необходим. После окончания работы модуль (i+1)- го уровня возвращает управление вызвавшему его модулю i- го уровня. Работа завершается окончанием выполнения модуля верхнего уровня ( главной программы). Процесс проектирования главной программы состоит в следующем: 1. Постановка задачи, для решения которой создается главная программа. 2. Определение входных данных программы. 3. Определение выходных данных программы. 4. Выделение модулей 2- го уровня, необходимых для решения поставленной задачи, т.е. для преобразования входных данных в выходные. Для каждого модуля 2 -го и последующих уровней, так же как и для главной программы, необходимо определить назначение модуля, его входные и выходные данные и, если необходимо, то выделить модули следующего уровня иерархии, т.е. повторить пункты 1- 4 процесса проектирования. На этапе пограммной реализации необходимо использовать приемы модульного программирования, т.е. независимого программирования каждого модуля. Необходимо начать с главного модуля и некоторого числа модулей верхнего уровня, после чего программа тестируется. Вместо незапрограммированных модулей делаются заглушки, например, оператор печати имени модуля. При реализации отдельных модулей необходимо придерживаться основных положений структурного программирования: 1. Любая программа составляется из алгоритмических структур трех видов - линейной, разветвляющейся, циклической. 2. Между ними передача управления осуществляется только вперед (сверху вниз). 3. Нельзя использовать в программе команды безусловного перехода GOTO. Для имен переменных необходимо использовать осмысленные имена, широко использовать ясные комментарии. Пример нисходящего проектирования программы. Рассмотрим следующую задачу. Пусть дано натуральное число N = 100. Необходимо вывести на экран всех близнецов среди первых N простых чисел. (Числа L и M называются близнецами, если L и M простые и разность между ними равна 2 ). Программу, реализующую эту задачу, назовем главной - MAIN. Входные данные программы - константа N = 100, выходные данные - множество пар близнецов среди первых 100 простых чисел, и число таких пар T_N. Алгоритм решения задачи поначалу можно представить как последовательное решение следующих двух подзадач: Подзадача 1. Просматриваем натуральные числа 2, 3, ...в порядке возрастания и формируем массив простых чисел P_A[ ] длиной N. Подзадача 2. Просматриваем массив простых чисел P_A. Если два соседних числа отличаются на 2, то выводим их как пару близнецов. Подзадачу 1 реализуем с помощью процедуры PRIME. Входные данные - натуральное число N = 100, выходные данные - массив простых чисел P_A длиной N. Подзадачу 2 реализуем с помощью процедуры TWINS, которая имеет входные данные- массив простых чиселP_A, а выходные данные - множество пар близнецов и число таких пар T_N. Имеем следующую иерархическую систему модулей Программа MAIN будет иметь следующий вид: MAIN PRIME TWINS Программа MAIN печатает множество пар близнецов среди первых 100 простых чисел и число таких пар N = 100 массив P_A[N] (массив простых чисел) -------------------------Функция PRIME (описание функции PRIME) Вывод "PRIME" (заглушка для функции) ------------------------Функция TWINS (описание функции TWINS ) Вывод " TWINS" (заглушка для функции) ------------------------Вызов PRIME Вызов TWINS Алгоритм решения подзадачи PRIME. Последовательно просматриваются натуральные числа и для каждого из них проверяются, является ли оно простым. Если да, то оно заносится в массив P_A, а счетчик простых чисел N_Pувеличивается на 1. Первые два простых числа - это 2 и 3. Следующие простые числа ищем среди нечетных. Функцию, проверяющую, является ли число простым, назовем IS_P. Если ее аргумент число простое, то она возвращает логическую величину true, иначе - false. Проверку числа на простоту можно осуществить по правилу: натуральное число будет простым тогда, когда оно не делится ни на одно простое число, меньшее его самого, что можно проверить по остатку от деления этих чисел. Иерархическая система модулей теперь имеет вид: M A IN P R IM E T W IN S IS _ P Функция PRIME будет иметь следующий вид: Функция PRIME формирует массив простых чисел N_P (число простых чисел, меньших М) ------------------------------------------------------------Функция IS_P(х) проверяет, является ли число х простым, возвращает логическую величину true, если х - простое, иначе возвращает false). Flag - логическая переменная, принимает значение ложь, если х делится нацело на одно из простых чисел меньших х. Псевдокод функции IS_P(х) j=2 Flag = true IS_P = true пока( jменьшеилиравноN_PиFlag=true) выполнить если остаток от деления х на элемент массива P_A[j] не равно 0 то увеличить j на 1 иначеFlag = falseиIS_P = false ----------------------------------------------------------------------ПсевдокодфункцииPrime М=3 (простое число) N_P = 2 (его номер по порядку или количество) P_A[1] = 2 P_A[2] = 3 пока (N_P меньше N = 100) выполнить увеличить М на 2 (следующее нечетное число) еслиIS_P(М)=true то увеличить N_P на 1 P_A[N_P] = M (новое значение массива простых чисел) ----------------------------------------------------------------------Функция TWINS Функция TWINS представляет собой цикл, в котором вычисляется разность между двумя соседними элементами массива P_A[]. Если она равна 2, то вывод пары близнецов, а счетчик пар близнецов T_N увеличиваем на 1. T_N = 0 ( число пар близнецов) цикл (по j от 1 до N-1) выполнить если P_A[j+1] - P_A[j] =2 то вывести на экран значения элементов массива P_A[j] и P_A[j+1] увеличить счетчик: T_N = T_N +1 вывести значение T_N Если вместо заглушек на место функций PRIME и TWINS установить вышеописанные функции, то поставленная нами задача будет решена. Алгоритм реализуется на выбранном языке программирования. 2.3 Основные элементы программирования Целью большинства программ является решение задач обработки информации. Программа решает задачи, манипулируя информацией или данными. При программировании необходимо использовать следующие элементы: * ввод данных в программу (с помощью клавиатуры или из файла) * выделение места для хранения данных в памяти * использование операторов языка программирования по обработке информации * вывод информациина внешние носители информации (монитор, файл, принтер) Операторы программы могут быть организованы так, что: * некоторые из них будут выполняться только тогда, когда специальное условие (или набор условий) истинно * другие будут повторяться несколько раз * третьи разбиты на группы, которые могут выполняться в различных местах вашей программы и вызов осуществляется по имени и с возможностью задания параметров. Семь основных элементов программирования: ввод, тип данных, операции, вывод, условное выполнение, циклы и подпрограммы. Этот список не полон, но он все же описывает те общие элементы, которые обычно включают программы. Краткое описание каждого элемента: - вывод означает запись информации на экран, на диск или в порт ввода-вывода; - типы данных - это константы, переменные и структуры, которые содержат числа (целые и вещественные), текст (символы и строки) или адреса (переменных и структур); - операции присваивают одно значение другому, комбинируют значения (складывают, делят и т.д.), и сравнивают значения (равно, не равно и т.д.); - ввод означает чтение данных с клавиатуры, с диска или из порта ввода-вывода; - условное выполнение относится к выполнению набора команд, если заданное условие истинно (и пропуску их, если оно ложно); - циклы выполняют набор команд некоторое фиксированное количество раз или пока истинно некоторое условие; - подпрограммы являются отдельно поименованными наборами команд, которые могут быть выполнены в любом месте программы с помощью ссылки по имени; 3 Введение в язык С 3.1. 3.2. 3.3. 3.4. 3.5. История создания языка С. Особенности языка. Структура программы языка C. Средства описания данных Стандартные типы данных и их внутреннее представление в памяти. Константы. 3.1 История создания языка С. Особенности языка. Язык C- это универсальный язык программирования, для которого характерны экономичность выражения, современный поток управления и структурыданных, широкий набор операторов. Язык C, первоначально предназначавшийся для написания операционной системы "UNIX" на ЭВМ DEC PDP-11, был разработан и реализован на этой системе Деннисом Ричи. Язык C, однако, не связан с какими-либо определенными аппаратными средствами или системами, и на нем легко писать программы, которые можно пропускать без изменений на любой ЭВМ, имеющей C- компилятор. Язык C является универсальным языком программирования. Он тесно связан с операционной системой "UNIX" , так как был развит на этой системе и так как "UNIX" и ее программное обеспечение написано на C. Сам язык , однако, не связан с какой-либо одной операционной системой или машиной; и хотя его называют языком системного программирования, так как он удобен для написания операционных систем , он с равным успехом использовался при написании больших вычислительных программ, программ для обработки текстов и баз данных. Язык C - это язык относительно "низкого уровня". В такой характеристике нет ничего оскорбительного; это просто означает, что C имеет дело с объектами того же вида, что и большинство ЭВМ, а именно, с символами, числами и адресами. Они могут объединяться и пересылаться посредством обычных арифметических и логических операций, осуществляемых реальными ЭВМ. В языке C отсутствуют операции, имеющие дело непосредственно с составными объектами, такими как строки символов, множества, списки или с массивами, рассматриваемыми как целое. Здесь, нет операций, оперирующим с целыми массивами и строками. Язык не предоставляет никаких других возможностей распределения памяти, кроме статического определения и механизма стеков, обеспечиваемого локальными переменныхфункций. Язык C не обеспечивает никаких возможностей ввода-вывода: здесь нет операторов ввода/вывода на консоль и никаких встроенных методов доступа к файлам. Все эти механизмы высокого уровня должны обеспечиваться явно вызываемыми функциями. Аналогично, язык C предлагает только простые, последовательные конструкции потоков управления: проверки, циклы, группирование и подпрограммы, но не мультипрограммирование, параллельные операции, синхронизацию или сопрограммы. Каждая реализация языка обеспечивает исчерпывающую, совместимую библиотеку функций для выполнения операций ввода-вывода, обработки строк и распределения памяти, но так как обращение к ним осуществляется только явно, можно, если необходимо, избежать их вызова - эти функции могут быть компактно написаны на самом C. Из-за того, что язык C отражает возможности современных компьютеров, программы на C оказываются достаточно эффективными, так что не возникает необходимости писать вместо этого программы на языке ассемблера. Хотя C соответствует возможностям многих ЭВМ, он не зависит от какой-либо конкретной архитектуры машины и в силу этого без особых усилий позволяет писать "переносимые" программы, т.е. программы, которые можно пропускать без изменений на различных аппаратных средствах. В языке C объектами основных типов данных являются символы, целые числа нескольких размеров и числа с плавающей точкой. Кроме того, имеется иерархия производных типов данных, создаваемых указателями, массивами, структурами, объединениями и функциями. Язык C включает основные конструкции потока управления, требуемые для хорошо структурированных программ: группирование операторов, принятие решений (if), циклы с проверкой завершения в начале (while, for) или в конце (do) и выбор одного из множества возможных вариантов (switch). В языке C имеются указатели и возможность адресной арифметики. Аргументы передаются функциям посредством копирования значения аргумента, и вызванная функция не может изменить фактический аргумент в вызывающей программе. Если желательно добиться "вызова по ссылке", можно неявно передать указатель, и функция сможет изменить объект, на который этот указатель указывает. Имена массивов передаются указанием начала массивов, так что аргументы типа массивов эффективно вызываются по ссылке. К любой функции можно обращаться рекурсивно, и ее локальные переменные обычно "автоматические" , т.е. создаются заново при каждом обращении. Описание одной функции не может содержаться внутри другой, но переменные могут описываться в соответствии с обычной блочной структурой. функции в C - программе могут транслироваться отдельно. переменные по отношению к функции могут быть внутренними, внешними, но известными только в пределах одного исходного файла, или полностью глобальными. Внутренние переменные могут быть автоматическими или статическими. Автоматические переменные для большей эффективности можно помещать в регистры, но объявление регистра является только указанием для компилятора и никак не связано с конкретными машинными регистрами. Язык C не является языком со строгими типами в смысле паскаля или алгола 68. Он сравнительно гибок к преобразованию данных. Существующие компиляторы не предусматривают никакой проверки во время выполнения программы индексов массивов, типов аргументов и т.д. 3.2 Структура программы на языке С . 3.3 Средства описания данных Переменные и константы являются основными объектами, с которыми оперирует программа. описания перечисляют переменные, которые будут использоваться, указывают их тип и, возможно, их начальные значения. Операции определяют, что с ними будет сделано. Выражения объединяют переменные и константы для получения новых значений. Все это - темы настоящей лекции. 3.3.1 Имена переменных Существуют некоторые ограничения на имена переменных и символических констант. Имена составляются из английских букв и цифр; первый символ должен быть буквой. Подчеркивание "_" тоже считается буквой; это полезно для удобочитаемости длинных имен переменных. Прописные и строчные буквы различаются; традиционная практика в "с" - использовать строчные буквы для имен переменных, а прописные - для символических констант. Играют роль только несколько символов внутреннего имени, хотя использовать можно и больше. Для внешних имен, таких как имена функций и внешних переменных, это число может оказаться меньше восьми, так как внешние имена используются различными ассемблерами и загрузчиками.. Кроме того, такие ключевые слова как if, else, int, float и т.д., зарезервированы: вы не можете использовать их в качестве имен переменных. (Они пишутся строчными буквами). Конечно, следует выбирать имена переменных таким образом, чтобы они означали нечто, относящееся к назначению переменных, и чтобы было менее вероятно спутать их при написании. 3.4 Стандартные типы данных и их внутреннее представление в памяти. В языке C имеется только несколько основных типовданных: char - один байт, в котором может находиться один символ из внутреннего набора символов. Переменные и константы типа char могут быть использованы в выражениях как однобайтовые целые числа. int– целое число, обычно соответствующее естественному размеру целых в используемой машине. float– число плавающей точкой одинарной точности. double- число плавающей точкой двойной точности. Кроме того имеется ряд квалификаторов, которые можно использовать с типомint: short (короткое), long (длинное) и unsigned (без знака). Квалификаторы short и long указывают на различные размеры целых. Числа без знака подчиняются законам арифметики по модулю 2 в степени n, где n - число битов в int; числа без знаков всегда положительны. Описания с квалификаторами имеют вид: short int x; long int y; unsignedintz; Cлово int в таких ситуациях может быть опущено. Цель состоит в том, чтобы short и long давали возможность в зависимости от практических нужд использовать различные длины целых; типint отражает наиболее "естественный" размер конкретной машины. Как вы видите, каждый компилятор свободно интерпретирует short и long в соответствии со своими аппаратными средствами. Все, на что вы можете твердо полагаться, это то, что short не длиннее, чем long. 3.4.1 Описания переменных Все переменные должны быть описаны до их использования. Описание состоит из спецификатора типа и следующего за ним списка переменных, имеющих этот тип, как, например, int lower, upper, step; char c, line[1000]; переменные можно распределять по описаниям любым образом; приведенные выше списки можно с тем же успехом записать в виде int lower; int upper; int step; charc; charline[1000]; Такая форма занимает больше места, но она удобна для добавления комментария к каждому описанию и для последующих модификаций. переменным могут быть присвоены начальные значения внутри их описания, хотя здесь имеются некоторые ограничения. Если за именем переменной следуют знак равенства и константа, то эта константа служит в качестве инициализатора, как, например, в char backslash = '\\'; int i = 0; floateps = 1.0e-5; Если рассматриваемая переменная является внешней или статической, то инициализация проводится только один раз, согласно концепции до начала выполнения программы. Инициализируемым явно автоматическим переменным начальные значения присваиваются при каждом обращении к функции, в которой они описаны. Автоматические переменные, не инициализируемые явно, имеют неопределенные значения, (т.е. мусор). Внешние и статические переменные по умолчанию инициализируются нулем, но, тем не менее, их явная инициализация является признаком хорошего стиля. 3.5 Константы. Данные программы хранятся в оперативной памяти компьютера в виде последовательности байт. Байт – минимальная адресуемая единица памяти и состоит из восьми бит. Адресация байт объектов данный в процессоре intelорганизована по принципу «младшими-вперед». Номера(адреса) байт в памяти. память номера байт 0 1 2 … Бит – двоичный разряд байта. нумерация бит в байте начинается с нуля и производится с конца. Номера бит в байте. Байт номера бит 7 6 5 4 3 2 1 0 3.5.1 Константытипаint Примеры записи целых констант Длинные константы записываются в виде 123l. Обычная целая константа, которая слишком длинна для типаint, рассматривается как long. Существует система обозначений для восьмеричных и шестнадцатеричных констант: лидирующий 0(нуль) в константетипаint указывает на восьмеричную константу, а стоящие впереди 0x соответствуют шестнадцатеричной константе. Например, десятичное число 31 можно записать как 037 в восьмеричной форме и как 0x1f в шестнадцатеричной. Шестнадцатеричные и восьмеричные константы могут также заканчиваться буквой l, что делает их относящимися к типуlong. 3.5.2 Константы вещественного типа Константытипаfloat (размер 4 байта) Примеры записи констант: –1.f , 3.2f, 123.456е-7f. Константытипаdouble(размер 8 байт) Примеры записи констант: –1. , 3.2, 123.456е-7. 3.5.3 Символьные константы Символьная константа - это один символ, заключенный в одинарные кавычки, как, например, 'х'. Значением символьной константы является численное значение этого символа во внутреннем машинном наборе символов. Например, в наборе символов ASCII символьный нуль, или '0', имеет значение 48, это значение совершенно отлично от числа 0. Написание '0' вместо численного значения, такого как 48, делает программу не зависящей от конкретного численного представления этого символа в данной машине. Символьные константы фактически это однобайтовые целые числа и точно так же участвуют в численных операциях, как и любые другие числа, хотя наиболее часто они используются в сравнении с другими символами. Некоторые неграфические символы могут быть представлены как символьные константы с помощью условных последовательностей, как, например, \n (новая строка), \t (табуляция), \0 (нулевой символ), \\ (обратная косая черта), \' (одинарная кавычка) и т.д. Хотя они выглядят как два символа, на самом деле являются одним. Кроме того, можно сгенерировать произвольную последовательность двоичных знаков размером в один байт, если написать '\ddd' где ddd - от одной до трех восьмеричных цифр, например #define formfeed '\014' /* form feed */ 3.5.4 Константное выражение Константное выражение - это выражение, состоящее из одних констант. Такие выражения обрабатываются во время компиляции и соответственно могут быть использованы в любом месте, где можно использовать константу, как, например #define maxline 1000 char line[maxline+1]; или seconds = 60 * 60 * hours; 3.5.5 Строчная константа Строчная константа - это последовательность, состоящая из нуля или более символов, заключенных в двойные кавычки, как, например, "i am a string" /* я - строка */ или "" /* null string */ /* нуль-строка */ Другой пример. Объявление переменной указательного типа и ее инициализация строковой константой. char *s=”строка”; Кавычки не являются частью строки, а служат только для ее ограничения. те же самые условные последовательности, которые использовались в символьных константах, применяются и в строках; символ двойной кавычки изображается как \". С технической точки зрения строка представляет собой массив, элементами которого являются отдельные символы. Чтобы программам было возможно определять конец строки, компилятор автоматически помещает в конец каждой строки нуль-символ \0. Такое представление означает, что не накладывается конкретного ограничения на то, какую длину может иметь строка, и чтобы определить эту длину, программы должны просматривать строку полностью. При этом для физического хранения строки требуется на одну ячейку памяти больше, чем число заключенных в кавычки символов. Следующая функцияstrlen(s) вычисляет длину символьной строкиs не считая конечный символ \0. int strlen(char s[]) /* return length of s */ { int i=0; while (s[i] != '\0') ++i; return(i); } 3.6 Особые типы данных Тип void. Имеет два разных смысла: 1) показать что функция не возвращает значения voidf00(…){…} 2) показать что используется адрес (или как принято говорить ссылка на объект) объекта неопределенного типа voidf01(void* ptr,…){…} Указательный тип. Предписывает что переменной указательного типа можно присвоить только адрес объекта определенного типа. Пример int * ptr; int x; ptr= &x;//положить значение переменной ptrравное адресупеременной х // но неверно floaty; ptr = &y;//не совпадают типы Ссылочный тип. Позволяет дать еще одно имя переменной. inty; int&py=y;//обязательная инициализация ссылки 3.7 Контрольные вопросы 1. Как объявить целую беззнаковую переменную длиной два байта 2. Какое значение имеет переменная y. int y=12+’0’*2; 3. какие значения имеет нулевой байт числа y. shorty=0x1224 4 Встроенные операции в языке С Средства описания действий. Встроенные операции в языке С. Арифметические, логические, битовые операции. Операции работы с указателями. Условная операция. Операции объединения и присваивания. Отношения сравнения. Преобразование типов. Сокращенная запись операций. Выражения. 4.1 Встроенные операции в языке С. Арифметические, логические, битовые операции. Операции работы с указателями. Условная операция. Операции объединения и присваивания. Отношения сравнения 4.1.1 Арифметические операции Бинарныеарифметические операции Бинарными арифметическими операциями являются +, -, *, / и операция деления по модулю %. Имеется унарная операция -. При делении целых дробная часть отбрасывается. Выражение x%y дает остаток от деления x на y и, следовательно, равно нулю, когда x делится на y точно. Например, год является високосным, если он делится на 4, но не делится на 100, исключая то, что делящиеся на 400 годы тоже являются високосными. Поэтому if(year % 4 == 0 &&year % 100 != 0 || year % 400 == 0) //год високосный else //год невисокосный Операцию % нельзя использовать с типамиfloat или double. Операции + и - имеют одинаковое старшинство, которое младше одинакового уровня старшинства операций *, / и %, которые в свою очередь младше унарного минуса. Арифметические операции группируются слева направо. 4.1.2 Операции отношения и логические операции Операциями отношения являются =>> =<< все они имеют одинаковое старшинство. Непосредственно за ними по уровню старшинства следуют операции равенства и неравенства: == != которые тоже имеют одинаковое старшинство. операции отношения младше арифметических операций, так что выражения типаi> сдвиг вправо ~ дополнение (унарная операция) Побитовая операция and часто используется для маскирования некоторого множества битов; например, оператор c = n& 0177 передает в 'с' семь младших битов n, полагая остальные равными нулю. Операция '|' побитового or используется для включения битов: c = x | mask устанавливает на единицу те биты в х, которые равны единице в mask. Следует быть внимательным и отличать побитовые операции & и | от логических связок && и ||, которые подразумевают вычисление значения истинности слева направо. Например, если х=1, а y=2, то значение х&y равно нулю, в то время как значение x&&y равно единице. Операции сдвига << и >> осуществляют соответственно сдвиг влево и вправо своего левого операнда на число битовых позиций, задаваемых правым операндом. Таким образом , х<<2 сдвигает х влево на две позиции, заполняя освобождающиеся биты нулями, что эквивалентно умножению на 4. Сдвиг вправо величины без знака заполняет освобождающиеся биты заполняются содержанием знакового бита /"арифметический сдвиг"/. Например shorty=-2,x; x=y>>1;//y=-2, x=-1 //т.е. y=0xfffe или y=1111 1111 1111 1110 в 2 с/с. Сдвиг дает x=1111 1111 1111 1111. Унарная операция ~ дает дополнение к целому; это означает , что каждый бит со значением 1 получает значение 0 и наоборот. Эта операция обычно оказывается полезной в выражениях типа x &~077 где последние шесть битов х маскируются нулем. Чтобы проиллюстрировать использование некоторых операций с битами, рассмотрим функцию unsignedgetbits(unsignedx, unsignedp, unsignedn), которая возвращает /сдвинутыми к правому краю/ начинающиеся с позиции р поле переменнойх длиной n битов. Мы предполагаем, что крайний правый бит имеет номер 0, и что n и р - разумно заданные положительные числа. Например, getbits(х,4,3) возвращает сдвинутыми к правому краю биты, занимающие позиции 4,3 и 2. unsignedgetbits(unsigned x, unsigned p, unsigned n) /* get n bits from position p */ { return((x >> (p+1-n)) &~(~0 << n)); } Операция x >> (p+1-n) сдвигает желаемое поле в правый конец слова. описаниеаргументаx как unsigned гарантирует, что при сдвиге вправо освобождающиеся биты будут заполняться нулями, а не содержимым знакового бита, независимо от того, на какой машине пропускается программа. Все биты константноговыражения ~0 равны 1; сдвиг его на n позиций влево с помощью операции ~0<>&~! Если е1 и е2 - выражения, то е1 оп= е2 эквивалентно е1 = (е1) оп (е2) за исключением того, что выражение е1 вычисляется только один раз. Обратите внимание на круглые скобки вокруг е2: x *= y + 1 то x = x * (y + 1) не x=x*y+1 В качестве примера приведем функциюbitcount, которая подсчитывает число равных 1 битов у целого аргумента. int bitcount(unsigned n) /* count 1 bits in n */ ( int b; for (b = 0; n != 0; n >>= 1) if (n & 01) b++; returnb; ) Не говоря уже о краткости, такие операторы присваивания имеют то преимущество, что они лучше соответствуют образу человеческого мышления. Кроме того, в громоздких выражениях, подобных yyval[yypv[p3+p4] + yypv[p1+p2]] += 2 такая операция присваивания облегчает понимание программы, так как нет необходимости скрупулезно проверять, являются ли два длинных выражения действительно одинаковыми. Такая операция присваивания может также помочь компилятору получить более эффективную программу. Мы уже использовали тот факт, что операция присваивания имеет некоторое значение и может входить в выражения. Самый типичный пример этого while ((c = getchar()) != EOF) Типом выражения присваивания является типего левого операнда. 4.1.7 Условные выражения операторы if (a > b) z = a; else z = b; вычисляют в z максимум из а и в. Условное выражение, записанное с помощью тернарной операции "?:", предоставляет другую возможность для записи этой и аналогичных конструкций. В выражении е1 ? e2 : е3 сначала вычисляется выражение е1. Если оно отлично от нуля (истинно), то вычисляется выражение е2, которое и становится значением условного выражения. В противном случае вычисляется е3, и оно становится значением условного выражения. Каждый раз вычисляется только одно из выражения е2 и е3. Таким образом, чтобы положить z равным максимуму из а и в, можно написать z = (a > b) ? a : b; /* z = max(a,b) */ Следует подчеркнуть, что условное выражение действительно является выражением и может использоваться точно так же, как любое другое выражение. Если е2 и е3 имеют разные типы, то тип результата определяется по правилам преобразования. Например, если f имеет типfloat, а n - типint, то выражение (n > 0) ? f : n Имеет типdouble независимо от того, положительно ли n или нет. Так как уровень старшинства операции ?: очень низок, прямо над присваиванием, то первое выражение в условном выражении можно не заключать в круглые скобки. Однако, мы все же рекомендуется это делать, так как скобки делают условную часть выражения более заметной. Использование условных выражений часто приводит к коротким программам. Например, следующий ниже оператор цикла выводит n элементов массива, по 10 в строке, разделяя каждый столбец одним пробелом и заканчивая каждую строку (включая последнюю) однимсимволомпереводастроки. for (i = 0; i < n; i++) printf("%6d%c",a[i],(i%10==9 || i==n-1) ? '\n' : ' ') Символ перевода строки записывается после каждого десятого элемента и после n-го элемента. За всеми остальными элементами следует один пробел. 4.1.8 Старшинство и порядок вычисления В приводимой ниже таблице сведены правила старшинства и ассоциативности всех операций. Операции, расположенные в одной строке, имеют один и тот же уровень старшинства; строки расположены в порядке убывания старшинства. Так, например, операции *, / и % имеют одинаковый уровень старшинства, который выше, чем уровень операций + и -. Таблица5.2 OPERATOR ASSOCIATIVITY () [] -> . LEFT TO RIGHT ! \^ ++ -- - (TYPE) * & SIZEOF RIGHT TO LEFT */% LEFT TO RIGHT +- LEFT TO RIGHT <<>> LEFT TO RIGHT <<= >>= LEFT TO RIGHT == != LEFT TO RIGHT & LEFT TO RIGHT ^ LEFT TO RIGHT | LEFT TO RIGHT && LEFT TO RIGHT || LEFT TO RIGHT ?: RIGHT TO LEFT = += -= и т.п. RIGHT TO LEFT , LEFT TO RIGHT 4.1.9 Операции -> и . Используются для доступа к полям структурных переменных или членам экземпляров классов. Отметим, что уровень старшинства побитовых логических операций &, ^ и | ниже уровня операций == и !=. Это приводит к тому, что осуществляющие побитовую проверку выражения, подобные if ((x & mask) == 0) ... для получения правильных результатов должны заключаться в круглые скобки. . 4.2 Выражения. Выражение - это синтаксически правильная последовательность операндов и операций. Операнд – это скалярная или индексированная переменная, вызов функции, а также любая правильная константа. Пример. sin(2.)+x<3 В этом выражении сначала вычисляется sin(2.), затем к результату прибавляется x и после этого выполняется сравнение результата с числом 3. Результат вычисления этого выражения равен 1.0. 4.3 Преобразование типов. Если в выражениях встречаются операнды различных типов, то они преобразуются к общему типу в соответствии с небольшим набором правил. В общем, автоматически производятся только преобразования, имеющие смысл, такие как, например, преобразование целого в плавающее в выражениях типаf+i. Выражения же, лишенные смысла, такие как использование переменнойтипаfloat в качестве индекса, запрещены. Во-первых, типыchar и int могут свободно смешиваться в арифметических выражениях: каждая переменнаятипаchar автоматически преобразуется в int. Это обеспечивает значительную гибкость при проведении определеных преобразований символов. Примером может служить функцияatoi, которая ставит в соответствие строке цифр ее численный эквивалент. int atoi(char s[]) /* convert s to integer */ { int i, n; n = 0; for ( i = 0; s[i]>='0' && s[i]<='9'; ++i) n = 10 * n + s[i] - '0'; return(n); } Выражение s[i] - '0' имеет численное значение находящегося в s[i] символа, потому что значение символов '0', '1' и т.д. образуют возрастающую последовательность расположенных подряд целых положительных чисел. Другой полезной формой автоматического преобразования типов является то, что выражения отношения, подобные i>j, и логические выражения, связанные операциями && и ||, по определению имеют значение 1, если они истинны, и 0, если они ложны. Таким образом, присваивание isdigit = c >= '0' && c <= '9'; полагает isdigit равным 1, если с - цифра, и равным 0 в противном случае. (В проверочной части операторов if, while, for и т.д. "Истинно" просто означает "не нуль"). Неявные арифметические преобразования работают в основном, как и ожидается. В общих чертах, если операция типа + или *, которая связывает два операнда (бинарная операция), имеет операнды разных типов, то перед выполнением операции "низший" тип преобразуется к "высшему" и получается результат "высшего" типа. Более точно, к каждой арифметической операции применяется следующая последовательность правил преобразования. Типы char и short преобразуются в int, а float в double. Затем, если один из операндов имеет тип double, то другой преобразуется в double, и результат имеет тип double. В противном случае, если один из операндов имеет тип long, то другой преобразуется в long, и результат имеет тип long. В противном случае, если один из операндов имеет тип unsigned, то другой преобразуется в unsigned и результат имеет тип unsigned. В противном случае операнды должны быть типа int, и результат имеет тип int. Подчеркнем, что все переменные типа float в выражениях преобразуются в double; в C вся плавающая арифметика выполняется с двойной точностью. Преобразования возникают и при присваиваниях; значение правой части преобразуется к типу левой, который и является типом результата. Символьные переменные преобразуются в целые. Обратное преобразование int в char ведет себя хорошо - лишние биты высокого порядка просто отбрасываются. Если х типа float, а i типа int, то как х = i; так и i = х; приводят к преобразованиям; при этом float преобразуется в int отбрасыванием дробной части. тип double преобразуется во float округлением. Длинные целые преобразуются в более короткие целые и в переменные типа char посредством отбрасывания лишних битов высокого порядка. Так как аргумент функции является выражением, то при передаче функциям аргументов также происходит преобразование типов: в частности, char и short становятся int, а float становится double. Именно поэтому мы описывали аргументы функций как int и double даже тогда, когда обращались к ним с переменными типа char и float. Наконец, в любом выражении может быть осуществлено явное преобразование типа с помощью конструкции, называемой перевод (cast). В этой конструкции, имеющей вид (имя типа) выражение Выражение преобразуется к указанному типу по правилам преобразования, изложенным выше. Фактически точный смысл операции перевода можно описать следующим образом: выражение как бы присваивается некоторой переменной указанного типа, которая затем используется вместо всей конструкции. Например, библиотечная процедура sqrt ожидает аргумента типа double sqrt((double) n) и значение n до передачи аргумента функции sqrt преобразует n к типу double. (Отметим, что операция перевод преобразует значение n в надлежащий тип; фактическое содержание переменной n при этом не изменяется). Операция перевода имеет тот же уровень старшинства, что и другие унарные операции, как указывается в таблице. 4.4 Контрольные вопросы 4. Как объявить целую беззнаковую переменную длиной два байта 5. Какое значение имеет переменная y. int y=12+’0’*2; 6. какие значения имеет нулевой байт числа y. shorty=0x1224 5 Операторы языка С 1. Операторы языка С. 2. Операторы присваивания, операторы управления вычислительным процессом. Операторы выбора if, if–else, switch, break. 3. Операторы управления циклами. Циклыwhile, do–while, for. 4. Управляющие операторы break, continue, goto. Управляющие операторы языка определяют порядок вычислений. 1.1 Операторы и блокиязыка С Такие выражения, как x=0, или i++, или printf(...), становятся операторами, если за ними следует точка с запятой, как, например, x = 0; i++; printf(...); В языке "C" точка с запятой является признаком конца оператора, а не разделителем операторов. Разрешается использование пустого оператора ; . Фигурные скобки { и } используются для объединения описаний и операторов в составной оператор или блок, так что они оказываются синтаксически эквивалентны одному оператору. Один явный пример такого типа дают фигурные скобки, в которые заключаются операторы, составляющие функцию, другой - фигурные скобки вокруг группы операторов в конструкциях if, else, while и for (на самом деле переменные могут быть описаны внутри любого блока). Точка с запятой никогда не ставится после фигурной скобки, которая завершает блок. 5.1 5.1.1 Операторы присваивания, операторы управления вычислительным процессом. Операторывыбора if, if–else, switch, break. 5.1.2 if - else Оператор if - else используется при необходимости сделать выбор. Формально синтаксис имеет вид if (выражение) оператор_1 else оператор_2, где часть else является необязательной. Сначала вычисляется выражение; если оно "истинно" /т.е. значение выражения отлично от нуля/, то выполняется оператор_1. Если оно ложно /значение выражения равно нулю/, и если есть часть с else, то вместо оператора_1 выполняется оператор_2. Так как if просто проверяет численное значение выражения, то возможно некоторое сокращение записи. Самой очевидной возможностью является запись if (выражение) вместо if (выражение != 0) То, что часть else в конструкции if - else является необязательной, приводит к двусмысленности в случае, когда else опускается во вложенной последовательности операторов if. Эта неоднозначность разрешается обычным образом - else связывается с ближайшим предыдущим if, не содержащим else. Например, в if ( n > 0 ) if( a > b ) z = a; else z = b; конструкция else относится к внутреннему if, как и показали, сдвинув else под соответствующий if. Если это не то, что вы хотите, то для получения нужного соответствия необходимо использовать фигурные скобки: if (n > 0) { if (a > b) z = a; } else z = b; Tакая двусмысленность особенно опасна в ситуациях типа if (n > 0) for (i = 0; i < n; i++) if (s[i] > 0) { printf("..."); return(i); } else /* wrong */ printf("error - n is zero\n"); Запись else под if ясно показывает, чего вы хотите, но компилятор не получит соответствующего указания и свяжет else с внутренним if. Ошибки такого рода очень трудно обнаруживаются. Между прочим, обратите внимание, что в if (a > b) z = a; else z = b; после z=a стоит точка с запятой. Дело в том, что согласно грамматическим правилам за if должен следовать оператор, а выражение типа z=a, являющееся оператором, всегда заканчивается точкой с запятой. 5.1.3 else - if Конструкция if (выражение) оператор elseif (выражение) оператор elseif (выражение) оператор else оператор встречается настолько часто, что заслуживает отдельного краткого рассмотрения. Такая последовательность операторов if является наиболее распространенным способом программирования выбора из нескольких возможных вариантов. выражения просматриваются последовательно; если какое-то выражение оказывается истинным, то выполняется относящийся к нему оператор, и этим вся цепочка заканчивается. Каждый оператор может быть либо отдельным оператором, либо группой операторов в фигурных скобках. Последняя часть с else имеет дело со случаем, когда ни одно из проверяемых условий не выполняется. Иногда при этом не надо предпринимать никаких явных действий; в этом случае хвост else оператор может быть опущен, или его можно использовать для контроля, чтобы засечь "невозможное" условие. Для иллюстрации выбора из трех возможных вариантов приведем программу функции, которая методом половинного деления определяет, находится ли данное значение х в отсортированном массиве v. Элементы массива v должны быть расположены в порядке возрастания. функция возвращает номер позиции (число между 0 и n-1), в которой значение х находится в v, и -1, если х не содержится в v. int binary(int x, int v[], int n) /* find x in v[0]...v[n-1] */ { int low, high, mid; low = 0; high = n - 1; while (low <= high) { mid = (low + high) / 2; if (x < v[mid]) high = mid - 1; else if (x > v[mid]) low = mid + 1; else /* found match */ return(mid); } return(-1); } Основной частью каждого шага алгоритма является проверка, будет ли х меньше, больше или равен среднему элементу v[mid]; использование конструкции else - if здесь вполне естественно. 5.1.4 Переключатель - switch Оператор switch дает специальный способ выбора одного из многих вариантов, который заключается в проверке совпадения значения данного выражения с одной из заданных констант и соответствующем ветвлении. В лекции 1 мы привели программу подсчета числа вхождений каждой цифры, символов пустых промежутков и всех остальных символов, использующую последовательность if...else if...else. Вот та же самая программа с переключателем. main() /* count digits,white space, others */ { int c, i, nwhite, nother, ndigit[10]; nwhite = nother = 0; for (i = 0; i < 10; i++) ndigit[i] = 0; while ((c = getchar()) != EOF) switch (c) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':ndigit[c-'0']++;break; case ' ': case '\n': case '\t': nwhite++; break; default : nother++; break; } printf("digits ="); for (i = 0; i < 10; i++) printf(" %d", ndigit[i]); printf("\nwhite space = %d, other = %d\n", nwhite, nother); Переключатель вычисляет целое выражение в круглых скобках (в данной программе - значение символа с) и сравнивает его значение со всеми случаями (case). Каждый случай должен быть помечен либо целым, либо символьной константой, либо константным выражением. Если значение константного выражения, стоящего после вариантного префикса case, совпадает со значением целого выражения, то выполнение начинается с этого случая. Если ни один из случаев не подходит, то выполняется оператор после префикса default. Префикс default является необязательным ,если его нет, и ни один из случаев не подходит, то вообще никакие действия не выполняются. Случаи и выбор по умолчанию могут располагаться в любом порядке. Все случаи должны быть различными. Оператор break приводит к немедленному выходу из переключателя. Поскольку случаи служат только в качестве меток, то если вы не предпримите явных действий после выполнения операторов, соответствующих одному случаю, вы провалитесь на следующий случай. Операторы break и return являются обычным способом выхода из переключателя. Оператор break можно использовать и для немедленного выхода из операторов цикла while, for и do. Проваливание сквозь случаи имеет как свои достоинства, так и недостатки. К положительным качествам можно отнести то, что оно позволяет связать несколько случаев с одним действием, как было с пробелом, табуляцией и новой строкой в нашем примере. Но в то же время оно обычно приводит к необходимости заканчивать каждый случай оператором break, чтобы избежать перехода к следующему случаю. 5.2 Операторы управления циклами. Циклы while, do–while, for. 5.2.1 Циклы - while и for В конструкции while (выражение) оператор вычисляется выражение. Если его значение отлично от нуля, то выполняется оператор и выражение вычисляется снова. Этот цикл продолжается до тех пор, пока значение выражения не станет нулем, после чего выполнение программы продолжается с места после оператора. Оператор for (выражение 1; выражение 2; выражение 3) оператор эквивалентен последовательности выражение 1;while (выражение 2) { оператор выражение 3;} Грамматически все три компонента в for являются выражениями. Наиболее распространенным является случай, когда выражение 1 и выражение 3 являются присваиваниями или обращениями к функциям, а выражение 2 - условным выражением. любая из трех частей может быть опущена, хотя точки с запятой при этом должны оставаться. Если отсутствует выражение 1 или выражение 3, то оно просто выпадает из расширения. Если же отсутствует проверка, выражение 2, то считается, как будто оно всегда истинно, так что for (;;) { ... } является бесконечным циклом, о котором предполагается, что он будет прерван другими средствами (такими как break или return). Использовать ли while или for - это, в основном дело вкуса. Например в while ((c = getchar()) == ' ' \!\! c == '\n' \!\! c == '\t') ; /* skipwhitespacecharacters */ нет ни инициализации, ни реинициализации, так что цикл while выглядит самым естественным. Цикл for, очевидно, предпочтительнее там, где имеется простая инициализация и реинициализация, поскольку при этом управляющие циклом операторы наглядным образом оказываются вместе в начале цикла. Это наиболее очевидно в конструкции for (i = 0; i= '0' && s[i] <= '9'; i++) n = 10 * n + s[i] - '0'; return(sign * n); } Преимущества централизации управления циклом становятся еще более очевидными, когда имеется несколько вложенных циклов. Следующая функция сортирует массив целых чисел по методу Шелла. Основная идея сортировки по шеллу заключается в том, что сначала сравниваются удаленные элементы, а не смежные, как в обычном методе сортировки. Это приводит к быстрому устранению большой части неупорядоченности и сокращает последующую работу. Интервал между элементами постепенно сокращается до единицы, когда сортировка фактически превращается в метод перестановки соседних элементов. void shell(int v[], int n) /* sort v[0]...v[n-1] into increasing order */ { int gap, i, j, temp; for (gap = n/2; gap > 0; gap /= 2) for (i = gap; i < n; i++) for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) { temp = v[j]; v[j] = v[j+gap]; v[j+gap] = temp; } } Здесь имеются три вложенных цикла. Самый внешний цикл управляет интервалом между сравниваемыми элементами, уменьшая его от n/2 вдвое при каждом проходе, пока он не станет равным нулю. Средний цикл сравнивает каждую пару элементов, разделенных на величину интервала; самый внутренний цикл переставляет любую неупорядоченную пару. Так как интервал в конце концов сводится к единице, все элементы в результате упорядочиваются правильно. Отметим, что в силу общности конструкции for внешний цикл укладывается в ту же самую форму, что и остальные, хотя он и не является арифметической прогрессией. Последней операцией языка "C" является запятая ",", которая чаще всего используется в операторе for. Два выражения, разделенные запятой, вычисляются слева направо, причем типом и значением результата являются тип и значение правого операнда. Таким образом, в различные части оператора for можно включить несколько выражений, например, для параллельного изменения двух индексов. Это иллюстрируется функцией reverse(s), которая располагает строку s в обратном порядке на том же месте. void reverse(char s[]) /* reverse string s in place */ { int c, i, j; for(i = 0, j = strlen(s) - 1; i < j; i++, j--) c = s[i]; s[i] = s[j]; s[j] = c; } } { Запятые, которые разделяют аргументы функций, переменные в описаниях и т.д., не имеют отношения к операции запятая и не обеспечивают вычислений слева направо. 5.2.2 Цикл do - while Циклы while и for обладают тем свойством, что в них проверка окончания осуществляется в начале, а не в конце цикла. Третий оператор цикла языка "C", do-while, проверяет условие окончания в конце, после каждого прохода через тело цикла; тело цикла всегда выполняется по крайней мере один раз. Синтаксис этого оператора имеет вид: do оператор while (выражение) Сначала выполняется оператор, затем вычисляется выражение. Если оно истинно, то оператор выполняется снова и т.д. Если выражение становится ложным, цикл заканчивается. Как и можно было ожидать, цикл do-while используется значительно реже, чем while и for, составляя примерно пять процентов от всех циклов. Тем не менее, иногда он оказывается полезным, как, например, в следующей функции itoa, которая преобразует число в символьную строку (обратная функции atoi). Эта задача оказывается несколько более сложной, чем может показаться сначала. Дело в том, что простые методы выделения цифр генерируют их в неправильном порядке. Мы предпочли получить строку в обратном порядке, а затем обратить ее. void itoa(int n, char s[]) /*convert n to characters in s */ { int i, sign; if ((sign = n) < 0) /* record sign */ n = -n; /* make n positive */ i = 0; do { /* generate digits in reverse order */ s[i++] = n % 10 + '0';/* get next digit */ } while ((n /=10) > 0); /* delete it */ if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); } Цикл do-while здесь необходим, или по крайней мере удобен, поскольку, каково бы ни было значение n, массив s должен содержать хотя бы один символ. В этом примере заключили в фигурные скобки один оператор, составляющий тело do-while, хотя это и не обязательно, для того, чтобы не принять часть while за начало оператора цикла while. 5.3 Управляющиеоператоры break, continue, go to. 5.3.1 Оператор break Иногда бывает удобным иметь возможность управлять выходом из цикла иначе, чем проверкой условия в начале или в конце. Оператор break позволяет выйти из операторов for, while и do до окончания цикла точно так же, как и из переключателя. Оператор break приводит к немедленному выходу из самого внутреннего охватывающего его цикла (или переключателя). Следующая программа удаляет хвостовые пробелы и табуляции из конца каждой строки файла ввода. Она использует оператор break для выхода из цикла, когда найден крайний правый отличный от пробела и табуляции символ. #define maxline 1000 main() /* remove trailing blanks and tabs */ { int n; char line[maxline]; while ((n = getline(line,maxline)) > 0) { while (--n >= 0) if (line[n] != ' ' && line[n] != '\t' && line[n] != '\n') break; line[n+1] = '\0'; printf("%s\n",line); } } функцияgetlineвозвращаетдлинустроки. Внутренний цикл начинается с последнего символа line (напомним, что --n уменьшает n до использования его значения) и движется в обратном направлении в поиске первого символа , который отличен от пробела, табуляции или новой строки. Цикл прерывается, когда либо найден такой символ, либо n становится отрицательным (т.е., когда просмотрена вся строка). Такое поведение правильно и в том случае, когда строка состоит только из символов пустых промежутков. В качестве альтернативы к break можно ввести проверку в сам цикл: while ((n = getline(line,maxline)) > 0) { while (--n >= 0 && (line[n] == ' ' \!\! line[n] == '\t' \!\! line[n] == '\n')) ; ... } Это уступает предыдущему варианту, так как проверка становится труднее для понимания. Проверок, которые требуют переплетения &&,\!\!, ! и круглых скобок, по возможности следует избегать. 5.3.2 Оператор continue Оператор continue родственен оператору break; он приводит к началу следующей итерации охватывающего цикла (for, while, do ). В циклах while и do это означает непосредственный переход к выполнению проверочной части; в цикле for управление передается на шаг реинициализации. (оператор continue применяется только в циклах, но не в переключателях. оператор continue внутри переключателя внутри цикла вызывает выполнение следующей итерации цикла). В качестве примера приведем фрагмент, который обрабатывает только положительные элементы массива а; отрицательные значения пропускаются. for (i = 0; i > n; i++) { if (a[i] > 0) /* skip negative elements */ continue; ... /* dopositiveelements */ } Оператор continue часто используется, когда последующая часть цикла оказывается слишком сложной, так что рассмотрение условия, обратного проверяемому, приводит к слишком глубокому уровню вложенности программы. 5.3.3 Оператор goto и метки В языке "C" предусмотрен и оператор goto и метки для ветвления. С формальной точки зрения оператор goto никогда не является необходимым, и на практике почти всегда можно обойтись без него. Тем не менее, укажем несколько ситуаций, где оператор goto может найти свое место. Наиболее характерным является его использование тогда, когда нужно прервать выполнение в некоторой глубоко вложенной структуре, например, выйти сразу из двух циклов. Здесь нельзя непосредственно использовать оператор break, так как он прерывает только самый внутренний цикл. Поэтому: for ( ... ) for ( ... ) { ... if (disaster) gotoerror; } ... error: Если программа обработки ошибок нетривиальна и ошибки могут возникать в нескольких местах, то такая организация оказывается удобной. Метка имеет такую же форму, что и имя переменной, и за ней всегда следует двоеточие. Метка может быть приписана к любому оператору той же функции, в которой находится оператор goto. В качестве другого примера рассмотрим задачу нахождения первого отрицательного элемента в двумерном массиве. Вот одна из возможностей: for (i = 0; i day_tab[leap][i]; i++) yearday -= day_tab[leap][i]; *pmonth = i; *pday = yearday; } Массивday_tab должен быть внешним как для day_of_year, так и для month_day, поскольку он используется обеими этими функциями. По определению в "C" двумерный массив по существу является одномерным массивом, каждый элемент которого является массивом. Поэтому индексы записываются как day_tab[i][j] анеday_tab [i, j] как в большинстве языков. В остальном с двумерными массивами можно в основном обращаться таким же образом, как в других языках. Элементы хранятся по строкам, т.е. при обращении к элементам в порядке их размещения в памяти быстрее всего изменяется самый правый индекс. Массив инициализируется с помощью списка начальных значений, заключенных в фигурные скобки; каждая строка двумерного массива инициализируется соответствующим подсписком. Мы поместили в начало массиваday_tab столбец из нулей для того, чтобы номера месяцев изменялись естественным образом от 1 до 12, а не от 0 до 11. Так как за экономию памяти у нас пока не награждают, такой способ проще, чем подгонка индексов. Если двумерный массив передается функции, то описание соответствующего аргумента функции должно содержать количество столбцов; количество строк несущественно, поскольку, как и прежде, фактически передается указатель. В нашем конкретном случае это указатель объектов, являющихся массивами из 13 чисел типаint. Таким образом, если бы требовалось передать массивday_tabфункцииf, то описание в f имело бы вид: void f(int day_tab[2][13]) { ... } Так как количество строк является несущественным, то описаниеаргумента в f могло бы быть таким: int day_tab[][13] илитаким int (*day_tab)[13] в котором говорится, что аргумент является указателеммассива из 13 целых. Круглые скобки здесь необходимы, потому что квадратные скобки [] имеют более высокий уровень старшинства, чем *; без круглых скобок int *day_tab[13]; является описаниеммассива из 13 указателей на целые. 6.3.2 Указатели и многомерные массивы Следует обратить внимание на различие между двумерным массивом и массивомуказателей, таким как name в приведенном выше примере. Если имеются описания int a[10][10]; int *b[10]; то a и b можно использовать сходным образом в том смысле, что как a[5][5], так и b[5][5] являются законными ссылками на отдельное число типаint. Но a - настоящий массив: под него отводится 100 ячеек памяти и для нахождения любого указанного элемента проводятся обычные вычисления с прямоугольными индексами. Для b, однако, описание выделяет только 10 указателей; каждый указатель должен быть установлен так, чтобы он указывал на массив целых. Если предположить, что каждый из них указывает на массив из 10 элементов, то тогда где-то будет отведено 100 ячеек памяти плюс еще десять ячеек для указателей. Таким образом, массивуказателей использует несколько больший объем памяти и может требовать наличие явного шага инициализации. Но при этом возникают два преимущества: доступ к элементу осуществляется косвенно через указатель, а не посредством умножения и сложения, и строки массива могут иметь различные длины. Это означает, что каждый элемент b не должен обязательно указывать на вектор из 10 элементов; некоторые могут указывать на вектор из двух элементов, другие - из двадцати, а третьи могут вообще ни на что не указывать. 7 Указатели 7.1. 7.2. 7.3. 7.4. 7.5. 7.6. Указатели. Объявление переменных указательного типа. Операции с указателями. Массивы указателей. Перенаправление указателей. Указатели на функции. Динамическое выделение памяти. Ссылочный тип. 7.1 Указатели. Объявление переменных указательного типа. Указатель - это переменная, содержащая адрес другой переменной. Иногда указатели дают единственную возможность выразить нужное действие, а отчасти потому, что они обычно ведут к более компактным и эффективным программам, чем те, которые могут быть получены другими способами. 7.1.1 Указатели и адреса Так как указатель содержит адрес объекта, это дает возможность "косвенного" доступа к этому объекту через указатель. Предположим, что х - переменная, например, типаint, а рх - указатель, созданный неким еще не указанным способом. Унарная операция & выдает адрес объекта, так что оператор рх = &х; присваивает адресхпеременнойрх; говорят, что рх "указывает" на х. Операция & применима только к переменным и элементам массива, конструкции вида &(х-1) и &3 являются незаконными. Нельзя также получить адрес регистровой переменной. Унарная операция *(название операции - разыменование)рассматривает свой операнд как адрес конечной цели и обращается по этому адресу, чтобы извлечь содержимое. Следовательно, если y тоже имеет типint, то y = *рх; присваивает y содержимое того, на что указывает рх. Так последовательность рх = &х; y = *рх; присваивает y то же самое значение, что и оператор y = x; переменные, участвующие во всем этом необходимо описать: int x, y; int *px; Описаниеуказателя int *px; должно рассматриваться как мнемоническое; оно говорит, что комбинация *px имеет типint. Это означает, что если px появляется в контексте *px, то это эквивалентно переменнойтипаint. Фактически синтаксис описанияпеременной имитирует синтаксис выражений, в которых эта переменная может появляться. Это замечание полезно во всех случаях, связанных со сложными описаниями. Например, double atof(), *dp; говорит, что atof() и *dp имеют в выражениях значения типаdouble. Вы должны также заметить, что из этого описания следует, что указатель может указывать только на определенный вид объектов. указатели могут входить в выражения. Например, если px указывает на целое x, то *px может появляться в любом контексте, где может встретиться x. Так оператор y = *px + 1 присваивает y значение, на 1 большее значения x; printf("%d\n", *px) выводит текущее значение x; d = sqrt((double) *px) получает в d квадратный корень из x, причем до передачи функцииsqrt значение x преобразуется к типуdouble. В выражениях вида y = *px + 1 унарные операции * и & связаны со своим операндом более сильно, чем арифметические операции, так что такое выражение берет то значение, на которое указывает px, прибавляет 1 и присваивает результат переменнойy. Ссылки на указатели могут появляться и в левой части присваиваний. Если px указывает на x, то *px = 0 полагает x равным нулю, а *px += 1 увеличивает его на единицу, как и выражение (*px)++ Круглые скобки в последнем примере необходимы; если их опустить, то поскольку унарные операции, подобные * и ++, выполняются справа налево, это выражение увеличит px, а не ту переменную, на которую он указывает. И наконец, так как указатели являются переменными, то с ними можно обращаться, как и с остальными переменными. Если py - другой указатель на переменнуютипаint, то py = px копирует содержимое px в py, в результате чего py указывает на то же, что и px. 7.1.2 Адресная арифметика Если p является указателем, то каков бы ни был сорт объекта, на который он указывает, операция p++ увеличивает p так, что он указывает на следующий элемент набора этих объектов, а операция p +=i увеличивает p так, чтобы он указывал на элемент, отстоящий на i элементов от текущего элемента. Эти и аналогичные конструкции представляют собой самые простые и самые распространенные формы арифметики указателей или адресной арифметики. Язык "C" последователен и постоянен в своем подходе к адресной арифметике; объединение в одно целое указателей, массивов и адресной арифметики является одной из наиболее сильных сторон языка. Иллюстрация некоторых из соответствующих возможностей языка на примере (полезной, несмотря на свою простоту) программы распределения памяти. Имеются две функции: функцияalloc(n) возвращает в качестве своего значения указательp, который указывает на первую из n последовательных символьных позиций, которые могут быть использованы вызывающей функциюallocпрограммой для хранения символов; функцияfree(p) освобождает приобретенную таким образом память, так что ее в дальнейшем можно снова использовать. программа является "элементарной", потому что обращения к free должны производиться в порядке, обратном тому, в котором производились обращения к alloc. Таким образом, управляемая функциямиalloc и free память является стеком или списком, в котором последний вводимый элемент извлекается первым. Стандартная библиотека языка "C" содержит аналогичные функции, не имеющие таких ограничений. Между тем, однако, для многих приложений нужна только тривиальная функцияalloc для распределения небольших участков памяти неизвестных заранее размеров в непредсказуемые моменты времени. Простейшая реализация состоит в том, чтобы функция раздавала отрезки большого символьного массива, которому мы присвоили имя allocbuf. Этот массив является собственностью функцийalloc и free. Так как они работают с указателями, а не с индексами массива, никакой другой функции не нужно знать имя этого массива. Он может быть описан как внешний статический, т.е. он будет локальным по отношению к исходному файлу, содержащему alloc и free, и невидимым за его пределами. При практической реализации этот массив может даже не иметь имени; вместо этого он может быть получен в результате запроса к операционной системе на указатель некоторого неименованного блока памяти. Другой необходимой информацией является то, какая часть массиваallocbuf уже использована. Мы пользуемся указателем первого свободного элемента, названным allocp. Когда к функцииalloc обращаются за выделением n символов, то она проверяет, достаточно ли осталось для этого места в allocbuf. Если достаточно, то alloc возвращает текущее значение allocp (т.е. начало свободного блока), затем увеличивает его на n, с тем чтобы он указывал на следующую свободную область. функцияfree(p) просто полагает allocp равным p при условии, что p указывает на позицию внутри allocbuf. #define null 0 /* pointer value for error report */ #define allocsize 1000 /* size of available space */ staticchar allocbuf[allocsize];/* storage for alloc */ staticchar *allocp = allocbuf; /* next free position */ char * alloc(int n) /* return pointer to n characters */ { if (allocp + n <= allocbuf + allocsize) { allocp += n; return(allocp - n); /* old p */ } else/* not enough room */ return(null); } void free(char *p) /* free storage pointed by p */ { if (p >= allocbuf && p < allocbuf + allocsize) allocp = p; } Некоторые пояснения. Вообще говоря, указатель может быть инициализирован точно так же, как и любая другая переменная, хотя обычно единственными осмысленными значениями являются null (это обсуждается ниже) или выражение, включающее адреса ранее определеныхданных соответствующего типа. описание static char *allocp = allocbuf; определяет allocp как указатель на символы и инициализирует его так, чтобы он указывал на allocbuf, т.е. на первую свободную позицию при начале работы программы. Так как имя массива является адресом его нулевого элемента, то это можно было бы записать в виде static char *allocp = &allocbuf[0]; используйте ту запись, которая вам кажется более естественной. С помощью проверки if (allocp + n<= allocbuf + allocsize) выясняется, осталось ли достаточно места, чтобы удовлетворить запрос на n символов. Если достаточно, то новое значение allocp не будет указывать дальше, чем на последнюю позицию allocbuf. Если запрос может быть удовлетворен, то alloc возвращает обычный указатель (обратите внимание на описание самой функции). Если же нет, то alloc должна вернуть некоторый признак, говорящий о том, что больше места не осталось. В языке "C" гарантируется, что ни один правильный указательданных не может иметь значение нуль, так что возвращение нуля может служить в качестве сигнала о ненормальном событии, в данном случае об отсутствии места. Вместо нуля пишем null, с тем чтобы более ясно показать, что это специальное значение указателя. Целые числа не могут осмысленно присваиваться указателям, а нуль - это особый случай. Проверкивида if (allocp + n <= allocbuf + aloocsize) и if (p >= allocbuf && p < allocbuf + allocsize) демонстрируют несколько важных аспектов арифметики указателей. Во-первых , при определеных условиях указатели можно сравнивать. Если p и q указывают на элементы одного и того же массива, то такие отношения, как <, >= и т.д., работают надлежащим образом. Например, p < q истинно, если p указывает на более ранний элемент массива, чем q. Отношения == и != тоже работают. Любой указатель можно осмысленным образом сравнить на равенство или неравенство с null. Но ни за что нельзя ручаться, если вы используете сравнения при работе с указателями, указывающими на разные массивы. Указатель и целое можно складывать и вычитать. Конструкция p + n подразумевает n-ый объект за тем, на который p указывает в настоящий момент. Это справедливо независимо от того, на какой вид объектов p должен указывать; компилятор сам масштабирует n в соответствии с определяемым из описанияp размером объектов, указываемых с помощью p. Масштабирующий множитель равен 1 для char, 2 для int и short, 4 для long и float и 8 для double. Вычитание указателей тоже возможно: если p и q указывают на элементы одного и того же массива, то p-q количество элементов между p и q. Этот факт можно использовать для написания еще одного варианта функции strlen: int strlen(char *s) /* return length of string s */ { char *p = s; while (*p != '\0') p++; return(p-s); } При описанииуказательp в этой функции инициализирован посредством строки s, в результате чего он указывает на первый символ строки. В цикле while по очереди проверяется каждый символ до тех пор, пока не появится символ конца строки \0. Так как значение \0 равно нулю, а while только выясняет, имеет ли выражение в нем значение 0, то в данном случае явную проверку можно опустить. Такие циклы часто записывают в виде while (*p) p++; Так как p указывает на символы, то операторp++ передвигает p каждый раз так, чтобы он указывал на следующий символ. В результате p-s дает число просмотренных символов, т.е. длину строки. Арифметика указателей последовательна: если бы мы имели дело с переменнымитипаfloat, которые занимают больше памяти, чем переменныетипаchar, и если бы p был указателем на float, то операторp++ передвинул бы p на следующее float. Таким образом, мы могли бы написать другой вариант функцииalloc, распределяющей память для float, вместо char, просто заменив всюду в alloc и free описатель char на float. Все действия с указателями автоматически учитывают размер объектов, на которые они указывают, так что больше ничего менять не надо. За исключением упомянутых выше операций (сложение и вычитание указателя и целого, вычитание и сравнение двух указателей), вся остальная арифметика указателей является незаконной. Запрещено складывать два указателя, умножать, делить, сдвигать или маскировать их, а также прибавлять к ним переменныетипаfloat или double. 7.1.3 Указатели и аргументы функций Так как в "с" передача аргументов функциям осуществляется "по значению", вызванная процедура не имеет непосредственной возможности изменить переменную из вызывающей программы. Что же делать, если вам действительно надо изменить аргумент? Например, программа сортировки захотела бы поменять два нарушающих порядок элемента с помощью функции с именем swap. Для этого недостаточно написать swap(a, b); определив функциюswap при этом следующим образом: void swap(int x, int y) /* wrong */ { int temp; temp = x; x = y; y = temp; } из-за вызова по значениюswap не может воздействовать на аргументыa и b в вызывающей функции. Имеется возможность получить желаемый эффект. Вызывающая программа передает указатели подлежащих изменению значений: swap(&a, &b); так как операция & выдает адрес переменной, то &a является указателем на a. В самой swapаргументы описываются как указатели и доступ к фактическим операндам осуществляется через них. void swap(int *px, *py) /* interchange *px and *py */ int *px, *py; { int temp; temp = *px; *px = *py; *py = temp; } Указатели в качестве аргументов обычно используются в функциях, которые должны возвращать более одного значения. (Можно сказать, что swap возвращает два значения, новые значения ее аргументов). В качестве примера рассмотрим функциюgetint, которая осуществляет преобразование поступающих в свободном формате данных, разделяя поток символов на целые значения, по одному целому за одно обращение. функцияgetint должна возвращать либо найденное значение, либо признак конца файла, если входные данные полностью исчерпаны. Эти значения должны возвращаться как отдельные объекты, какое бы значение ни использовалось для EOF, даже если это значение вводимого целого. Одно из решений, основывающееся на функциивводаscanf, состоит в том, чтобы при выходе на конец файла getint возвращала EOF в качестве значения функции; любое другое возвращенное значение говорит о нахождении нормального целого. Численное же значение найденного целого возвращается через аргумент, который должен быть указателем целого. Эта организация разделяет статус конца файла и численные значения. Следующий цикл заполняет массив целыми с помощью обращений к функции getint: int n, v, array[size]; for (n = 0; n < size && getint(&v) != EOF; n++) array[n] = v; В результате каждого обращения v становится равным следующему целому значению, найденному во входных данных. Обратите внимание, что в качестве аргументаgetint необходимо указать &v а не v. Использование просто v скорее всего приведет к ошибке адресации, поскольку getint полагает, что она работает именно с указателем. Сама getint является очевидной модификацией написанной функцииatoi: #include #include #include #define null 0 /* pointer value for error report */ #define allocsize 1000 /* size of available space */ staticchar allocbuf[allocsize];/* storage for alloc */ staticchar *allocp = allocbuf; /* next free position */ char * alloc(int n) /* return pointer to n characters */ { if (allocp + n <= allocbuf + allocsize) { allocp += n; return(allocp - n); /* old p */ } else/* not enough room */ return(null); } void free(char *p) /* free storage pointed by p */ { if (p >= allocbuf && p < allocbuf + allocsize) allocp = p; } int strlen(char *s) /* return length of string s */ { char *p = s; while (*p != '\0') p++; return(p-s); } char getint(int *pn) /* get next integer from input */ { int c,sign; while ((c = getch()) == ' ' || c == '\n' || c == '\t'); /* skip white space */ sign = 1; if (c == '+' || c == '-') { /* record sign */ sign = (c == '+') ? 1 : -1; c = getch(); } for (*pn = 0; c >= '0'&& c <= '9'; c = getch()) *pn = 10 * *pn + c - '0'; *pn *= sign; char CTRL_Z=26; if (c != CTRL_Z) ungetch(c);// in conio.h else return(EOF); } int main(){ setlocale(LC_ALL,"RUS"); int y=0; for(;;) if(getint(&y)!=EOF) printf("y=%d ",y); else {printf("\n всё ",y);break;} return 0; } Выражение *pn используется всюду в getint как обычная переменнаятипаint. Мы также использовали функцииgetch и ungetch , так что один лишний символ, который приходится считывать, может быть помещен обратно во ввод. 7.1.4 Указатели символов и функции Строчная константа, как, например, "i am a string" является массивом символов. Компилятор завершает внутреннее представление такого массива символом \0, так что программы могут находить его конец. Таким образом, длина массива в памяти оказывается на единицу больше числа символов между двойными кавычками. По-видимому чаще всего строчные константы появляются в качестве аргументов функций, как, например, в printf ("hello, world\n"); когда символьная строка, подобная этой, появляется в программе, то доступ к ней осуществляется с помощью указателя символов; функцияprintf фактически получает указатель символьного массива. Конечно, символьные массивы не обязаны быть только аргументами функций. Если описать message как char *message; то в результате оператора message = "nowisthetime"; переменнаяmessage станет указателем на фактический массив символов. Это не копирование строки; здесь участвуют только указатели. В языке "C" не предусмотрены какие-либо операции для обработки всей строки символов как целого. Проиллюстрируем другие аспекты указателей и массивов на примере двух функций из стандартной библиотекиввода-вывода. Первая функция - это void strcpy(char s[], char t[]), которая копирует строку t в строку s. аргументы написаны именно в этом порядке по аналогии с операцией присваивания, когда для того, чтобы присвоить t к s обычно пишут s = t Сначала версия с массивами: void strcpy(char s[], char t[]) /* copy t to s */ { int i; i = 0; while ((s[i] = t[i]) != '\0') i++; } Для сопоставления ниже дается вариант strcpy с указателями. void strcpy(char *s, char *t) /* copy t to s; pointer version 1 */ { while ((*s = *t) != '\0') { s++; t++; } } . На практике функцияstrcpy была бы записана не так, как показано выше. Вотвтораявозможность: void strcpy(char *s, char *t) /* copy t to s; pointer version 2 */ { while ((*s++ = *t++) != '\0'); } Здесь увеличение s и t внесено в проверочную часть. Значением *t++ является символ, на который указывал t до увеличения; постфиксная операция ++ не изменяет t, пока этот символ не будет извлечен. Точно так же этот символ помещается в старую позицию s, до того как s будет увеличено. Конечный результат заключается в том, что все символы, включая завершающий \0, копируются из t в s. И как последнее сокращение отметим, что сравнение с \0 является излишним, так что функцию можно записать в виде strcpy(char *s, char *t) /* copy t to s; pointer version 3 */ { while (*s++ = *t++); } Вторая функция - strcmp(s, t), которая сравнивает символьные строкиs и t, возвращая отрицательное, нулевое или положительное значение в соответствии с тем, меньше, равно или больше лексикографически s, чем t. Возвращаемое значение получается в результате вычитания символов из первой позиции, в которой s и t не совпадают. int strcmp(char s[], char t[]) /* return <0 if s0 if s>t */ { int i; i = 0; while (s[i] == t[i]) if (s[i++] == '\0') return(0); return(s[i]-t[i]); } Вот версия strcmp с указателями: int strcmp(char *s, char *t) /* return <0 if s0 if s>t */ { for ( ; *s == *t; s++, t++) if (*s == '\0') return(0); return(*s-*t); } так как ++ и -- могут быть как постфиксными, так и префиксными операциями, встречаются другие комбинации * и ++ и --, хотя и менее часто. Например *++p увеличивает p до извлечения символа, на который указывает p, а *--p сначала уменьшает p. 7.2 Операции с указателями. 7.3 Массивы указателей. Перенаправление указателей. 7.3.1 Массивы указателей,указатели указателей Так как указатели сами являются переменными, то вы вполне могли бы ожидать использования массивауказателей. Это действительно так. Проиллюстрируем это написанием программы сортировки в алфавитном порядке набора текстовых строк. Функция сортировки по Шеллу, которая упорядочивала массив целых будет работать и здесь, хотя теперь будем иметь дело со строками текста различной длины, которые, в отличие от целых, нельзя сравнивать или перемещать с помощью одной операции. Здесь есть необходимость в таком представлении данных, которое бы позволяло удобно и эффективно обрабатывать строки текста переменной длины. Здесь и возникают массивыуказателей. Если подлежащие сортировке сроки хранятся одна за другой в длинном символьном массиве (управляемом, например, функциейalloc ), то к каждой строке можно обратиться с помощью указателя на ее первый символ. Сами указатели можно хранить в массиве. Две строки можно сравнить, передав их указателифункцииstrcmp. Если две расположенные в неправильном порядке строки должны быть переставлены, то фактически переставляются указатели в массивеуказателей, а не сами тексты строк. Этим исключаются сразу две связанные проблемы: сложного управления памятью и больших дополнительных затрат на фактическую перестановку строк. Процесс сортировки включает три шага:  чтение всех строк ввода  их сортировка  вывод их в правильном порядке Как обычно, лучше разделить программу на несколько функций в соответствии с естественным делением задачи и выделить ведущую функцию, управляющую работой всей программы. Давайте отложим на некоторое время рассмотрение шага сортировки и сосредоточимся на структуреданных и вводе-выводе. функция, осуществляющая ввод, должна извлечь символы каждой строки, запомнить их и построить массивуказателей строк. Она должна также подсчитать число строк во вводе, так как эта информация необходима при сортировке и выводе. Так как функцияввода в состоянии справиться только с конечным числом вводимых строк, в случае слишком большого их числа она может возвращать некоторое число, отличное от возможного числа строк, например -1. Функция осуществляющая вывод, должна выводить строки в том порядке, в каком они появляются в массивеуказателей. #define null 0 #define lines 100 /* max lines to be sorted */ void main() /* sort input lines */ { char *lineptr[lines]; /*pointers to text lines */ int nlines; /* number of input lines read */ if ((nlines = readlines(lineptr, lines)) >= 0) { sort(lineptr, nlines); writelines(lineptr, nlines); } else printf("input too big to sort\n"); } #define maxlen 1000 int readlines(char *lineptr[], int maxlines) /* read input lines */ /* for sorting */ { int len, nlines; char *p, *alloc(), line[maxlen]; nlines = 0; while ((len = getline(line, maxlen)) > 0) if (nlines >= maxlines) return(-1); else if ((p = alloc(len)) == null) return (-1); else { line[len-1] = '\0'; /* zap newline */ strcpy(p,line); lineptr[nlines++] = p; } return(nlines); } Символ новой строки в конце каждой строки удаляется, так что он никак не будет влиять на порядок, в котором сортируются строки. void writelines(char *lineptr[],int nlines) /* write output lines */ { int i; for (i = 0; i < nlines; i++) printf("%s\n", lineptr[i]); } Существенно новым в этой программе является описание char *lineptr[lines]; которое сообщает, что lineptr является массивом из lines элементов, каждый из которых - указатель на переменныетипаchar. Это означает, что lineptr[i] - указатель на символы, а *lineptr[i] извлекает символ. Так как сам lineptr является массивом, который передается функцииwritelines, с ним можно обращаться как с указателем точно таким же образом, как в наших более ранних примерах. Тогда последнюю функцию можно переписать в виде: voidwritelines(char *lineptr[],intnlines) /* writeoutputlines */ char *lineptr[]; int nlines; { int i; while (--nlines >= 0) printf("%s\n", *lineptr++); } здесь *lineptr сначала указывает на первую строку; каждое увеличение передвигает указатель на следующую строку, в то время как nlines убывает до нуля. Программа сортировки по Шеллу требует небольших изменений: должны быть модифицированы описания, а операция сравнения выделена в отдельную функцию. void sort(char *v[],int n) /* sort strings v[0] ... v[n-1] */ /* into increasing order */ { int gap, i, j; char *temp; for (gap = n/2; gap > 0; gap /= 2) for (i = gap; i < n; i++) for (j = i - gap; j >= 0; j -= gap) { if (strcmp(v[j], v[j+gap]) <= 0) break; temp = v[j]; v[j] = v[j+gap]; v[j+gap] = temp; } } Так как каждый отдельный элемент массиваv (имя формального параметра, соответствующего lineptr) является указателем на символы, то и temp должен быть указателем на символы, чтобы их было можно копировать друг в друга. 7.3.2 Инициализация массивов указателей Рассмотрим задачу написания функцииmonth_name(n), которая возвращает указатель на символьную строку, содержащую имя n-го месяца. Это идеальная задача для применения внутреннего статического массива. функцияmonth_name содержит локальный массивсимвольных строк и при обращении к ней возвращает указатель нужной строки. Тема настоящего раздела - как инициализировать этот массив имен. char * month_name(intn) /* returnnameofn-thmonth */ { static char *name[] = { "illegal month", "january", "february", "march", "april", "may", "jun", "july", "august", "september", "october", "november", "december" }; return ((n < 1 || n > 12) ? name[0] : name[n]); } Инициализатором является просто список символьных строк; каждая строка присваивается соответствующей позиции в массиве. Более точно, символы i-ой строки помещаются в какое-то иное место, а ее указатель хранится в name[i]. Поскольку размер массиваname не указан, компилятор сам подсчитывает количество инициализаторов и соответственно устанавливает правильное число. 7.4 Указатели на функции. 7.4.1 Указатели на функции В языке "с" сами функции не являются переменными, но имеется возможность определить указатель на функцию, который можно обрабатывать, передавать другим функциям, помещать в массивы и т.д. Проиллюстрируем это, проведя модификацию написанной ранее программы сортировки так, чтобы при задании необязательного аргумента-n она бы сортировала строки ввода численно, а не лексикографически. Сортировка часто состоит из трех частей - сравнения, которое определяет упорядочивание любой пары объектов, перестановки, изменяющей их порядок, и алгоритма сортировки, осуществляющего сравнения и перестановки до тех пор, пока объекты не расположатся в нужном порядке. Алгоритм сортировки не зависит от операций сравнения и перестановки, так что, передавая в него различные функции сравнения и перестановки, мы можем организовать сортировку по различным критериям. Именно такой подход используется в нашей новой программе сортировки. Как и прежде, лексикографическое сравнение двух строк осуществляется функциейstrcmp, а перестановка функциейswap; нужна еще функцияnumcmp, сравнивающая две строки на основе численного значения и возвращающая условное указание того же вида, что и strcmp. Эти три функции описываются в main и указатели на них передаются в sort. В свою очередь функцияsort обращается к этим функциям через их указатели. #define lines 100 /* max number of lines to be sorted */ int main(int argc, char *argv[]) /* sort input lines */ { char *lineptr[lines]; /* pointers to text lines */ int nlines; /* number of input lines read */ int strcmp(), numcmp(); /* comparsion functions */ int swap(); /* exchange function */ int numeric = 0; /* 1 if numeric sort */ if(argc>1 && argv[1][0] == '-' && argv[1][1]=='n') numeric = 1; if(nlines = readlines(lineptr, lines)) >= 0) { if (numeric) sort(lineptr, nlines, numcmp, swap); else sort(lineptr, nlines, strcmp, swap); writelines(lineptr, nlines); } else printf("input too big to sort\n"); } Здесь strcmp, nimcmp и swap - адресафункций; так как известно, что это функции, операция & здесь не нужна совершенно аналогично тому, как она не нужна и перед именем массива. Передача адресовфункций организуется компилятором. Второй шаг состоит в модификации sort: void sort(char *v[],int n,int (*comp)(), int (*exch)()) /* sort strings v[0] ... v[n-1] */ /* into increasing order */ { int gap, i, j; for(gap = n/2; gap > 0; gap /= 2) for(i = gap; i < n; i++) for(j = i-gap; j >= 0; j -= gap) { if((*comp)(v[j], v[j+gap]) <= 0) break; (*exch)(&v[j], &v[j+gap]); } } Здесь следует обратить определенное внимание на описания. описание int (*comp)() говорит, что comp является указателем на функцию, которая возвращает значение типаint. Первые круглые скобки здесь необходимы; без них описание int *comp() говорило бы, что comp является функцией, возвращающей указатель на целые, что, конечно, совершенно другая вещь. Использование comp в строке if (*comp)(v[j], v[j+gap]) <= 0) полностью согласуется с описанием: comp - указатель на функцию, *comp - сама функция, а (*comp)(v[j], v[j+gap]) - обращение к ней. круглые скобки необходимы для правильного объединения компонентов. Функцияnumcmp, сравнивающую две строки по первому численному значению: int numcmp(char *s1, char *s2) /* compare s1 and s2 numerically */ { double atof(), v1, v2; v1 = atof(s1); v2 = atof(s2); if(v1 < v2) return(-1); else if(v1 > v2) return(1); else return (0); } Заключительный шаг состоит в добавлении функцииswap, переставляющей два указателя. Это легко сделать, непосредственно используя то, что мы изложили ранее в этой лекции. void swap(char *px[], char *py[]) /* interchange *px and *py */ { char *temp; temp = *px; *px = *py; *py = temp; } 7.4.2 Командная строка аргументов Системные средства, на которые опирается реализация языка "с", позволяют передавать командную строку аргументов или параметров начинающей выполняться программе. Когда функцияmain вызывается к исполнению, она вызывается с двумя аргументами. Первый аргумент (условно называемый argc) указывает число аргументов в командной строке, с которыми происходит обращение к программе; второй аргумент (argv) является указателем на массивсимвольных строк, содержащих эти аргументы, по одному в строке. Работа с такими строками - это обычное использование многоуровневых указателей. Самую простую иллюстрацию этой возможности и необходимых при этом описаний дает программаecho, которая просто печатает в одну строку аргументы командной строки, разделяя их пробелами. Таким образом, если дана команда echo hello, world то выходом будет hello, world по соглашению argv[0] является именем, по которому вызывается программа, так что argc по меньшей мере равен 1. В приведенном выше примере argc равен 3, а argv[0], argv[1] и argv[2] равны соответственно "echo", "hello," и "world". Первым фактическим аргументом является argv[1], а последним - argv[argc-1]. Если argc равен 1, то за именем программы не следует никакой командной строки аргументов. #include #include //в ярлыке - "D:\ПарамктрыКС.exe" a b void main(int argc, char *argv[]) /* echo arguments; 1st version */ { int i; for (i = 1; i < argc; i++) printf("%s%c", argv[i], (i 0) printf("%s%c",*++argv, (argc > 1) ? ' ' : '\n'); } Так как argv является указателем на начало массива строк- аргументов, то, увеличив его на 1 (++argv), мы вынуждаем его указывать на подлинный аргументargv[1], а не на argv[0]. Каждое последующее увеличение передвигает его на следующий аргумент; при этом *argv становится указателем на этот аргумент. Одновременно величина argc уменьшается; когда она обратится в нуль, все аргументы будут уже напечатаны. Другойвариант: void main(int argc, char *argv[])/* echo arguments; 3rd version */ { while (--argc > 0) printf((argc > 1) ? "%s" : "%s\n", *++argv); } Эта версия показывает, что аргумент формата функцииprintf может быть выражением, точно так же, как и любой другой. Такое использование встречается не очень часто, но его все же стоит запомнить. Как второй пример, внесем некоторые усовершенствования в программу отыскания заданной комбинации символов. В предыдущем примере поместили искомую комбинацию глубоко внутрь программы, что очевидно является совершенно неудовлетворительным. Изменим программу так, чтобы эта комбинация указывалась в качестве первого аргумента строки. #define maxline 1000 void main(int argc, char *argv[])/* find pattern from first argument */ int argc; char *argv[]; { char line[maxline]; if (argc != 2) printf ("usage: find pattern\n"); else while (getline(line, maxline) > 0) if (index(line, argv[1] >= 0) printf("%s", line); } Теперь может быть развита основная модель, иллюстрирующая дальнейшее использование указателей. Предположим, что надо предусмотреть два необязательных аргумента. Один утверждает: "напечатать все строки за исключением тех, которые содержат данную комбинацию", второй гласит: "перед каждой выводимой строкой должен печататься ее номер". Общепринятым соглашением в "с"-программах является то, что аргумент, начинающийся со знака минус, вводит необязательный признак или параметр. Если, для того, чтобы сообщить об инверсии, выберем -x, а для указания о нумерации нужных строк выберем -n("номер"), то команда find -x -n the при входных данных now is the time for all good men to come to the aid of their party. Должнавыдать 2:for all good men Нужно, чтобы необязательные аргументы могли располагаться в произвольном порядке, и чтобы остальная часть программы не зависела от количества фактически присутствующих аргументов. В частности, вызов функцииindex не должен содержать ссылку на argv[2], когда присутствует один необязательный аргумент, и на argv[1], когда его нет. Более того, для пользователей удобно, чтобы необязательные аргументы можно было объединить в виде: find -nx the вот сама программа: #define maxline 1000 void main(int argc, char *argv[])/* find pattern from first argument */ { char line[maxline], *s; long lineno = 0; int except = 0, number = 0; while (--argc > 0 && (*++argv)[0] == '-') for (s = argv[0]+1; *s != '\0'; s++) switch (*s) { case 'x': except = 1; break; case 'n': number = 1; break; default: printf("find: illegal option %c\n", *s); argc = 0; break; } if (argc != 1) printf("usage: find -x -n pattern\n"); else while (getlinе(line, maxline) > 0) { lineno++; if ((index(line, *argv) >= 0) != except) \ if (number) printf("%ld: ", lineno); printf("%s", line); } } } аргументargv увеличивается перед каждым необязательным аргументом, в то время как аргументargc уменьшается. Если нет ошибок, то в конце цикла величина argc должна равняться 1, а *argv должно указывать на заданную комбинацию. Обратите внимание на то, что *++argv является указателемаргументной строки; (*++argv)[0] - ее первый символ. Круглые скобки здесь необходимы, потому что без них выражение бы приняло совершенно отличный (и неправильный) вид *++(argv[0]). Другой правильной формой была бы **++argv. 7.5 Динамическое выделение памяти. Для динамического выделения памяти используется перегруженный оператор new(); Например как выделить память для массива из 10 целых. int *A1; A1=new int[10]; Выделение памяти для двумерного массива целых: int ** A2; A2=new int * [10]; for(int i=0;i<10;i++) A2[i]=new int[3]; Освобождение памяти для одномерного массива: delete [] A1; Освобождение памяти для двумерного массива: for(int i=0;i<10;i++)delete []A2[i]; delete [] A2; 8 Функции. 8.1. Объявление и определение функции. 8.2. Передача параметров. Возвращаемые значения. 8.3. Рекурсивное использование функций. 8.4. Передача указателей на функции в качестве аргумента функции. 8.5. Передача производных типов в качестве параметров функции. 8.6. Типы возвращаемых значений. Возвращение данных простых типов. Возвращение указателей и ссылок простых типов. Возвращение структурированных данных. . Возвращение указателей и ссылок структурированных типов. Функции и структура программ Функции разбивают большие вычислительные задачи на маленькие подзадачи и позволяют использовать в работе то, что уже сделано другими, а не начинать каждый раз с пустого места. Соответствующие функции часто могут скрывать в себе детали проводимых в разных частях программы операций, знать которые нет необходимости, проясняя тем самым всю программу, как целое, и облегчая мучения при внесении изменений. Язык "C" разрабатывался со стремлением сделать функции эффективными и удобными для использования. Программа может размещаться в одном или нескольких исходных файлах любым удобным образом; исходные файлы могут компилироваться отдельно и загружаться вместе наряду со скомпилированными ранее функциями из библиотек. 8.1 Объявление и определение функции. 8.1.1 Основные сведения Для начала давайте разработаем и составим программу вывода каждой строки ввода, которая содержит определенную комбинацию символов. Например, при поиске комбинации "the" в наборе строк nowisthetime for all good men to come to the aid of their party в качестве выхода получим now is the time men to come to the aid of their party основная схема выполнения задания четко разделяется на три части: while (имеется еще строка) if (строка содержит нужную комбинацию) вывод этой строки Конечно, возможно запрограммировать все действия в виде одной основной процедуры, но лучше использовать естественную структуру задачи и представить каждую часть в виде отдельной функции. С тремя маленькими кусками легче иметь дело, чем с одним большим, потому что отдельные не относящиеся к существу дела детали можно включить в функции и уменьшить возможность нежелательных взаимодействий. Кроме того, эти куски могут оказаться полезными сами по себе. Функция " имеется еще строка" - это getline, а "вывод этой строки" - это функцияprintf. Это значит, что осталось только написать процедуру для определения, содержит ли строка данную комбинацию символов или нет. Разарабатываемая функция: функцияindex(chars[], chart[]) возвращает позицию, или индекс, строки s, где начинается строка t, и -1, если s не содержит t. В качестве начальной позиции используем 0, а не 1, потому что в языке "C" массивы начинаются с позиции нуль. Когда нам в дальнейшем понадобится проверять на совпадение более сложные конструкции, нам придется заменить только функциюindex; остальная часть программы останется той же самой. Ниже приводится целиком вся программа, где можно видеть, как соединяются вместе отдельные части. Комбинация символов, по которой производится поиск, выступает в качестве символьной строки в аргументе функцииindex, что не является самым общим механизмом. #include #define maxline 1000 int getline(char s[], int lim) /* get line into s, return length * { int c, i; i = 0; while(--lim>0 && (c=getchar()) != EOF && c != '\n') s[i++] = c; if (c == '\n') s[i++] = c; s[i] = '\0'; return(i); } int index(char s[], char t[]) /* return index of t in s,-1 if none */ { int i, j, k; for (i = 0; s[i] != '\0'; i++) { for(j=i, k=0; t[k] !='\0' && s[j] == t[k]; j++; k++) ; if (t[k] == '\0') return(i); } return(-1); } voidmain() /* find all lines matching a pattern */ { char line[maxline]; while (getline(line, maxline) > 0) if (index(line, "the") >= 0) printf("%s", line); } Каждая функция имеет вид имя (список аргументов, если они имеются) описанияаргументов, если они имеются тип_возвращаемого_значения имя_функции(список параметров) { описания и операторы , если они имеются } Как и указывается, некоторые части могут отсутствовать; минимальной функцией является voiddummy () { } которая не совершает никаких действий. Программой является набор определений отдельных функций. Связь между функциями осуществляется через аргументы и возвращаемые функциями значения /в этом случае/; ее можно также осуществлять через внешние переменные. функции могут располагаться в исходном файле в любом порядке, а сама исходная программа может размещаться на нескольких файлах, но так, чтобы ни одна функция не расщеплялась. Операторreturn служит механизмом для возвращения значения из вызванной функции в функцию, которая к ней обратилась. За return может следовать любое выражение: return выражение; Вызывающая функция может игнорировать возвращаемое значение, если она этого пожелает. Более того, после return может не быть вообще никакого выражения; в этом случае в вызывающую программу не передается никакого значения. Управление также возвращется в вызывающую программу без передачи какого-либо значения и в том случае, когда при выполнении мы "проваливаемся" на конец функции, достигая закрывающейся правой фигурной скобки. Eсли функция возвращает значение из одного места и не возвращает никакого значения из другого места, это не является незаконным, но может быть признаком каких-то неприятностей. В любом случае "значением" функции, которая не возвращает значения, будет неопределенное значение. 8.1.2 Функции, возвращающие нецелые значения По умолчанию функция неявно описывается своим появлением в выражении или операторе, как, например, в while (getline(line, maxline) > 0) Если некоторое имя, которое не было описано ранее, появляется в выражении и за ним следует левая круглая скобка, то оно по контексту считается именем некоторой функции. Многие численные функции, такие как sqrt, sin и cos возвращают double; другие специальные функции возвращают значения других типов. Чтобы показать, как поступать в этом случае, давайте напишем и используем функциюatof(s), которая преобразует строку s в эквивалентное ей плавающее число двойной точности. функцияatof является расширением atoi; она обрабатывает необязательно знак и десятичную точку, а также целую и дробную часть, каждая из которых может как присутствовать, так и отсутствовать. Во-первых, сама atof должна описывать тип возвращаемого ею значения. Так как в выражениях типfloat преобразуется в double, то нет никакого смысла в том, чтобы atof возвращала float; можем с равным успехом воспользоваться дополнительной точностью, так что полагаем, что возвращаемое значение типаdouble. Имя типа должно стоять перед именем функции, как показывается ниже: double atof(char s[]) /* convert string s to double */ { double val, power; int i, sign; for(i=0; s[i]==' ' \!\! s[i]=='\n' \!\! s[i]=='\t'; i++) ; /* skip white space */ sign = 1; if (s[i] == '+' \!\! s[i] == '-') /* sign */ sign = (s[i++] == '+') ? 1 : -1; for (val = 0; s[i] >= '0' && s[i] <= '9'; i++) val = 10 * val + s[i] - '0'; if (s[i] == '.') i++; for (power = 1; s[i] >= '0' && s[i] <= '9'; i++) { val = 10 * val + s[i] - '0'; power *= 10; } return(sign * val / power); } 8.1.3 Аргументы функций Аргументы функций передаются по значению, т.е. вызванная функция получает свою временную копию каждого аргумента, а не его адрес. Это означает, что вызванная функция не может воздействовать на исходный аргумент в вызывающей функции. Внутри функции каждый аргумент по существу является локальной переменной, которая инициализируется тем значением, с которым к этой функции обратились. Если в качестве аргумента функции выступает имя массива, то передается адрес начала этого массива; сами элементы не копируются. функция может изменять элементы массива, используя индексацию и адрес начала. Таким образом, массив передается по ссылке. Можно показать, как использование указателей позволяет функциям воздействовать на отличные от массивовпеременные в вызывающих функциях. Не существует полностью удовлетворительного способа написания переносимой функции с переменным числом аргументов. Дело в том, что нет переносимого способа, с помощью которого вызванная функция могла бы определить, сколько аргументов было фактически передано ей в данном обращении. Обычно со случаем переменного числа аргументов безопасно иметь дело, если вызванная функция не использует аргументов, которые ей на самом деле не были переданы, и если типы согласуются. Самая распространенная в языке "C" функция с переменным числом аргументов - printf. Она получает из первого аргумента информацию, позволяющую определить количество остальных аргументов и их типы. Функцияprintfработает совершенно неправильно, если вызывающая функция передает ей недостаточное количество аргументов, или если их типы не согласуются с типами, указанными в первом аргументе. Эта функция не является переносимой и должна модифицироваться при использовании в различных условиях. Если же типыаргументов известны, то конец списка аргументов можно отметить, используя какое-то соглашение; например, считая, что некоторое специальное значение аргумента часто нуль) является признаком конца аргументов. 8.1.4 Внешние переменные Программа на языке "C" состоит из набора внешних объектов, которые являются либо переменными, либо функциями. Термин "внешний" используется главным образом в противопоставление термину "внутренний", которым описываются аргументы и автоматические переменные, определеные внутри функций. Внешние переменные определены вне какой-либо функции и, таким образом, потенциально доступны для многих функций. Сами функции всегда являются внешними, потому что правила языка "C" не разрешают определять одни функции внутри других. По умолчанию внешние переменные являются также и "глобальными", так что все ссылки на такую переменную, использующие одно и то же имя (даже из функций, скомпилированных независимо), будут ссылками на одно и то же. В силу своей глобальной доступности внешние переменные предоставляют другую, отличную от аргументов и возвращаемых значений, возможность для обмена данными между функциями. Если имя внешней переменной каким-либо образом описано, то любая функция имеет доступ к этой переменной, ссылаясь к ней по этому имени. В случаях, когда связь между функциями осуществляется с помощью большого числа переменных, внешние переменные оказываются более удобными и эффективными, чем использование длинных списков аргументов. Это соображение следует использовать с определенной осторожностью, так как оно может плохо отразиться на структурепрограмм и приводить к программам с большим числом связей по данным между функциями. Вторая причина использования внешних переменных связана с инициализацией. В частности, внешние массивы могут быть инициализированы, а автоматические нет. Третья причина использования внешних переменных обусловлена их областью действия и временем существования. Автоматические переменные являются внутренними по отношению к функциям; они возникают при входе в функцию и исчезают при выходе из нее. Внешние переменные, напротив, существуют постоянно. Они не появляются и не исчезают, так что могут сохранять свои значения в период от одного обращения к функции до другого. В силу этого, если две функции используют некоторые общие данные, причем ни одна из них не обращается к другой , то часто наиболее удобным оказывается хранить эти общие данные в виде внешних переменных, а не передавать их в функцию и обратно с помощью аргументов. 8.1.5 Правила, определяющие область действия Функции и внешние переменные, входящие в состав "C"-программы, не обязаны компилироваться одновременно; программа на исходном языке может располагаться в нескольких файлах, и ранее скомпилированные процедуры могут загружаться из библиотек. Два вопроса представляют интерес:  Как следует составлять описания, чтобы переменные правильно воспринимались во время  компиляции? Как следует составлять описания, чтобы обеспечить правильную связь частей программы при загрузке? 8.1.6 Область действия Областью действия имени является та часть программы, в которой это имя определено. Для автоматической переменной, описанной в начале функции, областью действия является та функция, в которой описано имя этой переменной, а переменные из разных функций, имеющие одинаковое имя, считаются не относящимися друг к другу. Это же справедливо и для аргументов функций. Область действия внешней переменной простирается от точки, в которой она объявлена в исходном файле, до конца этого файла. Например, если val, sp, push, pop и clear определены в одном файле в порядке, указанном выше, а именно: int sp = 0; double val[maxval]; double push(f) {...} double pop() {...} clear() {...} то переменныеval и sp можно использовать в push, pop и clear прямо по имени; никакие дополнительные описания не нужны. С другой стороны, если нужно сослаться на внешнюю переменную до ее определения, или если такая переменная определена в файле, отличном от того, в котором она используется, то необходимо описаниеextern. Важно различать описаниевнешней переменной и ее определение. описание указывает свойства переменной /ее тип, размер и т.д./; определение же вызывает еще и отведение памяти. Если вне какой бы то ни было функции появляются строчки intsp; doubleval[maxval]; то они определяют внешние переменныеsp и val, вызывают отведение памяти для них и служат в качестве описания для остальной части этого исходного файла. В то же время строчки externintsp; externdoubleval[]; описывают в остальной части этого исходного файлапеременнуюsp как int, а val как массивтипаdouble /размер которого указан в другом месте/, но не создают переменных и не отводят им места в памяти. Во всех файлах, составляющих исходную программу, должно содержаться только одно определениевнешней переменной; другие файлы могут содержать описанияextern для доступа к ней. /описаниеextern может иметься и в том файле, где находится определение/. Любая инициализация внешней переменной проводится только в определении. В определении должны указываться размеры массивов, а в описанииextern этого можно не делать. Хотя подобная организация приведенной выше программы и маловероятна, но val и sp могли бы быть определены и инициализированы в одном файле, а функцияpush, pop и clear определены в другом. В этом случае для связи были бы необходимы следующие определения и описания: вфайле 1: ---------int sp = 0; /* stack pointer */ double val[maxval]; /* value stack */ вфайле 2: ---------extern int sp; extern double val[]; double push(f) doublepop() {...} {...} clear() {...} так как описанияextern 'в файле 1' находятся выше и вне трех указанных функций, они относятся ко всем ним; одного набора описаний достаточно для всего 'файла 2'. Для программ большого размера возможность включения файлов, #include, позволяет иметь во всей программе только одну копию описанийextern и вставлять ее в каждый исходный файл во время его компиляции. Рассмотрим функциюgetop, выбирающей из файла ввода следующую операцию или операнд. Основная задача: пропустить пробелы, знаки табуляции и новые строки. Если следующий символ отличен от цифры и десятичной точки, то возвратить его. В противном случае собрать строку цифр /она может включать десятичную точку/ и возвратить number как сигнал о том, что выбрано число. Процедура существенно усложняется, если стремиться правильно обрабатывать ситуацию, когда вводимое число оказывается слишком длинным. функцияgetop считывает цифры подряд /возможно с десятичной точкой/ и запоминает их, пока последовательность не прерывается. Если при этом не происходит переполнения, то функция возвращает number и строку цифр. Если же число оказывается слишком длинным, то getop отбрасывает остальную часть строки из файла ввода, так что пользователь может просто перепечатать эту строку с места ошибки; функция возвращает toobig как сигнал о переполнении. intgetop(char s[],int lim) /* get next oprerator or operand */ { int i, c; while((c=getch())==' '\!\! c=='\t' \!\! c=='\n') ; if (c != '.' && (c < '0' \!\! c > '9')) return(c); s[0] = c; for(i=1; (c=getchar()) >='0' && c <= '9'; i++) if (i < lim) s[i] = c; if (c == '.') { /* collect fraction */ if (i < lim) s[i] = c; for(i++;(c=getchar()) >='0' && c<='9';i++) if (i < lim) s[i] =c; } if (i < lim) { /* number is ok */ ungetch(c); s[i] = '\0'; return (number); } else { /* it's too big; skip rest of line */ while (c != '\n' && c != EOF) c = getchar(); s[lim-1] = '\0'; return (toobig); } } Что представляют из себя функции 'getch' и 'ungetch'? Часто так бывает, что программа, считывающая входные данные, не может определить, что она прочла уже достаточно, пока она не прочтет слишком много. Одним из примеров является выбор символов, составляющих число: пока не появится символ, отличный от цифры, число не закончено. Но при этом программа считывает один лишний символ, символ, для которого она еще не подготовлена. Эта проблема была бы решена, если бы было бы возможно "прочесть обратно" нежелательный символ. Тогда каждый раз, прочитав лишний символ, программа могла бы поместить его обратно в файл ввода таким образом, что остальная часть программы могла бы вести себя так, словно этот символ никогда не считывался. Функцияgetch доставляет следующий символ ввода, подлежащий рассмотрению; функцияungetch помещает символ назад во ввод, так что при Упражнения Напишите функциюungets(s), которая будет возвращать во ввод целую строку. Предположите, что может возвращаться только один символ. Измените getch и ungetch соответствующим образом. Функцииgetch и ungetch не обеспечивают обработку возвращенного символа EOF переносимым образом. Решите, каким свойством должны обладать эти функции, если возвращается EOF, и реализуйте ваши выводы. 8.1.7 Статические переменные Статические переменные представляют собой третий класс памяти, в дополнении к автоматическим переменным и extern, с которыми мы уже встречались. Статические переменные могут быть либо внутренними, либо внешними. Внутренние статические переменные точно так же, как и автоматические, являются локальными для некоторой функции, но, в отличие от автоматических, они остаются существовать, а не появляются и исчезают вместе с обращением к этой функции. это означает, что внутренние статические переменные обеспечивают постоянное, недоступное извне хранение внутри функции. Символьные строки, появляющиеся внутри функции, как, например, аргументыprintf, являются внутренними статическими. Внешние статические переменные определены в остальной части того исходного файла, в котором они описаны, но не в каком-либо другом файле. Таким образом, они дают способ скрывать имена, которые в силу их совместного использования должны быть внешними, но все же не доступными для пользователей, чтобы исключалась возможность конфликта. Если две функции и две переменные объединить в одном файле, например следующим образом static char buf[bufsize]; /* buffer for ungetch */ static int bufp=0; /*next free position in buf */ getch() {...} ungetch() {...} то никакая другая функция не будет в состоянии обратиться к buf и bufp; фактически, они не будут вступать в конфликт с такими же именами из других файлов той же самой программы. Статическая память, как внутренняя, так и внешняя, специфицируется словом static, стоящим перед обычным описанием. Переменная является внешней, если она описана вне какой бы то ни было функции, и внутренней, если она описана внутри некоторой функции. Нормально функции являются внешними объектами; их имена известны глобально. возможно, однако, объявить функцию как static; тогда ее имя становится неизвестным вне файла, в котором оно описано. В языке "C" "static" отражает не только постоянство, но и степень того, что можно назвать "приватностью". Внутренние статические объекты определены только внутри одной функции; внешние статические объекты /переменные или функции/ определены только внутри того исходного файла, где они появляются, и их имена не вступают в конфликт с такими же именами переменных и функций из других файлов. Внешние статические переменные и функции предоставляют способ организовывать данные и работающие с ними внутренние процедуры таким образом, что другие процедуры и данные не могут прийти с ними в конфликт даже по недоразумению. Например, функцииgetch и ungetch образуют "модуль" для ввода и возвращения символов; необходимые для их работы переменные buf и bufp должны быть статическими, чтобы они не были доступны извне. Точно так же функцииpush, pop и clear формируют модуль обработки стека; var и sp тоже должны быть внешними статическими. 8.1.8 Регистровые переменные Четвертый и последний класс памяти называется регистровым. описаниеregister указывает компилятору, что данная переменная будет часто использоваться. Когда это возможно, переменные, описанные как register, располагаются в машинных регистрах, что может привести к меньшим по размеру и более быстрым программам. описаниеregister выглядит как register int x; register char c; и т.д.; часть int может быть опущена. описаниеregister можно использовать только для автоматических переменных и формальных параметров функций. В этом последнем случае описания выглядят следующим образом: f(c,n) register int c,n; { register int i; ... } На практике возникают некоторые ограничения на регистровые переменные, отражающие реальные возможности имеющихся аппаратных средств. В регистры можно поместить только несколько переменных в каждой функции, причем только определенныхтипов. В случае превышения возможного числа или использования неразрешенных типов слово register игнорируется. Кроме того невозможно извлечь адрес регистровой переменной. Эти специфические ограничения варьируются от машины к машине. 8.1.9 Блочная структура Язык "C" не является языком с блочной структурой- в нем нельзя описывать одни функции внутри других. Переменные же, с другой стороны, могут определяться по методу блочного структурирования. Описанияпеременных (включая инициализацию) могут следовать за левой фигурной скобкой,открывающей любой оператор, а не только за той, с которой начинается тело функции. переменные, описанные таким образом, вытесняют любые переменные из внешних блоков, имеющие такие же имена, и остаются определенными до соответствующей правой фигурной скобки. Напримерв if (n > 0) { int i; /* declare a new i */ for (i = 0; i < n; i++) ... } Областью действия переменнойi является "истинная" ветвь if; это i никак не связано ни с какими другими i в программе. Блочная структура влияет и на область действия внешних переменных. Если даны описания int x; double f() { double x; ... } То появление x внутри функцииf относится к внутренней переменнойтипаdouble, а вне f - к внешней целой переменной. Это же справедливо в отношении имен формальных параметров: intx; doublef(doublex) { ... } Внутри функцииf имя x относится к формальному параметру, а не к внешней переменной. 8.1.10 Инициализация Правила, относящиеся к инициализации. Если явная инициализация отсутствует, то внешним и статическим переменным присваивается значение нуль;автоматические и регистровые переменные имеют в этом случае неопределенные значения (мусор). Простые переменные (не массивы или структуры) можно инициализировать при их описании, добавляя вслед за именем знак равенства и константное выражение: int x = 1; char squote = '\''; long day = 60 * 24; /* minutes in a day */ Для внешних и статических переменных инициализация выполняется только один раз, на этапе компиляции. Автоматические и регистровые переменные инициализируются каждый раз при входе в функцию или блок. В случае автоматических и регистровых переменных инициализатор не обязан быть константой: на самом деле он может быть любым значимым выражением, которое может включать определеные ранее величины и даже обращения к функциям. Например, инициализация в программе бинарного поиска могла бы быть записана в виде void binary(int x, int v[],int n) { int low = 0; int high = n - 1; int mid; ... } вместо void binary(int x, int v[],int n) { int low, high, mid; low = 0; high = n - 1; ... } По своему результату, инициализации автоматических переменных являются сокращенной записью операторов присваивания. Внешние и статические массивы можно инициализировать, помещая вслед за описанием заключенный в фигурные скобки список начальных значений, разделенных запятыми. Например программа подсчета символов которая начинается с voidmain() /* countdigits, whitespace, others */ ( int c, i, nwhite, nother; int ndigit[10]; nwhite = nother = 0; for (i = 0; i < 10; i++) ndigit[i] = 0; ... ) может быть переписана в виде intnwhite = 0; intnother = 0; int ndigit[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; main() /* count digits, white space, others */ ( int c, i; ... ) Эти инициализации фактически не нужны, так как все присваиваемые значения равны нулю, но хороший стиль - сделать их явными. Если количество начальных значений меньше, чем указанный размер массива, то остальные элементы заполняются нулями. Перечисление слишком большого числа начальных значений является ошибкой. К сожалению, не предусмотрена возможность указания, что некоторое начальное значение повторяется, и нельзя инициализировать элемент в середине массив без перечисления всех предыдущих. Для символьных массивов существует специальный способ инициализации; вместо фигурных скобок и запятых можно использовать строку: char pattern[] = "the"; Это сокращение более длинной, но эквивалентной записи: char pattern[] = { 't', 'h', 'e', '\0' }; Если размер массив любого типа опущен, то компилятор определяет его длину, подсчитывая число начальных значений. В этом конкретном случае размер равен четырем (три символа плюс конечное \0). 8.1.11 Рекурсия В языке "C" функции могут использоваться рекурсивно; это означает, что функция может прямо или косвенно обращаться к себе самой. Традиционным примером является вывод числа в виде строки символов. как мы уже ранее отмечали, цифры генерируются не в том порядке: цифры младших разрядов появляются раньше цифр из старших разрядов, но печататься они должны в обратном порядке. Эту проблему можно решить двумя способами. Первый способ заключается в запоминании цифр в некотором массиве по мере их поступления и последующем их выводе в обратном порядке. Первый вариант функции printd следует этой схеме. voidprintd(intn) /* printnindecimal */ { char s[10]; int i; if (n < 0) { putchar('-'); n = -n; } i = 0; do { s[i++] = n % 10 + '0'; /* get next char */ } while ((n /= 10) > 0); /* discard it */ while (--i >= 0) putchar(s[i]); } Альтернативой этому способу является рекурсивное решение, когда при каждом вызове функция printd сначала снова обращается к себе, чтобы скопировать лидирующие цифры, а затем печатает последнюю цифру. voidprintd(int n) /* print n in decimal (recursive)*/ ( int i; if (n < 0) { putchar('-'); n = -n; } if ((i = n/10) != 0) printd(i); putchar(n % 10 + '0'); ) Когда функция вызывает себя рекурсивно, при каждом обращении образуется новый набор всех автоматических переменных, совершенно не зависящий от предыдущего набора. Таким образом, в printd(123) первая функция printd имеет n = 123. Она передает 12 второй printd, а когда та возвращает управление ей, выводит 3. Точно так же вторая printd передает 1 третьей (которая эту единицу печатает), а затем печатает 2. Рекурсия обычно не дает никакой экономии памяти, поскольку приходится где-то создавать стек для обрабатываемых значений. Не приводит она и к созданию более быстрых программ. Но рекурсивные программы более компактны, и они зачастую становятся более легкими для понимания и написания. Рекурсия особенно удобна при работе с рекурсивно определяемыми структурами данных, например, с деревьями. 8.1.12 Упражнения Приспособьте идеи, использованные в printd для рекурсивного написания itoa; т.е. Преобразуйте целое в строку с помощью рекурсивной процедуры. Напишите рекурсивный вариант функции reverse(s), которая располагает в обратном порядке строку s. Одной из идей процедурного программирования, которая оформилась в начале шестидесятых годов ХХ века, стало активное применение в практике программирования некоторого метода, основанного на организации серий взаимных обращений программ (функций) друг к другу. Вопросы об эффективности использования данного метода при разработке алгоритмических моделей актуальны и в настоящее время, несмотря на существование различных парадигм программирования, создание новых и совершенствование существующих языков программирования. Речь идет о рекурсивном методе в программировании, который рассматривается альтернативным по отношению к итерационному. Рекурсия – это определение объекта через обращение к самому себе. Рекурсивный алгоритм – это алгоритм, в описании которого прямо или косвенно содержится обращение к самому себе. В технике процедурного программирования данное понятие распространяется на функцию, которая реализует решение отдельного блока задачи посредством вызова из своего тела других функций, в том числе и себя самой. Если при этом на очередном этапе работы функция организует обращение к самой себе, то такая функция является рекурсивной. Прямое обращение функции к самой себе предполагает, что в теле функции содержится вызов этой же функции, но с другим набором фактических параметров. Такой способ организации работы называется прямой рекурсией. Например, чтобы найти сумму первых n натуральных чисел, надо сумму первых (n-1) чисел сложить с числом n, то есть имеет место зависимость: Sn=Sn-1+n. Вычисление происходит с помощью аналогичных рассуждений. Такая цепочка взаимных обращений в конечном итоге сведется к вычислению суммы одного первого элемента, которая равна самому элементу. При косвенном обращении функция содержит вызовы других функций из своего тела. При этом одна или несколько из вызываемых функций на определенном этапе обращаются к исходной функции с измененным набором входных параметров. Такая организация обращений называется косвенной рекурсией. Например, поиск максимального элемента в массиве размера n можно осуществлять как поиск максимума из двух чисел: одно их них – это последний элемент массива, а другое является максимальным элементом в массиве размера (n-1). Для нахождения максимального элемента массива размера (n-1) применяются аналогичные рассуждения. В итоге решение сводится к поиску максимального из первых двух элементов массива. Рекурсивный метод в программировании предполагает разработку решения задачи, основываясь на свойствах рекурсивности отдельных объектов или закономерностей. При этом исходная задача сводится к решению аналогичных подзадач, которые являются более простыми и отличаются другим набором параметров. Разработке рекурсивных алгоритмов предшествует рекурсивная триада – этапы моделирования задачи, на которых определяется набор параметров и соотношений между ними. Рекурсивную триаду составляют параметризация, выделение базы и декомпозиция. На этапе параметризации из постановки задачи выделяются параметры, которые описывают исходные данные. При этом некоторые дальнейшие разработки решения могут требовать введения дополнительных параметров, которые не оговорены в условии, но используются при составлении зависимостей. Необходимость в дополнительных параметрах часто возникает также при решении задач оптимизации рекурсивных алгоритмов, в ходе которых сокращается их временная сложность. Выделение базы рекурсии предполагает нахождение в решаемой задаче тривиальных случаев, результат для которых очевиден и не требует проведения расчетов. Верно найденная база рекурсии обеспечивает завершенность рекурсивных обращений, которые в конечном итоге сводятся к базовому случаю. Переопределение базы или ее динамическое расширение в ходе решения задачи часто позволяют оптимизировать рекурсивный алгоритм за счет достижения базового случая за более короткий путь обращений. Декомпозиция представляет собой сведение общего случая к более простым подзадачам, которые отличаются от исходной задачи набором входных данных. Декомпозиционные зависимости описывают не только связь между задачей и подзадачами, но и характер изменения значений параметров на очередном шаге. От выбранных отношений зависит трудоемкость алгоритма, так как для одной и той же задачи могут быть составлены различные зависимости. Пересмотр отношений декомпозиции целесообразно проводить комплексно, то есть параллельно с корректировкой параметров и анализом базовых случаев. 8.1.13 Анализ трудоемкости рекурсивных алгоритмов методом подсчета вершин дерева рекурсии Рекурсивные алгоритмы относятся к классу алгоритмов с высокой ресурсоемкостью, так как при большом количестве самовызовов рекурсивных функций происходит быстрое заполнение стековой области. Кроме того, организация хранения и закрытия очередного слоя рекурсивного стека являются дополнительными операциями, требующими временных затрат. На трудоемкость рекурсивных алгоритмов влияет и количество передаваемых функцией параметров. Рассмотрим один из методов анализа трудоемкости рекурсивного алгоритма, который строится на основе подсчета вершин рекурсивного дерева. Для оценки трудоемкости рекурсивных алгоритмов строится полное дерево рекурсии. Оно представляет собой граф, вершинами которого являются наборы фактических параметров при всех вызовах функции, начиная с первого обращения к ней, а ребрами – пары таких наборов, соответствующих взаимным вызовам. При этом вершины дерева рекурсии соответствуют фактическим вызовам рекурсивных функций. Следует заметить, что одни и те же наборы параметров могут соответствовать разным вершинам дерева. Корень полного дерева рекурсивных вызовов – это вершина полного дерева рекурсии, соответствующая начальному обращению к функции. Важной характеристикой рекурсивного алгоритма является глубина рекурсивных вызовов – наибольшее одновременное количество рекурсивных обращений функции, определяющее максима максимальное количество слоев рекурсивного стека, в котором осуществляется хранение отложенных вычислений. Количество элементов полных рекурсивных обращений всегда не меньше глубины рекурсивных вызовов. При разработке рекурсивных программ необходимо учитывать, что что глубина рекурсивных вызовов не должна превосходить максимального размера стека используемой вычислительной среды. При этом объем рекурсии - это одна из характеристик сложности рекурсивных вычислений для конкретного набора параметров, представляющая собой количество вершин полного рекурсивного дерева без единицы. Будем использовать следующие обозначения для конкретного входного параметра D D: R(D) – общее число вершин дерева рекурсии, RV(D) – объем рекурсии без листьев (внутренние вершины), RL(D) – количество листьев дерева рекурсии, HR(D) – глубина рекурсии. Например, для вычисления n -го го члена последовательности Фибоначчи разработана следующая рекурсивная функция: int Fib(int n){ //n – номер члена последовательности if(n<3) return 1; //база рекурсии returnFib(n-1)+Fib(n-2); //декомпозиция декомпозиция } Тогда полное дерево рекурсии для вычисления пятого члена последовательности Фибоначчи будет иметь вид (рис. 34.1): Рис. Полное дерево рекурсии для пятого члена последовательности Фибоначчи Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины. D=5 D=n R(D)=9 R(D)=2fn-1 RV(D)=4 RV(D)=fn-1 RL(D)=5 RL(D)=fn HR(D)=4 HR(D)=n-1 Пример 1. Задача о разрезании прямоугольника на квадраты. Дан прямоугольник, стороны которого выражены натуральными числами. Разрежьте его на минимальное число квадратов с натуральными сторонами. Найдите число получившихся квадратов. Разработаем рекурсивную триаду. Параметризация: m, n – натуральные числа чис , соответствующие размерам прямоугольника. База рекурсии: для m=n число получившихся квадратов равно 1, так как данный прямоугольник уже является квадратом. Декомпозиция: если ≠ , то возможны два случая m < n или m > n.. Отрежем от прямоугольника наибольший ольший по площади квадрат с натуральными сторонами. Длина стороны такого квадрата равна наименьшей из сторон прямоугольника. После того, как квадрат будет отрезан, размеры прямоугольника станут следующие: большая сторона уменьшится на длину стороны квадрата, квадрата, а меньшая не изменится. Число искомых квадратов будет вычисляться как число квадратов, на которые будет разрезан полученный прямоугольник, плюс один (отрезанный квадрат). К получившемуся прямоугольнику применим аналогичные рассуждения: проверим на соответствие етствие базе или перейдем к декомпозиции. Рис. Пример разрезания прямоугольника 13x5 на квадраты #include "stdafx.h" #include using namespace std; int kv(int m,int n); int _tmain(int argc, _TCHAR* argv[]) { int a,b,k; printf("Введите стороны прямоугольника->"); прямоугольника scanf("%d%d",&a,&b); k = kv(a,b); printf("Прямоугольник со сторонами %d и %d можно разрезать на %d квадратов",a,b,k); system("pause"); return 0; } int kv(int m,int n){ //m,n – стороныпрямоугольника if(m==n) return 1; //базарекурсии базарекурсии if(m>n) return 1+kv(m-n,n); n,n); //декомпозиция для m>n return 1+kv(m,n-m); m); //декомпозиция для m1 так как минимальное число вершин имеет двуугольник (отрезок). База рекурсии: для n=2 в качестве многоугольника рассматривается отрезок, центром тяжести которого является его середина (рис. 34А). ). При этом середина делит отрезок в отношении 1 : 1. Если координаты концов отрезка заданы как (x0,y0) и (x1,y1),, то координаты середины вычисляются по формуле: Декомпозиция: если n>2,, то рассмотрим последовательное нахождение центров тяжести треугольника, четырехугольника и т.д. Для n=3 центром тяжести треугольника является точка пересечения его медиан, медиан, которая делит каждую медиану в отношении 2 : 1, считая от вершины. Но основание медианы – это середина отрезка, являющегося стороной треугольника. Таким образом, для нахождения центра тяжести треугольника необходимо: найти центр тяжести стороны треугольника ика (отрезка), затем разделить в отношении 2 : 1, считая от вершины, отрезок, образованный основанием медианы и третьей вершиной. Для n=3 центром тяжести четырехугольника является точка, делящая в отношении 3 : 1, считая от вершины, отрезок: он образован центром ентром тяжести треугольника, построенного на трех вершинах, и четвертой вершиной. Рис. Примеры построения центров тяжести многоугольников Таким образом, для нахождения центра тяжести n -угольника угольника необходимо разделить в отношении (n-1): 1, считая от вершины, отрезок: он образован центром тяжести (n-1) -угольника и n -ой ой вершиной рассматриваемого многоугольника. Если концы отрезка заданы координатами вершины (xn,yn) и центра тяжести (n-1) -угольника (cxn-1,cyn--1),, то при делении отрезка в данном отношен отношении получаем координаты: #include "stdafx.h" #include using namespace std; #define max 20 void centr(int n,float *x, float *y, float *c); int _tmain(int argc, _TCHAR* argv[]){ int m, i=0; FILE *f; if ( ( f = fopen("in.txt", "r") ) == NULL ) perror("in.txt"); else { fscanf(f, "%d",&m); printf("\n%d",m); if ( m < 2 || m > max ) //вырожденный многоугольник printf ("Вырожденный многоугольник"); else { float *px,*py,*pc; px = new float[m]; py = new float[m]; pc = new float[2]; pc[0] = pc[1] = 0; while(i2) { //декомпозиция centr(n-1,x,y,c); c[0]= (x[n-1] + (n-1)*c[0])/n; c[1]= (y[n-1] + (n-1)*c[1])/n; } } Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины. D=4 D=n R(D)=3 R(D)=n-1 RV(D)=1 RV(D)=n-3 RL(D)=1 RL(D)=1 HR(D)=3 HR(D)=n-1 Однако в данном случае для более достоверной оценки необходимо учитывать емкостные характеристики алгоритма. Пример 3. Задача о разбиении целого на части. Найдите количество разбиений натурального числа на сумму натуральных слагаемых. Разбиение подразумевает представление натурального числа в виде суммы натуральных слагаемых, при этом суммы должны отличаться набором чисел, а не их последовательностью. В разбиение также может входить одно число. Например, разбиение числа 6 будет представлено 11 комбинациями: 6 5+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 2+2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+1 Рассмотрим решение в общем виде. Пусть зависимость R(n,k) вычисляет количество разбиений числа n на сумму слагаемых, не превосходящих k. Опишем свойства R(n,k). Если в сумме все слагаемые не превосходят 1, то такое представление единственно, то есть R(n,k)=1. Если рассматриваемое число равно 1, то при любом натуральном значении второго параметра разбиение также единственно: R(n,k)=1. Если второй параметр превосходит значение первого , то имеет место равенство R(n,k)=R(n,n), так как для представления натурального числа в сумму не могут входить числа, превосходящие его. Если в сумму входит слагаемое, равное первому параметру, то такое представление также единственно (содержит только это слагаемое), поэтому имеет место равенство: R(n,n)=R(n,n-1)+1. Осталось рассмотреть случай (n>k). Разобьем все представления числа n на непересекающиеся разложения: в одни обязательно будет входить слагаемое k, а другие суммы не содержат k. Первая группа сумм, содержащая k, эквивалентна зависимости R(n-k,k), что следует после вычитания числа k из каждой суммы. Вторая группа сумм содержит разбиение числа n на слагаемые, каждое из которых не превосходит k-1, то есть число таких представлений равно R(n,k-1). Так как обе группы сумм не пересекаются, то R(n,k)=R(n-k,k)+R(n,k-1). Разработаем рекурсивную триаду. Параметризация: Рассмотрим разбиение натурального числаn на сумму таких слагаемых, которые не превосходят натурального числаk. База рекурсии: исходя из свойств рассмотренной зависимости, выделяются два базовых случая: при n=1 R(n,k)=1, при k=1 R(n,k)=1. Декомпозиция: общий случай задачи сводится к трем случаям, которые и составляют декомпозиционные отношения. при n=k R(n,k)=R(n,n-1)+1, при nk R(n,k)=R(n-k,k)+R(n,k-1). #include "stdafx.h" #include using namespace std; unsigned long int Razbienie(unsigned long int n, unsigned long int k); int _tmain(int argc, _TCHAR* argv[]){ unsigned long int number, max,num; printf ("\nВведите натуральное число: "); scanf ("%d", &number); printf ("Введите максимальное натуральное слагаемое в сумме: "); scanf ("%d", &max); num=Razbienie(number,max); printf ("Число %d можно представить в виде суммы с максимальным слагаемым %d.", number, max); printf ("\nКоличество разбиений равно %d",num); system("pause"); return 0; } unsigned long int Razbienie(unsigned long int n, unsigned long int k){ if(n==1 || k==1) return 1; if(n<=k) return Razbienie(n,n-1)+1; return Razbienie(n,k-1)+Razbienie(n-k,k); } Пример 4. Задача о переводе натурального числа в шестнадцатеричную систему счисления. Дано натуральное число, не выходящее за пределы типа unsigned long. Число представлено в десятичной системе счисления. Переведите его в систему счисления с основанием 16. Пусть требуется перевести целое число n из десятичной в р -ичную систему счисления (по условию задачи, р = 16), то есть найти такое k, чтобы выполнялось равенство n10=kp. Параметризация: n – данное натуральное число, р – основание системы счисления. База рекурсии: на основании правил перевода чисел из десятичной системы в систему счисления с основанием р, деление нацело на основание системы выполняется до тех пор, пока неполное частное не станет равным нулю, то есть: если целая часть частного n и р равна нулю, то k = n. Данное условие можно реализовать иначе, сравнив n и р: целая часть частного равна нулю, если n < р. Декомпозиция: в общем случае k формируется из цифр целой части частного n и р, представленной в системе счисления с основанием р, и остатка от деления n на p. #include "stdafx.h" #include using namespace std; #define maxline 50 void perevod( unsigned long n, unsigned int p,FILE *pf); int _tmain(int argc, _TCHAR* argv[]){ unsigned long number10; unsigned int osn=16; char number16[maxline]; FILE *f; if ((f=fopen("out.txt", "w"))==NULL) perror("out.txt"); else { printf ("\nВведите число в десятичной системе: "); scanf("%ld", &number10); perevod(number10, osn, f); fclose(f); } if ((f=fopen("out.txt", "r"))==NULL) perror("out.txt"); else { fscanf(f,"%s",number16); printf("\n %ld(10)=%s(16)", number10, number16); fclose(f); } system("pause"); return 0; } void perevod(unsigned long n, unsigned int p, FILE *pf){ char c; unsigned int r; if(n >= p) perevod (n/p, p, pf);//декомпозиция r=n%p; c=r < 10 ? char (r+48) : char (r+55); putc(c, pf); } 8.2 Препроцессор языка "C" В языке "с" предусмотрены определеные расширения языка с помощью простого макропредпроцессора. одним из самых распространенных таких расширений, которое мы уже использовали, является конструкция #define; другим расширением является возможность включать во время компиляции содержимое других файлов. 8.2.1 Включение файлов Для облегчения работы с наборами конструкций #define и описаний (среди прочих средств) в языке "с" предусмотрена возможность включения файлов. Любая строка вида #include "filename" заменяется содержимым файла с именем filename. (Кавычки обязательны). Часто одна или две строки такого вида появляются в начале каждого исходного файла, для того чтобы включить общие конструкции #define и описания extern для глобальных переменных. Допускается вложенность конструкций #include. конструкция #include является предпочтительным способом связи описаний в больших программах. Этот способ гарантирует, что все исходные файлы будут снабжены одинаковыми определениями и описаниями переменных, и, следовательно, исключает особенно неприятный сорт ошибок. Естественно, когда какой-то включаемый файл изменяется, все зависящие от него файлы должны быть перекомпилированы. 8.2.2 Макроподстановка определение вида #define tes 1 приводит к макроподстановке самого простого вида - замене имени на строку символов. Имена в #define имеют ту же самую форму, что и идентификаторы в "с"; заменяющий текст совершенно произволен. Нормально заменяющим текстом является остальная часть строки; длинное определение можно продолжить, поместив \ в конец продолжаемой строки. "Область действия" имени, определенного в #define, простирается от точки определения до конца исходного файла. Имена могут быть переопределены, и определения могут использовать определения, сделанные ранее. Внутри заключенных в кавычки строк подстановки не производятся, так что если, например, yes - определенное имя, то в printf("yes") не будет сделано никакой подстановки. Так как реализация #define является частью работы макропредпроцессора, а не собственно компилятора, имеется очень мало грамматических ограничений на то, что может быть определено. Так, например, любители алгола могут объявить #define then #define begin { #define end ;} изатемнаписать if (i> 0) then begin a = 1; b=2 end Имеется также возможность определения макроса с аргументами, так что заменяющий текст будет зависеть от вида обращения к макросу. Определим, например, макрос с именем max следующим образом: #define max(a, b) ((a) > (b) ? (a) : (b)) когда строка x = max(p+q, r+s); будет заменена строкой x = ((p+q) > (r+s) ? (p+q) : (r+s)); Такая возможность обеспечивает "функцию максимума", которая расширяется в последовательный код, а не в обращение к функции. При правильном обращении с аргументами такой макрос будет работать с любыми типами данных; здесь нет необходимости в различных видах max для данных разных типов, как это было бы с функциями. Конечно, если вы тщательно рассмотрите приведенное выше расширение max, вы заметите определеные недостатки. Выражения вычисляются дважды; это плохо, если они влекут за собой побочные эффекты, вызванные, например, обращениями к функциям или использованием операций увеличения. Нужно позаботиться о правильном использовании круглых скобок, чтобы гарантировать сохранение требуемого порядка вычислений. (Рассмотрите макрос #define square(x) x * x при обращении к ней, как square(z+1). Здесь возникают даже некоторые чисто лексические проблемы: между именем макро и левой круглой скобкой, открывающей список ее аргументов, не должно быть никаких пробелов. Тем не менее аппарат макросов является весьма ценным. Один практический пример дает описываемая в лекции №7 стандартная библиотека ввода-вывода, в которой getchar и putchar определены как макросы (очевидно putchar должна иметь аргумент ), что позволяет избежать затрат на обращение к функции при обработке каждого символа. 8.2.3 Упражнение Определите макрос swap(x, y), который обменивает значениями два своих аргумента типа int. (В этом случае поможет блочная структура). 9 Производные типы данных – структуры, битовые поля, объединения, перечисления 9.1. Назначение производных типов данных. 9.2. Структуры, битовые поля, объединения, перечисления, создание имен новых типов данных. 9.3. Примеры использования производных типов данных. Стек. Дерево. 9.1.1 Структуры Структура - это набор из одной или более переменных, возможно различных типов, сгруппированных под одним именем для удобства обработки. Традиционным примером структуры является учетная карточка работающего: "служащий" описывается набором атрибутов таких, как фамилия, имя, отчество (ф.и.о.), адрес , код социального обеспечения, зарплата и т.д. Некоторые из этих атрибутов сами могут оказаться структурами: ф.и.о. Имеет несколько компонент, как и адрес. Основные сведения Рассмотрим процедуру преобразования даты. Дата состоит из нескольких частей таких, как день, месяц, и год, и, возможно, день года и имя месяца. Эти пять переменных можно объединить в одну структуру вида: structdate { int day; int month; int year; int yearday; char mon_name[4]; }; описаниеструктуры, состоящее из заключенного в фигурные скобки списка описаний, начинается с ключевого слова struct. За словом struct может следовать необязательное имя, (здесь это date). Имя структуры этого вида может использоваться в дальнейшем как сокращенная запись подробного описания. Элементы или переменные, упомянутые в структуре, называются членами. Члены структур могут иметь такие же имена, что и обычные переменные (т.е. не являющиеся членами структур), поскольку их имена всегда можно различить по контексту. Точно так же, как в случае любого другого базисного типа, за правой фигурной скобкой, закрывающей список членов, может следовать список переменных. оператор struct { ... } x,y,z; синтаксически аналогичен int x,y,z; в том смысле, что каждый из операторов описывает x, y и z в качестве переменных соответствующих типов и приводит к выделению для них памяти. Описаниеструктуры, за которым не следует списка переменных, не приводит к выделению какой-либо памяти; оно только определяет новый тип. Однако, если такое описание снабжено именем, то этот имя может быть использовано позднее при определении фактических экземпляров структур. Например, если дано приведенное выше описаниеdate, то struct date d; определяет переменнуюd в качестве структурытипаdate. Структуру можно инициализировать, поместив вслед за ее определением список инициализаторов для ее компонент: struct date d={ 4, 7, 1776, 186, "jul"}; Член экземпляра структуры может быть указан в выражении с помощью конструкции вида имя структуры . Член -------------------Операция указания члена структуры "." связывает имя структуры и имя члена. В качестве примера определим leap (признак високосности года) на основе даты, находящейся в структуреd, leap = d.year % 4 == 0 && d.year % 100 != 0 || d.year % 400 == 0; или проверим имя месяца if (strcmp(d.mon_name, "aug") == 0) ... Или преобразуем первый символ имени месяца так, чтобы оно начиналось с прописной буквы #include #include usingnamespace std; struct date { int day; int month; int year; int yearday; char mon_name[10];}; int main() { system("color f0"); date a={3,4,1,5,"october"}; a.mon_name[0] =toupper(a.mon_name[0]); cout<< a.mon_name< #include usingnamespace std; int day_tab[][13]= { {31,28,31,30,31,30,31,31,30,31,30,31}, {31,29,31,30,31,30,31,31,30,31,30,31} }; struct date { int day; int month; int year; int yearday; char mon_name[10];}; int day_of_year(struct date *pd) /* set day of year from month, day */ { int i, day, leap; day = pd->day; leap = pd->year % 4 == 0 && pd->year % 100 != 0 || pd->year % 400 == 0; for (i =0; i month-1; i++) day += day_tab[leap][i]; return(day); } int main() { system("color f0"); date a={3,4,1,5,"october"}; a.mon_name[0] =toupper(a.mon_name[0]); cout<< a.mon_name<year является новой. Если p - указатель на структуру, то p-> член структуры -----------------обращается к конкретному члену. (Операция -> - это знак минус, за которым следует знак ">".) Так как pd указывает на структуру, то к члену year можно обратиться и следующим образом (*pd).year но указателиструктур используются настолько часто, что запись -> оказывается удобным сокращением. круглые скобки в (*pd).year необходимы, потому что операция указания члена структуры старше , чем *. Обе операции, "->" и ".", ассоциируются слева направо, так что конструкции слева и справа эквивалентны p->q->memb (p->q)->memb emp.birthdate.month (emp.birthdate).month Для полноты ниже приводится другая функция, month_day, переписанная с использованием структур. voidmonth_day(struct date *pd) /* set month and day from day of year */ { int i, leap; leap = pd->year % 4 == 0 && pd->year % 100 != 0 || pd->year % 400 == 0; pd->day = pd->yearday; for (i = 1; pd->day > day_tab[leap][i]; i++) pd->day -= day_tab[leap][i]; pd->month = i; } Операции работы со структурами "->" и "." наряду со () для списка аргументов и [] для индексов находятся на самом верху иерархии старшинства операций и, следовательно, связываются в первую очередь. Если, например, имеется описание struct { int x; int *y; } *p; то выражение ++p->x увеличивает x, а не p, так как оно эквивалентно выражению ++(p->х). Для изменения порядка выполнения операций можно использовать круглые скобки: (++p)->x увеличивает p до доступа к x, а (p++)->x увеличивает p после. (Круглые скобки в последнем случае необязательны. Почему?) Совершенно аналогично *p->y извлекает то, на что указывает y; *p->y++ увеличивает y после обработки того, на что он указывает (точно так же, как и *s++); (*p->y)++ увеличивает то, на что указывает y; *p++>y увеличивает p после выборки того, на что указывает y. 9.1.3 Массивы структур структуры особенно подходят для управления массивами связанных переменных. Рассмотрим, например, программу подсчета числа вхождений каждого ключевого слова языка "C". Нам нужен массивсимвольных строк для хранения имен и массив целых для подсчета. одна из возможностей состоит в использовании двух параллельных массивовkeyword и keycount: char *keyword [nkeys]; int keycount [nkeys]; Но сам факт, что массивы параллельны, указывает на возможность другой организации. Каждое ключевое слово здесь по существу является парой: char *keyword; int keycount; и, следовательно, имеется массив пар. описаниеструктуры struct key { char *keyword; int keycount; } keytab [nkeys]; определяет массивkeytabструктур такого типа и отводит для них память. Каждый элемент массива является структурой. Это можно было бы записать и так: struct key { char *keyword; int keycount; }; struct key keytab [nkeys]; Так как структураkeytab фактически содержит постоянный набор имен, то легче всего инициализировать ее один раз и для всех членов при определении. Инициализация структур вполне аналогична предыдущим инициализациям - за определением следует заключенный в фигурные скобки список инициализаторов: struct key { char *keyword; int keycount; } keytab[] = { "break", 0, "case", 0, "char", 0, "continue", 0, "default", 0, /* ... */ "unsigned", 0, "while", 0 }; Инициализаторы перечисляются парами соответственно членам структуры. Было бы более точно заключать в фигурные скобки инициализаторы для каждой "строки" или структуры следующим образом: { "break", 0 }, { "case", 0 }, . . . Но когда инициализаторы являются простыми переменными или символьными строками и все они присутствуют, то во внутренних фигурных скобках нет необходимости. Как обычно, компилятор сам вычислит число элементов массиваkeytab, если инициализаторы присутствуют, а скобки [] оставлены пустыми. Программа подсчета ключевых слов начинается с определениямассиваkeytab. Ведущая программа читает свой файл ввода, последовательно обращаясь к функцииgetword, которая извлекает из ввода по одному слову за обращение. Каждое слово ищется в массивеkeytab с помощью варианта функции бинарного поиска. (Конечно, чтобы эта функция работала, список ключевых слов должен быть расположен в порядке возрастания). #define maxword 20 main() /* count "c" keywords */ { int n, t; char word[maxword]; while ((t = getword(word,maxword)) != EOF) if (t == letter) if((n = binary(word,keytab,nkeys)) >= 0) keytab[n].keycount++; for (n =0; n < nkeys; n++) if (keytab[n].keycount > 0) printf("%4d %s\n", keytab[n].keycount, keytab[n].keyword); } binary(word, tab, n) /* find word in tab[0]...tab[n-1] */ char *word; struct key tab[]; int n; { int low, high, mid, cond; low = 0; high = n - 1; while (low <= high) { mid = (low+high) / 2; if((cond = strcmp(word, tab[mid].keyword)) < 0) high = mid - 1; else if (cond > 0) low = mid + 1; else return (mid); } return(-1); } Функция getword возвращает letter каждый раз, как она находит слово, и копирует это слово в свой первый аргумент. Величина nkeys - это количество ключевых слов в массивеkeytab. Хотя мы можем сосчитать это число вручную, гораздо легче и надежнее поручить это машине, особенно в том случае, если список ключевых слов подвержен изменениям. Одной из возможностей было бы закончить список инициализаторов указанием на нуль и затем пройти в цикле сквозь массивkeytab, пока не найдется конец. Но, поскольку размер этого массива полностью определен к моменту компиляции, здесь имеется более простая возможность. Числоэлементовпростоесть size of keytab / size of struct key дело в том, что в языке "C" предусмотрена унарная операция sizeof, выполняемая во время компиляции, которая позволяет вычислить размер любого объекта. Выражение sizeof(object) выдает целое, равное размеру указанного объекта. (Размер определяется в неспецифицированных единицах, называемых "байтами", которые имеют тот же размер, что и переменныетипаchar). Объект может быть фактической переменной, массивом и структурой, или именем основного типа, как int или double, или именем производного типа, как структура. В нашем случае число ключевых слов равно размеру массива, деленному на размер одного элемента массива. Это вычисление используется в утверждении #define для установления значения nkeys: #define nkeys (sizeof(keytab) / sizeof(struct key)) Теперь перейдем к функцииgetword. Мы фактически написали более общий вариант функцииgetword, чем необходимо для этой программы, но он не на много более сложен. функцияgetword возвращает следующее "слово" из ввода, где словом считается либо строка букв и цифр, начинающихся с буквы, либо отдельный символ. тип объекта возвращается в качестве значения функции; это - letter, если найдено слово, EOF для конца файла и сам символ, если он не буквенный. getword(char *w, int lim) /* get next word from input */ { int c, t; if (type(c=*w++=getch()) !=letter) { *w='\0'; return(c); } while (--lim > 0) { t = type(c = *w++ = getch()); if (t ! = letter && t ! = digit) { ungetch(c); break; } } *(w-1) - '\0'; return(letter); } функцияgetwordиспользуетфункцииgetchиungetch: когданаборалфавитныхсимволовпрерывается, функцияgetwordполучаетодинлишнийсимвол. В результате вызова ungetch этот символ помещается назад во ввод для следующего обращения. функцияgetword обращается к функцииtype для определениятипа каждого отдельного символа из файла ввода. Вот вариант, справедливый только для алфавита ASCII. type(intc) /* returntypeofasciicharacter */ { if (c>= 'a' && c<= 'z' || c>= 'a' && c<= 'z') return(letter); else if (c>= '0' && c<= '9') return(digit); else return(c); } Символические константы letter и digit могут иметь любые значения, лишь бы они не вступали в конфликт с символами, отличными от буквенно-цифровых, и с EOF; очевидно возможен следующий выбор #define letter 'a' #define digit '0' функцияgetword могла бы работать быстрее, если бы обращения к функцииtype были заменены обращениями к соответствующему массивуtype[ ]. В стандартной библиотеке языка "C" предусмотрены макросы isalpha и isdigit, действующие необходимым образом. 9.1.4 Упражнения Сделайте такую модификацию функцииgetword и оцените, как изменится скорость работы программы. Напишите вариант функцииtype, не зависящий от конкретного набора символов. Напишите вариант программы подсчета ключевых слов, который бы не учитывал появления этих слов в заключенных в кавычки строках. 9.1.5 Указатели на структуры Чтобы проиллюстрировать некоторые соображения, связанные с использованием указателей и массивовструктур, давайте снова составим программу подсчета ключевых строк, используя на этот раз указатели, а не индексы массивов. Внешнее описаниемассиваkeytab не нужно изменять, но функцииmain и binary требуют модификации. main() /* count c keyword; pointer version */ { int t; char word[maxword]; struct key *binary(), *p; while ((t = getword(word, maxword;) !=EOF) if (t==letter) if ((p=binary(word,keytab,nkeys)) !=null) p->keycount++; for (p=keytab; p>keytab + nkeys; p++) if (p->keycount > 0) printf("%4d %s/n", p->keycount, p->keyword); } struct key *binary(word, tab, n) /* find word */ char *word /* in tab[0]...tab[n-1] */ struct key tab []; int n; { int cond; struct key *low = &tab[0]; struct key *high = &tab[n-1]; struct key *mid; while (low <= high) { mid = low + (high-low) / 2; if ((cond = strcmp(word, mid->keyword)) < 0) high = mid - 1; else if (cond > 0) low = mid + 1; else return(mid); } return(null); } Здесь имеется несколько моментов, которые стоит отметить. Во-первых, описаниефункцииbinary должно указывать, что она возвращает указатель на структурутипаkey, а не на целое; это объявляется как в функцииmain, так и в binary. Если функцияbinary находит слово, то она возвращает указатель на него; если же нет, она возвращает null. Во-вторых, все обращения к элементам массиваkeytab осуществляются через указатели. Это влечет за собой одно существенное изменение в функцииbinary: средний элемент больше нельзя вычислять просто по формуле mid = (low + high) / 2 потому что сложение двух указателей не дает какого-нибудь полезного результата (даже после деления на 2) и в действительности является незаконным. Эту формулу надо заменить на mid = low + (high-low) / 2 в результате которой mid становится указателем на элемент, расположенный посередине между low и high. Вам также следует разобраться в инициализации low и high. указатель можно инициализировать адресом ранее определенного объекта; именно как мы здесь и поступили. В функцииmain мы написали for (p=keytab; p < keytab + nkeys; p++) Если p является указателемструктуры, то любая арифметика с p учитывает фактический размер данной структуры, так что p++ увеличивает p на нужную величину, в результате чего p указывает на следующий элемент массиваструктур. Но не считайте, что размер структуры равен сумме размеров ее членов, - из-за требований выравнивания для различных объектов в структуре могут возникать "дыры". И, наконец, несколько второстепенный вопрос о форме записи программы. Если возвращаемая функцией величина имеет тип, как, например, в struct key *binary(word, tab, n) Tо может оказаться, что имя функции трудно выделить среди текста. В связи с этим иногда используется другой стиль записи: structkey * binary(word, tab, n) 9.2 9.2.1 Примеры использования производных типов данных. Дерево. Стек. Дерево Структуры, ссылающиеся на себя Предположим, что нам надо справиться с более общей задачей, состоящей в подсчете числа появлений всех слов в некотором файле ввода. Так как список слов заранее не известен, мы не можем их упорядочить удобным образом и использовать бинарный поиск. Мы даже не можем осуществлять последовательный просмотр при поступлении каждого слова, с тем чтобы установить, не встречалось ли оно ранее; такая программа будет работать вечно. (Более точно, ожидаемое время работы растет как квадрат числа вводимых слов). Как же нам организовать программу, чтобы справиться со списком произвольных слов? Одно из решений состоит в том, чтобы все время хранить массив поступающих до сих пор слов в упорядоченном виде, помещая каждое слово в нужное место по мере их поступления. Oднако это не следует делать, перемещая слова в линейном массиве, - это также потребует слишком много времени. Вместо этого мы используем структуруданных, называемую двоичным деревом. Каждому новому слову соответствует один "узел" дерева; каждый узел содержит: указатель текста слова ---------------------счетчик числа появлений ----------------------указатель узла левого потомка ----------------------------указатель узла правого потомка -----------------------------Никакой узел не может иметь более двух детей; возможно отсутствие детей или наличие только одного потомка. Узлы создаются таким образом, что левое поддерево каждого узла содержит только те слова, которые меньше слова в этом узле, а правое поддерево только те слова, которые больше. Чтобы определить, находится ли новое слово уже в дереве, начинают с корня и сравнивают новое слово со словом, хранящимся в этом узле. Если слова совпадают, то вопрос решается утвердительно. Если новое слово меньше слова в дереве, то переходят к рассмотрению левого потомка; в противном случае исследуется правый потомок. Если в нужном направлении потомок отсутствует, то значит новое слово не находится в дереве и место этого недостающего потомка как раз и является местом, куда следует поместить новое слово. Поскольку поиск из любого узла приводит к поиску одного из его потомков, то сам процесс поиска по существу является рекурсивным. В соответствии с этим наиболее естественно использовать рекурсивные процедурыввода и вывода. Возвращаясь назад к описанию узла, ясно, что это будет структура с четырьмя компонентами: struct tnode { /* the basic node */ char *word; /* points to the text */ int count; /* number of occurrences */ struct tnode *left; /* left child */ struct tnode *right; /* right child */ }; Это "рекурсивное" описание узла может показаться рискованным, но на самом деле оно вполне корректно. структура не имеет права содержать ссылку на саму себя, но struct tnode *left; описывает left как указатель на узел, а не как сам узел. Текст самой программы оказывается удивительно маленьким, если, конечно, иметь в распоряжении набор написанных нами ранее процедур, обеспечивающих нужные действия. Мы имеем в виду функциюgetword для извлечения каждого слова из файла ввода и функциюalloc для выделения места для хранения слов. Ведущая программа просто считывает слова с помощью функцииgetword и помещает их в дерево, используя функциюtree. #define maxword 20 main() /* word freguency count */ { struct tnode *root, *tree(); char word[maxword]; int t; root = null; while ((t = getword(word, maxword)) |= EOF) if (t == letter) root = tree(root, word); treeprint(root); } Функцияtree . Слово передается функциейmain к верхнему уровню (корню) дерева. На каждом этапе это слово сравнивается со словом, уже хранящимся в этом узле, и с помощью рекурсивного обращения к tree просачивается вниз либо к левому, либо к правому поддереву. В конце концов это слово либо совпадает с каким-то словом, уже находящимся в дереве (в этом случае счетчик увеличивается на единицу), либо программа натолкнется на нулевой указатель, свидетельствующий о необходимости создания и добавления к дереву нового узла. В случае создания нового узла функцияtree возвращает указатель этого узла, который помещается в родительский узел. struct tnode *tree(p, w) /* install w at or below p */ struct tnode *p; char *w; { struct tnode *talloc(); char *strsave(); int cond; if (p == null) { /* a new word has arrived */ p == talloc(); /* make a new node */ p->word = strsave(w); p->count = 1; p->left = p->right = null; } else if ((cond = strcmp(w, p->word)) == 0) p->count++; /* repeated word */ else if (cond < 0)/* lower goes into left subtree */ p->left = tree(p->left, w); else /* greater into right subtree */ p->right = tree(p->right, w); return(p); } Память для нового узла выделяется функциейtalloc, являющейся адаптацией для данного случая функцииalloc, написанной нами ранее. Она возвращает указатель свободного пространства, пригодного для хранения нового узла дерева. (Мы вскоре обсудим это подробнее). Новое слово копируется функциейstrsave в скрытое место, счетчик инициализируется единицей, и указатели обоих потомков полагаются равными нулю. Эта часть программы выполняется только при добавлении нового узла к ребру дерева. Мы здесь опустили проверку на ошибки возвращаемых функцийstrsave и talloc значений (что неразумно для практически работающей программы). функцияtreeprint печатает дерево, начиная с левого поддерева; в каждом узле сначала печатается левое поддерево (все слова, которые младше этого слова), затем само слово, а затем правое поддерево (все слова, которые старше). Если вы неуверенно оперируете с рекурсией, нарисуйте дерево сами и напечатайте его с помощью функцииtreeprint; это одна из наиболее ясных рекурсивных процедур, которую можно найти. treeprint (p) /* print tree p recursively */ struct tnode *p; { if (p != null) { treeprint (p->left); printf("%4d %s\n", p->count, p->word); treeprint (p->right); } } Практическое замечание: если дерево становится "несбалансированным" из-за того, что слова поступают не в случайном порядке, то время работы программы может расти слишком быстро. В худшем случае, когда поступающие слова уже упорядочены, настоящая программа осуществляет дорогостоящую имитацию линейного поиска. Существуют различные обобщения двоичного дерева, особенно 2-3 деревья и avl деревья, которые не ведут себя так "в худших случаях", но мы не будем здесь на них останавливаться. Прежде чем расстаться с этим примером, уместно сделать небольшое отступление в связи с вопросом о распределении памяти. Ясно, что в программе желательно иметь только один распределитель памяти, даже если ему приходится размещать различные виды объектов. Но если мы хотим использовать один распределитель памяти для обработки запросов на выделение памяти для указателей на переменныетипаchar и для указателей на struct tnode, то при этом возникают два вопроса. Первый: как выполнить то существующее на большинстве реальных машин ограничение, что объекты определеныхтипов должны удовлетворять требованиям выравнивания (например, часто целые должны размещаться в четных адресах)? Второй: как организовать описания, чтобы справиться с тем, что функцияalloc должна возвращать различные виды указателей ? Вообще говоря, требования выравнивания легко выполнить за счет выделения некоторого лишнего пространства, просто обеспечив то, чтобы распределитель памяти всегда возвращал указатель, удовлетворяющий всем ограничениям выравнивания. Например, на PDP-11 достаточно, чтобы функцияalloc всегда возвращала четный указатель, поскольку в четный адрес можно поместить любой тип объекта. Единственный расход при этом - лишний символ при запросе на нечетную длину. Аналогичные действия предпринимаются на других машинах. Таким образом, реализация alloc может не оказаться переносимой, но ее использование будет переносимым. Вопрос описаниятипафункцииalloc является проблемным для любого языка, который серьезно относится к проверке типов. Лучший способ в языке "C" - объявить, что alloc возвращает указатель на переменнуютипаchar, а затем явно преобразовать этот указатель к желаемому типу с помощью операции перевода типов. Таким образом, если описать p в виде char *p; то (struct tnode *) p преобразует его в выражениях в указатель на структурутипаtnode. Следовательно, функциюtalloc можно записать в виде: struct tnode *talloc() { char *alloc(); return ((struct tnode *) alloc(sizeof(struct tnode))); } это более чем достаточно для работающих в настоящее время компиляторов, но это и самый безопасный путь с учетом будущего. 9.2.2 Упражнения 1. Напишите программу, которая читает "C"-программу и печатает в алфавитном порядке каждую группу имен переменных, которые совпадают в первых семи символах, но отличаются где-то дальше. (Сделайте так, чтобы 7 было параметром). 2. Напишите программу вывода перекрестных ссылок, т.е. программу, которая выводит список всех слов документа и для каждого из этих слов выводит список номеров строк, в которые это слово входит. 3. Напишите программу, которая печатает слова из своего файла ввода, расположенные в порядке убывания частоты их появления. Перед каждым словом напечатайте число его появлений. 4. Укажите что выведет программа #include #include using namespace std; struct r{int a;r(int t){a=t;}} ar[]={r(1),r(3)}; int main() { system("color f0"); r * ptr_r=ar; cout << (((r)*ptr_r++).a)<<" "; cout<<((*ptr_r).a)<next) if (strcmp(s, np->name) == 0) return(np); /* found it */ return(null); /* not found */ функцияinstall использует функциюlookup для определения, не присутствует ли уже вводимое в данный момент имя; если это так, то новое определение должно вытеснить старое. В противном случае создается совершенно новый элемент. Если по какой-либо причине для нового элемента больше нет места, то функцияinstall возвращает null. struct nlist *install(name, def) /* put (name, def) */ char *name, *def; { struct nlist *np, *lookup(); char *strsave(), *alloc(); int hashval; if((np = lookup(name)) == null) \( /* not found */ np = (struct nlist *) alloc(sizeof(*np)); if (np == null) return(null); if ((np->name = strsave(name)) == null) return(null); hashval = hash(np->name); np->next = hashtab[hashval]; hashtab[hashval] = np; } else /* already there */ free((np->def);/* free previous definition */ if ((np->def = strsave(def)) == null) return (null); return(np); } функцияstrsave просто копирует строку, указанную в качестве аргумента, в место хранения, полученное в результате обращения к функцииalloc. 9.2.3 Упражнения Напишите процедуру, которая будет удалять имя и определение из таблицы, управляемой функциямиlookup и install. Разработайте простую, основанную на функциях этого раздела, версию процессора для обработки конструкций#define, пригодную для использования с "C"-программами. Вам могут также оказаться полезными функцииgetchar и ungetch. 9.2.4 Поля Когда вопрос экономии памяти становится очень существенным, то может оказаться необходимым помещать в одно машинное слово несколько различных объектов; одно из особенно распространенных употреблений набор однобитовых признаков в применениях, подобных символьным таблицам компилятора. Внешне обусловленные форматы данных, такие как интерфейсы аппаратных средств также зачастую предполагают возможность получения слова по частям. Представьте себе фрагмент компилятора, который работает с символьной таблицей. С каждым идентификатором программы связана определенная информация, например, является он или нет ключевым словом, является ли он или нет внешним и/или статическим и т.д. Самый компактный способ закодировать такую информацию - поместить набор однобитовых признаков в отдельную переменнуютипаchar или int. Обычный способ, которым это делается, состоит в определении набора "масок", отвечающих соответствующим битовым позициям, как в #define keyword 01 #define external 02 #define static 04 (числа должны быть степенями двойки). Тогда обработка битов сведется к "жонглированию битами" с помощью операций сдвига, маскирования и дополнения. Некоторые часто встречающиеся идиомы: flags |= external | static; включает биты external и static в flags, в то время как flags &= \^(еxternal | static); их выключает, а if ((flags & (external | static)) == 0) ... истинно, если оба бита выключены. Хотя этими идиомами легко овладеть, язык "C" в качестве альтернативы предлагает возможность определения и обработки полей внутри слова непосредственно, а не посредством побитовых логических операций. Поле - это набор смежных битов внутри одной переменнойтипаint. Синтаксис определения и обработки полей основывается на структурах. Например, символьную таблицу конструкций#define, приведенную выше, можно бы было заменить определением трех полей: struct { unsigned is_keyword : 1; unsigned is_extern : 1; unsigned is_static : 1; } flags; Здесь определяется переменная с именем flags, которая содержит три 1-битовых поля. Следующее за двоеточием число задает ширину поля в битах. Поля описаны как unsigned, чтобы подчеркнуть, что они действительно будут величинами без знака. На отдельные поля можно ссылаться, как flags.is_static, flags. is_extern, flags.is_keyword И т.д., то есть точно так же, как на другие члены структуры. Поля ведут себя подобно небольшим целым без знака и могут участвовать в арифметических выражениях точно так же, как и другие целые. Таким образом, предыдущие примеры более естественно переписать так: flags.is_extern = flags.is_static = 1; длявключениябитов; flags.is_extern = flags.is_static = 0; длявыключениябитов; if (flags.is_extern == 0 &&flags.is_static == 0)... для их проверки. Поле не может перекрывать границу int; если указанная ширина такова, что это должно случиться, то поле выравнивается по границе следующего int. Полям можно не присваивать имена; неименованные поля (только двоеточие и ширина) используются для заполнения свободного места. Чтобы вынудить выравнивание на границу следующего int, можно использовать специальную ширину 0. При работе с полями имеется ряд моментов, на которые следует обратить внимание. По-видимому наиболее существенным является то, что отражая природу различных аппаратных средств, распределение полей на некоторых машинах осуществляется слева направо, а на некоторых справа налево. Это означает, что хотя поля очень полезны для работы с внутренне определенымиструктурамиданных, при разделении внешне определяемых данных следует тщательно рассматривать вопрос о том, какой конец поступает первым. Другие ограничения, которые следует иметь в виду: поля не имеют знака; они могут храниться только в переменныхтипаint (или, что эквивалентно, типаunsigned); они не являются массивами; они не имеют адресов, так что к ним не применима операция &. 9.2.5 Объединения Oбъединения - это переменная, которая в различные моменты времени может содержать объекты разных типов и размеров, причем компилятор берет на себя отслеживание размера и требований выравнивания. Объединения представляют возможность работать с различными видами данных в одной области памяти, не вводя в программу никакой машинно-зависимой информации. В качестве примера, снова из символьной таблицы компилятора, предположим, что константы могут быть типаint, float или быть указателями на символы. значение каждой конкретной константы должно храниться в переменной соответствующего типа, но все же для управления таблицей самым удобным было бы, если это значение занимало бы один и тот же объем памяти и хранилось в том же самом месте независимо от его типа. это и является назначением объединения - выделить отдельную переменную, в которой можно законно хранить любую одну из переменных нескольких типов. Как и в случае полей, синтаксис основывается на структурах. unionu_tag { int ival; float fval; char *pval; } uval; переменнаяuval будет иметь достаточно большой размер, чтобы хранить наибольший из трех типов, независимо от машины, на которой осуществляется компиляция, - программа не будет зависить от характеристик аппаратных средств. Любой из этих трех типов может быть присвоен uvar и затем использован в выражениях, пока такое использование совместимо: извлекаемый тип должен совпадать с последним помещенным типом. Дело программиста - следить за тем, какой тип хранится в объединении в данный момент; если что-либо хранится как один тип, а извлекается как другой, то результаты будут зависеть от используемой машины. Синтаксически доступ к членам объединения осуществляется следующим образом: имя объединения.член -------------------или указатель объединения ->член ---------------------------то есть точно так же, как и в случае структур. если для отслеживания типа, хранимого в данный момент в uval, используется переменнаяutype, то можно встретить такой участок программы: if (utype == int) printf("%d\n", uval.ival); else if (utype == float) printf("%f\n", uval.fval); else if (utype == string) printf("%s\n", uval.pval); else printf("bad type %d in utype\n", utype); Объединения могут появляться внутри структур и массивов и наоборот. Запись для обращения к члену объединения в структуре (или наоборот) совершенно идентична той, которая используется во вложенных структурах. Например, в массивеструктур, определеным следующим образом struct { char *name; int flags; int utype; union { int ival; float fval; char *pval; } uval; } symtab[nsym]; на переменнуюival можно сослаться как symtab[i].uval.ival а на первый символ строки pval как *symtab[i].uval.pval В сущности объединение является структурой, в которой все члены имеют нулевое смещение. Сама структура достаточно велика, чтобы хранить "самый широкий" член, и выравнивание пригодно для всех типов, входящих в объединение. Как и в случае структур, единственными операциями, которые в настоящее время можно проводить с объединениями, являются доступ к члену и извлечение адреса; объединения не могут быть присвоены, переданы функциям или возвращены ими. указатели объединений можно использовать в точно такой же манере, как и указателиструктур. 9.2.6 Определение типа В языке "C" предусмотрена возможность, называемая typedef для введения новых имен для типовданных. Например, описание typedef int length; делает имя length синонимом для int. "Тип" length может быть использован в описаниях, переводов типов и т.д. Точно таким же образом, как и типint: length len, maxlen; length *lengths[]; Аналогично описанию typedef char *string; делает string синонимом для char*, то есть для указателя на символы, что затем можно использовать в описаниях вида string p, lineptr[lines], alloc(); Обратите внимание, что объявляемый в конструкцииtypedefтип появляется в позиции имени переменной, а не сразу за словом typedef. Синтаксически конструкцияtypedef подобна описаниям класса памяти extern, static и т. д. Мы также использовали прописные буквы, чтобы яснее выделить имена. В качестве более сложного примера мы используем конструкциюtypedef для описания узлов дерева, рассмотренных ранее в этой лекции: typedef struct tnode { /* the basic node */ char *word; /* points to the text */ int count; /* number of occurrences */ struct tnode *left; /* left child */ struct tnode *right; /* right child */ } treenode, *treeptr; В результате получаем два новых ключевых слова: treenode (структура) и treeptr (указатель на структуру). Тогда функциюtalloc можно записать в виде treeptr talloc() { char *alloc(); return((treeptr) alloc(sizeof(treenode))); } Необходимо подчеркнуть, что описаниеtypedef не приводит к созданию нового в каком-либо смысле типа; оно только добавляет новое имя для некоторого существующего типа. При этом не возникает и никакой новой семантики: описанные таким способом переменные обладают точно теми же свойствами, что и переменные, описанные явным образом. По существу конструкцияtypedef сходна с #define за исключением того, что она интерпретируется компилятором и потому может осуществлять подстановки текста, которые выходят за пределы возможностей макропроцессора языка "C". Например, typedef int (*pfi) (); создает типpfi для "указателяфункции, возвращающей значение типаint", который затем можно было бы использовать в программе сортировки в контексте вида pfi strcmp, numcmp, swap; Имеются две основные причины применения описанийtypedef. Первая причина связана с параметризацией программы, чтобы облегчить решение проблемы переносимости. Если для типовданных, которые могут быть машинно-зависимыми, использовать описаниеtypedef, то при переносе программы на другую машину придется изменить только эти описания. Одна из типичных ситуаций состоит в использовании определяемых с помощью typedef имен для различных целых величин и в последующем подходящем выборе типовshort, int и long для каждой имеющейся машины. Второе назначение typedef состоит в обеспечении лучшей документации для программы - тип с именем treeptr может оказаться более удобным для восприятия, чем тип, который описан только как указатель сложной структуры. И наконец, всегда существует вероятность, что в будущем компилятор или некоторая другая программа, такая как lint, сможет использовать содержащуюся в описанияхtypedef информацию для проведения некоторой дополнительной проверки программы. 10 Организация операций ввода-вывода 10.1. Ввод-вывод на консоль. 10.2. Потоки. Неформатированный ввод-вывод. Чтение и запись символов. Ввод- вывод строк. 10.3. Форматированный ввод-вывод. Модификация форматов. 10.1 Ввод и вывод В этой лекции будет описана "стандартная библиотека ввода/вывода", то есть набор функций, разработанных для обеспечения стандартной системы ввода/вывода для "с"- программ. Эти функции предназначены для удобства программного интерфейса, и все же отражают только те операции, которые могут быть обеспечены на большинстве современных операционных систем. процедуры достаточно эффективны для того, чтобы пользователи редко чувствовали необходимость обойти их "ради эффективности", как бы ни была важна конкретная задача. И, наконец, эти процедуры задуманы быть "переносимыми" в том смысле, что они должны существовать в совместимом виде на любой системе, где имеется язык "с", и что программы, которые ограничивают свои взаимодействия с системой возможностями, предоставляемыми стандартной библиотекой, можно будет переносить с одной системы на другую по существу без изменений. 10.1.1 Обращение к стандартной библиотеке Каждый исходный файл, который обращается к функции из стандартной библиотеки, должен вначале содержать строку #include в файле stdio.h определяются некоторые макросы и переменные, используемые библиотекой ввода/вывода. Использование угловых скобок вместо обычных двойных кавычек - указание компилятору искать этот файл в справочнике, содержащем заголовки стандартной информации. 10.2 Консоль. Ввод-вывод. 10.2.1 Стандартный ввод и вывод - функции GETCHAR и PUTCHAR Самый простой механизм ввода заключается в чтении по одному символу за раз из "стандартного ввода", обычно с терминала пользователя, с помощью функцииgetchar. функцияgetchar() при каждом к ней обращении возвращает следующий вводимый символ. В большинстве сред, которые поддерживают язык "с", терминал может быть заменен некоторым файлом с помощью обозначения <: если некоторая программаprog использует функциюgetchar то командная строка prog если prog использует putchar, то командная строка prog>outfile приведет к записи стандартного вывода в файл outfile, а не на терминал. На системе UNIX можно также использовать поточный механизм. Строка prog | anotherprog помещает стандартный выводprog в стандартный вводanotherprog. И опять prog не будет осведомлена об изменении направления. Вывод, осуществляемый функциейprintf, также поступает в стандартный вывод, и обращения к putchar и printf могут перемежаться. Рассмотримпрограммуlower, которая преобразует прописные буквы из своего ввода в строчные: #include main() /* convert input to lower case */ { int c; while ((c = getchar()) != EOF) putchar(isupper(c) ? tolower(c) : c); } "Функции" isupper и tolower на самом деле являются макросами, определеными в stdio.h. Макрос isupper проверяет, является ли его аргумент буквой из верхнего регистра, и возвращает ненулевое значение, если это так, и нуль в противном случае. Макрос tolower преобразует букву из верхнего регистра в ту же букву нижнего регистра. Кроме того, в стандартной библиотекеввода/вывода "функции" getchar и putchar на самом деле могут быть макросами. Это позволяет избежать накладных расходов на обращение к функции для обработки каждого символа. 10.3 Форматированный ввод-вывод. Модификация форматов. 10.3.1 Форматный вывод - функция printf Две функции: printf для вывода и scanf для ввода позволяют преобразовывать численные величины в символьное представление и обратно. Они также позволяют генерировать и интерпретировать форматные строки. Функция printf(control, arg1, arg2, ...) преобразует, определяет формат и печатает свои аргументы в стандартный вывод под управлением строки control. Управляющая строка содержит два типа объектов: обычные символы, которые просто копируются в выходной поток, и спецификации преобразований , каждая из которых вызывает преобразование и печать очередного аргументаprintf. Каждая Спецификация преобразования начинается с символа % и заканчивается символом преобразования. Между % и символом преобразования могут находиться: знак минус, который указывает о выравнивании преобразованного аргумента по левому краю его поля. Строка цифр, задающая минимальную ширину поля. Преобразованное число будет выведено в поле по крайней мере этой ширины, а если необходимо, то и в более широком. Если преобразованный аргумент имеет меньше символов, чем указанная ширина поля, то он будет дополнен слева (или справа, если было указано выравнивание по левому краю)заполняющими символами до этой ширины. Заполняющим символом обычно является пробел, а если ширина поля указывается с лидирующим нулем, то этим символом будет нуль (лидирующий нуль в данном случае не означает восьмеричной ширины поля). Точка, которая отделяет ширину поля от следующей строки цифр. Строка цифр (точность), которая указывает максимальное число символов строки, которые должны быть выведены, или число выводимых справа от десятичной точки цифр для переменныхтипаfloat или double. Модификатор длины l, который указывает, что соответствующий элемент данных имеет тип long, а не int. Ниже приводятся символы преобразования и их смысл: d - аргументпреобразуется к десятичному виду. o- аргументпреобразуется в беззнаковую восьмеричную форму (без лидирующего нуля). x - аргументпреобразуется в беззнаковую шестнадцатеричную форму (без лидирующих 0x). u - аргументпреобразуется в беззнаковую десятичную форму. c - аргументрассматривается как отдельный символ. s - аргументявляется строкой: символы строки печатаются до тех пор, пока не будет достигнут нулевой символ или не будет напечатано количество символов, указанное в спецификации точности. e - аргумент, рассматриваемый как переменнаятипа float или double, преобразуется в десятичную форму в виде [-]m.nnnnnne[+-]xx, где длина строки из цифр n определяется указанной точностью. Точность по умолчанию равна 6. f - аргумент, рассматриваемый как переменнаятипаfloat или double, преобразуется в десятичную форму в виде [-]mmm.nnnnn, где длина строки из n определяется указанной точностью. Точность по умолчанию равна 6. Отметим, что эта точность не определяет количество выводимых в формате f значащих цифр. g - Используется или формат %e или %f, какой короче; незначащие нули не печатаются. Если идущий за % символ не является символом преобразования, то печатается сам этот символ; следовательно, символ % можно напечатать, указав %%. Большинство из форматных преобразований очевидно. Единственным исключением является то, как точность взаимодействует со строками. Следующая таблица демонстрирует влияние задания различных спецификаций на печать "hello, world"" (12 символов). Мы поместили поместили двоеточия вокруг каждого поля для того, чтобы вы могли видеть его протяженность. %10s hello, world %10-s hello, world %20s hello, world %-20s hello, world %20.10s hello, wor %-20.10s hello, wor %.10s hello, wor printf использует свой первый аргумент для определения числа последующих аргументов и их типов. Если количество аргументов окажется недостаточным или они будут иметь несоответственные типы, то возникнет путаница и вы получите бессмысленные результаты. р 10.3.2 Упражнение Напишите программу, которая будет печатать разумным образом произвольный ввод. Как минимум она должна печатать неграфические символы в восьмеричном или шестнадцатеричном виде (в соответствии с принятыми у вас обычаями) и складывать длинные д строки. 10.3.3 Форматный ввод - функция scanf Осуществляющая вводфункцияscanf является аналогом printf и позволяет проводить в обратном направлении многие из тех же самых преобразований. функция scanf(control, arg1, arg2, ...) читает символы из стандартного ввода, интерпретирует их в соответствии с форматом, указанном в аргументеcontrol,, и помещает результаты в остальные аргументы. Управляющий аргумент описывается ниже; другие аргументы, каждый из которых должен быть указателем, определяют, куда следует поместить соответствующим образом преобразованный ввод. Управляющая строка обычно содержит спецификации преобразования, которые используются для непосредственной интерпретации входных последовательностей. Управляющая строка может содержать: пробелы, табуляции или символы новой строки ("символы пустых промежутков"), которые игнорируются. Обычные символы (не %), которые предполагаются совпадающими со следующими отличными от символов пустых промежутков символами волами входного потока. Спецификации преобразования, состоящие из символа %, необязательного символа подавления присваивания *, необязательного числа, задающего максимальную ширину поля и символа преобразования. Спецификация преобразования управляет преобразованием прео следующего поля ввода. Нормально результат помещается в переменную, которая указывается соответствующим аргументом. Если, однако , с помощью символа * указано подавление присваивания, то это поле ввода просто пропускается и никакого присваивания не производится. Поле ввода определяется как строка символов, которые отличны от символов простых промежутков; оно продолжается либо до следующего символа пустого промежутка, либо пока не будет исчерпана ширина поля, если она указана. Отсюда следует, что при поиске нужного ей ввода, функцияscanf будет пересекать границы строк, поскольку символ новой строки входит в число пустых промежутков. Символ преобразования определяет интерпретацию поля ввода; согласно требованиям основанной на вызове по значению семантики мантики языка "с" соответствующий аргумент должен быть указателем. Допускаются следующие символы преобразования: d - на вводе ожидается десятичное целое; соответствующий аргумент должен быть указателем на целое. o- На вводе ожидается восьмеричное целое (с лидирующим нулем или без него); соответствующий аргумент должен быть указателем на целое. x - На вводе ожидается шестнадцатеричное целое (с лидирующими 0x или без них); соответствующий аргумент должен быть указателем на целое. це h - На вводе ожидается целое типа short; соответствующий аргумент должен быть указателем на целое типа short. c - Ожидается отдельный символ; соответствующий аргумент должен быть указателем на символы; следующий вводимый символ помещается в указанное указанное место. Обычный пропуск символов пустых промежутков в этом случае подавляется; для чтения следующего символа, который не является символом пустого промежутка, пользуйтесь спецификацией преобразования %1s. s - Ожидается символьная строка; соответствующий аргумент должен быть указателем символов, который указывает на массив символов, который достаточно велик для принятия строки и добавляемого в конце символа \0. f - Ожидается число с плавающей точкой; соответствующий аргумент должен быть указателем на переменнуютипа float. Е - символ преобразования e является синонимом для f. Формат вводапеременнойтипа float включает необязательный знак, строку цифр, возможно содержащую десятичную точку и необязательное поле экспоненты, состоящее из буквы e, за которой следует целое, возможно имеющее знак. Перед символами преобразования d, o и x может стоять l, которая означает , что в списке аргументов должен находиться указатель на переменнуютипаlong, а не типаint. Аналогично, буква l может стоять перед символами преобразования e или f, говоря о том, что в списке аргументов должен находиться указатель на переменнуютипаdouble, а не типаfloat. Например, обращение int i; float x; char name[50]; scanf("%d %f %s", &i, &x, name); со строкой на вводе 25 54.32e-1 thompson приводит к присваиванию i значения 25, x - значения 5.432 и name - строки "thompson", надлежащим образом законченной символом \0. эти три поля ввода можно разделить столькими пробелами, табуляциями и символами новых строк, сколько вы пожелаете. Обращение int i; float x; char name[50]; scanf("%2d %f %*d %2s", &i, &x, name); с вводом 56789 0123 45a72 присвоит i значение 56, x - 789.0, пропустит 0123 и поместит в name строку "45". При следующем обращении к любой процедуреввода рассмотрение начнется с буквы a. В этих двух примерах name является указателем и, следовательно, перед ним не нужно помещать знак &. В качестве другого примера спроектируем элементарный калькулятор, используя для преобразования вводафункциюscanf: #include main() /* rudimentary desk calculator */ { double sum, v; sum =0; while (scanf("%lf", &v) !=EOF) printf("\t%.2f\n", sum += v); } выполнение функцииscanf заканчивается либо тогда, когда она исчерпывает свою управляющую строку, либо когда некоторый элемент ввода не совпадает с управляющей спецификацией. В качестве своего значения она возвращает число правильно совпадающих и присвоенных элементов ввода. Это число может быть использовано для определения количества найденных элементов ввода. При выходе на конец файла возвращается EOF; подчеркнем, что это значение отлично от 0, что следующий вводимый символ не удовлетворяет первой спецификации в управляющей строке. При следующем обращении к scanf поиск возобновляется непосредственно за последним введенным символом. Заключительное предостережение: аргументы функцииscanf должны быть указателями. Несомненно наиболее распространенная ошибка состоит в написании scanf("%d", n); вместо scanf("%d", &n); 10.3.4 Форматное преобразование в памяти От функцииscanf и printf происходят функцииsscanf и sprintf, которые осуществляют аналогичные преобразования, но оперируют со строкой, а не с файлом. Обращения к этим функциям имеют вид: sprintf(string, control, arg1, arg2, ...) sscanf(string, control, arg1, arg2, ...) Функцияsprintf преобразует свои аргументыarg1, arg2 и т.д. В соответствии с форматом, указанным в control, но помещает результаты в string, а не в стандартный вывод. Kонечно, строка string должна быть достаточно велика, чтобы принять результат. Например, если name - это символьный массив, а n целое, то sprintf(name, "temp%d", n); создает в name строку вида tempnnn, где nnn - значение n. функцияsscanf выполняет обратные преобразования - она просматривает строку string в соответствии с форматом в аргументеcontrol и помещает результирующие значения в аргументыarg1, arg2 и т.д. Эти аргументы должны быть указателями. В результате обращения sscanf(name, "temp%d", &n); переменнаяn получает значение строки цифр, следующих за temp в name. Упражнение. Спроектируйте настольный калькулятор используя для ввода и преобразования чисел scanf и/или sscanf. 10.4 Неформатированный ввод-вывод. Ввод- вывод строк. 10.4.1 Ввод и вывод строк Стандартная библиотека содержит функциюfgets, совершенно аналогичную функцииgetline. В результате обращения fgets(line, maxline, fp) следующая строка ввода (включая символ новой строки) считывается из файла fp в символьный массивline; самое большое maxline-1 символ будет прочитан. Результирующая строка заканчивается символом \0. Нормально функцияfgets возвращает line; в конце файла она возвращает null. Предназначенная для выводафункцияfputs записывает строку (которая не обязана содержать символ новой строки) в файл: fputs(line, fp) Исходные коды функций fgets и fputs приводены ниже, скопированными непосредственно из стандартной библиотеки ввода-вывода: #include char *fgets(char *s,int n,register FILE *iop) /*get at most n chars from iop*/ { register int c; register char *cs; cs = s; while(--n>0&&(c=getc(iop)) !=EOF) if ((*cs++ = c)=='\n') break; *cs = '\0'; return((c==EOF && cs==s) ?NULL : s); } voidfputs(register char *s,register file *iop) /*put string s on fils iop* { register int c; while (c = *s++) putc(c,iop); } Упражнения 1. Напишите программу сравнения двух файлов, которая будет выводить первую строку и позицию символа, где они различаются. 2. Напишите программу вывода набора файлов, которая начинает каждый новый файл с новой страницы и выводит для каждого файла заголовок и счетчик текущих страниц. 11 Файловая система 11.1. Файловый ввод-вывод. Обработка файлов. 11.2. Функции для работы с файлами. 11.3. Форматированный файловый ввод-вывод. 11.1 Файловый ввод-вывод. Обработка файлов. 11.1.1 Доступ к файлам Правила работы с файлами. Прежде чем можно считывать из некоторого файла или записывать в него, этот файл должен быть открыт с помощью функцииfopen из стандартной библиотеки. функцияfopen берет внешнее имя, проводит некоторые обслуживающие действия и возвращает внутреннее имя, которое должно использоваться при последующих чтениях из файла или записях в него. Это внутреннее имя, называемое "указателем файла", фактически является указателемструктуры, которая содержит информацию о файле, такую как место размещения буфера, текущая позиция символа в буфере, происходит ли чтение из файла или запись в него и тому подобное. Пользователи не обязаны знать эти детали, потому что среди определений для стандартного ввода-вывода, получаемых из файла stdio.h, содержится определениеструктуры с именем FILE. . Единственное необходимое для указателя файла описание демонстрируется примером: FILE *fp; Здесь говорится, что fp является указателем на FILE и fopen возвращает указатель на FILE. Oбратите внимание, что FILE является именем типа, подобным int, а не ярлыку структуры; это реализовано как typedef. Фактическое обращение к функцииfopen в программе имеет вид: fp=fopen(name,mode); Первым аргументом функцииfopen является "имя" файла, которое задается в виде символьной строки. Второй аргументmode("режим") также является символьной строкой, которая указывает, как этот файл будет использоваться. Допустимыми режимами являются: чтение ("r"), запись ("w") и добавление ("a"). Если вы откроете файл, который еще не существует, для записи или добавления, то такой файл будет создан (если это возможно). Открытие существующего файла на запись приводит к отбрасыванию его старого содержимого. Попытка чтения несуществующего файла является ошибкой. Ошибки могут быть обусловлены и другими причинами (например, попыткой чтения из файла, не имея на то разрешения). При наличии какой-либо ошибки функция возвращает нулевое значение указателяnull (которое для удобства также определяется в файле stdio.h). Другой необходимой вещью является способ чтения или записи, если файл уже открыт. Здесь имеется несколько возможностей, из которых getc и putc являются простейшими. функцияgetc возвращает следующий символ из файла; ей необходим указатель файла, чтобы знать, из какого файла читать. Таким образом, c=getc(fp) помещает в "C" следующий символ из файла, указанного посредством fp, и EOF, если достигнут конец файла. функцияputc, являющаяся обращением к функцииgetc, putc(c,fp) помещает символ "c" в файл fp и возвращает "c". Подобно функциямgetchar и putchar, getc и putc могут быть макросами, а не функциями. При запуске программы автоматически открываются три файла, которые снабжены определенымиуказателями файлов. Этими файлами являются стандартный ввод, стандартный вывод и стандартный вывод ошибок; соответствующие указатели файлов называются stdin, stdout и stderr. Обычно все эти указатели связаны с терминалом, но stdin и stdout могут быть перенаправлены на файлы или в поток (pipe). Функцииgetchar и putchar могут быть определены в терминалахgetc, putc, stdin и stdout следующим образом: #define getchar() getc(stdin) #define putchar(c) putc(c, stdout). При работе с файлами для форматного ввода и вывода можно использовать функцииfscanf и fprintf. Они идентичны функциямscanf и printf, за исключением того, что первым аргументом является указатель файла, определяющий тот файл, который будет читаться или куда будет вестись запись; управляющая строка будет вторым аргументом. Пример программы cop для копирования файлов. #include main(int argc, char *argv[]) /*cop: copy files*/ { FILE *fp; if ((fp=fopen("10.in","r"))==NULL){ printf("cop:can't open %\n","1.out"); return 1; } else { FILE *f2=fopen("10.out","w"); filecopy(fp,f2); fclose(fp); fclose(f2); return 0; } } указатели файлов stdin и stdout заранее определены в библиотеке ввода-вывода как стандартный ввод и стандартный вывод; они могут быть использованы в любом месте, где можно использовать объект типаFILE *. Они однако являются константами, а не переменными, так что не пытайтесь им что-либо присваивать. функцияfclose является обратной по отношению к fopen; она разрывает связь между указателем файла и внешним именем, установленную функциейfopen, и высвобождает указатель файла для другого файла. Большинство операционных систем имеют некоторые ограничения на число одновременно открытых файлов, которыми может распоряжаться программа. Имеется и другая причина для применения функцииfclose к выходному файлу - она вызывает выдачу информации из буфера, в котором putc собирает вывод. (При нормальном завершении работы программыфункцияfclose вызывается автоматически для каждого открытого файла). 11.1.2 Обработка ошибок - STDERR и EXIT Обработка ошибок в в разработанной функции cop недостаточно хороша. Это заключается в том, что если один из файлов по некоторой причине оказывается недоступным, диагностическое сообщение об этом выводится в конце объединенного вывода. Это приемлемо, если вывод поступает на терминал, но не годится, если вывод поступает в некоторый файл или через поточный (pipeline) механизм в другую программу. Чтобы лучше обрабатывать такую ситуацию, к программе точно таким же образом, как stdin и stdout, присоединяется второй выходной файл, называемый stderr. Если это вообще возможно, вывод, записанный в файле stderr, появляется на терминале пользователя, даже если стандартный вывод направляется в другое место. Давайте переделаем программуcop таким образом, чтобы сообщения об ошибках писались в стандартный файл ошибок. #include #include main(int argc, char *argv[]) /*cop: copy files*/ { FILE *fp; if ((fp=fopen("10.in","r"))==NULL){ fprintf(stderr,"cop: can't open,%s\n", "10.in"); exit(1); } else { FILE *f2=fopen("10.out","w"); filecopy(fp,f2); fclose(fp); fclose(f2); return 0; } } Программа сообщает об ошибках двумя способами. диагностическое сообщение, выдаваемое функциейprintf, поступает в stderr и, таким образом, оказывается на терминале пользователя, а не исчезает в потоке (pipeline) или в выходном файле. Программа также использует функциюexit из стандартной библиотеки, обращение к которой вызывает завершение выполнения программы. Аргумент функции exit доступен любой программе, обращающейся к данной функции, так что успешное или неудачное завершение данной программы может быть проверено другой программой, использующей эту в качестве подзадачи. По соглашению величина 0 в качестве возвращаемого значения свидетельствует о том, что все в порядке, а различные ненулевые значения являются признаками нормальных ситуаций. функцияexit вызывает функциюfclose для каждого открытого выходного файла, с тем чтобы вывести всю помещенную в буферы выходную информацию, а затем вызывает функцию_exit. функция_exit приводит к немедленному завершению без очистки каких-либо буферов; конечно, при желании к этой функции можно обратиться непосредственно. 11.2 Функции для работы с файлами. 11.3 Форматированный файловый ввод-вывод.