От С к С++

И. Ю. Каширин, В. С. Новичков





                От С к С++





2-е издание, стереотипное




Допущено УМО по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности «Программное обеспечение вычислительной техники и автоматизированных систем»










Москва
Горячая линия - Телеком 2012

     Каширин И. Ю., Новичков В. С.
К31    От С к C++: Учебное пособие для вузов. - 2-е изд., сте     реотип. - М.: Горячая линия - Телеком, 2012. - 334 с.: ил.
     ISBN 978-5-9912-0259-6.
        Учебное пособие содержит необходимые теоретические сведения и набор упражнений и задач различной степени сложности, позволяющих приобрести навыки практического программирования на алгоритмических языках С и С++ (Си и Си++) и проконтролировать усвоение материала. Практические задания для программирования на С++ имеют «сквозную» структуру - распределены по мере изложения разделов. Материал книги успешно апробирован авторами в высших технических учебных заведениях.
        Для студентов высших и средних учебных заведений, может быть использована начинающими программистами при изучении алгоритмических языков С и С++.
ББК 32.973
Адрес издательства в Интернет WWW.TECHBOOK.ru

Учебное издание

Каширин Игорь Юрьевич, Новичков Валентин Семенович
От С к C++: Учебное пособие
2-е издание, стереотипное
Редактор П. В. Румянцев Художник В. Г. Ситников Подготовка оригинал-макета И. М. Чумаковой
.
Подписано к печати 25.03.2012. Формат 60x88 1/16. Усл. печ. л. 21.
Тираж 200 экз. (1-й завод 100 экз.)
ISBN 978-5-9912-0259-6                       © И. Ю. Каширин,
     В. С. Новичков, 2005, 2012 © Оформление издательства «Горячая линия - Телеком», 2012

    ПРЕДИСЛОВИЕ

   Среди современных алгоритмических языков языки С и С++ занимают, пожалуй, первое место по распространенности и разнообразию версий. Они относятся к семейству универсальных языков программирования, т. е. ориентированных на весьма широкий круг задач, которые могут решаться при помощи ЭВМ. Кроме того, авторы этой книги признают лидерство языков С и С++ среди известных универсальных языков как наиболее концептуально целостных. Дело в том, что разработка любого из инструментальных программных средств, к которым относятся и языки программирования, основана на строгом теоретическом базисе.
   Теория разработки алгоритмических языков учитывает отлаживае-мость программ (как быстрый поиск ошибок), гибкость языка при внесении текущих изменений в программу, возможности дальнейшего развития самого языка и его средств программистом и т. д. В этом отношении язык С довольно полно отвечает основным требованиям теории, являясь последовательным преемником оригинальных решений, воплощенных ранее в цепочке поколений языков Ассемблера, Фортрана, Алгола. Взяв из них самое лучшее, язык С приобрел множество новых свойств, сделавших его одним из первых универсальных функциональных языков.
   Язык программирования С разработан сотрудниками фирмы Bell Labs Деннисом Ритчи и Кеном Томпсоном в 1972 г. во время их совместной работы над операционной системой UNIX на ЭВМ PDP-11. Однако его популярность быстро переросла рамки конкретной ЭВМ, конкретной операционной системы и конкретных задач системного программирования. В настоящее время ни одна инструментальная операционная система не может считаться полной, если в ее состав не входит компилятор языка С.
   В некотором смысле язык С является самым универсальным языком, так как кроме набора средств, присущих современным языкам программирования высокого уровня (структурность, модульность, определяемые типы данных), в него включены средства для программирования на уровне Ассемблера (указатели, побитовые операции, операции сдвига). Большой набор операторов и операций позволяет писать компактные и эффективные программы.
   Однако такие мощные средства требуют от программиста осторожности, аккуратности и хорошего знания языка со всеми его преимуществами и недостатками.
   В настоящей книге рассматриваются реализации С и С++, разработанные фирмой Borland.

3

И. Ю. Каширин, В. С.Новичков. От С к C++

    Язык С - структурированный, модульный, компилируемый, универсальный язык, традиционно используемый для системного программирования. Он является переносимым языком, так как прикладные программы, написанные на нем, могут быть легко перенесены с одного компьютера на другой, даже если они имеют различные операционные системы. Язык С может использоваться практически для любых задач.
    Строгое следование авторов языка С функциональной концепции позволило изящно достроить язык и перевести его в объектно-ориентированную версию - С++, практически не меняя ни старой синтаксической, ни семантической основы.
    Быстрое развитие языка программирования С++ с появлением новых версий, использующих идеи CASE-технологии, свидетельствует о том, что идеология С не только современна, но и будет иметь большое будущее.
    Настоящая книга состоит из двух основных частей, описывающих соответственно программирование на языках C и C++. Для чтения книги практически не нужно иметь навыков программирования на каких-либо более простых алгоритмических языках.
    В то же время читателю, уже знакомому с языком С, может быть рекомендовано начинать чтение с более поздних глав, посвященных программированию на языке С++.
    Практические упражнения, приведенные в конце каждой главы, имеют различную степень сложности и значительно облегчат понимание материала при их выполнении.
    Книга может быть использована как для самостоятельного изучения, так и для чтения курса лекций с лабораторным практикумом в высших учебных заведениях.

4

    ГЛАВА 1. ПРОГРАММИРОВАНИЕ ЛИНЕЙНЫХ АЛГОРИТМОВ

    1.1. Этапы решения задач на ЭВМ

    Решение любой задачи с использованием ЭВМ состоит из нескольких взаимосвязанных этапов, среди которых можно выделить следующие:
   1)  техническое задание (постановка задачи);
   2)  формализация (математическая постановка задачи);
   3)  выбор (или разработка) метода решения;
   4)  разработка алгоритма (алгоритмизация);
   5)  выбор языка программирования;
   6)  определение структуры данных;
   7)  оптимизация алгоритма;
   8)  подготовка отладки;
   9)  тесты и методы «ручной» проверки (без использования ЭВМ);
    10) запись программы на конкретном языке программирования;
    11) тестирование и отладка;
    12) выполнение программы и обработка результатов;
    13) документирование.
    Последовательное выполнение перечисленных этапов составляет полный цикл разработки, отладки и выполнения программы. Приведенное разделение является условным. С развитием современных технологий программирования порядок и содержание этапов может меняться.
    Рассмотрим более подробно некоторые наиболее общие и необходимые этапы.
    Постановка задачи. При постановке задачи первостепенное внимание должно быть уделено выяснению конечной цели и выработке общего подхода к исследуемой проблеме: выяснению, существует ли решение поставленной задачи и единственно ли оно; изучению общих свойств рассматриваемого физического явления или объекта; анализу возможностей конкретной ЭВМ и данной системы программирования. На этом этапе требуется глубокое понимание существа поставленной задачи. Правильно сформулировать задачу иногда не менее сложно, чем ее решить.
    Формализация. Формализация, как правило, сводится к построению математической модели рассматриваемого явления, когда в результате анализа существа задачи определяются объем и специфика исходных данных, вводится система условных обозначений, устанавливается

5

И. Ю. Каширин, В. С.Новичков. От С к C++

принадлежность решаемой задачи к одному из известных классов задач и выбирается соответствующий математический аппарат. При этом нужно уметь сформулировать на языке математики конкретные задачи физики, механики, экономики, технологии и т. д. Для успешного преодоления этого этапа требуются не только солидные сведения из соответствующей предметной области, но и хорошее знание вычислительной математики, т. е. тех методов, которые могут быть использованы при решении задачи на машине.
    Выбор метода решения. После того как определена математическая формулировка задачи, надо выбрать метод ее решения. Вообще говоря, применение любого метода приводит к построению ряда формул и к формулировке правил, определяющих связи между этими формулами. Все это разбивается на отдельные действия так, чтобы вычислительный процесс мог быть выполнен машиной. При выборе метода надо учитывать, во-первых, сложность формул и соотношений, связанных с тем или иным численным методом, во-вторых, необходимую точность вычислений и характеристики самого метода. На выбор метода решения большое влияние оказывают вкусы и знания самого пользователя.
    Этот этап - важнейший в процессе решения задачи. С ним связаны многочисленные неудачи, являющиеся результатом легкомысленного подхода к ошибкам вычислений. При решении задачи на ЭВМ необходимо помнить, что любой получаемый результат является приближенным! Если известен алгоритм точного решения, то, кроме случайных ошибок (сбоев в работе ЭВМ), возможны ошибки, связанные с ограниченной точностью представления чисел в ЭВМ. При вычислениях, заключающихся в нахождении результата с заданной степенью точности, возникает дополнительная погрешность, которую, если возможно, оценивают на данном этапе (до выхода непосредственно на ЭВМ). Эта погрешность определяется выбранным численным методом решения задачи.
    Разработка алгоритма. Данный этап является первым этапом программирования и заключается в разложении вычислительного процесса на возможные составные части, установлении порядка их следования, описании содержания каждой такой части в той или иной форме и последующей проверке, которая должна показать, обеспечивается ли реализация выбранного метода. В большинстве случаев не удается сразу получить удовлетворительный результат, поэтому составление алгоритма проводится методом «проб и ошибок» и для получения окончательного варианта требуется несколько шагов коррекции и анализа.
    Как правило, в процессе разработки алгоритм проходит несколько этапов детализации. Первоначально составляется укрупненная схема алгоритма, в которой отражаются наиболее важные и существенные связи

6

Глава 1. Программирование линейных алгоритмов

между исследуемыми процессами (или частями процесса). На последующих этапах раскрываются (детализируются) выделенные на предыдущих этапах части вычислительного процесса, имеющие некоторое самостоятельное значение. Кроме того, на каждом этапе детализации выполняется многократная проверка и исправление (отработка) схемы алгоритма. Подобный подход позволяет избежать возможных ошибочных решений.
    Ориентируясь на крупноблочную структуру алгоритма, можно быстрее и проще разработать несколько различных его вариантов, провести их анализ, оценку и выбрать наилучший (оптимальный).
    Эффект поэтапной детализации алгоритма во многом зависит от того, как осуществляется его структуризация: расчленение алгоритмического процесса на составные части, что должно определяться не произволом пользователя (программиста), а внутренней логикой самого процесса. Каждый элемент крупноблочной схемы алгоритма должен быть максимально самостоятельным и логически завершенным в такой степени, чтобы дальнейшую его детализацию можно было выполнять независимо от детализации остальных элементов. Это упрощает процесс проектирования алгоритма и позволяет осуществлять его разработку по частям одновременно нескольким людям.
    В процессе разработки алгоритма могут использоваться различные способы его описания, отличающиеся по простоте, наглядности, компактности, степени формализации, ориентации на машинную реализацию и другим показателям. В практике программирования наибольшее распространение получили:
    1) словесная запись алгоритмов;
    2) схемы алгоритмов;
    3) псевдокод (формальные алгоритмические языки);
    4) структурограммы (диаграммы Насси-Шнейдермана).
    Разработка алгоритмов является в значительной степени творческим, эвристическим процессом, как правило, требует большой эрудиции, изобретательности, нестандартных и нетрадиционных подходов к решению задачи.
    Составление программы. Представление алгоритма в форме, допускающей ввод в машину и последующий перевод на машинный язык, относится к этапу составления программы (программированию), т. е. разработанный алгоритм задачи необходимо изложить на языке, который будет понятен ЭВМ.
    Отладка программы. Составление программы представляет собой трудоемкий процесс, требующий от исполнителя напряженного внимания. Практика показывает, что в вычислениях следует избегать поспеш

7

И. Ю. Каширин, В. С.Новичков. От С к C++

ности и придерживаться золотого правила: «лучше меньше, да лучше». Но на предыдущих этапах столько возможностей допустить ошибку, что, как бы мы тщательно ни действовали, первоначально составленная программа обычно содержит ошибки и машина или не может дать ответа, или приводит неправильное решение.
    Отладка начинается с того, что аккуратно записанная программа проверяется непосредственно лицом, осуществившим подготовку и программирование задачи. Выясняется правильность написания программы, выявляются смысловые и синтаксические ошибки и т. п. Затем программа вводится в память ЭВМ и ошибки, оставшиеся незамеченными, выявляются уже непосредственно с помощью машины.
    Опытный пользователь ЭВМ знает, что необходим действенный контроль над процессом вычислений, позволяющий своевременно обнаруживать и предотвращать ошибки. Для этого используются различного рода интуитивные соображения, правдоподобные рассуждения и контрольные формулы. Начинающий пользователь часто считает отладку излишней, а получение контрольных точек - неприятной дополнительной работой. Однако очень скоро он убеждается, что поиск пропущенной ошибки требует значительно большего времени, чем время, затраченное на контроль.
    Гарантией правильности решения может служить, например:
    а)    проверка выполнения условий задачи (например, для алгебраического уравнения найденные корни подставляются в исходное уравнение и проверяются расхождения левой и правой частей);
    б)    качественный анализ задачи;
    в)    пересчет (по возможности другим методом).
    Для некоторых сложных по структуре программ процесс отладки может потребовать значительно больше машинного времени и усилий специалистов, чем собственно решение на ЭВМ, так как плохо спланированные процессы алгоритмизации, программирования и отладки приводят к ошибкам, которые могут быть обнаружены лишь после многократных проверок.
    Вычисления и обработка результатов. Только после того как появится полная уверенность, что программа обеспечивает получение правильных результатов, можно приступать непосредственно к расчетам по программе.
    После завершения расчетов наступает этап использования результатов вычислений в практической деятельности или, как говорят, этап внедрения результатов. Интерпретация результатов вычислений снова относится к той предметной области знаний, откуда возникла задача.

8

Глава 1. Программирование линейных алгоритмов

   Прежде чем приступать к составлению непосредственно программ на языке, рассмотрим вкратце первый этап программирования.

    1.2.  Разработка алгоритма решения задачи

   1.2.1. Понятие алгоритма
   Термин «алгоритм» произошел от имени арабского математика альХорезми (IX в.), который описал общие правила (названные позднее алгоритмами) выполнения основных арифметических действий в десятичной системе счисления. Понятие алгоритма используется сегодня не только в математике, но и во многих областях человеческой деятельности; например, говорят об алгоритме управления производственным процессом, алгоритме управления полетом ракеты, алгоритме пользования бытовым прибором. Причем интуитивно под алгоритмом понимают некоторую систему правил, обладающих определенными свойствами.
   Изучая понятие алгоритма, мы будем предполагать, что его исполнителем является автоматическое устройство, а именно ЭВМ. Это накладывает на запись алгоритма целый ряд обязательных требований. Сформулируем эти требования в виде перечня свойств, которыми должны обладать алгоритмы, предназначенные для исполнения на ЭВМ.
   1.    Первым свойством алгоритма является дискретный, т. е. пошаговый, характер определяемого им процесса. Возникающая в результате такого разбиения запись алгоритма представляет собой упорядоченную последовательность отдельных предписаний (правил, директив, команд), образующих прерывную (или дискретную) структуру алгоритма - только выполнив требования одного предписания, можно приступить к исполнению следующего.
   2.    Исполнитель может выполнить алгоритм, если он ему понятен, т. е. записан на понятном ему языке и содержит предписания, которые исполнитель может выполнить. Набор действий, которые могут быть выполнены исполнителем, называется системой команд исполнителя. Алгоритм не должен содержать описание действий, не входящих в систему команд исполнителя.
   3.    Алгоритм, предназначенный для исполнения некоторым техническим устройством, не должен содержать предписаний, приводящих к неоднозначным действиям. Алгоритм рассчитан на чисто механическое исполнение, и если применять его повторно к одним и тем же исходным данным, то всегда должен получиться один и тот же результат; если при этом каждый раз сравнивать результаты, полученные после соответствующих шагов алгоритмического процесса, то они тоже должны быть

9

И. Ю. Каширин, В. С.Новичков. От С к C++

одинаковыми. Это свойство определенности и однозначности, или детерминированности, алгоритмов позволяет использовать в качестве исполнителя специальные машины-автоматы.
    4.    Основополагающим свойством алгоритма является его массовость или применимость к некоторому классу объектов, возможность получения результата при различных исходных данных в некоторой области допустимых значений. Например, исходными данными в алгоритмах альХорезми могут быть любые пары десятичных чисел. Конечно, его способ не всегда самый рациональный по сравнению с известными приемами быстрого счета. Но смысл массовости алгоритма состоит как раз в том, что он одинаково пригоден для всех случаев, требует лишь механического выполнения цепочки простых действий и при этом исполнителю нет нужды в затратах творческой энергии.
    5.    Цель выполнения алгоритма - получение определенного результата посредством выполнения указанных преобразований над исходными данными. В алгоритмах аль-Хорезми исходными данными являются два десятичных числа, результатом - также некоторое десятичное число. Причем при точном исполнении всех предписаний алгоритмический процесс должен заканчиваться за конечное число шагов. Это обязательное требование к алгоритмам.
    В математике известны вычислительные процедуры алгоритмического характера, не обладающие свойством конечности. Например, процедура вычисления числа п. Однако если мы введем условие завершения вида «закончить после получения n десятичных знаков числа п», то получим алгоритм вычисления n десятичных знаков числа п. На этом принципе построены многие вычислительные алгоритмы.
    6.    Эффективный алгоритм должен быть выполнен не просто за конечное время, а за разумное конечное время. Время выполнения алгоритма - очень важный параметр, однако понятие эффективности алгоритма чаще трактуется шире и включает такие аспекты, как сложность, необходимые ресурсы, информационно-программное обеспечение. Эффективность алгоритма часто определяет возможность его практической реализации.
    Перечисленные свойства алгоритма, по существу, являются неформальным его определением. Объединяя их в одно целое, мы можем сформулировать это определение следующим образом. Алгоритм - это полное и точное описание на некотором языке конечной последовательности действий, которые должен выполнить исполнитель, чтобы за конечное время перейти от (варьируемых) исходных данных к искомому результату.

10